Module fr.dufrenoy.util

Package fr.dufrenoy.util

Interface TreeList<E>

Type Parameters:

E - the type of elements maintained by this list

All Superinterfaces:

Collection<E>, Iterable<E>, List<E>

All Known Implementing Classes:

SynchronizedTreeList, UnsynchronizedTreeList

public interface TreeList<E>
extends List<E>

A sorted list that contains no duplicate elements, backed by a red-black tree.

Elements are ordered using either a Comparator supplied at construction time, or their natural ordering. Two elements a and b are considered duplicates if and only if compare(a, b) == 0.

Unlike a general-purpose List, the position of each element is determined by its sort order, not by the caller. The following optional List operations are therefore not supported and will always throw UnsupportedOperationException:

• List.add(int, Object)
• List.addAll(int, java.util.Collection)
• List.set(int, Object)
• ListIterator.add(E)
• ListIterator.set(E)

subList(int, int) returns a live view of this list bounded by element values. The view reflects mutations to the parent list and vice versa. Adding an element outside the view's value range throws IllegalArgumentException, following the same convention as TreeMap.subMap(Object, Object).

All elements inserted into a TreeList must be mutually comparable using the list's comparator (or natural ordering). Attempting to insert an incomparable element will throw a ClassCastException.

null elements are not permitted.

Duplicate elements are silently rejected: List.add(Object) returns false if the element is already present, leaving the list unchanged.

The List.equals(Object) contract is position-based: a TreeList is equal to any List containing the same elements in the same sorted order.

Two implementations are provided:

• UnsynchronizedTreeList — not thread-safe; O(log n) for insertion, removal, and index-based access.
• SynchronizedTreeList — thread-safe, backed by a ReentrantReadWriteLock.

Version:

1.0

Author:

Dufrenoy

See Also:

UnsynchronizedTreeList, SynchronizedTreeList

Method Summary

Modifier and Type	Method	Description
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.
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 interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.List

add, add, addAll, addAll, clear, contains, containsAll, equals, get, hashCode, indexOf, isEmpty, iterator, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, replaceAll, retainAll, set, size, sort, spliterator, toArray, toArray

Method Detail

comparator

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.

Returns:

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

subList

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).

Specified by:

subList in interface List<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