/* * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.opendaylight.yangtools.triemap; /** * Similar to Scala's ListMap, this is a single-linked list of set of map entries. Aside from the Set contract, this * class fulfills the requirements for an immutable map entryset. * * @author Robert Varga * * @param the type of keys * @param the type of values */ abstract class LNodeEntries extends LNodeEntry { private static final class Single extends LNodeEntries { Single(final K k, final V v) { super(k, v); } @Override LNodeEntries next() { return null; } } private static final class Multiple extends LNodeEntries { // Modified during remove only, otherwise final LNodeEntries next; // Used in remove() only Multiple(final LNodeEntries e) { this(e.getKey(), e.getValue(), null); } Multiple(final K k, final V v, final LNodeEntries next) { super(k, v); this.next = next; } @Override LNodeEntries next() { return next; } } LNodeEntries(final K k, final V v) { super(k, v); } static LNodeEntries map(final K k1, final V v1, final K k2, final V v2) { return new Multiple<>(k1, v1, new Single<>(k2, v2)); } /** * Return the remainder of this list. Useful for implementing Iterator-like contract. Null indicates there are no * more entries. * * @return Remainder of this list, or null if nothing remains */ abstract LNodeEntries next(); final LNodeEntry findEntry(final Equivalence 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. LNodeEntries entry = this; do { if (equiv.equivalent(entry.getKey(), key)) { return entry; } entry = entry.next(); } while (entry != null); return null; } final LNodeEntries insert(final K key, final V value) { return new Multiple<>(key, value, this); } final LNodeEntries replace(final LNodeEntry entry, final V v) { final LNodeEntries removed; return (removed = remove(entry)) == null ? new Single<>(entry.getKey(), v) : new Multiple<>(entry.getKey(), v, removed); } final LNodeEntries remove(final LNodeEntry entry) { if (entry == this) { return next(); } // This will result in a list with a long tail, i.e last entry storing explicit null. Overhead is amortized // against the number of entries. We do not retain chains shorter than two, so the worst-case overhead is // half-a-reference for an entry. final Multiple ret = new Multiple<>(this); Multiple last = ret; LNodeEntries cur = next(); while (cur != null) { // We cannot use equals() here, as it is wired to key equality and we must never compare entries based on // that property. This method is intended to remove a known reference, so identity is what we want. if (entry == cur) { last.next = cur.next(); return ret; } final Multiple tmp = new Multiple<>(cur); last.next = tmp; last = tmp; cur = cur.next(); } throw new IllegalStateException(String.format("Entry %s not found", entry)); } }