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
  23 /**
  24  * Mimic immutable ListMap in Scala
  25  *
  26  * @author Roman Levenstein <romixlev@gmail.com>
  27  *
  28  * @param <V>
  29  */
  30 final class ListMap<K, V> {
  31     private final K k;
  32     private final V v;
  33
  34     // Modified during remove0 only
  35     private ListMap<K, V> next;
  36
  37     private ListMap(final K k, final V v) {
  38         this(k, v, null);
  39     }
  40
  41     private ListMap(final K k, final V v, final ListMap<K, V> next) {
  42         this.k = k;
  43         this.v = v;
  44         this.next = next;
  45     }
  46
  47     static <K,V> ListMap<K, V> map(final K k1, final V v1, final K k2, final V v2) {
  48         return new ListMap<>(k1, v1, new ListMap<>(k2, v2));
  49     }
  50
  51     int size() {
  52         return next == null ? 1 : next.size() + 1;
  53     }
  54
  55     Option<V> get(final K key) {
  56         if (key.equals(k)) {
  57             return Option.makeOption(v);
  58         }
  59         return next == null ? Option.makeOption() : next.get(key);
  60     }
  61
  62     ListMap<K,V> add(final K key, final V value) {
  63         return new ListMap<>(key, value, remove(key));
  64     }
  65
  66     ListMap<K, V> remove(final K key) {
  67          if (!contains(key)) {
  68             return this;
  69         }
  70
  71         return remove0(key);
  72     }
  73
  74     private boolean contains(final K key) {
  75         if (key.equals(this.k)) {
  76             return true;
  77         }
  78
  79         return next != null && next.contains(key);
  80     }
  81
  82     private ListMap<K, V> remove0(final K key) {
  83         ListMap<K, V> n = this;
  84         ListMap<K, V> ret = null;
  85         ListMap<K, V> lastN = null;
  86         while (n != null) {
  87             if (key.equals(n.k)) {
  88                 n = n.next;
  89                 continue;
  90             }
  91
  92             if (ret != null) {
  93                 lastN.next = new ListMap<>(n.k, n.v);
  94                 lastN = lastN.next;
  95             } else {
  96                 ret = new ListMap<>(n.k, n.v);
  97                 lastN = ret;
  98             }
  99             n = n.next;
 100         }
 101         return ret;
 102     }
 103
 104     Iterator<Entry<K, V>> iterator() {
 105         return new NodeIterator<>(this);
 106     }
 107
 108     static final class NodeIterator<K,V> implements Iterator<Entry<K, V>> {
 109         private ListMap<K, V> n;
 110
 111         NodeIterator(final ListMap<K, V> n) {
 112             this.n = n;
 113         }
 114
 115         @Override
 116         public boolean hasNext() {
 117             return n != null;
 118         }
 119
 120         @Override
 121         public Entry<K, V> next() {
 122             if (n == null) {
 123                 throw new NoSuchElementException();
 124             }
 125
 126             final Entry<K, V> res = new SimpleImmutableEntry<>(n.k, n.v);
 127             n = n.next;
 128             return res;
 129         }
 130     }
 131 }