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