com.bluegosling.collections.maps

Class AbstractRandomAccessNavigableMap<K,V>

java.lang.Object

com.bluegosling.collections.AbstractNavigableMap<K,V>

com.bluegosling.collections.maps.AbstractRandomAccessNavigableMap<K,V>

Type Parameters:

K - the type of keys in the map

V - the type of values in the map

All Implemented Interfaces:

RandomAccessNavigableMap<K,V>, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>

Direct Known Subclasses:

AbstractRandomAccessNavigableMap.RandomAccessSubMap, AbstractRandomAccessNavigableMap.SubMapByIndices

public abstract class AbstractRandomAccessNavigableMap<K,V>
extends AbstractNavigableMap<K,V>
implements RandomAccessNavigableMap<K,V>

An abstract base class for RandomAccessNavigableMap implementations. Sub-classes must implement most of the methods needed to implement a normal AbstractNavigableMap. The main differences follow:

• Methods firstEntry() and lastEntry() do not need to be implemented. This abstract map implements them in terms of random access, e.g. getEntry(0)
• New random access methods, RandomAccessNavigableMap.getEntry(int) and RandomAccessNavigableMap.removeEntry(int), must be implemented.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	AbstractRandomAccessNavigableMap.BaseListIteratorImpl<T>
protected class	AbstractRandomAccessNavigableMap.EntryListIteratorImpl
protected class	AbstractRandomAccessNavigableMap.KeyListIteratorImpl
protected class	AbstractRandomAccessNavigableMap.RandomAccessEntrySet
protected class	AbstractRandomAccessNavigableMap.RandomAccessKeySet
protected class	AbstractRandomAccessNavigableMap.RandomAccessSubMap A sub-map view, with key value bounds, not indices.
protected class	AbstractRandomAccessNavigableMap.SubMapByIndices A sub-map view, defined by a range of indices.
protected class	AbstractRandomAccessNavigableMap.SubMapByIndicesAndByValueBounds A sub-map view for a AbstractRandomAccessNavigableMap.SubMapByIndices.
protected static class	AbstractRandomAccessNavigableMap.SubMapByIndicesIterator<K,V> Implements an iterator over a sub-map (by indices) of elements for the various set views of this map.
protected class	AbstractRandomAccessNavigableMap.ValueList
protected class	AbstractRandomAccessNavigableMap.ValueListIteratorImpl

Nested classes/interfaces inherited from class com.bluegosling.collections.AbstractNavigableMap

AbstractNavigableMap.BaseIteratorImpl<T>, AbstractNavigableMap.DescendingKeyIteratorImpl, AbstractNavigableMap.EntryIteratorImpl, AbstractNavigableMap.EntrySet, AbstractNavigableMap.KeyIteratorImpl, AbstractNavigableMap.KeySet, AbstractNavigableMap.SubMap, AbstractNavigableMap.ValueCollection, AbstractNavigableMap.ValueIteratorImpl

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

Map.Entry<K,V>

Field Summary

Fields inherited from class com.bluegosling.collections.AbstractNavigableMap

comparator, modCount

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	AbstractRandomAccessNavigableMap() Constructs a new, empty map that orders keys according to their natural ordering.
protected	AbstractRandomAccessNavigableMap(Comparator<? super K> comparator) Constructs a new, empty map that orders keys using the specified comparator.

Method Summary

Modifier and Type	Method and Description
RandomAccessNavigableSet<K>	descendingKeySet()
RandomAccessNavigableMap<K,V>	descendingMap()
RandomAccessSet<Map.Entry<K,V>>	entrySet()
Map.Entry<K,V>	firstEntry()
RandomAccessNavigableMap<K,V>	headMap(K toKey)
RandomAccessNavigableMap<K,V>	headMap(K toKey, boolean inclusive)
int	indexOfKey(Object key) Determines the random access index at which the given key is found in the map.
RandomAccessSet<K>	keySet()
Map.Entry<K,V>	lastEntry()
ListIterator<Map.Entry<K,V>>	listIterator() Returns a list iterator that can iterator backwards and forwards over the set of mappings.
ListIterator<Map.Entry<K,V>>	listIterator(int index) Returns a list iterator that can iterator backwards and forwards over the set of mappings, starting at a given index into the set.
RandomAccessNavigableSet<K>	navigableKeySet()
protected void	rangeCheck(int index) Checks that the specified index is greater than or equal to zero and less than this map's Map.size().
protected void	rangeCheckWide(int index) Checks that the specified index is greater than or equal to zero and less than or equal to this map's Map.size().
RandomAccessNavigableMap<K,V>	subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
RandomAccessNavigableMap<K,V>	subMap(K fromKey, K toKey)
RandomAccessNavigableMap<K,V>	subMapByIndices(int startIndex, int endIndex) Returns a view of a region of this map.
RandomAccessNavigableMap<K,V>	tailMap(K fromKey)
RandomAccessNavigableMap<K,V>	tailMap(K fromKey, boolean inclusive)
List<V>	values()

