third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.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  * Mimic immutable ListMap in Scala
  26  *
  27  * @author Roman Levenstein <romixlev@gmail.com>
  28  *
  29  * @param <V>
  30  */
  31 final class ListMap<K, V> {
  32     private final K k;
  33     private final V v;
  34
  35     // Modified during remove0 only
  36     private ListMap<K, V> next;
  37
  38     private ListMap(final K k, final V v) {
  39         this(k, v, null);
  40     }
  41
  42     private ListMap(final K k, final V v, final ListMap<K, V> next) {
  43         this.k = k;
  44         this.v = v;
  45         this.next = next;
  46     }
  47
  48     static <K,V> ListMap<K, V> map(final K k1, final V v1, final K k2, final V v2) {
  49         return new ListMap<>(k1, v1, new ListMap<>(k2, v2));
  50     }
  51
  52     Optional<Entry<K, V>> maybeSingleton() {
  53         return next != null ? Optional.empty() : Optional.of(new SimpleImmutableEntry<>(k, v));
  54     }
  55
  56     int size() {
  57         int sz = 1;
  58         for (ListMap<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
  59             sz++;
  60         }
  61         return sz;
  62     }
  63
  64     Optional<V> get(final Equivalence<? super K> equiv, final K key) {
  65         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  66         ListMap<K, V> head = this;
  67         do {
  68             if (equiv.equivalent(head.k, key)) {
  69                 return Optional.of(head.v);
  70             }
  71
  72             head = head.next;
  73         } while (head != null);
  74
  75         return Optional.empty();
  76     }
  77
  78     ListMap<K,V> add(final Equivalence<? super K> equiv, final K key, final V value) {
  79         return new ListMap<>(key, value, remove(equiv, key));
  80     }
  81
  82     ListMap<K, V> remove(final Equivalence<? super K> equiv, final K key) {
  83          if (!contains(equiv, key)) {
  84             return this;
  85         }
  86
  87         return remove0(key);
  88     }
  89
  90     private boolean contains(final Equivalence<? super K> equiv, final K key) {
  91         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  92         ListMap<K, V> head = this;
  93         do {
  94             if (equiv.equivalent(head.k, key)) {
  95                 return true;
  96             }
  97             head = head.next;
  98         } while (head != null);
  99
 100         return false;
 101     }
 102
 103     private ListMap<K, V> remove0(final K key) {
 104         ListMap<K, V> n = this;
 105         ListMap<K, V> ret = null;
 106         ListMap<K, V> lastN = null;
 107         while (n != null) {
 108             if (key.equals(n.k)) {
 109                 n = n.next;
 110                 continue;
 111             }
 112
 113             if (ret != null) {
 114                 lastN.next = new ListMap<>(n.k, n.v);
 115                 lastN = lastN.next;
 116             } else {
 117                 ret = new ListMap<>(n.k, n.v);
 118                 lastN = ret;
 119             }
 120             n = n.next;
 121         }
 122         return ret;
 123     }
 124
 125     Iterator<Entry<K, V>> iterator() {
 126         return new NodeIterator<>(this);
 127     }
 128
 129     static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
 130         private ListMap<K, V> n;
 131
 132         NodeIterator(final ListMap<K, V> n) {
 133             this.n = n;
 134         }
 135
 136         @Override
 137         public boolean hasNext() {
 138             return n != null;
 139         }
 140
 141         @Override
 142         public Entry<K, V> next() {
 143             if (n == null) {
 144                 throw new NoSuchElementException();
 145             }
 146
 147             final Entry<K, V> res = new SimpleImmutableEntry<>(n.k, n.v);
 148             n = n.next;
 149             return res;
 150         }
 151     }
 152 }