third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/LNodeEntries.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.Iterator;
  19 import java.util.Map.Entry;
  20 import java.util.NoSuchElementException;
  21
  22 /**
  23  * Similar to Scala's ListMap. Stores a linked set of entries, guaranteed to contain unique entry keys.
  24  *
  25  * @author Robert Varga
  26  *
  27  * @param <K> the type of keys
  28  * @param <V> the type of values
  29  */
  30 final class LNodeEntries<K, V> extends LNodeEntry<K, V> {
  31     // Modified during remove only
  32     private LNodeEntries<K, V> next;
  33
  34     private LNodeEntries(final K k, final V v) {
  35         this(k, v, null);
  36     }
  37
  38     private LNodeEntries(final K k, final V v, final LNodeEntries<K, V> next) {
  39         super(k, v);
  40         this.next = next;
  41     }
  42
  43     static <K,V> LNodeEntries<K, V> map(final K k1, final V v1, final K k2, final V v2) {
  44         return new LNodeEntries<>(k1, v1, new LNodeEntries<>(k2, v2));
  45     }
  46
  47     boolean isSingle() {
  48         return next == null;
  49     }
  50
  51     int size() {
  52         int sz = 1;
  53         for (LNodeEntries<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
  54             sz++;
  55         }
  56         return sz;
  57     }
  58
  59     LNodeEntry<K, V> findEntry(final Equivalence<? super K> equiv, final K key) {
  60         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  61         LNodeEntries<K, V> entry = this;
  62         do {
  63             if (equiv.equivalent(entry.getKey(), key)) {
  64                 return entry;
  65             }
  66
  67             entry = entry.next;
  68         } while (entry != null);
  69
  70         return null;
  71     }
  72
  73     LNodeEntries<K,V> insert(final K key, final V value) {
  74         return new LNodeEntries<>(key, value, this);
  75     }
  76
  77     LNodeEntries<K, V> replace(final LNodeEntry<K, V> entry, final V v) {
  78         return new LNodeEntries<>(entry.getKey(), v, remove(entry));
  79     }
  80
  81     LNodeEntries<K, V> remove(final LNodeEntry<K, V> entry) {
  82         if (entry == this) {
  83             return next;
  84         }
  85
  86         final LNodeEntries<K, V> ret = new LNodeEntries<>(getKey(), getValue());
  87
  88         LNodeEntries<K, V> last = ret;
  89         LNodeEntries<K, V> cur = next;
  90         while (cur != null) {
  91             // We cannot use equals() here, as it is wired to key/value equality,
  92             // which we really do not want.
  93             if (entry == cur) {
  94                 last.next = cur.next;
  95                 return ret;
  96             }
  97
  98             last.next = new LNodeEntries<>(cur.getKey(), cur.getValue());
  99             last = last.next;
 100             cur = cur.next;
 101         }
 102
 103         throw new IllegalStateException(String.format("Entry %s not found", entry));
 104     }
 105
 106     Iterator<Entry<K, V>> iterator() {
 107         return new NodeIterator<>(this);
 108     }
 109
 110     static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
 111         private LNodeEntries<K, V> n;
 112
 113         NodeIterator(final LNodeEntries<K, V> n) {
 114             this.n = n;
 115         }
 116
 117         @Override
 118         public boolean hasNext() {
 119             return n != null;
 120         }
 121
 122         @Override
 123         public Entry<K, V> next() {
 124             if (n == null) {
 125                 throw new NoSuchElementException();
 126             }
 127
 128             final Entry<K, V> res = n;
 129             n = n.next;
 130             return res;
 131         }
 132     }
 133 }