org.zkoss.util
Class TreeArray

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList
          org.zkoss.util.TreeArray

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.lang.Iterable, java.util.Collection, java.util.List, ListX

Direct Known Subclasses:

CheckableTreeArray

public class TreeArray
extends java.util.AbstractList
implements ListX, java.lang.Cloneable, java.io.Serializable

Red-black tree based array implementation of List interface. Unlike LinkedList, the random access by index is as fast as log(n). Unlike ArrayList, the insertion is as fast as log(n). It is a great compromise between randown and sequential access.

In additions, it extends the features by also implementing ListX.

The deriving class might override newEntry if it also extends RbEntry; override insert(RbEntry, RbEntry) for adding element; override delete(RbEntry) for removing element; clear() for clearing the whole list.

Also, RbEntry.setElement might be overrided if the deriving class wants to do something when the set method is called.

The iterator method is designed such that next() will proceed correctly even if getElement() throws an exception.

The original algorithm is invented by Henri Chen.

Author:

tomyeh

See Also:

ListX, Serialized Form

Nested Class Summary

protected static class

TreeArray.RbEntry Caller shall use AbstractList.Entry instead of RbEntry for better portability.

Nested classes/interfaces inherited from interface org.zkoss.util.ListX

ListX.Entry

Field Summary

protected int	_hashCode
protected TreeArray.RbEntry	_root
protected int	_size
protected static boolean	BLACK
protected static boolean	RED

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

TreeArray()

TreeArray(java.util.Collection c)
Constructor with a collection.

Method Summary

void	add(int index, java.lang.Object element)
void	addAllByOrder(java.util.Collection cn) Adds all elements by their natural ordering.
void	addAllByOrder(java.util.Collection cn, java.util.Comparator c) Adds all elements by the specified comparator.
void	addByOrder(java.lang.Object element) Adds an element by its natural ordering.
void	addByOrder(java.lang.Object element, java.util.Comparator c) Adds an element by the specified comparator.
ListX.Entry	addEntry(int index, java.lang.Object element) Inserts the specified element at the specified position in this list.
ListX.Entry	addEntry(ListX.Entry insertBefore, java.lang.Object element) Inserts the sepcified element in front of the specified entry.
ListX.Entry	addEntry(java.lang.Object element) Appends the specified element to the end of this list.
protected TreeArray.RbEntry	checkNotOrphan(ListX.Entry entry) Converts and checks whether it is not orphan
protected void	checkRange(int index)
protected void	checkRangePlus(int index)
void	clear() Clears the whole list.
java.lang.Object	clone()
protected void	decSize()
protected TreeArray.RbEntry	delete(int index)
protected void	delete(TreeArray.RbEntry p) All remove methods are done thru this method.
java.util.ListIterator	entryIterator()
java.util.ListIterator	entryIterator(int index)
protected TreeArray.RbEntry	first() Returns the first node.
java.lang.Object	get(int index)
java.lang.Object	getByOrder(java.lang.Object element) Gets an element by its natural ordering.
java.lang.Object	getByOrder(java.lang.Object element, java.util.Comparator c) Gets an element by its natural ordering.
ListX.Entry	getEntry(int index) Gets the entry of the specified index, rather than the element added by List.add.
protected TreeArray.RbEntry	getRbEntry(int index)
int	hashCode()
protected void	incSize()
int	indexOfEntry(ListX.Entry p) Gets the index of the specified entry.
protected int	indexOfEntry(TreeArray.RbEntry p)
protected void	indexOutOfBounds(int index)
protected TreeArray.RbEntry	insert(int index, TreeArray.RbEntry p)
protected TreeArray.RbEntry	insert(TreeArray.RbEntry insertBefore, TreeArray.RbEntry p) All add methods are done thru this method.
java.util.Iterator	iterator()
java.util.ListIterator	listIterator(int index)
protected TreeArray.RbEntry	newEntry(java.lang.Object element) Creates an instance of RbEntry.
java.lang.Object	remove(int index)
boolean	removeByOrder(java.lang.Object element) Removes an element by its natural ordering.
boolean	removeByOrder(java.lang.Object element, java.util.Comparator c) Removes an element by the specified comparator.
ListX.Entry	removeEntry(int index) Remove the entry at the specified location from the list.
void	removeEntry(ListX.Entry p) Remove the entry from the list.
int	search(java.lang.Object element) Searches an element by its natural ordering.
int	search(java.lang.Object element, java.util.Comparator c) Searches an element by the specified comparator.
java.lang.Object	set(int index, java.lang.Object element)
int	size()
void	sort() Sorts all elements ascendingly by the natural ordering.
void	sort(java.util.Comparator c) Sorts all elements ascendingly by the specified comparator.

