|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.AbstractCollection
java.util.AbstractList
org.zkoss.util.TreeArray
public class TreeArray
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.
ListX
,
Serialized FormNested 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 |
---|
protected static final boolean RED
protected static final boolean BLACK
protected transient TreeArray.RbEntry _root
protected transient int _size
protected transient int _hashCode
Constructor Detail |
---|
public TreeArray()
public TreeArray(java.util.Collection c)
c
- the collection to add; null to ignoreMethod Detail |
---|
public final void addByOrder(java.lang.Object element)
All elements are assumed to implement Comparable.
public final void addByOrder(java.lang.Object element, java.util.Comparator c)
public final boolean removeByOrder(java.lang.Object element)
All elements are assumed to implement Comparable.
public final boolean removeByOrder(java.lang.Object element, java.util.Comparator c)
public final void addAllByOrder(java.util.Collection cn)
All elements are assumed to implement Comparable.
public final void addAllByOrder(java.util.Collection cn, java.util.Comparator c)
public final int search(java.lang.Object element)
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());
}
public final int search(java.lang.Object element, java.util.Comparator c)
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.
public final java.lang.Object getByOrder(java.lang.Object element)
search(Object)
public final java.lang.Object getByOrder(java.lang.Object element, java.util.Comparator c)
search(Object, Comparator)
public final void sort()
All elements are assumed to implement Comparable.
public final void sort(java.util.Comparator c)
public final int size()
size
in interface java.util.Collection
size
in interface java.util.List
size
in class java.util.AbstractCollection
public final java.lang.Object get(int index)
get
in interface java.util.List
get
in class java.util.AbstractList
public java.lang.Object set(int index, java.lang.Object element)
set
in interface java.util.List
set
in class java.util.AbstractList
public void add(int index, java.lang.Object element)
add
in interface java.util.List
add
in class java.util.AbstractList
public java.lang.Object remove(int index)
remove
in interface java.util.List
remove
in class java.util.AbstractList
public final java.util.Iterator iterator()
iterator
in interface java.lang.Iterable
iterator
in interface java.util.Collection
iterator
in interface java.util.List
iterator
in class java.util.AbstractList
public final java.util.ListIterator listIterator(int index)
listIterator
in interface java.util.List
listIterator
in class java.util.AbstractList
public void clear()
Note clear actually invokes RbEntry.clear to do the real cleanup. Deriving classes might override RbEntry.clear.
clear
in interface java.util.Collection
clear
in interface java.util.List
clear
in class java.util.AbstractList
protected final TreeArray.RbEntry getRbEntry(int index)
public final ListX.Entry getEntry(int index)
ListX
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.
getEntry
in interface ListX
index
- the index from which the entry is retrieved
protected final int indexOfEntry(TreeArray.RbEntry p)
public final int indexOfEntry(ListX.Entry p)
ListX
indexOfEntry
in interface ListX
p
- the entry to locate
public int hashCode()
hashCode
in interface java.util.Collection
hashCode
in interface java.util.List
hashCode
in class java.util.AbstractList
public final java.util.ListIterator entryIterator(int index)
public final java.util.ListIterator entryIterator()
protected TreeArray.RbEntry newEntry(java.lang.Object element)
public final ListX.Entry addEntry(ListX.Entry insertBefore, java.lang.Object element)
ListX
Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
addEntry
in interface ListX
insertBefore
- the entry before which an new entry will be
inserted; append is assumed if nullelement
- the element to insert
public final ListX.Entry addEntry(int index, java.lang.Object element)
ListX
addEntry
in interface ListX
index
- index at which the specified element is to be inserted.element
- element to be inserted.
public final ListX.Entry addEntry(java.lang.Object element)
ListX
addEntry
in interface ListX
element
- the element to be inserted.
public final void removeEntry(ListX.Entry p)
ListX
removeEntry
in interface ListX
p
- the entry returned by getEntry.public final ListX.Entry removeEntry(int index)
ListX
removeEntry
in interface ListX
index
- the location of the entry to remove
protected final TreeArray.RbEntry first()
protected final TreeArray.RbEntry insert(int index, TreeArray.RbEntry p)
protected TreeArray.RbEntry insert(TreeArray.RbEntry insertBefore, TreeArray.RbEntry p)
Note: p is inserted before insertBefore.
protected TreeArray.RbEntry delete(int index)
protected void delete(TreeArray.RbEntry p)
protected final void incSize()
protected final void decSize()
protected final void checkRange(int index)
protected final void checkRangePlus(int index)
protected final void indexOutOfBounds(int index)
protected final TreeArray.RbEntry checkNotOrphan(ListX.Entry entry)
public java.lang.Object clone()
clone
in class java.lang.Object
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |