Module fr.dufrenoy.util

Package fr.dufrenoy.util

Class UnsynchronizedTreeList<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractList<E>

fr.dufrenoy.util.UnsynchronizedTreeList<E>

Type Parameters:

E - the type of elements maintained by this list

All Implemented Interfaces:

TreeList<E>, Serializable, Iterable<E>, Collection<E>, List<E>

public class UnsynchronizedTreeList<E>
extends AbstractList<E>
implements TreeList<E>, Serializable

A non-thread-safe implementation of TreeList backed by a red-black tree augmented with subtree sizes (order-statistic tree).

The augmentation stores, in each node, the size of the subtree rooted at that node. This allows index-based access (get(int), remove(int)) to run in O(log n) rather than O(n).

All structural operations (add(Object), remove(int), remove(Object)) run in O(log n). Lookup operations (contains(Object), indexOf(Object)) also run in O(log n) by exploiting the sorted order.

This implementation is not thread-safe. For concurrent use, prefer SynchronizedTreeList.

Version:

1.0

Author:

Dufrenoy

See Also:

TreeList, SynchronizedTreeList, Serialized Form

Field Summary

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

Constructors

Constructor	Description
UnsynchronizedTreeList()	Constructs an empty UnsynchronizedTreeList ordered by the natural ordering of its elements.
UnsynchronizedTreeList(Collection<? extends E> c)	Constructs a UnsynchronizedTreeList containing the elements of the given collection, ordered by their natural ordering.
UnsynchronizedTreeList(Comparator<? super E> comparator)	Constructs an empty UnsynchronizedTreeList ordered by the given comparator.
UnsynchronizedTreeList(Comparator<? super E> comparator, Collection<? extends E> c)	Constructs a UnsynchronizedTreeList containing the elements of the given collection, ordered by the given comparator.

Method Summary

Modifier and Type	Method	Description
void	add(int index, E element)	Not supported.
boolean	add(E e)	Inserts the specified element in its sorted position in this list.
boolean	addAll(int index, Collection<? extends E> c)
boolean	addAll(Collection<? extends E> c)
void	clear()	Removes all elements from this list.
Optional<Comparator<? super E>>	comparator()	Returns the comparator used to order the elements in this list, or an empty Optional if the elements are ordered by their natural ordering.
boolean	contains(Object o)	Returns true if this list contains the specified element.
E	get(int index)	Returns the element at the specified position in this list.
int	indexOf(Object o)	Returns the index of the first (and only) occurrence of the specified element in this list, or -1 if it is not present.
Iterator<E>	iterator()	Returns an iterator over the elements in this list in sorted (ascending) order.
int	lastIndexOf(Object o)	Equivalent to indexOf(Object) since this list contains no duplicates.
ListIterator<E>	listIterator(int index)	Returns a list iterator over the elements in this list in sorted order, starting at the specified position.
E	remove(int index)	Removes the element at the specified position in this list.
boolean	remove(Object o)	Removes the specified element from this list if it is present.
boolean	removeAll(Collection<?> c)	Removes from this list all elements that are contained in the specified collection.
boolean	retainAll(Collection<?> c)	Retains only the elements in this list that are contained in the specified collection.
E	set(int index, E element)	Not supported.
int	size()	Returns the number of elements in this list.
TreeList<E>	subList(int fromIndex, int toIndex)	Returns a live view of the portion of this list whose elements range from the element at fromIndex (inclusive) to the element at toIndex (exclusive).

Methods inherited from class java.util.AbstractList

equals, hashCode, listIterator, removeRange

Methods inherited from class java.util.AbstractCollection

containsAll, isEmpty, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.List

containsAll, equals, hashCode, isEmpty, listIterator, replaceAll, sort, spliterator, toArray, toArray

Constructor Detail

UnsynchronizedTreeList

public UnsynchronizedTreeList()

Constructs an empty UnsynchronizedTreeList ordered by the natural ordering of its elements.

All elements inserted must implement Comparable. Attempting to insert an element that does not will throw a ClassCastException.

UnsynchronizedTreeList

public UnsynchronizedTreeList(Comparator<? super E> comparator)

Constructs an empty UnsynchronizedTreeList ordered by the given comparator.