Methods inherited from class java.util.AbstractList

add, addAll, equals, indexOf, lastIndexOf, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.List

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray

Field Detail

RED

protected static final boolean RED

See Also:

Constant Field Values

BLACK

protected static final boolean BLACK

See Also:

Constant Field Values

_root

protected transient TreeArray.RbEntry _root

_size

protected transient int _size

_hashCode

protected transient int _hashCode

Constructor Detail

TreeArray

public TreeArray()

TreeArray

public TreeArray(java.util.Collection c)

Constructor with a collection.

Parameters:

c - the collection to add; null to ignore

Method Detail

addByOrder

public final void addByOrder(java.lang.Object element)

Adds an element by its natural ordering. This array must be sorted into ascending order according to the natural ordering. To sort, either sort or add all elements by order.

All elements are assumed to implement Comparable.

addByOrder

public final void addByOrder(java.lang.Object element,
                             java.util.Comparator c)

Adds an element by the specified comparator. This array must be sorted into ascending order according to the specified comparator. To sort, either sort or add all elements by order.

removeByOrder

public final boolean removeByOrder(java.lang.Object element)

Removes an element by its natural ordering. This array must be sorted into ascending order according to the natural ordering. To sort, either sort or add all elements by order.

All elements are assumed to implement Comparable.

removeByOrder

public final boolean removeByOrder(java.lang.Object element,
                                   java.util.Comparator c)

Removes an element by the specified comparator. This array must be sorted into ascending order according to the specified comparator. To sort, either sort or add all elements by order.

addAllByOrder

public final void addAllByOrder(java.util.Collection cn)

Adds all elements by their natural ordering. This array must be sorted into ascending order according to the natural ordering. To sort, either sort or add all elements by order.

All elements are assumed to implement Comparable.

addAllByOrder

public final void addAllByOrder(java.util.Collection cn,
                                java.util.Comparator c)

Adds all elements by the specified comparator. This array must be sorted into ascending order according to the specified comparator. To sort, either sort or add all elements by order.

search

public final int search(java.lang.Object element)

Searches an element by its natural ordering. This array must be sorted into ascending order according to the natural ordering. To sort, either sort or add all elements by order, addByOrder(Object).

All elements are assumed to implement Comparable. Note: the element argument of this method is passed as the argument of the compareTo method. Thus, it is OK to pass any kind of object, as long as the elements stored in this array is able to detect it.

For example, you might use a String to search the element, and your element's compareTo shall be implemented as follows.

public int compareTo(Object o) {
  return o instanceof String ?
                _name.compareTo((String)o):
                _name.compareTo(((YourClass)o).getName());
}

search

public final int search(java.lang.Object element,
                        java.util.Comparator c)

Searches an element by the specified comparator. This array must be sorted into ascending order according to the specified comparator. To sort, either sort or add all elements by order, addByOrder(Object, Comparator).

All elements are assumed to implement Comparable. Note: the element argument of this method is passed as the argument of the compareTo method. Thus, it is OK to pass any kind of object, as long as the elements stored in this array is able to detect it.

getByOrder

public final java.lang.Object getByOrder(java.lang.Object element)

Gets an element by its natural ordering. It is a shortcut of get(search(element)).

Returns:

null if not found

See Also:

search(Object)

getByOrder

public final java.lang.Object getByOrder(java.lang.Object element,
                                         java.util.Comparator c)

Gets an element by its natural ordering. It is a shortcut of get(search(element, c)).

Returns:

null if not found

See Also:

search(Object, Comparator)

sort

public final void sort()

Sorts all elements ascendingly by the natural ordering.

All elements are assumed to implement Comparable.

sort

public final void sort(java.util.Comparator c)

Sorts all elements ascendingly by the specified comparator.

size

public final int size()

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.List

Specified by:

size in class java.util.AbstractCollection

get

public final java.lang.Object get(int index)

Specified by:

get in interface java.util.List

Specified by:

get in class java.util.AbstractList

set

public java.lang.Object set(int index,
                            java.lang.Object element)

Specified by:

set in interface java.util.List

Overrides:

set in class java.util.AbstractList

add

public void add(int index,
                java.lang.Object element)

Specified by:

add in interface java.util.List

Overrides:

add in class java.util.AbstractList

remove

public java.lang.Object remove(int index)

Specified by:

remove in interface java.util.List

Overrides:

remove in class java.util.AbstractList

iterator

public final java.util.Iterator iterator()

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.List

Overrides:

iterator in class java.util.AbstractList

listIterator

public final java.util.ListIterator listIterator(int index)

