org.lenskit.util.keys

## Class SortedKeyIndex

• All Implemented Interfaces:
Serializable, KeyIndex

@Immutable
public abstract class SortedKeyIndex
extends Object
implements KeyIndex, Serializable

Implement an index of long keys, sorted by key. Keys can be mapped back to integer indexes (contiguous and 0-based) and vice versa.

Since:
3.0
Serialized Form
• ### Method Summary

All Methods
Modifier and Type Method and Description
boolean containsKey(long key)
Query whether this set contains the specified key in its domain.
static SortedKeyIndex create(long... keys)
Create a key set with some keys.
static SortedKeyIndex empty()
Create an empty key domain.
int findLowerBound(long key)
Get the lower bound, the first index whose key is greater than or equal to the specified key.
int findUpperBound(long key)
Get the upper bound, the first index whose key is greater than the specified key.
static SortedKeyIndex fromCollection(Collection<Long> keys)
Create a key set from a collection of keys.
SortedKeyIndex frozenCopy()
Get a frozen copy of this key index.
int getIndex(long key)
Get the index of a key.
abstract long getKey(int idx)
Get the key at an index.
LongList getKeyList()
Get the key set’s list of keys (domain) as a list.
int getLowerBound()
Get the lower bound of this index.
int getUpperBound()
Get the upper bound of this index.
LongBidirectionalIterator keyIterator()
Create an iterator over keys.
LongBidirectionalIterator keyIterator(int initial)
Create an iterator over keys.
LongSortedArraySet keySet()
Get a view of the index as a set.
int size()
Get the domain size of this set.
abstract SortedKeyIndex subIndex(int lb, int ub)
Create a view of a subset of this index.
abstract int tryGetIndex(long key)
Get the index for a key.
static SortedKeyIndex wrap(long[] keys, int size)
Wrap a key array (with a specified size) into a key set.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Method Detail

• #### wrap

public static SortedKeyIndex wrap(long[] keys,
int size)

Wrap a key array (with a specified size) into a key set.

Parameters:
keys - The key array. This array must be sorted, and must not contain duplicates. For efficiency, this condition is not checked unless assertions are enabled. Since this method is only intended to be used when implementing test cases or other data structures, callers of this method should ensure sortedness and throw the appropriate exception.
size - The length of the array to actually use.
Returns:
The key set.
• #### fromCollection

public static SortedKeyIndex fromCollection(Collection<Long> keys)

Create a key set from a collection of keys.

Parameters:
keys - The key collection.
Returns:
The key set.
• #### create

public static SortedKeyIndex create(long... keys)

Create a key set with some keys. All keys are initially active.

Parameters:
keys - The keys.
Returns:
The key set.
• #### empty

public static SortedKeyIndex empty()

Create an empty key domain.

Returns:
An empty key domain.
• #### size

public int size()

Get the domain size of this set.

Specified by:
size in interface KeyIndex
Returns:
The domain size.
• #### getLowerBound

public int getLowerBound()

Get the lower bound of this index.

Specified by:
getLowerBound in interface KeyIndex
Returns:
The index’s lower bound.
• #### getUpperBound

public int getUpperBound()

Get the upper bound of this index.

Specified by:
getUpperBound in interface KeyIndex
Returns:
The index’s upper bound.
• #### subIndex

public abstract SortedKeyIndex subIndex(int lb,
int ub)

Create a view of a subset of this index.

Parameters:
lb - The index of the lower bound of the subset (inclusive).
ub - The index of the upper bound of the subset (exclusive);
• #### tryGetIndex

public abstract int tryGetIndex(long key)

Get the index for a key.

Specified by:
tryGetIndex in interface KeyIndex
Parameters:
key - The key.
Returns:
The index, or a negative value if the key is not in the domain. Such a negative value is the insertion point, as defined by Arrays.binarySearch(long[], int, int, long).
• #### getIndex

public int getIndex(long key)
Description copied from interface: KeyIndex

Get the index of a key.

Specified by:
getIndex in interface KeyIndex
Parameters:
key - The key to query.
Returns:
The key’s index.
• #### findUpperBound

public int findUpperBound(long key)

Get the upper bound, the first index whose key is greater than the specified key.

Parameters:
key - The key to search for.
Returns:
The index of the first key greater than the specified key, or getUpperBound() if the key is the last key in the domain.
• #### findLowerBound

public int findLowerBound(long key)

Get the lower bound, the first index whose key is greater than or equal to the specified key. This method is paired with findUpperBound(long); the interval [findLowerBound(k),findUpperBound(k)) contains the index of k, if the key is in the domain, and is empty if the key is not in the domain.

Parameters:
key - The key to search for.
Returns:
The index of the first key greater than or equal to key; will be getLowerBound() if key is less than or equal to the lowest key.
• #### containsKey

public boolean containsKey(long key)

Query whether this set contains the specified key in its domain.

Specified by:
containsKey in interface KeyIndex
Parameters:
key - The key.
Returns:
true if the key is in the domain.
• #### getKey

public abstract long getKey(int idx)

Get the key at an index.

Specified by:
getKey in interface KeyIndex
Parameters:
idx - The index to query.
Returns:
The key at the specified index.
Throws:
IndexOutOfBoundsException - if idx is outside the range [lowerBound, upperBound)].
• #### keyIterator

public LongBidirectionalIterator keyIterator()

Create an iterator over keys.

Returns:
An iterator over the keys corresponding to the iterator’s indexes.
• #### keyIterator

public LongBidirectionalIterator keyIterator(int initial)

Create an iterator over keys.

Parameters:
initial - The initial index (the first thing to be returned by Iterator.next()).
Returns:
An iterator over the keys corresponding to the iterator’s indexes.
• #### keySet

public LongSortedArraySet keySet()

Get a view of the index as a set.

Returns:
The set of keys.
• #### getKeyList

public LongList getKeyList()

Get the key set’s list of keys (domain) as a list.

Specified by:
getKeyList in interface KeyIndex
Returns:
A list of all keys in the key domain.
• #### frozenCopy

public SortedKeyIndex frozenCopy()
Description copied from interface: KeyIndex

Get a frozen copy of this key index. If the key index is mutable, then this method will return an immutable copy of it. If the key index is already immutable, it may just return itself without copying.

Specified by:
frozenCopy in interface KeyIndex
Returns:
An immutable key index with the same contents as this key index.