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.AbstractMap.SimpleImmutableEntry;
  19 import java.util.Iterator;
  20 import java.util.Map.Entry;
  21 import java.util.NoSuchElementException;
  22 import java.util.Optional;
  23
  24 /**
  25  * Similar to Scala's ListMap. Stores a linked set of entries, guaranteed to contain unique entry keys.
  26  *
  27  * @author Robert Varga
  28  *
  29  * @param <K> the type of keys
  30  * @param <V> the type of values
  31  */
  32 final class LNodeEntries<K, V> extends LNodeEntry<K, V> {
  33     // Modified during remove0 only
  34     private LNodeEntries<K, V> next;
  35
  36     private LNodeEntries(final K k, final V v) {
  37         this(k, v, null);
  38     }
  39
  40     private LNodeEntries(final K k, final V v, final LNodeEntries<K, V> next) {
  41         super(k, v);
  42         this.next = next;
  43     }
  44
  45     static <K,V> LNodeEntries<K, V> map(final K k1, final V v1, final K k2, final V v2) {
  46         return new LNodeEntries<>(k1, v1, new LNodeEntries<>(k2, v2));
  47     }
  48
  49     Optional<Entry<K, V>> maybeSingleton() {
  50         return next != null ? Optional.empty() : Optional.of(new SimpleImmutableEntry<>(key(), value()));
  51     }
  52
  53     int size() {
  54         int sz = 1;
  55         for (LNodeEntries<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
  56             sz++;
  57         }
  58         return sz;
  59     }
  60
  61     LNodeEntry<K, V> findEntry(final Equivalence<? super K> equiv, final K key) {
  62         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  63         LNodeEntries<K, V> head = this;
  64         do {
  65             if (equiv.equivalent(head.key(), key)) {
  66                 return head;
  67             }
  68
  69             head = head.next;
  70         } while (head != null);
  71
  72         return null;
  73     }
  74
  75     LNodeEntries<K,V> insert(final K key, final V value) {
  76         return new LNodeEntries<>(key, value, this);
  77     }
  78
  79     LNodeEntries<K, V> replace(final LNodeEntry<K, V> entry, final V v) {
  80         return new LNodeEntries<>(entry.key(), v, remove(entry));
  81     }
  82
  83     LNodeEntries<K, V> remove(final LNodeEntry<K, V> entry) {
  84         if (entry == this) {
  85             return next;
  86         }
  87
  88         final LNodeEntries<K, V> ret = new LNodeEntries<>(key(), value());
  89
  90         LNodeEntries<K, V> last = ret;
  91         LNodeEntries<K, V> cur = next;
  92         while (cur != null) {
  93             if (entry.equals(cur)) {
  94                 last.next = cur.next;
  95                 return ret;
  96             }
  97
  98             last.next = new LNodeEntries<>(cur.key(), cur.value());
  99             last = last.next;
 100             cur = cur.next;
 101         }
 102
 103         throw new IllegalStateException("Entry " + entry + " not found in entries " + this);
 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 = new SimpleImmutableEntry<>(n.key(), n.value());
 129             n = n.next;
 130             return res;
 131         }
 132     }
 133 }