org.zkoss.util
Class TreeArray

java.lang.Object
  extended by java.util.AbstractCollection
      extended by java.util.AbstractList
          extended by 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


Copyright © 2005-2009 Potix Corporation. All Rights Reserved. SourceForge.net Logo