Package io.permazen.util

Class ImmutableNavigableMap<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

io.permazen.util.AbstractNavigableMap<K,V>

io.permazen.util.ImmutableNavigableMap<K,V>

Type Parameters:

K - key type

V - value type

All Implemented Interfaces:

ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>

public class ImmutableNavigableMap<K,V>
extends AbstractNavigableMap<K,V>
implements ConcurrentNavigableMap<K,V>

An immutable NavigableMap implementation optimized for read efficiency.

Because the keys and values are stored in arrays, it's also possible to get the key and/or value by index; see getKey(), getValue(), and getEntry().

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

AbstractMap.SimpleEntry<K extends Object,V extends Object>, AbstractMap.SimpleImmutableEntry<K extends Object,V extends Object>

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K extends Object,V extends Object>

Field Summary

Fields inherited from class io.permazen.util.AbstractNavigableMap

bounds

Constructor Summary

Constructors

Constructor	Description
ImmutableNavigableMap(NavigableMap<K,V> source)	Constructor.
ImmutableNavigableMap(NavigableMap<K,V> source, Comparator<? super K> comparator)	Constructor.
ImmutableNavigableMap(K[] keys, V[] vals, int minIndex, int maxIndex, Comparator<? super K> comparator)	Primary constructor.
ImmutableNavigableMap(K[] keys, V[] vals, Comparator<? super K> comparator)	Convenience constructor.

Method Summary

Modifier and Type	Method	Description
int	binarySearch(K key)	Search for the given element in the underlying array.
Map.Entry<K,V>	ceilingEntry(K minKey)
K	ceilingKey(K minKey)
Comparator<? super K>	comparator()
boolean	containsKey(Object obj)
boolean	containsValue(Object obj)
protected ImmutableNavigableMap<K,V>	createSubMap(boolean reverse, Bounds<K> newBounds)	Create a (possibly reversed) view of this instance with (possibly) tighter lower and/or upper bounds.
ImmutableNavigableMap<K,V>	descendingMap()
ImmutableNavigableSet<Map.Entry<K,V>>	entrySet()
Map.Entry<K,V>	firstEntry()
K	firstKey()
Map.Entry<K,V>	floorEntry(K maxKey)
K	floorKey(K maxKey)
V	get(Object obj)
Map.Entry<K,V>	getEntry(int index)	Get the entry at the specified index.
K	getKey(int index)	Get the key at the specified index.
V	getValue(int index)	Get the value at the specified index.
ImmutableNavigableMap<K,V>	headMap(K maxKey)
ImmutableNavigableMap<K,V>	headMap(K newMaxKey, boolean inclusive)
Map.Entry<K,V>	higherEntry(K minKey)
K	higherKey(K minKey)
boolean	isEmpty()
Map.Entry<K,V>	lastEntry()
K	lastKey()
Map.Entry<K,V>	lowerEntry(K maxKey)
K	lowerKey(K maxKey)
NavigableSet<K>	navigableKeySet()
Map.Entry<K,V>	pollFirstEntry()
Map.Entry<K,V>	pollLastEntry()
V	putIfAbsent(K key, V value)
boolean	remove(Object key, Object value)
V	replace(K key, V value)
boolean	replace(K key, V oldValue, V newValue)
int	size()
ImmutableNavigableMap<K,V>	subMap(K newMinKey, boolean minInclusive, K newMaxKey, boolean maxInclusive)
ImmutableNavigableMap<K,V>	subMap(K minKey, K maxKey)
ImmutableNavigableMap<K,V>	tailMap(K minKey)
ImmutableNavigableMap<K,V>	tailMap(K newMinKey, boolean inclusive)
List<V>	values()

Methods inherited from class io.permazen.util.AbstractNavigableMap

descendingKeySet, getBounds, getComparator, isWithinLowerBound, isWithinUpperBound, keySet, remove, searchAbove, searchBelow

Methods inherited from class java.util.AbstractMap

clear, clone, equals, hashCode, put, putAll, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.concurrent.ConcurrentMap

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll

Methods inherited from interface java.util.concurrent.ConcurrentNavigableMap

descendingKeySet, keySet

Methods inherited from interface java.util.Map

clear, equals, hashCode, put, putAll, remove

Constructor Details

ImmutableNavigableMap

public ImmutableNavigableMap(NavigableMap<K,V> source)

Constructor.

Parameters:

source - data source

Throws:

IllegalArgumentException - if source is null

ImmutableNavigableMap

public ImmutableNavigableMap(NavigableMap<K,V> source,
 Comparator<? super K> comparator)

Constructor.

Parameters:

source - data source

comparator - key comparator, or null for natural ordering

Throws:

IllegalArgumentException - if source is null

ImmutableNavigableMap

public ImmutableNavigableMap(K[] keys,
 V[] vals,
 Comparator<? super K> comparator)

Convenience constructor.

Equivalent to: ImmutableNavigableMap(keys, vals, 0, Math.min(keys.length, vals.length), comparator).

