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.Entry;
  21 import java.util.NoSuchElementException;
  22
  23 /**
  24  * Mimic immutable ListMap in Scala
  25  *
  26  * @author Roman Levenstein <romixlev@gmail.com>
  27  *
  28  * @param <V>
  29  */
  30 final class ListMap<K, V> {
  31     private final K k;
  32     private final V v;
  33
  34     // Modified during remove0 only
  35     private ListMap<K, V> next;
  36
  37     private ListMap(final K k, final V v) {
  38         this(k, v, null);
  39     }
  40
  41     private ListMap(final K k, final V v, final ListMap<K, V> next) {
  42         this.k = k;
  43         this.v = v;
  44         this.next = next;
  45     }
  46
  47     static <K,V> ListMap<K, V> map(final K k1, final V v1, final K k2, final V v2) {
  48         return new ListMap<>(k1, v1, new ListMap<>(k2, v2));
  49     }
  50
  51     int size() {
  52         int sz = 1;
  53         for (ListMap<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
  54             sz++;
  55         }
  56         return sz;
  57     }
  58
  59     Option<V> get(final K key) {
  60         if (key.equals(k)) {
  61             return Option.makeOption(v);
  62         }
  63
  64         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  65         for (ListMap<K, V> m = next; m != null; m = m.next) {
  66             if (key.equals(m.k)) {
  67                 return Option.makeOption(m.v);
  68             }
  69         }
  70
  71         return Option.makeOption();
  72     }
  73
  74     ListMap<K,V> add(final K key, final V value) {
  75         return new ListMap<>(key, value, remove(key));
  76     }
  77
  78     ListMap<K, V> remove(final K key) {
  79          if (!contains(key)) {
  80             return this;
  81         }
  82
  83         return remove0(key);
  84     }
  85
  86     private boolean contains(final K key) {
  87         if (key.equals(k)) {
  88             return true;
  89         }
  90
  91         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  92         for (ListMap<K, V> m = next; m != null; m = m.next) {
  93             if (key.equals(m.k)) {
  94                 return true;
  95             }
  96         }
  97
  98         return false;
  99     }
 100
 101     private ListMap<K, V> remove0(final K key) {
 102         ListMap<K, V> n = this;
 103         ListMap<K, V> ret = null;
 104         ListMap<K, V> lastN = null;
 105         while (n != null) {
 106             if (key.equals(n.k)) {
 107                 n = n.next;
 108                 continue;
 109             }
 110
 111             if (ret != null) {
 112                 lastN.next = new ListMap<>(n.k, n.v);
 113                 lastN = lastN.next;
 114             } else {
 115                 ret = new ListMap<>(n.k, n.v);
 116                 lastN = ret;
 117             }
 118             n = n.next;
 119         }
 120         return ret;
 121     }
 122
 123     Iterator<Entry<K, V>> iterator() {
 124         return new NodeIterator<>(this);
 125     }
 126
 127     static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
 128         private ListMap<K, V> n;
 129
 130         NodeIterator(final ListMap<K, V> n) {
 131             this.n = n;
 132         }
 133
 134         @Override
 135         public boolean hasNext() {
 136             return n != null;
 137         }
 138
 139         @Override
 140         public Entry<K, V> next() {
 141             if (n == null) {
 142                 throw new NoSuchElementException();
 143             }
 144
 145             final Entry<K, V> res = new SimpleImmutableEntry<>(n.k, n.v);
 146             n = n.next;
 147             return res;
 148         }
 149     }
 150 }