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

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