third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java

   1 package org.opendaylight.yangtools.triemap;
   2
   3 import java.util.Iterator;
   4 import java.util.AbstractMap.SimpleImmutableEntry;
   5 import java.util.Map;
   6 import java.util.Map.Entry;
   7
   8 /**
   9  * Mimic immutable ListMap in Scala
  10  *
  11  * @author Roman Levenstein <romixlev@gmail.com>
  12  *
  13  * @param <V>
  14  */
  15 abstract class ListMap<K,V> {
  16
  17     ListMap<K,V> next;
  18
  19     static <K,V> ListMap<K, V> map(K k, V v, ListMap<K, V> tail){
  20         return new Node<K, V> (k, v, tail);
  21     }
  22
  23     static <K,V> ListMap<K, V> map(K k, V v){
  24         return new Node<K, V> (k, v, null);
  25     }
  26
  27     static <K,V> ListMap<K, V> map(K k1, V v1, K k2, V v2){
  28         return new Node<K, V> (k1, v1, new Node<K,V>(k2,v2, null));
  29     }
  30
  31     public abstract int size ();
  32
  33     public abstract boolean isEmpty() ;
  34
  35     abstract public boolean contains(K k, V v);
  36
  37     abstract public boolean contains(K key);
  38
  39     abstract public Option<V> get (K key);
  40
  41     abstract public ListMap<K, V> add (K key, V value);
  42
  43     abstract public ListMap<K, V> remove (K key);
  44
  45     abstract public Iterator<Map.Entry<K, V>> iterator();
  46
  47
  48     static class EmptyListMap<K,V> extends ListMap<K, V> {
  49         public ListMap<K,V> add (K key, V value) {
  50             return ListMap.map(key, value, null);
  51         }
  52
  53         public boolean contains(K k, V v) {
  54             return false;
  55         }
  56
  57         public boolean contains(K k) {
  58             return false;
  59         }
  60
  61         public ListMap<K,V> remove(K key) {
  62             return this;
  63         }
  64
  65         @Override
  66         public int size () {
  67             return 0;
  68         }
  69
  70         @Override
  71         public boolean isEmpty () {
  72             return true;
  73         }
  74
  75         @Override
  76         public Option<V> get (K key) {
  77             return Option.makeOption (null);
  78         }
  79
  80         @Override
  81         public Iterator<Entry<K, V>> iterator () {
  82             return new EmptyListMapIterator<K, V> ();
  83         }
  84
  85         static class EmptyListMapIterator<K,V> implements Iterator<Entry<K, V>> {
  86
  87             @Override
  88             public boolean hasNext () {
  89                 return false;
  90             }
  91
  92             @Override
  93             public Entry<K, V> next () {
  94                 return null;
  95             }
  96
  97             @Override
  98             public void remove () {
  99                 throw new RuntimeException("Operation not supported");
 100             }
 101
 102         }
 103     }
 104
 105     static class Node<K,V> extends ListMap<K, V> {
 106         final K k;
 107         final V v;
 108
 109         Node(K k, V v, ListMap<K,V> next) {
 110             this.k = k;
 111             this.v = v;
 112             this.next = next;
 113         }
 114
 115         public ListMap<K,V> add (K key, V value) {
 116             return ListMap.map(key, value, remove (key));
 117         }
 118
 119         public boolean contains(K k, V v) {
 120             if(k.equals (this.k) && v.equals (this.v))
 121                 return true;
 122             else if(next != null)
 123                 return next.contains (k, v);
 124             return false;
 125         }
 126
 127         public boolean contains(K k) {
 128             if(k.equals (this.k))
 129                 return true;
 130             else if(next != null)
 131                 return next.contains (k);
 132             return false;
 133         }
 134
 135         public ListMap<K,V> remove(K key) {
 136             if(!contains(key))
 137                 return this;
 138             else
 139                 return remove0(key);
 140         }
 141
 142         private ListMap<K, V> remove0 (K key) {
 143             ListMap<K, V> n = this;
 144             ListMap<K, V> newN = null;
 145             ListMap<K, V> lastN = null;
 146             while (n != null) {
 147                 if(n instanceof EmptyListMap) {
 148                     newN.next = n;
 149                     break;
 150                 }
 151                 Node<K, V> nn = (Node<K, V>)n;
 152                 if (key.equals (nn.k)) {
 153                     n = n.next;
 154                     continue;
 155                 } else {
 156                     if (newN != null) {
 157                         lastN.next = ListMap.map (nn.k, nn.v, null);
 158                         lastN = lastN.next;
 159                     } else {
 160                         newN = ListMap.map (nn.k, nn.v, null);
 161                         lastN = newN;
 162                     }
 163                 }
 164                 n = n.next;
 165             }
 166             return newN;
 167         }
 168
 169         @Override
 170         public int size () {
 171             if(next == null)
 172                 return 1;
 173             else
 174                 return 1+next.size ();
 175         }
 176
 177         @Override
 178         public boolean isEmpty () {
 179             return false;
 180         }
 181
 182         @Override
 183         public Option<V> get (K key) {
 184             if(key.equals (k))
 185                 return Option.makeOption (v);
 186             if(next != null)
 187                 return next.get (key);
 188             return Option.makeOption (null);
 189         }
 190
 191
 192         @Override
 193         public Iterator<Entry<K, V>> iterator () {
 194             return new NodeIterator<K, V> (this);
 195         }
 196
 197         static class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
 198             ListMap<K, V> n;
 199
 200             public NodeIterator (Node<K, V> n) {
 201                 this.n = n;
 202             }
 203
 204             @Override
 205             public boolean hasNext () {
 206 //                return n!= null && n.next != null && !(n.next instanceof EmptyListMap);
 207                 return n!= null && !(n instanceof EmptyListMap);
 208             }
 209
 210             @Override
 211             public Entry<K, V> next () {
 212                 if (n instanceof Node) {
 213                     Node<K, V> nn = (Node<K, V>) n;
 214                     Entry<K, V> res = new SimpleImmutableEntry<K, V> (nn.k, nn.v);
 215                     n = n.next;
 216                     return res;
 217                 } else {
 218                     return null;
 219                 }
 220             }
 221
 222             @Override
 223             public void remove () {
 224                 throw new RuntimeException("Operation not supported");
 225             }
 226
 227         }
 228     }
 229 }