Parameters:

keys - sorted key array; this array is not copied and must be already sorted

vals - value array corresponding to keys; this array is not copied

comparator - key comparator, or null for natural ordering

Throws:

IllegalArgumentException - if keys or vals is null

IllegalArgumentException - if keys and vals have different lengths

ImmutableNavigableMap

public ImmutableNavigableMap(K[] keys,
 V[] vals,
 int minIndex,
 int maxIndex,
 Comparator<? super K> comparator)

Primary constructor.

Parameters:

keys - sorted key array; this array is not copied and must be already sorted

vals - value array corresponding to keys; this array is not copied

minIndex - minimum index into arrays (inclusive)

maxIndex - maximum index into arrays (exclusive)

comparator - key comparator, or null for natural ordering

Throws:

IllegalArgumentException - if keys or vals is null

IllegalArgumentException - if keys and vals has length less than maxIndex

IllegalArgumentException - if minIndex > maxIndex

Method Details

getKey

public K getKey(int index)

Get the key at the specified index.

Parameters:

index - index into the ordered key array

Returns:

the key at the specified index

Throws:

IndexOutOfBoundsException - if index is negative or greater than or equal to size()

getValue

public V getValue(int index)

Get the value at the specified index.

Parameters:

index - index into the ordered value array

Returns:

the value at the specified index

Throws:

IndexOutOfBoundsException - if index is negative or greater than or equal to size()

getEntry

public Map.Entry<K,V> getEntry(int index)

Get the entry at the specified index.

Parameters:

index - index into the ordered entry array

Returns:

the entry at the specified index

Throws:

IndexOutOfBoundsException - if index is negative or greater than or equal to size()

binarySearch

public int binarySearch(K key)

Search for the given element in the underlying array.

This method works like Arrays.binarySearch(), returning either the index of key in the underlying array given to the constructor if found, or else the one's complement of key's insertion point.

The array searched is the array given to the constructor, or if ImmutableNavigableMap(NavigableMap) was used, an array containing all of the keys in this map.

Parameters:

key - key to search for

Returns:

index of key, or -(insertion point) - 1 if not found

comparator

public Comparator<? super K> comparator()

Specified by:

comparator in interface SortedMap<K,V>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Map<K,V>

Overrides:

isEmpty in class AbstractNavigableMap<K,V>

size

public int size()

Specified by:

size in interface Map<K,V>

Overrides:

size in class AbstractMap<K,V>

containsKey

public boolean containsKey(Object obj)

Specified by:

containsKey in interface Map<K,V>

Overrides:

containsKey in class AbstractNavigableMap<K,V>

get

public V get(Object obj)

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractMap<K,V>

values

public List<V> values()

Specified by:

values in interface Map<K,V>

Specified by:

values in interface SortedMap<K,V>

Overrides:

values in class AbstractMap<K,V>

containsValue

public boolean containsValue(Object obj)

Specified by:

containsValue in interface Map<K,V>

Overrides:

containsValue in class AbstractMap<K,V>

firstKey

public K firstKey()

Specified by:

firstKey in interface SortedMap<K,V>

Overrides:

firstKey in class AbstractNavigableMap<K,V>

firstEntry

public Map.Entry<K,V> firstEntry()

Specified by:

firstEntry in interface NavigableMap<K,V>

Overrides:

firstEntry in class AbstractNavigableMap<K,V>

lastKey

public K lastKey()

Specified by:

lastKey in interface SortedMap<K,V>

Overrides:

lastKey in class AbstractNavigableMap<K,V>

lastEntry

public Map.Entry<K,V> lastEntry()

Specified by:

lastEntry in interface NavigableMap<K,V>

Overrides:

lastEntry in class AbstractNavigableMap<K,V>

lowerKey

public K lowerKey(K maxKey)

Specified by:

lowerKey in interface NavigableMap<K,V>

Overrides:

lowerKey in class AbstractNavigableMap<K,V>

lowerEntry

public Map.Entry<K,V> lowerEntry(K maxKey)

Specified by:

lowerEntry in interface NavigableMap<K,V>

Overrides:

lowerEntry in class AbstractNavigableMap<K,V>

floorKey

public K floorKey(K maxKey)

Specified by:

floorKey in interface NavigableMap<K,V>

Overrides:

floorKey in class AbstractNavigableMap<K,V>

floorEntry

public Map.Entry<K,V> floorEntry(K maxKey)

Specified by:

floorEntry in interface NavigableMap<K,V>

Overrides:

floorEntry in class AbstractNavigableMap<K,V>

higherKey

public K higherKey(K minKey)

Specified by:

higherKey in interface NavigableMap<K,V>

Overrides:

higherKey in class AbstractNavigableMap<K,V>

higherEntry

public Map.Entry<K,V> higherEntry(K minKey)

Specified by:

higherEntry in interface NavigableMap<K,V>

Overrides:

higherEntry in class AbstractNavigableMap<K,V>