Methods inherited from class com.bluegosling.collections.AbstractNavigableMap

ceilingEntry, ceilingKey, clear, comparator, containsKey, containsValue, equals, firstKey, floorEntry, floorKey, get, getEntry, getModCount, hashCode, higherKey, isEmpty, lastKey, lowerKey, pollFirstEntry, pollLastEntry, putAll, remove, removeEntry, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.bluegosling.collections.maps.RandomAccessNavigableMap

getEntry, removeEntry

Methods inherited from interface java.util.NavigableMap

ceilingEntry, ceilingKey, floorEntry, floorKey, higherEntry, higherKey, lowerEntry, lowerKey, pollFirstEntry, pollLastEntry

Methods inherited from interface java.util.SortedMap

comparator, firstKey, lastKey

Methods inherited from interface java.util.Map

clear, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, equals, forEach, get, getOrDefault, hashCode, isEmpty, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size

Constructor Detail

AbstractRandomAccessNavigableMap

protected AbstractRandomAccessNavigableMap()

Constructs a new, empty map that orders keys according to their natural ordering.

AbstractRandomAccessNavigableMap

protected AbstractRandomAccessNavigableMap(Comparator<? super K> comparator)

Constructs a new, empty map that orders keys using the specified comparator.

Parameters:

comparator - determines ordering of keys in the map

Method Detail

rangeCheck

protected void rangeCheck(int index)

Checks that the specified index is greater than or equal to zero and less than this map's Map.size().

Parameters:

index - an index to check

rangeCheckWide

protected void rangeCheckWide(int index)

Checks that the specified index is greater than or equal to zero and less than or equal to this map's Map.size(). This is for certain operations where an index equal to the size (after the last valid index in the map) is allowed.

Parameters:

index - an index to check

indexOfKey

public int indexOfKey(Object key)

Description copied from interface: RandomAccessNavigableMap

Determines the random access index at which the given key is found in the map.

Specified by:

indexOfKey in interface RandomAccessNavigableMap<K,V>

Parameters:

key - a key

Returns:

the index at which the given key is found or -1 if the key is not present

listIterator

public ListIterator<Map.Entry<K,V>> listIterator()

Description copied from interface: RandomAccessNavigableMap

Returns a list iterator that can iterator backwards and forwards over the set of mappings. Being a list iterator, it also provides random access indices for the mappings.

Specified by:

listIterator in interface RandomAccessNavigableMap<K,V>

Returns:

a list iterator over the mappings in this map

listIterator

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

Description copied from interface: RandomAccessNavigableMap

Returns a list iterator that can iterator backwards and forwards over the set of mappings, starting at a given index into the set. Indices are zero-based, so an index of zero starts with the first mapping, an index of one starts with the second, and so on.

Specified by:

listIterator in interface RandomAccessNavigableMap<K,V>

Parameters:

index - a random access index

Returns:

a list iterator over the mappings in this map, starting from the given index

firstEntry

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

Specified by:

firstEntry in interface NavigableMap<K,V>

lastEntry

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

Specified by:

lastEntry in interface NavigableMap<K,V>

subMapByIndices

public RandomAccessNavigableMap<K,V> subMapByIndices(int startIndex,
                                                     int endIndex)

Description copied from interface: RandomAccessNavigableMap

Returns a view of a region of this map. Unlike RandomAccessNavigableMap.subMap(K, boolean, K, boolean), this bounds of this region are defined by random access indices instead of key values.

Specified by:

subMapByIndices in interface RandomAccessNavigableMap<K,V>

Parameters:

startIndex - the starting index, inclusive, of the region

endIndex - the ending index, exclusive, of the region

Returns:

a view of a region of this map between the given indices

keySet

public RandomAccessSet<K> keySet()

Description copied from class: AbstractNavigableMap

This default implementation delegates to AbstractNavigableMap.navigableKeySet().

Specified by:

keySet in interface RandomAccessNavigableMap<K,V>

Specified by:

keySet in interface Map<K,V>

Specified by:

keySet in interface SortedMap<K,V>

Overrides:

keySet in class AbstractNavigableMap<K,V>

values

public List<V> values()

