Class RefList<T extends Ref>
- Type Parameters:
T
- the type of reference being stored in the collection.
- Direct Known Subclasses:
RefDirectory.PackedRefList
RefDatabase
.
This list is a hybrid of a Map<String,Ref> and of a List<Ref>. It tracks reference instances by name by keeping them sorted and performing binary search to locate an entry. Lookup time is O(log N), but addition and removal is O(N + log N) due to the list expansion or contraction costs.
This list type is copy-on-write. Mutation methods return a new copy of the
list, leaving this
unmodified. As a result we cannot easily implement
the List
interface contract.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
RefList.Builder<T extends Ref>
Builder to facilitate fast construction of an immutable RefList. -
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionAdd an item at a specific index.asList()
Castthis
as an immutable, standardList
.final boolean
Determine if a reference is present.final RefList.Builder
<T> copy
(int n) Obtain a builder initialized with the firstn
elements.Create an empty unmodifiable reference list.final int
Locate an entry by name.final T
get
(int idx) Get the reference at a particular index.final T
Get a reference object by name.final boolean
isEmpty()
Get if this list is empty.iterator()
Store a reference, adding or replacing as necessary.remove
(int idx) Remove an item at a specific index.Obtain a new copy of the list after changing one element.final int
size()
Get number of items in this list.toRefList
(BinaryOperator<T> mergeFunction) toString()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Field Details
-
EMPTY
-
list
-
cnt
final int cnt
-
-
Constructor Details
-
RefList
RefList(Ref[] list, int cnt) -
RefList
Initialize this list to use the same backing array as another list.- Parameters:
src
- the source list.
-
-
Method Details
-
emptyList
Create an empty unmodifiable reference list.- Returns:
- an empty unmodifiable reference list.
-
iterator
-
asList
Castthis
as an immutable, standardList
.- Returns:
this
as an immutable, standardList
.
-
size
public final int size()Get number of items in this list.- Returns:
- number of items in this list.
-
isEmpty
public final boolean isEmpty()Get if this list is empty.- Returns:
- true if the size of this list is 0.
-
find
Locate an entry by name.- Parameters:
name
- the name of the reference to find.- Returns:
- the index the reference is at. If the entry is not present
returns a negative value. The insertion position for the given
name can be computed from
-(index + 1)
.
-
contains
Determine if a reference is present.- Parameters:
name
- name of the reference to find.- Returns:
- true if the reference is present; false if it is not.
-
get
Get a reference object by name.- Parameters:
name
- the name of the reference.- Returns:
- the reference object; null if it does not exist in this list.
-
get
Get the reference at a particular index.- Parameters:
idx
- the index to obtain. Must be0 <= idx < size()
.- Returns:
- the reference value, never null.
-
copy
Obtain a builder initialized with the firstn
elements.Copies the first
n
elements from this list into a new builder, which can be used by the caller to add additional elements.- Parameters:
n
- the number of elements to copy.- Returns:
- a new builder with the first
n
elements already added.
-
set
Obtain a new copy of the list after changing one element.This list instance is not affected by the replacement. Because this method copies the entire list, it runs in O(N) time.
- Parameters:
idx
- index of the element to change.ref
- the new value, must not be null.- Returns:
- copy of this list, after replacing
idx
withref
.
-
add
Add an item at a specific index.This list instance is not affected by the addition. Because this method copies the entire list, it runs in O(N) time.
- Parameters:
idx
- position to add the item at. If negative the method assumes it was a direct return value fromfind(String)
and will adjust it to the correct position.ref
- the new reference to insert.- Returns:
- copy of this list, after making space for and adding
ref
.
-
remove
Remove an item at a specific index.This list instance is not affected by the addition. Because this method copies the entire list, it runs in O(N) time.
- Parameters:
idx
- position to remove the item from.- Returns:
- copy of this list, after making removing the item at
idx
.
-
put
Store a reference, adding or replacing as necessary.This list instance is not affected by the store. The correct position is determined, and the item is added if missing, or replaced if existing. Because this method copies the entire list, it runs in O(N + log N) time.
- Parameters:
ref
- the reference to store.- Returns:
- copy of this list, after performing the addition or replacement.
-
toString
-
toRefList
public static <T extends Ref> Collector<T,?, toRefListRefList<T>> (@Nullable BinaryOperator<T> mergeFunction)
-