| java.util.AbstractList
 org.zkoss.util.TreeArray
All known Subclasses: org.zkoss.util.CheckableTreeArray,
| TreeArray | | public class TreeArray extends AbstractList implements ListX,Cloneable,java.io.Serializable(Code) | | 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 |
| Inner Class :protected static class RbEntry implements Entry | |
| Field Summary | |
| final protected static boolean | BLACK
| | final protected static boolean | RED
| | protected transient int | _hashCode
| | protected transient RbEntry | _root
| | protected transient int | _size
|
| Method Summary | |
| public void | add(int index, Object element)
| | final public void | addAllByOrder(Collection cn)
Adds all elements by their natural ordering.
This array must be sorted into ascending order according to
the natural ordering. | | final public void | addAllByOrder(Collection cn, Comparator c)
Adds all elements by the specified comparator.
This array must be sorted into ascending order according to
the specified comparator. | | final public void | addByOrder(Object element)
Adds an element by its natural ordering.
This array must be sorted into ascending order according to
the natural ordering. | | final public void | addByOrder(Object element, Comparator c)
Adds an element by the specified comparator.
This array must be sorted into ascending order according to
the specified comparator. | | final public Entry | addEntry(Entry insertBefore, Object element)
| | final public Entry | addEntry(int index, Object element)
| | final public Entry | addEntry(Object element)
| | final protected RbEntry | checkNotOrphan(Entry entry)
| | final protected void | checkRange(int index)
| | final protected void | checkRangePlus(int index)
| | public void | clear()
Clears the whole list. | | public Object | clone()
| | final protected void | decSize()
| | protected RbEntry | delete(int index)
| | protected void | delete(RbEntry p)
All remove methods are done thru this method. | | final public ListIterator | entryIterator(int index)
| | final public ListIterator | entryIterator()
| | final protected RbEntry | first()
Returns the first node. | | final public Object | get(int index)
| | final public Object | getByOrder(Object element)
Gets an element by its natural ordering. | | final public Object | getByOrder(Object element, Comparator c)
Gets an element by its natural ordering. | | final public Entry | getEntry(int index)
| | final protected RbEntry | getRbEntry(int index)
| | public int | hashCode()
| | final protected void | incSize()
| | final protected int | indexOfEntry(RbEntry p)
| | final public int | indexOfEntry(Entry p)
| | final protected void | indexOutOfBounds(int index)
| | final protected RbEntry | insert(int index, RbEntry p)
| | protected RbEntry | insert(RbEntry insertBefore, RbEntry p)
All add methods are done thru this method. | | final public Iterator | iterator()
| | final public ListIterator | listIterator(int index)
| | protected RbEntry | newEntry(Object element)
Creates an instance of RbEntry. | | public Object | remove(int index)
| | final public boolean | removeByOrder(Object element)
Removes an element by its natural ordering.
This array must be sorted into ascending order according to
the natural ordering. | | final public boolean | removeByOrder(Object element, Comparator c)
Removes an element by the specified comparator.
This array must be sorted into ascending order according to
the specified comparator. | | final public void | removeEntry(Entry p)
| | final public Entry | removeEntry(int index)
| | final public int | search(Object element)
Searches an element by its natural ordering.
This array must be sorted into ascending order according to
the natural ordering. | | final public int | search(Object element, Comparator c)
Searches an element by the specified comparator.
This array must be sorted into ascending order according to
the specified comparator. | | public Object | set(int index, Object element)
| | final public int | size()
| | final public void | sort()
Sorts all elements ascendingly by the natural ordering. | | final public void | sort(Comparator c)
Sorts all elements ascendingly by the specified comparator. |
| BLACK | | final protected static boolean BLACK(Code) | | |
| RED | | final protected static boolean RED(Code) | | |
| _hashCode | | protected transient int _hashCode(Code) | | |
| _root | | protected transient RbEntry _root(Code) | | |
| _size | | protected transient int _size(Code) | | |
| TreeArray | | public TreeArray()(Code) | | |
| TreeArray | | public TreeArray(Collection c)(Code) | | Constructor with a collection.
Parameters:
c - the collection to add; null to ignore |
| addAllByOrder | | final public void addAllByOrder(Collection cn)(Code) | | 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 | | final public void addAllByOrder(Collection cn, Comparator c)(Code) | | 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.
|
| addByOrder | | final public void addByOrder(Object element)(Code) | | 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 | | final public void addByOrder(Object element, Comparator c)(Code) | | 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.
|
| addEntry | | final public Entry addEntry(Entry insertBefore, Object element)(Code) | | |
| addEntry | | final public Entry addEntry(int index, Object element)(Code) | | |
| checkNotOrphan | | final protected RbEntry checkNotOrphan(Entry entry)(Code) | | Converts and checks whether it is not orphan
|
| checkRange | | final protected void checkRange(int index)(Code) | | |
| checkRangePlus | | final protected void checkRangePlus(int index)(Code) | | |
| clear | | public void clear()(Code) | | 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.
|
| decSize | | final protected void decSize()(Code) | | |
| delete | | protected RbEntry delete(int index)(Code) | | |
| delete | | protected void delete(RbEntry p)(Code) | | All remove methods are done thru this method. Override it if necessary.
|
| first | | final protected RbEntry first()(Code) | | Returns the first node.
|
| getEntry | | final public Entry getEntry(int index)(Code) | | |
| getRbEntry | | final protected RbEntry getRbEntry(int index)(Code) | | |
| hashCode | | public int hashCode()(Code) | | |
| incSize | | final protected void incSize()(Code) | | |
| indexOfEntry | | final protected int indexOfEntry(RbEntry p)(Code) | | |
| indexOfEntry | | final public int indexOfEntry(Entry p)(Code) | | |
| indexOutOfBounds | | final protected void indexOutOfBounds(int index)(Code) | | |
| insert | | final protected RbEntry insert(int index, RbEntry p)(Code) | | |
| insert | | protected RbEntry insert(RbEntry insertBefore, RbEntry p)(Code) | | All add methods are done thru this method. Override it if necessary.
Note: p is inserted before insertBefore.
|
| newEntry | | protected RbEntry newEntry(Object element)(Code) | | Creates an instance of RbEntry. Override it if necessary
|
| removeByOrder | | final public boolean removeByOrder(Object element)(Code) | | 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 | | final public boolean removeByOrder(Object element, Comparator c)(Code) | | 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.
|
| removeEntry | | final public void removeEntry(Entry p)(Code) | | |
| removeEntry | | final public Entry removeEntry(int index)(Code) | | |
| search | | final public int search(Object element)(Code) | | 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,
TreeArray.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 | | final public int search(Object element, Comparator c)(Code) | | 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,
TreeArray.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.
|
| size | | final public int size()(Code) | | |
| sort | | final public void sort()(Code) | | Sorts all elements ascendingly by the natural ordering.
All elements are assumed to implement Comparable.
|
| sort | | final public void sort(Comparator c)(Code) | | Sorts all elements ascendingly by the specified comparator.
|
| Fields inherited from java.util.AbstractList | protected transient int modCount(Code)(Java Doc)
|
|
|