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

   1 /*
   2  * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package org.opendaylight.yangtools.triemap;
  17
  18 import java.util.AbstractMap.SimpleImmutableEntry;
  19 import java.util.Iterator;
  20 import java.util.Map;
  21 import java.util.Map.Entry;
  22
  23 /**
  24  * Mimic immutable ListMap in Scala
  25  *
  26  * @author Roman Levenstein <romixlev@gmail.com>
  27  *
  28  * @param <V>
  29  */
  30 abstract class ListMap<K,V> {
  31
  32     ListMap<K,V> next;
  33
  34     static <K,V> ListMap<K, V> map(final K k, final V v, final ListMap<K, V> tail){
  35         return new Node<> (k, v, tail);
  36     }
  37
  38     static <K,V> ListMap<K, V> map(final K k, final V v){
  39         return new Node<> (k, v, null);
  40     }
  41
  42     static <K,V> ListMap<K, V> map(final K k1, final V v1, final K k2, final V v2){
  43         return new Node<> (k1, v1, new Node<>(k2,v2, null));
  44     }
  45
  46     public abstract int size ();
  47
  48     public abstract boolean isEmpty() ;
  49
  50     abstract public boolean contains(K k, V v);
  51
  52     abstract public boolean contains(K key);
  53
  54     abstract public Option<V> get (K key);
  55
  56     abstract public ListMap<K, V> add (K key, V value);
  57
  58     abstract public ListMap<K, V> remove (K key);
  59
  60     abstract public Iterator<Map.Entry<K, V>> iterator();
  61
  62
  63     static class EmptyListMap<K,V> extends ListMap<K, V> {
  64         @Override
  65         public ListMap<K,V> add (final K key, final V value) {
  66             return ListMap.map(key, value, null);
  67         }
  68
  69         @Override
  70         public boolean contains(final K k, final V v) {
  71             return false;
  72         }
  73
  74         @Override
  75         public boolean contains(final K k) {
  76             return false;
  77         }
  78
  79         @Override
  80         public ListMap<K,V> remove(final K key) {
  81             return this;
  82         }
  83
  84         @Override
  85         public int size () {
  86             return 0;
  87         }
  88
  89         @Override
  90         public boolean isEmpty () {
  91             return true;
  92         }
  93
  94         @Override
  95         public Option<V> get (final K key) {
  96             return Option.makeOption (null);
  97         }
  98
  99         @Override
 100         public Iterator<Entry<K, V>> iterator () {
 101             return new EmptyListMapIterator<> ();
 102         }
 103
 104         static class EmptyListMapIterator<K,V> implements Iterator<Entry<K, V>> {
 105
 106             @Override
 107             public boolean hasNext () {
 108                 return false;
 109             }
 110
 111             @Override
 112             public Entry<K, V> next () {
 113                 return null;
 114             }
 115
 116             @Override
 117             public void remove () {
 118                 throw new RuntimeException("Operation not supported");
 119             }
 120
 121         }
 122     }
 123
 124     static class Node<K,V> extends ListMap<K, V> {
 125         final K k;
 126         final V v;
 127
 128         Node(final K k, final V v, final ListMap<K,V> next) {
 129             this.k = k;
 130             this.v = v;
 131             this.next = next;
 132         }
 133
 134         @Override
 135         public ListMap<K,V> add (final K key, final V value) {
 136             return ListMap.map(key, value, remove (key));
 137         }
 138
 139         @Override
 140         public boolean contains(final K k, final V v) {
 141             if(k.equals (this.k) && v.equals (this.v)) {
 142                 return true;
 143             } else if(next != null) {
 144                 return next.contains (k, v);
 145             }
 146             return false;
 147         }
 148
 149         @Override
 150         public boolean contains(final K k) {
 151             if(k.equals (this.k)) {
 152                 return true;
 153             } else if(next != null) {
 154                 return next.contains (k);
 155             }
 156             return false;
 157         }
 158
 159         @Override
 160         public ListMap<K,V> remove(final K key) {
 161             if(!contains(key)) {
 162                 return this;
 163             } else {
 164                 return remove0(key);
 165             }
 166         }
 167
 168         private ListMap<K, V> remove0 (final K key) {
 169             ListMap<K, V> n = this;
 170             ListMap<K, V> newN = null;
 171             ListMap<K, V> lastN = null;
 172             while (n != null) {
 173                 if(n instanceof EmptyListMap) {
 174                     newN.next = n;
 175                     break;
 176                 }
 177                 Node<K, V> nn = (Node<K, V>)n;
 178                 if (key.equals (nn.k)) {
 179                     n = n.next;
 180                     continue;
 181                 } else {
 182                     if (newN != null) {
 183                         lastN.next = ListMap.map (nn.k, nn.v, null);
 184                         lastN = lastN.next;
 185                     } else {
 186                         newN = ListMap.map (nn.k, nn.v, null);
 187                         lastN = newN;
 188                     }
 189                 }
 190                 n = n.next;
 191             }
 192             return newN;
 193         }
 194
 195         @Override
 196         public int size () {
 197             if(next == null) {
 198                 return 1;
 199             } else {
 200                 return 1+next.size ();
 201             }
 202         }
 203
 204         @Override
 205         public boolean isEmpty () {
 206             return false;
 207         }
 208
 209         @Override
 210         public Option<V> get (final K key) {
 211             if(key.equals (k)) {
 212                 return Option.makeOption (v);
 213             }
 214             if(next != null) {
 215                 return next.get (key);
 216             }
 217             return Option.makeOption (null);
 218         }
 219
 220
 221         @Override
 222         public Iterator<Entry<K, V>> iterator () {
 223             return new NodeIterator<> (this);
 224         }
 225
 226         static class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
 227             ListMap<K, V> n;
 228
 229             public NodeIterator (final Node<K, V> n) {
 230                 this.n = n;
 231             }
 232
 233             @Override
 234             public boolean hasNext () {
 235 //                return n!= null && n.next != null && !(n.next instanceof EmptyListMap);
 236                 return n!= null && !(n instanceof EmptyListMap);
 237             }
 238
 239             @Override
 240             public Entry<K, V> next () {
 241                 if (n instanceof Node) {
 242                     Node<K, V> nn = (Node<K, V>) n;
 243                     Entry<K, V> res = new SimpleImmutableEntry<> (nn.k, nn.v);
 244                     n = n.next;
 245                     return res;
 246                 } else {
 247                     return null;
 248                 }
 249             }
 250
 251             @Override
 252             public void remove () {
 253                 throw new RuntimeException("Operation not supported");
 254             }
 255
 256         }
 257     }
 258 }