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 K key) {
  65         if (key.equals(k)) {
  66             return Optional.of(v);
  67         }
  68
  69         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  70         for (ListMap<K, V> m = next; m != null; m = m.next) {
  71             if (key.equals(m.k)) {
  72                 return Optional.of(m.v);
  73             }
  74         }
  75
  76         return Optional.empty();
  77     }
  78
  79     ListMap<K,V> add(final K key, final V value) {
  80         return new ListMap<>(key, value, remove(key));
  81     }
  82
  83     ListMap<K, V> remove(final K key) {
  84          if (!contains(key)) {
  85             return this;
  86         }
  87
  88         return remove0(key);
  89     }
  90
  91     private boolean contains(final K key) {
  92         if (key.equals(k)) {
  93             return true;
  94         }
  95
  96         // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
  97         for (ListMap<K, V> m = next; m != null; m = m.next) {
  98             if (key.equals(m.k)) {
  99                 return true;
 100             }
 101         }
 102
 103         return false;
 104     }
 105
 106     private ListMap<K, V> remove0(final K key) {
 107         ListMap<K, V> n = this;
 108         ListMap<K, V> ret = null;
 109         ListMap<K, V> lastN = null;
 110         while (n != null) {
 111             if (key.equals(n.k)) {
 112                 n = n.next;
 113                 continue;
 114             }
 115
 116             if (ret != null) {
 117                 lastN.next = new ListMap<>(n.k, n.v);
 118                 lastN = lastN.next;
 119             } else {
 120                 ret = new ListMap<>(n.k, n.v);
 121                 lastN = ret;
 122             }
 123             n = n.next;
 124         }
 125         return ret;
 126     }
 127
 128     Iterator<Entry<K, V>> iterator() {
 129         return new NodeIterator<>(this);
 130     }
 131
 132     static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
 133         private ListMap<K, V> n;
 134
 135         NodeIterator(final ListMap<K, V> n) {
 136             this.n = n;
 137         }
 138
 139         @Override
 140         public boolean hasNext() {
 141             return n != null;
 142         }
 143
 144         @Override
 145         public Entry<K, V> next() {
 146             if (n == null) {
 147                 throw new NoSuchElementException();
 148             }
 149
 150             final Entry<K, V> res = new SimpleImmutableEntry<>(n.k, n.v);
 151             n = n.next;
 152             return res;
 153         }
 154     }
 155 }