Parameters:

comparator - the comparator used to order elements, or null to use natural ordering

UnsynchronizedTreeList

public UnsynchronizedTreeList(Collection<? extends E> c)

Constructs a UnsynchronizedTreeList containing the elements of the given collection, ordered by their natural ordering. Duplicate elements (as determined by natural ordering) are silently discarded.

Parameters:

c - the collection whose elements are to be placed into this list

Throws:

ClassCastException - if any element is not mutually comparable

NullPointerException - if c is null, or if any element of c is null

UnsynchronizedTreeList

public UnsynchronizedTreeList(Comparator<? super E> comparator,
                              Collection<? extends E> c)

Constructs a UnsynchronizedTreeList containing the elements of the given collection, ordered by the given comparator. Duplicate elements (as determined by the comparator) are silently discarded.

Parameters:

comparator - the comparator used to order elements, or null to use natural ordering

c - the collection whose elements are to be placed into this list

Throws:

ClassCastException - if any element is not mutually comparable

NullPointerException - if c is null, or if any element of c is null

Method Detail

comparator

public Optional<Comparator<? super E>> comparator()

Returns the comparator used to order the elements in this list, or an empty Optional if the elements are ordered by their natural ordering.

Specified by:

comparator in interface TreeList<E>

Returns:

the comparator used to order this list, or an empty Optional if natural ordering is used

size

public int size()

Returns the number of elements in this list.

Specified by:

size in interface Collection<E>

Specified by:

size in interface List<E>

Specified by:

size in class AbstractCollection<E>

Returns:

the number of elements in this list

get

public E get(int index)

Returns the element at the specified position in this list. Runs in O(log n) using the augmented subtree sizes.

Specified by:

get in interface List<E>

Specified by:

get in class AbstractList<E>

Parameters:

index - index of the element to return

Returns:

the element at the specified position

Throws:

IndexOutOfBoundsException - if index < 0 || index >= size()

add

public boolean add(E e)

Inserts the specified element in its sorted position in this list. Returns false if an element equal to e (as determined by the comparator or natural ordering) is already present, leaving the list unchanged.

Specified by:

add in interface Collection<E>

Specified by:

add in interface List<E>

Overrides:

add in class AbstractList<E>

Parameters:

e - the element to add

Returns:

true if this list changed as a result of the call, false if e was already present

Throws:

ClassCastException - if e is not mutually comparable with the existing elements

NullPointerException - if e is null

add

public void add(int index,
                E element)

Not supported. The position of elements in a TreeList is determined by sort order, not by the caller.

Specified by:

add in interface List<E>

Overrides:

add in class AbstractList<E>

Throws:

UnsupportedOperationException - always

addAll

public boolean addAll(Collection<? extends E> c)

Specified by:

addAll in interface Collection<E>

Specified by:

addAll in interface List<E>

Overrides:

addAll in class AbstractCollection<E>

Throws:

NullPointerException - if c is null, or if any element of c is null

addAll

public boolean addAll(int index,
                      Collection<? extends E> c)

Specified by:

addAll in interface List<E>

Overrides:

addAll in class AbstractList<E>

Throws:

UnsupportedOperationException - always (positional insertion is not supported)

remove

public E remove(int index)

Removes the element at the specified position in this list. Runs in O(log n).

Specified by:

remove in interface List<E>

Overrides:

remove in class AbstractList<E>

Parameters:

index - the index of the element to be removed

Returns:

the element previously at the specified position

Throws:

IndexOutOfBoundsException - if index < 0 || index >= size()

remove

public boolean remove(Object o)

Removes the specified element from this list if it is present. Runs in O(log n) using the sorted structure.

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface List<E>

Overrides:

remove in class AbstractCollection<E>

Parameters:

o - the element to be removed

Returns:

true if this list contained the specified element

removeAll

public boolean removeAll(Collection<?> c)

Removes from this list all elements that are contained in the specified collection. Runs in O(m log n) where m is the size of c.

Specified by:

removeAll in interface Collection<E>

Specified by:

removeAll in interface List<E>

Overrides:

removeAll in class AbstractCollection<E>

Parameters:

c - the collection containing elements to be removed

Returns:

true if this list changed as a result of the call

Throws:

NullPointerException - if c is null

retainAll

public boolean retainAll(Collection<?> c)

Retains only the elements in this list that are contained in the specified collection. Runs in O(n log m) where m is the size of c.

Specified by:

retainAll in interface Collection<E>

Specified by:

retainAll in interface List<E>

Overrides:

retainAll in class AbstractCollection<E>

Parameters:

c - the collection containing elements to be retained

Returns:

true if this list changed as a result of the call

Throws:

NullPointerException - if c is null

clear

public void clear()

Removes all elements from this list. The list will be empty after this call returns.

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface List<E>

Overrides:

clear in class AbstractList<E>

set

public E set(int index,
             E element)

Not supported. The position of elements in a TreeList is determined by sort order, not by the caller.

Specified by:

set in interface List<E>

Overrides:

set in class AbstractList<E>

Throws:

UnsupportedOperationException - always

subList

public TreeList<E> subList(int fromIndex,
                           int toIndex)

Returns a live view of the portion of this list whose elements range from the element at fromIndex (inclusive) to the element at toIndex (exclusive). The returned view is itself a TreeList: it is sorted, contains no duplicates, and supports the same operations as this list.

The view is bounded by element values, not by indices. After creation, the view contains all elements e in this list such that compare(fromElement, e) <= 0 and compare(e, toElement) < 0, where fromElement and toElement are the elements at positions fromIndex and toIndex at the time the view was created.

Structural modifications through the view (add, remove, clear) are reflected in the parent list, and vice versa. However, if the parent list is structurally modified outside the view, the view becomes invalid and subsequent operations will throw ConcurrentModificationException (fail-fast).

Adding an element that falls outside the view's value range throws IllegalArgumentException, following the same convention as TreeMap.subMap(Object, Object).

Returns a live view bounded by the element values at positions fromIndex and toIndex at the time this method is called.

Specified by:

subList in interface List<E>

Specified by:

subList in interface TreeList<E>

Overrides:

subList in class AbstractList<E>

Parameters:

fromIndex - low endpoint (inclusive) of the subList

toIndex - high endpoint (exclusive) of the subList

Returns:

a view of the specified range within this list

Throws:

IndexOutOfBoundsException - if fromIndex < 0 or toIndex > size()

IllegalArgumentException - if fromIndex > toIndex

contains

public boolean contains(Object o)

Returns true if this list contains the specified element. Runs in O(log n) by performing a binary search on the red-black tree.

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface List<E>

Overrides:

contains in class AbstractCollection<E>

Parameters:

o - the element whose presence is to be tested

Returns:

true if this list contains the element

indexOf

public int indexOf(Object o)

Returns the index of the first (and only) occurrence of the specified element in this list, or -1 if it is not present. Runs in O(log n) by performing a binary search on the red-black tree.

Specified by:

indexOf in interface List<E>

Overrides:

indexOf in class AbstractList<E>

Parameters:

o - the element to search for

Returns:

the index of the element, or -1 if not present

lastIndexOf

public int lastIndexOf(Object o)

Equivalent to indexOf(Object) since this list contains no duplicates.

Specified by:

lastIndexOf in interface List<E>

Overrides:

lastIndexOf in class AbstractList<E>

Parameters:

o - the element to search for

Returns:

the index of the element, or -1 if not present

iterator

public Iterator<E> iterator()

Returns an iterator over the elements in this list in sorted (ascending) order. The iterator performs an in-order traversal of the underlying red-black tree in O(n) total.

The iterator does not support Iterator.remove().

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface List<E>

Overrides:

iterator in class AbstractList<E>

Returns:

an iterator over the elements in sorted order

listIterator

public ListIterator<E> listIterator(int index)

Returns a list iterator over the elements in this list in sorted order, starting at the specified position.

ListIterator.add(Object) and ListIterator.set(Object) are not supported and will throw UnsupportedOperationException.

Specified by:

listIterator in interface List<E>

Overrides:

listIterator in class AbstractList<E>

Parameters:

index - index of the first element to be returned by ListIterator.next()

Returns:

a list iterator over the elements in sorted order

Throws:

IndexOutOfBoundsException - if index < 0 || index > size()