Class PathCopyingPersistentTreeMap<K extends Comparable<? super K>,V>
- java.lang.Object
-
- org.sosy_lab.common.collect.PathCopyingPersistentTreeMap<K,V>
-
- 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 Object implements PersistentSortedMap<K,V>, Serializable
This is an implementation ofPersistentSortedMap
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.pdfThe 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 (butnull
values) and always compares according to the natural ordering. All methods may throwClassCastException
is key objects are passed that do not implementComparable
.The natural ordering of the keys needs to be consistent with equals.
As for all
PersistentMap
s, all collection views and all iterators are immutable. They do not reflect changes made to the map and all their modifying operations throwUnsupportedOperationException
.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
-
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description @Nullable Map.Entry<K,V>
ceilingEntry(K pKey)
@Nullable K
ceilingKey(K pKey)
void
clear()
Deprecated.@Nullable Comparator<? super K>
comparator()
V
compute(K pKey, BiFunction<? super K,? super V,? extends V> pRemappingFunction)
Deprecated.V
computeIfAbsent(K pKey, Function<? super K,? extends V> pMappingFunction)
Deprecated.V
computeIfPresent(K pKey, BiFunction<? super K,? super V,? extends V> pRemappingFunction)
Deprecated.boolean
containsKey(Object pObj)
boolean
containsValue(Object pValue)
static <K extends Comparable<? super K>,V>
PersistentSortedMap<K,V>copyOf(Map<K,V> map)
Iterator<Map.Entry<K,V>>
descendingEntryIterator()
NavigableSet<K>
descendingKeySet()
org.sosy_lab.common.collect.OurSortedMap<K,V>
descendingMap()
PersistentSortedMap<K,V>
empty()
Replacement for {PersistentMap.clear()
that returns an empty instance.Iterator<Map.Entry<K,V>>
entryIterator()
NavigableSet<Map.Entry<K,V>>
entrySet()
boolean
equals(@Nullable Object pObj)
@Nullable Map.Entry<K,V>
firstEntry()
K
firstKey()
@Nullable Map.Entry<K,V>
floorEntry(K pKey)
@Nullable K
floorKey(K pKey)
@Nullable V
get(Object pObj)
@Nullable Map.Entry<K,V>
getEntry(Object pKey)
V
getOrDefault(Object pKey, V pDefaultValue)
int
hashCode()
org.sosy_lab.common.collect.OurSortedMap<K,V>
headMap(K pToKey)
org.sosy_lab.common.collect.OurSortedMap<K,V>
headMap(K pToKey, boolean pToInclusive)
@Nullable Map.Entry<K,V>
higherEntry(K pKey)
@Nullable K
higherKey(K pKey)
boolean
isEmpty()
NavigableSet<K>
keySet()
@Nullable Map.Entry<K,V>
lastEntry()
K
lastKey()
@Nullable Map.Entry<K,V>
lowerEntry(K pKey)
@Nullable K
lowerKey(K pKey)
V
merge(K pKey, V pValue, BiFunction<? super V,? super V,? extends V> pRemappingFunction)
Deprecated.NavigableSet<K>
navigableKeySet()
static <K extends Comparable<? super K>,V>
PersistentSortedMap<K,V>of()
Map.Entry<K,V>
pollFirstEntry()
Deprecated.Map.Entry<K,V>
pollLastEntry()
Deprecated.V
put(K key, V value)
Deprecated.void
putAll(Map<? extends K,? extends V> pM)
Deprecated.PersistentSortedMap<K,V>
putAndCopy(K key, V value)
Replacement for {PersistentMap.put(Object, Object)
that returns a fresh instance.V
putIfAbsent(K pKey, V pValue)
Deprecated.V
remove(Object pKey)
Deprecated.boolean
remove(Object pKey, Object pValue)
Deprecated.PersistentSortedMap<K,V>
removeAndCopy(Object key)
Replacement for {PersistentMap.remove(Object)
that returns a fresh instance.V
replace(K pKey, V pValue)
Deprecated.boolean
replace(K pKey, V pOldValue, V pNewValue)
Deprecated.void
replaceAll(BiFunction<? super K,? super V,? extends V> pFunction)
Deprecated.int
size()
org.sosy_lab.common.collect.OurSortedMap<K,V>
subMap(K pFromKey, boolean pFromInclusive, K pToKey, boolean pToInclusive)
org.sosy_lab.common.collect.OurSortedMap<K,V>
subMap(K pFromKey, K pToKey)
org.sosy_lab.common.collect.OurSortedMap<K,V>
tailMap(K pFromKey)
org.sosy_lab.common.collect.OurSortedMap<K,V>
tailMap(K pFromKey, boolean pFromInclusive)
static <T,K extends Comparable<? super K>,V>
Collector<T,?,PersistentSortedMap<K,V>>toPathCopyingPersistentTreeMap(Function<? super T,? extends K> keyFunction, Function<? super T,? extends V> valueFunction)
Return aCollector
that accumulates elements into aPathCopyingPersistentTreeMap
.static <T,K extends Comparable<? super K>,V>
Collector<T,?,PersistentSortedMap<K,V>>toPathCopyingPersistentTreeMap(Function<? super T,? extends K> keyFunction, Function<? super T,? extends V> valueFunction, BinaryOperator<V> mergeFunction)
Return aCollector
that accumulates elements into aPathCopyingPersistentTreeMap
.String
toString()
Collection<V>
values()
-
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.util.Map
containsValue, forEach
-
Methods inherited from interface java.util.NavigableMap
ceilingKey, descendingKeySet, floorKey, higherKey, lowerKey, navigableKeySet
-
Methods inherited from interface org.sosy_lab.common.collect.PersistentMap
clear, compute, computeIfAbsent, computeIfPresent, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll
-
Methods inherited from interface org.sosy_lab.common.collect.PersistentSortedMap
headMap, keySet, pollFirstEntry, pollLastEntry, subMap, tailMap
-
-
-
-
Method Detail
-
of
public static <K extends Comparable<? super K>,V> PersistentSortedMap<K,V> of()
-
copyOf
public static <K extends Comparable<? super K>,V> PersistentSortedMap<K,V> copyOf(Map<K,V> map)
-
toPathCopyingPersistentTreeMap
public static <T,K extends Comparable<? super K>,V> Collector<T,?,PersistentSortedMap<K,V>> toPathCopyingPersistentTreeMap(Function<? super T,? extends K> keyFunction, Function<? super T,? extends V> valueFunction)
Return aCollector
that accumulates elements into aPathCopyingPersistentTreeMap
. Keys and values are the result of the respective functions. If duplicate keys appear, the collector throws anIllegalArgumentException
.
-
toPathCopyingPersistentTreeMap
public static <T,K extends Comparable<? super K>,V> Collector<T,?,PersistentSortedMap<K,V>> toPathCopyingPersistentTreeMap(Function<? super T,? extends K> keyFunction, Function<? super T,? extends V> valueFunction, BinaryOperator<V> mergeFunction)
Return aCollector
that accumulates elements into aPathCopyingPersistentTreeMap
. Keys and values are the result of the respective functions. Duplicate keys are resolved using the given merge function.
-
putAndCopy
public PersistentSortedMap<K,V> putAndCopy(K key, V value)
Description copied from interface:PersistentMap
Replacement for {PersistentMap.put(Object, Object)
that returns a fresh instance.- Specified by:
putAndCopy
in interfacePersistentMap<K extends Comparable<? super K>,V>
- Specified by:
putAndCopy
in interfacePersistentSortedMap<K extends Comparable<? super K>,V>
-
removeAndCopy
public PersistentSortedMap<K,V> removeAndCopy(Object key)
Description copied from interface:PersistentMap
Replacement for {PersistentMap.remove(Object)
that returns a fresh instance.- Specified by:
removeAndCopy
in interfacePersistentMap<K extends Comparable<? super K>,V>
- Specified by:
removeAndCopy
in interfacePersistentSortedMap<K extends Comparable<? super K>,V>
-
equals
public boolean equals(@Nullable Object pObj)
-
hashCode
public int hashCode()
-
empty
public PersistentSortedMap<K,V> empty()
Description copied from interface:PersistentMap
Replacement for {PersistentMap.clear()
that returns an empty instance.- Specified by:
empty
in interfacePersistentMap<K extends Comparable<? super K>,V>
- Specified by:
empty
in interfacePersistentSortedMap<K extends Comparable<? super K>,V>
-
containsKey
public boolean containsKey(Object pObj)
- Specified by:
containsKey
in interfaceMap<K extends Comparable<? super K>,V>
-
getOrDefault
public V getOrDefault(Object pKey, V pDefaultValue)
- Specified by:
getOrDefault
in interfaceMap<K extends Comparable<? super K>,V>
-
isEmpty
public boolean isEmpty()
-
firstEntry
public @Nullable Map.Entry<K,V> firstEntry()
- Specified by:
firstEntry
in interfaceNavigableMap<K extends Comparable<? super K>,V>
-
lastEntry
public @Nullable Map.Entry<K,V> lastEntry()
- Specified by:
lastEntry
in interfaceNavigableMap<K extends Comparable<? super K>,V>
-
ceilingEntry
public @Nullable Map.Entry<K,V> ceilingEntry(K pKey)
- Specified by:
ceilingEntry
in interfaceNavigableMap<K extends Comparable<? super K>,V>
-
floorEntry
public @Nullable Map.Entry<K,V> floorEntry(K pKey)
- Specified by:
floorEntry
in interfaceNavigableMap<K extends Comparable<? super K>,V>
-
higherEntry
public @Nullable Map.Entry<K,V> higherEntry(K pKey)
- Specified by:
higherEntry
in interfaceNavigableMap<K extends Comparable<? super K>,V>
-
lowerEntry
public @Nullable Map.Entry<K,V> lowerEntry(K pKey)
- Specified by:
lowerEntry
in interfaceNavigableMap<K extends Comparable<? super K>,V>
-
comparator
public @Nullable Comparator<? super K> comparator()
- Specified by:
comparator
in interfaceSortedMap<K extends Comparable<? super K>,V>
-
descendingMap
public org.sosy_lab.common.collect.OurSortedMap<K,V> descendingMap()
- Specified by:
descendingMap
in interfaceNavigableMap<K extends Comparable<? super K>,V>
- Specified by:
descendingMap
in interfacePersistentSortedMap<K extends Comparable<? super K>,V>
-
entrySet
public NavigableSet<Map.Entry<K,V>> entrySet()
- Specified by:
entrySet
in interfaceMap<K extends Comparable<? super K>,V>
- Specified by:
entrySet
in interfacePersistentSortedMap<K extends Comparable<? super K>,V>
- Specified by:
entrySet
in interfaceSortedMap<K extends Comparable<? super K>,V>
-
subMap
public org.sosy_lab.common.collect.OurSortedMap<K,V> subMap(K pFromKey, boolean pFromInclusive, K pToKey, boolean pToInclusive)
- Specified by:
subMap
in interfaceNavigableMap<K extends Comparable<? super K>,V>
- Specified by:
subMap
in interfacePersistentSortedMap<K extends Comparable<? super K>,V>
-
headMap
public org.sosy_lab.common.collect.OurSortedMap<K,V> headMap(K pToKey, boolean pToInclusive)
- Specified by:
headMap
in interfaceNavigableMap<K extends Comparable<? super K>,V>
- Specified by:
headMap
in interfacePersistentSortedMap<K extends Comparable<? super K>,V>
-
tailMap
public org.sosy_lab.common.collect.OurSortedMap<K,V> tailMap(K pFromKey, boolean pFromInclusive)
- Specified by:
tailMap
in interfaceNavigableMap<K extends Comparable<? super K>,V>
- Specified by:
tailMap
in interfacePersistentSortedMap<K extends Comparable<? super K>,V>
-
ceilingKey
public final @Nullable K ceilingKey(K pKey)
- Specified by:
ceilingKey
in interfaceNavigableMap<K,V>
-
floorKey
public final @Nullable K floorKey(K pKey)
- Specified by:
floorKey
in interfaceNavigableMap<K,V>
-
higherKey
public final @Nullable K higherKey(K pKey)
- Specified by:
higherKey
in interfaceNavigableMap<K,V>
-
lowerKey
public final @Nullable K lowerKey(K pKey)
- Specified by:
lowerKey
in interfaceNavigableMap<K,V>
-
headMap
public final org.sosy_lab.common.collect.OurSortedMap<K,V> headMap(K pToKey)
-
tailMap
public final org.sosy_lab.common.collect.OurSortedMap<K,V> tailMap(K pFromKey)
-
subMap
public final org.sosy_lab.common.collect.OurSortedMap<K,V> subMap(K pFromKey, K pToKey)
-
keySet
public final NavigableSet<K> keySet()
-
navigableKeySet
public NavigableSet<K> navigableKeySet()
- Specified by:
navigableKeySet
in interfaceNavigableMap<K,V>
-
descendingKeySet
public final NavigableSet<K> descendingKeySet()
- Specified by:
descendingKeySet
in interfaceNavigableMap<K,V>
-
pollFirstEntry
@Deprecated public final Map.Entry<K,V> pollFirstEntry()
Deprecated.- Specified by:
pollFirstEntry
in interfaceNavigableMap<K,V>
-
pollLastEntry
@Deprecated public final Map.Entry<K,V> pollLastEntry()
Deprecated.- Specified by:
pollLastEntry
in interfaceNavigableMap<K,V>
-
clear
@Deprecated public final void clear()
Deprecated.
-
put
@Deprecated public final V put(K key, V value)
Deprecated.
-
putIfAbsent
@Deprecated public final V putIfAbsent(K pKey, V pValue)
Deprecated.- Specified by:
putIfAbsent
in interfaceMap<K,V>
-
putAll
@Deprecated public final void putAll(Map<? extends K,? extends V> pM)
Deprecated.
-
remove
@Deprecated public final V remove(Object pKey)
Deprecated.
-
remove
@Deprecated public final boolean remove(Object pKey, Object pValue)
Deprecated.
-
replace
@Deprecated public final V replace(K pKey, V pValue)
Deprecated.
-
replace
@Deprecated public final boolean replace(K pKey, V pOldValue, V pNewValue)
Deprecated.
-
compute
@Deprecated public final V compute(K pKey, BiFunction<? super K,? super V,? extends V> pRemappingFunction)
Deprecated.
-
computeIfAbsent
@Deprecated public final V computeIfAbsent(K pKey, Function<? super K,? extends V> pMappingFunction)
Deprecated.- Specified by:
computeIfAbsent
in interfaceMap<K,V>
-
computeIfPresent
@Deprecated public final V computeIfPresent(K pKey, BiFunction<? super K,? super V,? extends V> pRemappingFunction)
Deprecated.- Specified by:
computeIfPresent
in interfaceMap<K,V>
-
merge
@Deprecated public final V merge(K pKey, V pValue, BiFunction<? super V,? super V,? extends V> pRemappingFunction)
Deprecated.
-
replaceAll
@Deprecated public final void replaceAll(BiFunction<? super K,? super V,? extends V> pFunction)
Deprecated.- Specified by:
replaceAll
in interfaceMap<K,V>
-
containsValue
public boolean containsValue(Object pValue)
- Specified by:
containsValue
in interfaceMap<K,V>
-
-