*/
package org.opendaylight.yangtools.triemap;
-import java.util.Iterator;
-import java.util.Map.Entry;
-import java.util.Optional;
-
final class LNode<K, V> extends MainNode<K, V> {
- private final ListMap<K, V> listmap;
+ // Internally-linked single list of of entries
+ private final LNodeEntries<K, V> entries;
+ private final int size;
- private LNode(final ListMap<K, V> listmap) {
- this.listmap = listmap;
+ private LNode(final LNodeEntries<K, V> entries, final int size) {
+ this.entries = entries;
+ this.size = size;
}
LNode(final K k1, final V v1, final K k2, final V v2) {
- this(ListMap.map(k1, v1, k2, v2));
+ this(LNodeEntries.map(k1, v1, k2, v2), 2);
}
- LNode<K, V> inserted(final K k, final V v) {
- return new LNode<>(listmap.add(k, v));
+ LNode<K, V> insertChild(final K key, final V value) {
+ return new LNode<>(entries.insert(key, value), size + 1);
}
- MainNode<K, V> removed(final K k, final TrieMap<K, V> ct) {
- // We only ever create ListMaps with two or more entries, and remove them as soon as they reach one element
- // (below), so we cannot observe a null return here.
- final ListMap<K, V> updmap = listmap.remove(k);
- if (updmap.size() > 1) {
- return new LNode<>(updmap);
+ MainNode<K, V> removeChild(final LNodeEntry<K, V> entry, final int hc) {
+ // While remove() can return null, that case will never happen here, as we are starting off with two entries
+ // so we cannot observe a null return here.
+ final LNodeEntries<K, V> map = entries.remove(entry);
+
+ // If the returned LNode would have only one element, we turn it into a TNode, hence above null return from
+ // remove() can never happen.
+ if (size == 2) {
+ // create it tombed so that it gets compressed on subsequent accesses
+ return new TNode<>(map.getKey(), map.getValue(), hc);
}
- final Entry<K, V> kv = updmap.iterator().next();
- // create it tombed so that it gets compressed on subsequent accesses
- return new TNode<>(kv.getKey(), kv.getValue(), ct.computeHash(kv.getKey()));
+ return new LNode<>(map, size - 1);
}
- Optional<V> get(final K k) {
- return listmap.get(k);
+ MainNode<K, V> replaceChild(final LNodeEntry<K, V> entry, final V value) {
+ return new LNode<>(entries.replace(entry, value), size);
}
- @Override
- int cachedSize(final TrieMap<K, V> ct) {
- return listmap.size();
+ LNodeEntry<K, V> get(final Equivalence<? super K> equiv, final K key) {
+ return entries.findEntry(equiv, key);
+ }
+
+ LNodeEntries<K, V> entries() {
+ return entries;
}
@Override
- String string(final int lev) {
- // (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
- return "LNode";
+ int trySize() {
+ return size;
}
- Iterator<Entry<K, V>> iterator() {
- return listmap.iterator();
+ @Override
+ int size(final ImmutableTrieMap<?, ?> ct) {
+ return size;
}
-}
\ No newline at end of file
+}