Description copied from class: AbstractNavigableMap

This default implementation returns a AbstractNavigableMap.ValueCollection.

Specified by:

values in interface RandomAccessNavigableMap<K,V>

Specified by:

values in interface Map<K,V>

Specified by:

values in interface SortedMap<K,V>

Overrides:

values in class AbstractNavigableMap<K,V>

entrySet

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

Description copied from class: AbstractNavigableMap

This default implementation returns an AbstractNavigableMap.EntrySet.

Specified by:

entrySet in interface RandomAccessNavigableMap<K,V>

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in interface SortedMap<K,V>

Overrides:

entrySet in class AbstractNavigableMap<K,V>

descendingMap

public RandomAccessNavigableMap<K,V> descendingMap()

Description copied from class: AbstractNavigableMap

This default implementation should suffice for any NavigableMap since the map provides all necessary operations to trivially reverse the order. It simply uses inverse operations to return the descending view of this map. For example, the inverse of NavigableMap.firstEntry() is NavigableMap.lastEntry(), the inverse of the key set's iterator() is its descendingIterator(), etc.

Specified by:

descendingMap in interface RandomAccessNavigableMap<K,V>

Specified by:

descendingMap in interface NavigableMap<K,V>

Overrides:

descendingMap in class AbstractNavigableMap<K,V>

navigableKeySet

public RandomAccessNavigableSet<K> navigableKeySet()

Description copied from class: AbstractNavigableMap

This default implementation returns a AbstractNavigableMap.KeySet.

Specified by:

navigableKeySet in interface RandomAccessNavigableMap<K,V>

Specified by:

navigableKeySet in interface NavigableMap<K,V>

Overrides:

navigableKeySet in class AbstractNavigableMap<K,V>

descendingKeySet

public RandomAccessNavigableSet<K> descendingKeySet()

Description copied from class: AbstractNavigableMap

This default implementation returns AbstractNavigableMap.navigableKeySet().descendingSet().

Specified by:

descendingKeySet in interface RandomAccessNavigableMap<K,V>

Specified by:

descendingKeySet in interface NavigableMap<K,V>

Overrides:

descendingKeySet in class AbstractNavigableMap<K,V>

subMap

public RandomAccessNavigableMap<K,V> subMap(K fromKey,
                                            boolean fromInclusive,
                                            K toKey,
                                            boolean toInclusive)

Description copied from class: AbstractNavigableMap

This default implementation returns a AbstractNavigableMap.SubMap with the specified bounds.

Specified by:

subMap in interface RandomAccessNavigableMap<K,V>

Specified by:

subMap in interface NavigableMap<K,V>

Overrides:

subMap in class AbstractNavigableMap<K,V>

headMap

public RandomAccessNavigableMap<K,V> headMap(K toKey,
                                             boolean inclusive)

Description copied from class: AbstractNavigableMap

This default implementation returns a AbstractNavigableMap.SubMap with the specified upper bound and no lower bound.

Specified by:

headMap in interface RandomAccessNavigableMap<K,V>

Specified by:

headMap in interface NavigableMap<K,V>

Overrides:

headMap in class AbstractNavigableMap<K,V>

tailMap

public RandomAccessNavigableMap<K,V> tailMap(K fromKey,
                                             boolean inclusive)

Description copied from class: AbstractNavigableMap

This default implementation returns a AbstractNavigableMap.SubMap with the specified lower bound and no upper bound.

Specified by:

tailMap in interface RandomAccessNavigableMap<K,V>

Specified by:

tailMap in interface NavigableMap<K,V>

Overrides:

tailMap in class AbstractNavigableMap<K,V>

subMap

public RandomAccessNavigableMap<K,V> subMap(K fromKey,
                                            K toKey)

Description copied from class: AbstractNavigableMap

This default implementation simply calls subMap(fromKey, true, toKey, false). The return type is also overridden to provide access to the full NavigableMap interface of the returned view.

Specified by:

subMap in interface RandomAccessNavigableMap<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 RandomAccessNavigableMap<K,V> headMap(K toKey)

Description copied from class: AbstractNavigableMap

This default implementation simply calls headMap(toKey, false). The return type is also overridden to provide access to the full NavigableMap interface of the returned view.

Specified by:

headMap in interface RandomAccessNavigableMap<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 RandomAccessNavigableMap<K,V> tailMap(K fromKey)

Description copied from class: AbstractNavigableMap

This default implementation simply calls tailMap(fromKey, true). The return type is also overridden to provide access to the full NavigableMap interface of the returned view.

Specified by:

tailMap in interface RandomAccessNavigableMap<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>