public class IlvHashTreeList<E> extends AbstractList<E> implements Cloneable, RandomAccess
java.util.List
interface for ordered sets. It has not only fast random access to
arbitrary elements (get method), but also fast lookup
(contains and indexOf methods) and fast
destructive operations (add, remove methods).
Elements are compared by this class through equals; the
elements should also provide a good hashCode function.
Compared to the Set interface, this class allows elements
to be inserted at arbitrary positions. Whereas in HashSet,
an element's position is arbitrary; in LinkedHashSet,
an element's position depends when it was inserted; and in
TreeSet, an element's position depends how it compares
through a given Comparator.
In this class, for a set of N objects, each of the operations
get, contains, indexOf
have a worst-case time complexity of O(log N). add and
remove also have a worst-case time complexity of O(log N)
if the list contains no duplicated elements, or O((log N)^2) if the list
contains duplicated elements. In contrast, for ArrayList and
Vector, get is O(1) but the other four
functions are O(N). And in a combination of HashSet with
LinkedList, get, contains and
indexOf can be made O(1) but add,
remove are still O(N).
Internally, this class uses a balanced binary tree and a hash table to guarantee the O(log N) complexity of each elementary operation.
modCount| Constructor and Description |
|---|
IlvHashTreeList()
Creates an empty list.
|
IlvHashTreeList(Collection<? extends E> source)
Creates a list initialized with the elements of the given collection,
in the order they are returned by the collection's iterator.
|
IlvHashTreeList(E[] source)
Creates a list initialized with the elements of the given array,
in the order they are stored in the array.
|
| Modifier and Type | Method and Description |
|---|---|
void |
add(int index,
E element)
Inserts the given element at the specified position in this list.
|
int |
binarySearch(E key)
Searches the list for the specified object using the binary search
algorithm.
|
int |
binarySearch(E key,
Comparator<? super E> c)
Searches the list for the specified object using the binary search
algorithm.
|
void |
clear()
Removes all the elements from this list.
|
Object |
clone() |
boolean |
contains(Object element)
Returns
true if and only if element is in the
list. |
E |
get(int index)
Returns the element at the specified position in this list.
|
E |
getFirstElement()
Returns the first element of the list.
|
E |
getLastElement()
Returns the last element of the list.
|
int |
indexOf(Object element)
Returns the index of a given element in the list,
or -1 if the given value is not an element of this list.
|
Iterator<E> |
iterator()
Returns an iterator over the elements in this list in proper sequence.
|
int |
lastIndexOf(Object element)
Returns the index of a given element in the list,
or -1 if the given value is not an element of this list.
|
int |
limitedBinarySearch(E key,
Comparator<? super E> c,
int low,
int high)
Like binarySearch, except that it is a priori known that insertion points
are constrained:
1. either low = 0, or object > get(low-1),
2. either high = size()-1, or object < get(high+1).
|
int |
limitedBinarySearch(E key,
int low,
int high)
Like binarySearch, except that it is a priori known that insertion points
are constrained:
1. either low = 0, or object > get(low-1),
2. either high = size()-1, or object < get(high+1).
|
ListIterator<E> |
listIterator()
Returns a list iterator of the elements in this list (in proper sequence).
|
ListIterator<E> |
listIterator(int index)
Returns a list iterator of the elements in this list (in proper sequence),
starting at the specified position.
|
E |
remove(int index)
Removes the element at the specified position from this list.
|
boolean |
remove(Object element)
Removes the first occurrence of the specified element from this list.
|
E |
set(int index,
E element)
Replaces the element at the specified position in this list with the
given element.
|
int |
size()
Returns the number of elements of this list.
|
add, addAll, equals, hashCode, removeRange, subListaddAll, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toStringfinalize, getClass, notify, notifyAll, wait, wait, waitaddAll, containsAll, isEmpty, removeAll, replaceAll, retainAll, sort, spliterator, toArray, toArrayparallelStream, removeIf, streampublic IlvHashTreeList()
public IlvHashTreeList(Collection<? extends E> source)
public IlvHashTreeList(E[] source)
public E getFirstElement()
public E getLastElement()
public int size()
size in interface Collection<E>size in interface List<E>size in class AbstractCollection<E>public boolean contains(Object element)
true if and only if element is in the
list.contains in interface Collection<E>contains in interface List<E>contains in class AbstractCollection<E>public Iterator<E> iterator()
public boolean remove(Object element)
remove in interface Collection<E>remove in interface List<E>remove in class AbstractCollection<E>true if this list contained the specified element.public void clear()
clear in interface Collection<E>clear in interface List<E>clear in class AbstractList<E>public E get(int index)
public E set(int index, E element)
public void add(int index,
E element)
public E remove(int index)
public int indexOf(Object element)
public int lastIndexOf(Object element)
lastIndexOf in interface List<E>lastIndexOf in class AbstractList<E>public ListIterator<E> listIterator()
listIterator in interface List<E>listIterator in class AbstractList<E>public ListIterator<E> listIterator(int index)
listIterator in interface List<E>listIterator in class AbstractList<E>public int binarySearch(E key)
java.util.Arrays.Sort(Object[])
method) prior to making this call. If it is not sorted, the results are
undefined. If the list contains multiple elements equal to the specified
object, there is no guarantee which one will be found.key - the value to be searched for.(-(insertion point) - 1). The
insertion point is defined as the point at which the key would
be inserted into the list: the index of the first element greater
than the key, or list.size(), if all elements in the list are
less than the specified key. Note that this guarantees that the
return value will be >= 0 if and only if the key is found.Collections.binarySearch(List, Object),
Arrays.binarySearch(Object[], Object)public int binarySearch(E key, Comparator<? super E> c)
java.util.Arrays.Sort(Object[], Comparator)
method), prior to making this call. If it is not sorted, the results are
undefined. If the list contains multiple elements equal to the specified
object, there is no guarantee which one will be found.key - the value to be searched for.c - the comparator by which the list is ordered. A null
value indicates that the elements' natural ordering
should be used.(-(insertion point) - 1). The
insertion point is defined as the point at which the key would
be inserted into the list: the index of the first element greater
than the key, or list.size(), if all elements in the list are
less than the specified key. Note that this guarantees that the
return value will be >= 0 if and only if the key is found.Collections.binarySearch(List, Object, Comparator),
Arrays.binarySearch(Object[], Object, Comparator)public int limitedBinarySearch(E key, int low, int high)
public int limitedBinarySearch(E key, Comparator<? super E> c, int low, int high)
© Copyright Rogue Wave Software, Inc. 1997, 2018. All Rights Reserved.