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 abstract class LNodeEntries<K, V> extends LNodeEntry<K, V> {
  31     private static final class Single<K, V> extends LNodeEntries<K, V> {
  32         Single(final K k, final V v) {
  33             super(k, v);
  34         }
  35
  36         @Override
  37         boolean isSingle() {
  38             return true;
  39         }
  40
  41         @Override
  42         LNodeEntries<K, V> next() {
  43             return null;
  44         }
  45     }
  46
  47     private static final class Multiple<K, V> extends LNodeEntries<K, V> {
  48         // Modified during remove only
  49         LNodeEntries<K, V> next;
  50
  51         // Used in remove() only
  52         Multiple(final LNodeEntries<K, V> e) {
  53             this(e.getKey(), e.getValue(), null);
  54         }
  55
  56         Multiple(final K k, final V v, final LNodeEntries<K, V> next) {
  57             super(k, v);
  58             this.next = next;
  59         }
  60
  61         @Override
  62         boolean isSingle() {
  63             return next == null;
  64         }
  65
  66         @Override
  67         LNodeEntries<K, V> next() {
  68             return next;
  69         }
  70     }
  71
  72     LNodeEntries(final K k, final V v) {
  73         super(k, v);
  74     }
  75
  76     static <K,V> LNodeEntries<K, V> map(final K k1, final V v1, final K k2, final V v2) {
  77         return new Multiple<>(k1, v1, new Single<>(k2, v2));
  78     }
  79
  80     abstract boolean isSingle();
  81
  82     abstract LNodeEntries<K, V> next();
  83
  84     final LNodeEntry<K, V> findEntry(final Equivalence<? super K> equiv, final K key) {
  85         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  86         LNodeEntries<K, V> entry = this;
  87         do {
  88             if (equiv.equivalent(entry.getKey(), key)) {
  89                 return entry;
  90             }
  91
  92             entry = entry.next();
  93         } while (entry != null);
  94
  95         return null;
  96     }
  97
  98     final LNodeEntries<K,V> insert(final K key, final V value) {
  99         return new Multiple<>(key, value, this);
 100     }
 101
 102     final LNodeEntries<K, V> replace(final LNodeEntry<K, V> entry, final V v) {
 103         final LNodeEntries<K, V> removed = remove(entry);
 104         return removed == null ? new Single<>(entry.getKey(), v) : new Multiple<>(entry.getKey(), v, removed);
 105     }
 106
 107     final LNodeEntries<K, V> remove(final LNodeEntry<K, V> entry) {
 108         if (entry == this) {
 109             return next();
 110         }
 111
 112         final Multiple<K, V> ret = new Multiple<>(this);
 113
 114         Multiple<K, V> last = ret;
 115         LNodeEntries<K, V> cur = next();
 116         while (cur != null) {
 117             // We cannot use equals() here, as it is wired to key/value equality,
 118             // which we really do not want.
 119             if (entry == cur) {
 120                 last.next = cur.next();
 121                 return ret;
 122             }
 123
 124             final Multiple<K, V> tmp = new Multiple<>(cur);
 125             last.next = tmp;
 126             last = tmp;
 127             cur = cur.next();
 128         }
 129
 130         throw new IllegalStateException(String.format("Entry %s not found", entry));
 131     }
 132
 133     // No need to specialize these two methods, as they are invoked only from a stable LNode, at which point it is
 134     // guaranteed to be a Multiple.
 135     final int size() {
 136         int sz = 1;
 137         for (LNodeEntries<?, ?> wlk = next(); wlk != null; wlk = wlk.next()) {
 138             sz++;
 139         }
 140         return sz;
 141     }
 142
 143     final Iterator<Entry<K, V>> iterator() {
 144         return new NodeIterator<>(this);
 145     }
 146
 147     static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
 148         private LNodeEntries<K, V> n;
 149
 150         NodeIterator(final LNodeEntries<K, V> n) {
 151             this.n = n;
 152         }
 153
 154         @Override
 155         public boolean hasNext() {
 156             return n != null;
 157         }
 158
 159         @Override
 160         public Entry<K, V> next() {
 161             if (n == null) {
 162                 throw new NoSuchElementException();
 163             }
 164
 165             final Entry<K, V> res = n;
 166             n = n.next();
 167             return res;
 168         }
 169     }
 170 }