ceilingKey

public K ceilingKey(K minKey)

Specified by:

ceilingKey in interface NavigableMap<K,V>

Overrides:

ceilingKey in class AbstractNavigableMap<K,V>

ceilingEntry

public Map.Entry<K,V> ceilingEntry(K minKey)

Specified by:

ceilingEntry in interface NavigableMap<K,V>

Overrides:

ceilingEntry in class AbstractNavigableMap<K,V>

pollFirstEntry

public Map.Entry<K,V> pollFirstEntry()

Specified by:

pollFirstEntry in interface NavigableMap<K,V>

Overrides:

pollFirstEntry in class AbstractNavigableMap<K,V>

pollLastEntry

public Map.Entry<K,V> pollLastEntry()

Specified by:

pollLastEntry in interface NavigableMap<K,V>

Overrides:

pollLastEntry in class AbstractNavigableMap<K,V>

navigableKeySet

public NavigableSet<K> navigableKeySet()

Specified by:

navigableKeySet in interface ConcurrentNavigableMap<K,V>

Specified by:

navigableKeySet in interface NavigableMap<K,V>

entrySet

public ImmutableNavigableSet<Map.Entry<K,V>> entrySet()

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in interface SortedMap<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

putIfAbsent

public V putIfAbsent(K key,
 V value)

Specified by:

putIfAbsent in interface ConcurrentMap<K,V>

Specified by:

putIfAbsent in interface Map<K,V>

replace

public V replace(K key,
 V value)

Specified by:

replace in interface ConcurrentMap<K,V>

Specified by:

replace in interface Map<K,V>

replace

public boolean replace(K key,
 V oldValue,
 V newValue)

Specified by:

replace in interface ConcurrentMap<K,V>

Specified by:

replace in interface Map<K,V>

remove

public boolean remove(Object key,
 Object value)

Specified by:

remove in interface ConcurrentMap<K,V>

Specified by:

remove in interface Map<K,V>

descendingMap

public ImmutableNavigableMap<K,V> descendingMap()

Specified by:

descendingMap in interface ConcurrentNavigableMap<K,V>

Specified by:

descendingMap in interface NavigableMap<K,V>

Overrides:

descendingMap in class AbstractNavigableMap<K,V>

subMap

public ImmutableNavigableMap<K,V> subMap(K minKey,
 K maxKey)

Specified by:

subMap in interface ConcurrentNavigableMap<K,V>

Specified by:

subMap in interface NavigableMap<K,V>

Specified by:

subMap in interface SortedMap<K,V>

Overrides:

subMap in class AbstractNavigableMap<K,V>

headMap

public ImmutableNavigableMap<K,V> headMap(K maxKey)

Specified by:

headMap in interface ConcurrentNavigableMap<K,V>

Specified by:

headMap in interface NavigableMap<K,V>

Specified by:

headMap in interface SortedMap<K,V>

Overrides:

headMap in class AbstractNavigableMap<K,V>

tailMap

public ImmutableNavigableMap<K,V> tailMap(K minKey)

Specified by:

tailMap in interface ConcurrentNavigableMap<K,V>

Specified by:

tailMap in interface NavigableMap<K,V>

Specified by:

tailMap in interface SortedMap<K,V>

Overrides:

tailMap in class AbstractNavigableMap<K,V>

headMap

public ImmutableNavigableMap<K,V> headMap(K newMaxKey,
 boolean inclusive)

Specified by:

headMap in interface ConcurrentNavigableMap<K,V>

Specified by:

headMap in interface NavigableMap<K,V>

Overrides:

headMap in class AbstractNavigableMap<K,V>

tailMap

public ImmutableNavigableMap<K,V> tailMap(K newMinKey,
 boolean inclusive)

Specified by:

tailMap in interface ConcurrentNavigableMap<K,V>

Specified by:

tailMap in interface NavigableMap<K,V>

Overrides:

tailMap in class AbstractNavigableMap<K,V>

subMap

public ImmutableNavigableMap<K,V> subMap(K newMinKey,
 boolean minInclusive,
 K newMaxKey,
 boolean maxInclusive)

Specified by:

subMap in interface ConcurrentNavigableMap<K,V>

Specified by:

subMap in interface NavigableMap<K,V>

Overrides:

subMap in class AbstractNavigableMap<K,V>

createSubMap

protected ImmutableNavigableMap<K,V> createSubMap(boolean reverse,
 Bounds<K> newBounds)

Description copied from class: AbstractNavigableMap

Create a (possibly reversed) view of this instance with (possibly) tighter lower and/or upper bounds. The newBounds are consistent with the new ordering (i.e., reversed relative to this instance's ordering if reverse is true) and have already been range-checked against this instance's current bounds.

Specified by:

createSubMap in class AbstractNavigableMap<K,V>

Parameters:

reverse - whether the new map's ordering should be reversed relative to this instance's ordering

newBounds - new bounds

Returns:

restricted and/or reversed view of this instance