|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.AbstractCollection<E>
java.util.AbstractList<T>
com.scottlogic.util.SortedList<T>
T
- the type of element that this sorted list will store.public class SortedList<T>
SortedList is an implementation of a List
, backed by an AVL tree.
Does not support any optional operations, with the exception of: remove(int)
,
remove(Object)
, clear
and add()
.
Performs all the main operations: contains
, add
, remove
and get
in time O(log(n)), where n is the number of elements in the list.
This implementation is not synchronised so if you need multi-threaded access then consider wrapping
it using the Collections.synchronizedList(java.util.List
method.
The iterators this list provides are fail-fast, so any structural
modification, other than through the iterator itself, cause it to throw a
ConcurrentModificationException
.
List
,
Collection
,
AbstractList
,
Serialized FormNested Class Summary | |
---|---|
protected class |
SortedList.Node
Inner class used to represent positions in the tree. |
Field Summary |
---|
Fields inherited from class java.util.AbstractList |
---|
modCount |
Constructor Summary | |
---|---|
SortedList(java.util.Comparator<? super T> comparator)
Constructs a new, empty SortedList which sorts the elements according to the given Comparator . |
Method Summary | ||
---|---|---|
protected void |
add(SortedList.Node toAdd)
Add the given Node to this SortedList . |
|
boolean |
add(T object)
Inserts the given object into this {code SortedList} at the appropriate location, so as to ensure that the elements in the list are kept in the order specified by the given Comparator . |
|
void |
clear()
Removes all elements from the list, leaving it empty. |
|
boolean |
contains(java.lang.Object obj)
Returns whether or not the given object is present in this SortedList . |
|
protected SortedList.Node |
findFirstNodeWithValue(T value)
Returns the node representing the given value in the tree, which can be null if no such node exists. |
|
protected SortedList.Node |
findNodeAtIndex(int index)
Returns the Node at the given index. |
|
T |
get(int index)
Returns the element at the given index in this SortedList . |
|
protected SortedList.Node |
getRoot()
Returns the root node of this SortedList , which is
null in the case that this list is empty. |
|
boolean |
isEmpty()
Returns whether or not the list contains any elements. |
|
java.util.Iterator<T> |
iterator()
Provides an Iterator which provides the elements of this SortedList
in the order determined by the given Comparator . |
|
T |
remove(int index)
Removes and returns the element at the given index in this SortedList . |
|
boolean |
remove(java.lang.Object value)
Removes the first element in the list with the given value, if such a node exists, otherwise does nothing. |
|
protected void |
remove(SortedList.Node toRemove)
Removes the given Node from this SortedList , re-balancing if required,
adds to modCount too. |
|
int |
size()
Returns the number of elements in this SortedList . |
|
java.lang.Object[] |
toArray()
Returns a new array containing all the elements in this SortedList . |
|
|
toArray(E[] holder)
Copies the elements in the SortedList to the given array if it is large
enough to store them, otherwise it returns a new array of the same type with the
elements in it. |
Methods inherited from class java.util.AbstractList |
---|
add, addAll, equals, hashCode, indexOf, lastIndexOf, listIterator, listIterator, removeRange, set, subList |
Methods inherited from class java.util.AbstractCollection |
---|
addAll, containsAll, removeAll, retainAll, toString |
Methods inherited from class java.lang.Object |
---|
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
Methods inherited from interface java.util.List |
---|
addAll, containsAll, removeAll, retainAll |
Constructor Detail |
---|
public SortedList(java.util.Comparator<? super T> comparator)
Comparator
.
comparator
- the Comparator
to sort the elements by.Method Detail |
---|
public boolean add(T object)
Comparator
.
This method only allows non-null
values to be added, if the given
object is null
, the list remains unaltered and false returned.
add
in interface java.util.Collection<T>
add
in interface java.util.List<T>
add
in class java.util.AbstractList<T>
object
- the object to add.
protected void add(SortedList.Node toAdd)
SortedList
.
This method can be overridden by a subclass in order to change the definition of the Node
s
that this List will store.
This implementation uses the Node#compareTo(Node)
method in order to ascertain where the
given Node
should be stored. It also increments the modCount for this list.
toAdd
- the Node
to add.public java.util.Iterator<T> iterator()
Iterator
which provides the elements of this SortedList
in the order determined by the given Comparator
.
This implementation allows the entire list to be iterated over in time O(n), where n is the number of elements in the list.
iterator
in interface java.lang.Iterable<T>
iterator
in interface java.util.Collection<T>
iterator
in interface java.util.List<T>
iterator
in class java.util.AbstractList<T>
Iterator
which provides the elements of this SortedList
in the order determined by the given Comparator
.public int size()
SortedList
.
size
in interface java.util.Collection<T>
size
in interface java.util.List<T>
size
in class java.util.AbstractCollection<T>
SortedList
.protected SortedList.Node getRoot()
SortedList
, which is
null
in the case that this list is empty.
SortedList
, which is
null
in the case that this list is empty.public boolean contains(java.lang.Object obj)
SortedList
.
The comparison check uses the Object#equals(Object)
method and work
under the assumption that the given obj
must have type T
to be equal to the elements in this SortedList
. Works in time
O(log(n)), where n is the number of elements in the list.
contains
in interface java.util.Collection<T>
contains
in interface java.util.List<T>
contains
in class java.util.AbstractCollection<T>
obj
- the object to check for.
protected SortedList.Node findFirstNodeWithValue(T value)
This method performs a binary search using the given comparator, and hence works in time O(log(n)).
value
- the value to search for.
public T remove(int index)
SortedList
. Since the list
is sorted this is the "index"-th smallest element, counting from 0-n-1.
For example, calling remove(0)
will remove the smallest element in the list.
remove
in interface java.util.List<T>
remove
in class java.util.AbstractList<T>
index
- the index of the element to remove.
java.lang.IllegalArgumentException
- in the case that the index is not a valid index.public boolean remove(java.lang.Object value)
Returns whether or not a matching element was found and removed or not.
remove
in interface java.util.Collection<T>
remove
in interface java.util.List<T>
remove
in class java.util.AbstractCollection<T>
value
- the object to remove from this SortedList
.
true
if the given object was found in this
SortedList
and removed, false
otherwise.protected void remove(SortedList.Node toRemove)
Node
from this SortedList
, re-balancing if required,
adds to modCount
too.
Operates in time O(log(n)), where n is the number of elements in the list.
toRemove
- the Node
, which must be a Node
in this SortedList
.public T get(int index)
SortedList
. Since the list is sorted,
this is the "index"th smallest element, counting from 0-n-1.
For example, calling get(0)
will return the smallest element in the list.
get
in interface java.util.List<T>
get
in class java.util.AbstractList<T>
index
- the index of the element to get.
SortedList
.
java.lang.IllegalArgumentException
- in the case that the index is not a valid index.protected SortedList.Node findNodeAtIndex(int index)
Node
at the given index.
index
- the index to search for.
Node
object at the specified index.
java.lang.IllegalArgumentException
- in the case that the the index is not valid.public boolean isEmpty()
isEmpty
in interface java.util.Collection<T>
isEmpty
in interface java.util.List<T>
isEmpty
in class java.util.AbstractCollection<T>
true
if the list has no element in it
and false
otherwise.public void clear()
clear
in interface java.util.Collection<T>
clear
in interface java.util.List<T>
clear
in class java.util.AbstractList<T>
public java.lang.Object[] toArray()
SortedList
.
toArray
in interface java.util.Collection<T>
toArray
in interface java.util.List<T>
toArray
in class java.util.AbstractCollection<T>
public <E> E[] toArray(E[] holder)
SortedList
to the given array if it is large
enough to store them, otherwise it returns a new array of the same type with the
elements in it.
If the length of the given array is larger than the size of this SortedList
then, the elements in this list are put into the start of the given array and the
rest of the array is left untouched.
toArray
in interface java.util.Collection<T>
toArray
in interface java.util.List<T>
toArray
in class java.util.AbstractCollection<T>
java.lang.ClassCastException
- in the case that the provided array can not hold
objects of this type stored in this SortedList
.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |