BUG-7464: Make ListMap obey TrieMap equivalence

[yangtools.git] / third-party / triemap / src / main / java / org / opendaylight / yangtools / triemap / ListMap.java

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
index 1522b6611fa72df49272e431b8436408e1f73b80..b2f1c10af5f02b41934c609fbfe3c286416d6690 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
@@ -19,6 +19,7 @@ import java.util.AbstractMap.SimpleImmutableEntry;
 import java.util.Iterator;
 import java.util.Map.Entry;
 import java.util.NoSuchElementException;
+import java.util.Optional;
 
 /**
  * Mimic immutable ListMap in Scala
@@ -48,35 +49,55 @@ final class ListMap<K, V> {
         return new ListMap<>(k1, v1, new ListMap<>(k2, v2));
     }
 
-    int size() {
-        return next == null ? 1 : next.size() + 1;
+    Optional<Entry<K, V>> maybeSingleton() {
+        return next != null ? Optional.empty() : Optional.of(new SimpleImmutableEntry<>(k, v));
     }
 
-    Option<V> get(final K key) {
-        if (key.equals(k)) {
-            return Option.makeOption(v);
+    int size() {
+        int sz = 1;
+        for (ListMap<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
+            sz++;
         }
-        return next == null ? Option.makeOption() : next.get(key);
+        return sz;
     }
 
-    ListMap<K,V> add(final K key, final V value) {
-        return new ListMap<>(key, value, remove(key));
+    Optional<V> get(final Equivalence<? super K> equiv, final K key) {
+        // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
+        ListMap<K, V> head = this;
+        do {
+            if (equiv.equivalent(head.k, key)) {
+                return Optional.of(head.v);
+            }
+
+            head = head.next;
+        } while (head != null);
+
+        return Optional.empty();
     }
 
-    ListMap<K, V> remove(final K key) {
-         if (!contains(key)) {
+    ListMap<K,V> add(final Equivalence<? super K> equiv, final K key, final V value) {
+        return new ListMap<>(key, value, remove(equiv, key));
+    }
+
+    ListMap<K, V> remove(final Equivalence<? super K> equiv, final K key) {
+         if (!contains(equiv, key)) {
             return this;
         }
 
         return remove0(key);
     }
 
-    private boolean contains(final K key) {
-        if (key.equals(this.k)) {
-            return true;
-        }
+    private boolean contains(final Equivalence<? super K> equiv, final K key) {
+        // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
+        ListMap<K, V> head = this;
+        do {
+            if (equiv.equivalent(head.k, key)) {
+                return true;
+            }
+            head = head.next;
+        } while (head != null);
 
-        return next != null && next.contains(key);
+        return false;
     }
 
     private ListMap<K, V> remove0(final K key) {