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