Package org.sosy_lab.common.collect

Class PathCopyingPersistentTreeMap<K extends Comparable<? super K>,​V extends @Nullable Object>

  • Type Parameters:
    K - The type of keys.
    V - The type of values.
    All Implemented Interfaces:
    Serializable, Map<K,​V>, NavigableMap<K,​V>, SortedMap<K,​V>, PersistentMap<K,​V>, PersistentSortedMap<K,​V>
    @Immutable(containerOf={"K","V"})
public final class PathCopyingPersistentTreeMap<K extends Comparable<? super K>,​V extends @Nullable Object>
extends Object
implements PersistentSortedMap<K,​V>, Serializable
    This is an implementation of PersistentSortedMap that is based on left-leaning red-black trees (LLRB) and path copying. Left-leaning red-black trees are similar to red-black trees and 2-3 trees, but are considerably easier to implement than red-black trees. They are described by Robert Sedgewick here: http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

    The operations insert, lookup, and remove are guaranteed to run in O(log n) time. Insert and remove allocate at most O(log n) memory. Traversal through all entries also allocates up to O(log n) memory. Per entry, this map needs memory for one object with 4 reference fields and 1 boolean. (This is a little bit less than TreeMap needs.)

    This implementation does not support null keys (but null values) and always compares according to the natural ordering. All methods may throw ClassCastException is key objects are passed that do not implement Comparable.

    The natural ordering of the keys needs to be consistent with equals.

    As for all PersistentMaps, all collection views and all iterators are immutable. They do not reflect changes made to the map and all their modifying operations throw UnsupportedOperationException.

    All instances of this class are fully-thread safe. However, note that each modifying operation allocates a new instance whose reference needs to be published safely in order to be usable by other threads. Two concurrent accesses to a modifying operation on the same instance will create two new maps, each reflecting exactly the operation executed by the current thread, and not reflecting the operation executed by the other thread.

    See Also:
    Serialized Form