Specified by:

listIterator in interface java.util.List

Overrides:

listIterator in class java.util.AbstractList

clear

public void clear()

Clears the whole list. Overrides it if the derived class has other data to clear. Note it doesn't call removeEx.

Note clear actually invokes RbEntry.clear to do the real cleanup. Deriving classes might override RbEntry.clear.

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.List

Overrides:

clear in class java.util.AbstractList

getRbEntry

protected final TreeArray.RbEntry getRbEntry(int index)

getEntry

public final ListX.Entry getEntry(int index)

Description copied from interface: ListX

Gets the entry of the specified index, rather than the element added by List.add. An entry is an internal representation of an object that holding the element stored by List.add.

The caller should consider the returned entry as opaque. The caller could store it for later use. It is useful when you want to extend the list's features, such as providing two or more indexing methods.

In other words, even if the underlying structure of a list is changed (e.g., a new element is inserted), the caller holding entries won't be affected.

Specified by:

getEntry in interface ListX

Parameters:

index - the index from which the entry is retrieved

Returns:

the entry

indexOfEntry

protected final int indexOfEntry(TreeArray.RbEntry p)

indexOfEntry

public final int indexOfEntry(ListX.Entry p)

Description copied from interface: ListX

Gets the index of the specified entry.

Specified by:

indexOfEntry in interface ListX

Parameters:

p - the entry to locate

Returns:

the index; -1 if entry is orphan

hashCode

public int hashCode()

Specified by:

hashCode in interface java.util.Collection

Specified by:

hashCode in interface java.util.List

Overrides:

hashCode in class java.util.AbstractList

entryIterator

public final java.util.ListIterator entryIterator(int index)

entryIterator

public final java.util.ListIterator entryIterator()

newEntry

protected TreeArray.RbEntry newEntry(java.lang.Object element)

Creates an instance of RbEntry. Override it if necessary

addEntry

public final ListX.Entry addEntry(ListX.Entry insertBefore,
                                  java.lang.Object element)

Description copied from interface: ListX

Inserts the sepcified element in front of the specified entry.

Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Specified by:

addEntry in interface ListX

Parameters:

insertBefore - the entry before which an new entry will be inserted; append is assumed if null

element - the element to insert

Returns:

the new entry containing the inserted element.

addEntry

public final ListX.Entry addEntry(int index,
                                  java.lang.Object element)

Description copied from interface: ListX

Inserts the specified element at the specified position in this list. It is an enhanced version of List.add -- it returns the entry containing the element.

Specified by:

addEntry in interface ListX

Parameters:

index - index at which the specified element is to be inserted.

element - element to be inserted.

Returns:

the new entry that conatining the inserted element.

addEntry

public final ListX.Entry addEntry(java.lang.Object element)

Description copied from interface: ListX

Appends the specified element to the end of this list. It is an enhanced version of List.add -- it returns the entry containing the element.

Specified by:

addEntry in interface ListX

Parameters:

element - the element to be inserted.

Returns:

the new entry that conatining the inserted element.

removeEntry

public final void removeEntry(ListX.Entry p)

Description copied from interface: ListX

Remove the entry from the list. The entry object does not be deleted, and it is just no longer referenced by the list.

Specified by:

removeEntry in interface ListX

Parameters:

p - the entry returned by getEntry.

removeEntry

public final ListX.Entry removeEntry(int index)

Description copied from interface: ListX

Remove the entry at the specified location from the list. Unlike List.remove(int), it returns the entry being removed.

Specified by:

removeEntry in interface ListX

Parameters:

index - the location of the entry to remove

Returns:

the entry being removed

first

protected final TreeArray.RbEntry first()

Returns the first node.

insert

protected final TreeArray.RbEntry insert(int index,
                                         TreeArray.RbEntry p)

insert

protected TreeArray.RbEntry insert(TreeArray.RbEntry insertBefore,
                                   TreeArray.RbEntry p)

All add methods are done thru this method. Override it if necessary.

Note: p is inserted before insertBefore.

delete

protected TreeArray.RbEntry delete(int index)

delete

protected void delete(TreeArray.RbEntry p)

All remove methods are done thru this method. Override it if necessary.

incSize

protected final void incSize()

decSize

protected final void decSize()

checkRange

protected final void checkRange(int index)

checkRangePlus

protected final void checkRangePlus(int index)

indexOutOfBounds

protected final void indexOutOfBounds(int index)

checkNotOrphan

protected final TreeArray.RbEntry checkNotOrphan(ListX.Entry entry)

Converts and checks whether it is not orphan

clone

public java.lang.Object clone()

Overrides:

clone in class java.lang.Object