TreeArray.java
| Index Score | ||
|---|---|---|
 |
 |
org.zkoss.util |
 |
 |
ZK |
View: Reasons, Metrics, Source Code
These are the metrics that contribute to the Enerjy Score for this file, ranked by impact. So the metrics listed at the top influence the score to a greater extent that the metrics listed at the bottom.
| Metric | Description | |
|---|---|---|
| JAVA0034 | JAVA0034 Missing braces in if statement |  |
| CYCLOMATIC | Cyclomatic complexity | |
| FUNCTIONS | Number of function declarations | |
| RETURNS | Number of return points from functions | |
| INTERFACE_COMPLEXITY | Interface complexity | |
| COMPARISONS | Number of comparison operators | |
| JAVA0108 | JAVA0108 Incorrect javadoc: no @param tag for 'parameter' | |
| LOGICAL_LINES | Number of statements | |
| JAVA0035 | JAVA0035 Missing braces in for statement | |
| BLOCKS | Number of blocks | |
| PARAMS | Number of formal parameter declarations | |
| DECL_COMMENTS | Comments in declarations | |
| ELOC | Effective lines of code | |
| OPERATORS | Number of operators | |
| JAVA0110 | JAVA0110 Incorrect javadoc: no @return tag | |
| PROGRAM_LENGTH | Halstead program length | |
| LOC | Lines of code | |
| OPERANDS | Number of operands | |
| LINES | Number of lines in the source file | |
| LOOPS | Number of loops | |
| JAVA0020 | JAVA0020 Field name does not have required form | |
| SIZE | Size of the file in bytes | |
| JAVA0117 | JAVA0117 Missing javadoc: method 'method' | |
| DOC_COMMENT | Number of javadoc comment lines | |
| COMMENTS | Comment lines | |
| JAVA0123 | JAVA0123 Use all three components of for loop | |
| JAVA0145 | JAVA0145 Tab character used in source file | |
| EXITS | Procedure exits | |
| PROGRAM_VOCAB | Halstead program vocabulary | |
| UNIQUE_OPERANDS | Number of unique operands | |
| JAVA0143 | JAVA0143 Synchronized method | |
| LINE_COMMENT | Number of line comments | |
| JAVA0254 | JAVA0254 Use enhanced for loop construct instead of Iterator | |
| UNIQUE_OPERATORS | Number of unique operators | |
| JAVA0150 | JAVA0150 java.lang.Error (or subclass) thrown | |
| JAVA0277 | JAVA0277 Iterator.next() implementation does not throw NoSuchElementException | |
| PROGRAM_VOLUME | Halstead program volume | |
| JAVA0136 | JAVA0136 N methods defined in class (maximum: M) | |
| JAVA0126 | JAVA0126 Method declares unchecked exception in throws | |
| WHITESPACE | Number of whitespace lines | |
| NEST_DEPTH | Maximum nesting depth | |
/* TreeArray.java
{{IS_NOTE
Purpose: Red-black tree based array implementation of List interface.
Description:
History:
2001/5/9, Tom M. Yeh: Created.
}}IS_NOTE
Copyright (C) 2001 Potix Corporation. All Rights Reserved.
{{IS_RIGHT
This program is distributed under GPL Version 2.0 in the hope that
it will be useful, but WITHOUT ANY WARRANTY.
}}IS_RIGHT
*/
package org.zkoss.util;
import java.util.*;
/**
* 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.
*
* <p>In additions, it extends the features by also implementing
* ListX.
*
* <p>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.
*
* <p>Also, RbEntry.setElement might be overrided if the deriving class
* wants to do something when the set method is called.
*
* <p>The iterator method is designed such that next() will proceed correctly
* even if getElement() throws an exception.
*
* <p>The original algorithm is invented by Henri Chen.
*
* @author tomyeh
* @see ListX
*/
public class TreeArray extends AbstractList
implements ListX, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 20060622L;
protected static final boolean RED = false;
protected static final boolean BLACK = true;
/**
* Caller shall use AbstractList.Entry instead of RbEntry for
* better portability.
*/
protected static class RbEntry implements Entry {
protected Object element; //use setElement and getElement
protected int leftNum; //# of elements on its left sub-tree
protected RbEntry left;
protected RbEntry right;
protected RbEntry parent;
protected boolean color; //a black node
protected boolean orphan = false; //not belonging to any list
protected RbEntry(Object element) {
this.element = element;
}
/**
* Override it if you want to something when an element is retrieved.
* All other parts that get element must invoke this method
*/
public Object getElement() {
return this.element;
}
/**
* Override it if you want to do something when an element
* is set. All other parts that set element will invoke this method.
*/
public void setElement(Object element) {
this.element = element;
}
public final boolean isOrphan() {
return orphan;
}
protected final RbEntry nextEntry() {
if (right != null)
return right.leftMost();
return firstRightAncestor();
}
public final Entry next() {
return nextEntry();
}
protected final RbEntry previousEntry() {
if (left!=null)
return left.rightMost();
return firtLeftAncestor();
}
public final Entry previous() {
return previousEntry();
}
//-- utilities --/
/**
* Gets the leftmost leaf of the specified subtree.
* It is the entry with lowest index in the subtree.
*/
protected final RbEntry leftMost() {
for (RbEntry p=this;; p=p.left)
if (p.left==null)
return p;
}
/**
* Gets the rihtmost leaf of the specified subtree.
* It is the entry with highest index in the subtree.
*/
protected final RbEntry rightMost() {
for (RbEntry p=this;; p=p.right)
if (p.right==null)
return p;
}
/**
* Gets the first ancestor at the left of the specified entry.
* "At the left" we mean the returned ancesor's right is the entry
* or its ancestor. It is also the first parent with lower index.
*/
protected final RbEntry firtLeftAncestor() {
for (RbEntry p=this; p.parent!=null; p=p.parent)
if (p.parent.right == p)
return p.parent;
return null;
}
/**
* Gets the first parent at the right of the specified entry.
* "At the right" we mean the returned ancesor's right is the entry
* or its ancestor. It is also the first parent with higer index.
*/
protected final RbEntry firstRightAncestor() {
for (RbEntry p=this; p.parent != null; p = p.parent)
if (p.parent.left == p)
return p.parent;
return null;
}
//It doesn't maintain the tree but reset itself as an orphan.
private final void setOrphan() {
orphan = true;
left = right = parent = null;
}
/**
* Called by TreeArray.clear to do clear recursively.
* Since it always be invoked to clear the whole tree,
* it doesn't have to maintain leftNum or other tree info.
* <p>However, this.element is kept.
*/
protected void clear() {
if (left != null) left.clear();
if (right != null) right.clear();
setOrphan();
}
}//class RbEntry
protected transient RbEntry _root = null;
protected transient int _size = 0;
protected transient int _hashCode = 0;
public TreeArray() {
}
/** Constructor with a collection.
* @param c the collection to add; null to ignore
*/
public TreeArray(Collection c) {
this();
if (c != null)
addAll(c);
}
//-- its own extension --//
/**
* 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.
* <p>All elements are assumed to implement Comparable.
*/
public final void addByOrder(Object element) {
int j = search(element);
if (j < 0)
j = -j-1;
add(j, element);
}
/**
* 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.
*/
public final void addByOrder(Object element, Comparator c) {
int j = search(element, c);
if (j < 0)
j = -j-1;
add(j, 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.
* <p>All elements are assumed to implement Comparable.
*/
public final boolean removeByOrder(Object element) {
int j = search(element);
if (j >= 0) {
remove(j);
return true;
}
return false;
}
/**
* 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.
*/
public final boolean removeByOrder(Object element, Comparator c) {
int j = search(element, c);
if (j >= 0) {
remove(j);
return true;
}
return false;
}
/**
* 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.
* <p>All elements are assumed to implement Comparable.
*/
public final void addAllByOrder(Collection cn) {
for (Iterator it = cn.iterator(); it.hasNext();)
addByOrder(it.next());
}
/**
* 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.
*/
public final void addAllByOrder(Collection cn, Comparator c) {
for (Iterator it = cn.iterator(); it.hasNext();)
addByOrder(it.next(), c);
}
/**
* 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, {@link #addByOrder(Object)}.
*
* <p>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.
*
* <p>For example, you might use a String to search the element,
* and your element's compareTo shall be implemented as follows.
*
* <pre><code>public int compareTo(Object o) {
* return o instanceof String ?
* _name.compareTo((String)o):
* _name.compareTo(((YourClass)o).getName());
*}
*/
public final int search(Object element) {
return Collections.binarySearch(this, element);
}
/**
* 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, {@link #addByOrder(Object, Comparator)}.
*
* <p>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 int search(Object element, Comparator c) {
return Collections.binarySearch(this, element, c);
}
/**
* Gets an element by its natural ordering.
* It is a shortcut of get(search(element)).
*
* @see #search(Object)
* @return null if not found
*/
public final Object getByOrder(Object element) {
int j = search(element);
return j >= 0 ? get(j): null;
}
/**
* Gets an element by its natural ordering.
* It is a shortcut of get(search(element, c)).
*
* @see #search(Object, Comparator)
* @return null if not found
*/
public final Object getByOrder(Object element, Comparator c) {
int j = search(element, c);
return j >= 0 ? get(j): null;
}
/**
* Sorts all elements ascendingly by the natural ordering.
* <p>All elements are assumed to implement Comparable.
*/
public final void sort() {
Collections.sort(this);
}
/**
* Sorts all elements ascendingly by the specified comparator.
*/
public final void sort(Comparator c) {
Collections.sort(this, c);
}
//-- overriding AbstractList --//
public final int size() {
return _size;
}
public final Object get(int index) {
return getRbEntry(index).getElement();
}
public Object set(int index, Object element) {
RbEntry p = getRbEntry(index);
Object old = p.getElement();
p.setElement(element);
return old;
}
public void add(int index, Object element) {
addEntry(index, element);
}
public Object remove(int index) {
RbEntry p = getRbEntry(index);
delete(p);
return p.getElement();
}
public final Iterator iterator() {
return listIterator();
}
public final ListIterator listIterator(int index) {
return new Iter(index);
}
/**
* Clears the whole list. Overrides it if the derived class has
* other data to clear. Note it doesn't call removeEx.
*
* <p>Note clear actually invokes RbEntry.clear to do the real
* cleanup. Deriving classes might override RbEntry.clear.
*/
public void clear() {
if (_root != null) {
_root.clear();
modCount++;
_size = 0;
_root = null;
}
}
//-- overriding ListX --//
protected final RbEntry getRbEntry(int index) {
checkRange(index);
int baseIndex = 0;
RbEntry p = _root;
do {
int thisIndex = baseIndex + p.leftNum;
if (index == thisIndex) {
return p;
} else if (index < thisIndex) {
p = p.left;
} else {
baseIndex = thisIndex + 1;
p = p.right;
}
} while (p != null); //it might be modified by someone else
throw new ConcurrentModificationException();
}
public final Entry getEntry(int index) {
return getRbEntry(index);
}
protected final int indexOfEntry(RbEntry p) {
if (p.orphan)
return -1;
int v = p.leftNum;
RbEntry lowParent = p.firtLeftAncestor();
if (lowParent != null)
v += indexOfEntry(lowParent) + 1;
return v;
}
public final int indexOfEntry(Entry p) {
return indexOfEntry((RbEntry)p);
}
public int hashCode() {
if (_hashCode == 0)
_hashCode = super.hashCode();
return _hashCode;
}
//-- Extra features --//
public final ListIterator entryIterator(int index) {
return new EntryIter(index);
}
public final ListIterator entryIterator() {
return new EntryIter(0);
}
/**
* Creates an instance of RbEntry. Override it if necessary
*/
protected RbEntry newEntry(Object element) {
return new RbEntry(element);
}
public final Entry addEntry(Entry insertBefore, Object element) {
return insert(checkNotOrphan(insertBefore), newEntry(element));
}
public final Entry addEntry(int index, Object element) {
return insert(index, newEntry(element));
}
public final Entry addEntry(Object element) {
return addEntry(_size, element);
}
public final void removeEntry(Entry p) {
delete(checkNotOrphan(p));
}
public final Entry removeEntry(int index) {
return delete(index);
}
//-- utilities --/
/** Returns the first node. */
protected final RbEntry first() {
return _root==null ? null: _root.leftMost();
}
private static final boolean colorOf(RbEntry p) {
return (p == null ? BLACK : p.color);
}
private static final RbEntry parentOf(RbEntry p) {
return (p == null ? null: p.parent);
}
private static final void setColor(RbEntry p, boolean c) {
if (p != null) p.color = c;
}
private static final RbEntry leftOf(RbEntry p) {
return (p == null)? null: p.left;
}
private static final RbEntry rightOf(RbEntry p) {
return (p == null)? null: p.right;
}
protected final RbEntry insert(int index, RbEntry p) {
checkRangePlus(index); //index==_size is ok
return insert(index<_size ? getRbEntry(index): null, p);
}
private static final void changeAncestorLeftNum(RbEntry p, int diff) {
for (; p.parent!=null; p=p.parent)
if (p.parent.left == p)
p.parent.leftNum += diff;
}
/**
* All add methods are done thru this method. Override it if necessary.
*
* <p>Note: p is inserted <b>before</b> insertBefore.
*/
protected RbEntry insert(RbEntry insertBefore, final RbEntry p) {
assert !p.orphan;
if (_root == null) {
_root = p;
} else {
if (insertBefore != null && insertBefore.left == null) {
insertBefore.left = p;
} else {
insertBefore = insertBefore==null ? _root: insertBefore.left;
insertBefore = insertBefore.rightMost();
insertBefore.right = p;
}
p.parent = insertBefore;
changeAncestorLeftNum(p, 1);
}
fixAfterInsert(p); //fix up for red-black rule
incSize();
return p;
}
private final void rotateLeft(RbEntry x) {
RbEntry y = x.right;
x.right = y.left;
if (y.left != null)
y.left.parent = x;
y.parent = x.parent;
if (x.parent == null)
_root = y;
else if (x.parent.left == x)
x.parent.left = y;
else
x.parent.right = y;
y.left = x;
x.parent = y;
y.leftNum += x.leftNum+1;
}
private final void rotateRight(RbEntry y) {
RbEntry x = y.left;
y.left = x.right;
if (x.right != null)
x.right.parent = y;
x.parent = y.parent;
if (y.parent == null)
_root = x;
else if (y.parent.right == y)
y.parent.right = x;
else
y.parent.left = x;
x.right = y;
y.parent = x;
y.leftNum -= x.leftNum+1;
}
private final void fixAfterInsert(RbEntry x) {
x.color = RED;
while (x!=null && x!=_root && x.parent.color==RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
RbEntry y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
if (parentOf(parentOf(x)) != null)
rotateRight(parentOf(parentOf(x)));
}
} else {
RbEntry y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
if (parentOf(parentOf(x)) != null)
rotateLeft(parentOf(parentOf(x)));
}
}
}//while
_root.color = BLACK;
}
protected RbEntry delete(int index) {
RbEntry p = getRbEntry(index);
delete(p);
return p;
}
/**
* All remove methods are done thru this method. Override it if necessary.
*/
protected void delete(RbEntry p) {
assert !p.orphan;
if (p.left!=null && p.right!=null)
swapPosition(p.nextEntry(), p);
//Make sure at least one of left or right is null by
//swapping with next, whose left is null (right.leftMost)
changeAncestorLeftNum(p, -1);
decSize();
RbEntry replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
_root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
if (p.color == BLACK)
fixAfterDelete(replacement);
} else { // No children
if (p.parent == null) // size==1
_root = null;
else if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
}
p.setOrphan();
}
/**
* Swap the linkages of two nodes in a tree. We cannot only swap the
* element field because the binding of entry and element have to remain.
*/
private final void swapPosition(RbEntry x, RbEntry y) {
// Save initial values.
RbEntry px = x.parent, lx = x.left, rx = x.right;
RbEntry py = y.parent, ly = y.left, ry = y.right;
boolean xWasLeftChild = px != null && x == px.left;
boolean yWasLeftChild = py != null && y == py.left;
// Swap, handling special cases of one being the other's parent.
if (x == py) { // x was y's parent
x.parent = y;
if (yWasLeftChild) {
y.left = x;
y.right = rx;
} else {
y.right = x;
y.left = lx;
}
} else {
x.parent = py;
if (py != null) {
if (yWasLeftChild)
py.left = x;
else
py.right = x;
}
y.left = lx;
y.right = rx;
}
if (y == px) { // y was x's parent
y.parent = x;
if (xWasLeftChild) {
x.left = y;
x.right = ry;
} else {
x.right = y;
x.left = ly;
}
} else {
y.parent = px;
if (px != null) {
if (xWasLeftChild)
px.left = y;
else
px.right = y;
}
x.left = ly;
x.right = ry;
}
// Fix children's parent pointers
if (x.left != null)
x.left.parent = x;
if (x.right != null)
x.right.parent = x;
if (y.left != null)
y.left.parent = y;
if (y.right != null)
y.right.parent = y;
// Swap colors
boolean c = x.color;
x.color = y.color;
y.color = c;
// Swap leftNum
int v = x.leftNum;
x.leftNum = y.leftNum;
y.leftNum = v;
// Check if root changed
if (_root == x)
_root = y;
else if (_root == y)
_root = x;
}
private void fixAfterDelete(RbEntry x) {
while (x != _root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
RbEntry sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = _root;
}
} else { // symmetric
RbEntry sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = _root;
}
}
}
setColor(x, BLACK);
}
protected final void incSize() {modCount++; _size++; }
protected final void decSize() {modCount++; _size--; }
protected final void checkRange(int index) {
if (index >= _size || index < 0)
indexOutOfBounds(index);
}
protected final void checkRangePlus(int index) {
if (index > _size || index < 0)
indexOutOfBounds(index);
}
protected final void indexOutOfBounds(int index) {
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + _size);
}
/**
* Converts and checks whether it is not orphan
*/
protected final RbEntry checkNotOrphan(Entry entry) {
RbEntry p = (RbEntry)entry;
if (p.orphan)
throw new IllegalStateException();
return p;
}
private class EntryIter implements ListIterator {
private RbEntry _cursor;
private RbEntry _lastRet = null;
private int _expectedModCount;
private EntryIter(int index) {
checkRangePlus(index); //index==_size is ok
_cursor = index<_size ? getRbEntry(index): null;
_expectedModCount = modCount;
}
public final boolean hasNext() {
checkComodification();
return _cursor != null;
}
public Object next() {
checkComodification();
if (_cursor == null)
throw new NoSuchElementException();
_lastRet = _cursor;
Object obj = _cursor;
_cursor = _cursor.nextEntry();
return obj;
}
public final boolean hasPrevious() {
checkComodification();
if (_cursor == null)
return _size > 0;
else
return _cursor.previousEntry() != null;
}
public Object previous() {
checkComodification();
if (_cursor == null) {
if (_size == 0)
throw new NoSuchElementException();
_cursor = getRbEntry(_size-1);
} else {
RbEntry prev = _cursor.previousEntry();
if (prev == null)
throw new NoSuchElementException();
_cursor = prev;
}
_lastRet = _cursor;
return _cursor;
}
public final int nextIndex() {
return _cursor==null ? _size: indexOfEntry(_cursor);
}
public final int previousIndex() {
return _cursor==null ? _size-1: indexOfEntry(_cursor)-1;
}
public final void remove() {
if (_lastRet == null)
throw new IllegalStateException();
checkComodification();
if (_lastRet == _cursor)
_cursor = _cursor.nextEntry();
delete(_lastRet);
_expectedModCount = modCount;
_lastRet = null;
}
public final void set(Object obj) {
if (_lastRet == null)
throw new IllegalStateException();
checkComodification();
_lastRet.setElement(obj);
//no need to update _expectdModCount here
}
public final Object get() {
return _lastRet.getElement();
}
public final void add(Object obj) {
checkComodification();
insert(_cursor, newEntry(obj));
_expectedModCount = modCount;
}
private final void checkComodification() {
if (modCount != _expectedModCount)
throw new ConcurrentModificationException();
}
}//EntryIter
private class Iter extends EntryIter {
private Iter(int index) {
super(index);
}
public final Object next() {
return ((RbEntry)super.next()).getElement();
}
public final Object previous() {
return ((RbEntry)super.previous()).getElement();
}
}//Iter
//-- cloneable --//
public Object clone() {
TreeArray clone;
try {
clone = (TreeArray)super.clone();
}catch(CloneNotSupportedException e) {
throw new InternalError();
}
//Put clone into "virgin" state
clone._size = 0;
clone._root = null;
clone.modCount = 0;
// Initialize clone with our elements
for (RbEntry p = first(); p != null; p = p.nextEntry())
clone.add(p.getElement());
return clone;
}
//-- Serializable --//
//NOTE: they must be declared as private
private synchronized void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
s.writeInt(_size);
for (RbEntry p = first(); p != null; p = p.nextEntry())
s.writeObject(p.getElement());
}
private synchronized void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
int size = s.readInt();
for (int i=0; i<size; i++)
add(s.readObject());
}
}
The table below shows all metrics for TreeArray.java.
| Metric | Value | Description | |
|---|---|---|---|
| BLOCKS | 136.00 | Number of blocks | |
| BLOCK_COMMENT | 18.00 | Number of block comment lines | |
| COMMENTS | 220.00 | Comment lines | |
| COMMENT_DENSITY | 0.42 | Comment density | |
| COMPARISONS | 119.00 | Number of comparison operators | |
| CYCLOMATIC | 203.00 | Cyclomatic complexity | |
| DECL_COMMENTS | 39.00 | Comments in declarations | |
| DOC_COMMENT | 181.00 | Number of javadoc comment lines | |
| ELOC | 530.00 | Effective lines of code | |
| EXEC_COMMENTS | 10.00 | Comments in executable code | |
| EXITS | 60.00 | Procedure exits | |
| FUNCTIONS | 89.00 | Number of function declarations | |
| HALSTEAD_DIFFICULTY | 148.78 | Halstead difficulty | |
| HALSTEAD_EFFORT | 0.00 | Halstead effort | |
| INTERFACE_COMPLEXITY | 183.00 | Interface complexity | |
| JAVA0001 | 0.00 | JAVA0001 Package name does not contain only lower case letters | |
| JAVA0002 | 0.00 | JAVA0002 Package name does not begin with a top level domain name or country code | |
| JAVA0003 | 0.00 | JAVA0003 Minimize use of on-demand (.*) imports | |
| JAVA0004 | 0.00 | JAVA0004 Unnecessary import from java.lang | |
| JAVA0005 | 0.00 | JAVA0005 Imports not in specified order | |
| JAVA0006 | 0.00 | JAVA0006 Empty finally block | |
| JAVA0007 | 0.00 | JAVA0007 Should not declare public field | |
| JAVA0008 | 0.00 | JAVA0008 Empty catch block | |
| JAVA0009 | 0.00 | JAVA0009 Protected member in final class | |
| JAVA0010 | 0.00 | JAVA0010 Non-instantiable class does not contain a non-private static member | |
| JAVA0011 | 0.00 | JAVA0011 Abstract class does not contain an abstract method | |
| JAVA0012 | 0.00 | JAVA0012 Non-constructor method with same name as declaring class | |
| JAVA0013 | 0.00 | JAVA0013 Non-blank final field is not static | |
| JAVA0014 | 0.00 | JAVA0014 Class with only static members has non-private constructor | |
| JAVA0015 | 0.00 | JAVA0015 Package class contains public nested type | |
| JAVA0016 | 0.00 | JAVA0016 Abstract class contains public constructor | |
| JAVA0017 | 0.00 | JAVA0017 Class name does not have required form | |
| JAVA0018 | 0.00 | JAVA0018 Method name does not have required form | |
| JAVA0019 | 0.00 | JAVA0019 Interface name does not have required form | |
| JAVA0020 | 6.00 | JAVA0020 Field name does not have required form | |
| JAVA0021 | 0.00 | JAVA0021 Interface method name does not have required form | |
| JAVA0022 | 0.00 | JAVA0022 Static final field name does not have required form | |
| JAVA0023 | 0.00 | JAVA0023 Empty finalize method | |
| JAVA0024 | 0.00 | JAVA0024 Empty class | |
| JAVA0025 | 0.00 | JAVA0025 Method override is empty | |
| JAVA0026 | 0.00 | JAVA0026 Finalize method with parameters | |
| JAVA0029 | 0.00 | JAVA0029 Private method not used | |
| JAVA0030 | 0.00 | JAVA0030 Private field not used | |
| JAVA0031 | 0.00 | JAVA0031 Case statement not properly closed | |
| JAVA0032 | 0.00 | JAVA0032 Switch statement missing default | |
| JAVA0033 | 0.00 | JAVA0033 default: not last case in switch statement | |
| JAVA0034 | 56.00 | JAVA0034 Missing braces in if statement | |
| JAVA0035 | 10.00 | JAVA0035 Missing braces in for statement | |
| JAVA0036 | 0.00 | JAVA0036 Missing braces in while statement | |
| JAVA0038 | 0.00 | JAVA0038 Non-case label in switch statement | |
| JAVA0039 | 0.00 | JAVA0039 Break statement with label | |
| JAVA0040 | 0.00 | JAVA0040 Switch statement contains N cases (maximum: M) | |
| JAVA0041 | 0.00 | JAVA0041 Nested synchronized block | |
| JAVA0042 | 0.00 | JAVA0042 Empty synchronized statement | |
| JAVA0043 | 0.00 | JAVA0043 Inner class does not use outer class | |
| JAVA0044 | 0.00 | JAVA0044 Serializable class with no instance variables | |
| JAVA0045 | 0.00 | JAVA0045 Serializable class with only transient fields | |
| JAVA0046 | 0.00 | JAVA0046 Name of class not derived from Exception ends with 'Exception' | |
| JAVA0047 | 0.00 | JAVA0047 Serializable class derives from invalid base class | |
| JAVA0048 | 0.00 | JAVA0048 Name of class derived from Exception does not end with 'Exception' | |
| JAVA0049 | 0.00 | JAVA0049 Nested block at depth N (maximum: M) | |
| JAVA0050 | 0.00 | JAVA0050 Class derives from java.lang.Error | |
| JAVA0051 | 0.00 | JAVA0051 Class derives from java.lang.RuntimeException | |
| JAVA0052 | 0.00 | JAVA0052 Class derives from java.lang.Throwable | |
| JAVA0053 | 0.00 | JAVA0053 Unused label | |
| JAVA0054 | 0.00 | JAVA0054 Inheritance depth N exceeds maximum M | |
| JAVA0055 | 0.00 | JAVA0055 Class should be interface | |
| JAVA0056 | 0.00 | JAVA0056 Unnecessary abstract modifier for interface or annotation | |
| JAVA0057 | 0.00 | JAVA0057 Unnecessary default constructor | |
| JAVA0058 | 0.00 | JAVA0058 Constructor calls super() | |
| JAVA0059 | 0.00 | JAVA0059 Method override only calls super() | |
| JAVA0061 | 0.00 | JAVA0061 Inaccessible member in anonymous class | |
| JAVA0062 | 0.00 | JAVA0062 Public class missing public member or protected constructor | |
| JAVA0063 | 0.00 | JAVA0063 Identifier name should not contain '$' | |
| JAVA0064 | 0.00 | JAVA0064 N variations of identifier name (maximum: M) | |
| JAVA0065 | 0.00 | JAVA0065 Unnecessary final modifier for method in final class | |
| JAVA0066 | 0.00 | JAVA0066 Unnecessary modifier for interface nested type | |
| JAVA0067 | 0.00 | JAVA0067 Array descriptor on identifier name | |
| JAVA0068 | 0.00 | JAVA0068 Modifiers not declared in recommended order | |
| JAVA0071 | 0.00 | JAVA0071 Strings compared with == | |
| JAVA0073 | 0.00 | JAVA0073 Integer division in floating-point context | |
| JAVA0074 | 0.00 | JAVA0074 Use of Object.notify() | |
| JAVA0075 | 0.00 | JAVA0075 Method parameter hides field | |
| JAVA0076 | 0.00 | JAVA0076 Use of magic number | |
| JAVA0077 | 0.00 | JAVA0077 Private field not used in declaring class | |
| JAVA0078 | 0.00 | JAVA0078 Floating point values compared with == | |
| JAVA0079 | 0.00 | JAVA0079 Use of instance to reference static member | |
| JAVA0080 | 0.00 | JAVA0080 Import declaration not used | |
| JAVA0081 | 0.00 | JAVA0081 Boolean literal in comparison | |
| JAVA0082 | 0.00 | JAVA0082 Unnecessary widening cast | |
| JAVA0083 | 0.00 | JAVA0083 Unnecessary instanceof test | |
| JAVA0084 | 0.00 | JAVA0084 Should use compound assignment operator | |
| JAVA0085 | 0.00 | JAVA0085 Use of sun.* class | |
| JAVA0087 | 0.00 | JAVA0087 Use of Thread.sleep() | |
| JAVA0089 | 0.00 | JAVA0089 Use of restricted package | |
| JAVA0092 | 0.00 | JAVA0092 Use of restricted type | |
| JAVA0093 | 0.00 | JAVA0093 Redundant assignment | |
| JAVA0094 | 0.00 | JAVA0094 Field hides a superclass field | |
| JAVA0095 | 0.00 | JAVA0095 Uninitialized private field | |
| JAVA0096 | 0.00 | JAVA0096 Field in nested class hides outer field | |
| JAVA0098 | 0.00 | JAVA0098 Minimize use of implicit field initializers | |
| JAVA0100 | 0.00 | JAVA0100 Class contains N non-final fields (maximum: M) | |
| JAVA0101 | 0.00 | JAVA0101 Unnecessary modifier for field in interface | |
| JAVA0102 | 0.00 | JAVA0102 Last statement in finalize() not super.finalize() | |
| JAVA0103 | 0.00 | JAVA0103 Explicit call to finalize() | |
| JAVA0104 | 0.00 | JAVA0104 finalize() only calls super.finalize() | |
| JAVA0105 | 0.00 | JAVA0105 Duplicate import declaration | |
| JAVA0106 | 0.00 | JAVA0106 Unnecessary import from current package | |
| JAVA0108 | 23.00 | JAVA0108 Incorrect javadoc: no @param tag for 'parameter' | |
| JAVA0109 | 0.00 | JAVA0109 Incorrect javadoc: no parameter 'parameter' | |
| JAVA0110 | 13.00 | JAVA0110 Incorrect javadoc: no @return tag | |
| JAVA0111 | 0.00 | JAVA0111 Incorrect javadoc: @return tag for void method | |
| JAVA0112 | 0.00 | JAVA0112 Incorrect javadoc: no exception 'exception' in throws | |
| JAVA0113 | 0.00 | JAVA0113 Incorrect javadoc: no @author tag | |
| JAVA0114 | 1.00 | JAVA0114 Incorrect javadoc: no @version tag | |
| JAVA0115 | 0.00 | JAVA0115 Incorrect javadoc: no @throws or @exception tag for 'exception' | |
| JAVA0116 | 0.00 | JAVA0116 Missing javadoc: field 'field' | |
| JAVA0117 | 16.00 | JAVA0117 Missing javadoc: method 'method' | |
| JAVA0118 | 0.00 | JAVA0118 Missing javadoc: type 'type' | |
| JAVA0119 | 0.00 | JAVA0119 Control variable changed within body of for loop | |
| JAVA0123 | 3.00 | JAVA0123 Use all three components of for loop | |
| JAVA0125 | 0.00 | JAVA0125 Continue statement with label | |
| JAVA0126 | 0.00 | JAVA0126 Method declares unchecked exception in throws | |
| JAVA0128 | 0.00 | JAVA0128 Public constructor in non-public class | |
| JAVA0130 | 0.00 | JAVA0130 Non-static method does not use instance fields | |
| JAVA0131 | 0.00 | JAVA0131 Compatible method does not override base | |
| JAVA0132 | 1.00 | JAVA0132 Method overload with compatible signature | |
| JAVA0133 | 0.00 | JAVA0133 Non-synchronized method overrides synchronized method | |
| JAVA0135 | 1.00 | JAVA0135 Only one of Object.equals and Object.hashCode defined: missing 'method' | |
| JAVA0136 | 1.00 | JAVA0136 N methods defined in class (maximum: M) | |
| JAVA0137 | 0.00 | JAVA0137 Non-abstract class missing constructor | |
| JAVA0138 | 0.00 | JAVA0138 N parameters defined for method (maximum: M) | |
| JAVA0139 | 0.00 | JAVA0139 Definition of main other than public static void main(java.lang.String[]) | |
| JAVA0141 | 0.00 | JAVA0141 Unnecessary modifier for method in interface | |
| JAVA0143 | 2.00 | JAVA0143 Synchronized method | |
| JAVA0144 | 0.00 | JAVA0144 Line exceeds maximum M characters | |
| JAVA0145 | 1891.00 | JAVA0145 Tab character used in source file | |
| JAVA0150 | 1.00 | JAVA0150 java.lang.Error (or subclass) thrown | |
| JAVA0153 | 0.00 | JAVA0153 Inefficient conversion of integer to string | |
| JAVA0159 | 0.00 | JAVA0159 Inefficient conversion of string to integer | |
| JAVA0160 | 0.00 | JAVA0160 Method does not throw specified exception | |
| JAVA0161 | 0.00 | JAVA0161 Conditional wait() not in loop | |
| JAVA0163 | 0.00 | JAVA0163 Empty statement | |
| JAVA0165 | 0.00 | JAVA0165 Conflicting return statement in finally block | |
| JAVA0166 | 0.00 | JAVA0166 Generic exception caught | |
| JAVA0167 | 0.00 | JAVA0167 ThreadDeath not rethrown | |
| JAVA0169 | 0.00 | JAVA0169 Unnecessary catch block: exception 'exception' | |
| JAVA0170 | 0.00 | JAVA0170 Caught exception not derived from java.lang.Exception | |
| JAVA0171 | 0.00 | JAVA0171 Unused local variable | |
| JAVA0173 | 0.00 | JAVA0173 Unused method parameter | |
| JAVA0174 | 0.00 | JAVA0174 Assigned local variable never used | |
| JAVA0175 | 0.00 | JAVA0175 Successive assignment to variable | |
| JAVA0176 | 0.00 | JAVA0176 Local variable name does not have required form | |
| JAVA0177 | 1.00 | JAVA0177 Variable declaration missing initializer | |
| JAVA0179 | 0.00 | JAVA0179 Local variable hides visible field | |
| JAVA0233 | 0.00 | JAVA0233 Definition of serialVersionUID other than 'private static final long serialVersionUID' | |
| JAVA0234 | 0.00 | JAVA0234 Class is Serializable but does not define serialVersionUID | |
| JAVA0235 | 0.00 | JAVA0235 Class defines serialVersionUID but does not implement Serializable | |
| JAVA0236 | 0.00 | JAVA0236 Attempt to clone an object which does not implement Cloneable | |
| JAVA0237 | 0.00 | JAVA0237 Class implements Cloneable but does not have public clone method | |
| JAVA0238 | 0.00 | JAVA0238 Clone method does not call super.clone() | |
| JAVA0239 | 0.00 | JAVA0239 Class declares 'readObject' or 'writeObject' but does not implement Serializable | |
| JAVA0240 | 0.00 | JAVA0240 Serializable class which declares readObject or writeObject but not both | |
| JAVA0241 | 0.00 | JAVA0241 'readObject' or 'writeObject' should be declared private in Serializable class | |
| JAVA0242 | 0.00 | JAVA0242 Transient field in non-Serializable class | |
| JAVA0243 | 0.00 | JAVA0243 'readResolve' or 'writeReplace' should be declared private or protected | |
| JAVA0244 | 0.00 | JAVA0244 Field or method name in subclass differs only by case from inherited field or method | |
| JAVA0245 | 0.00 | JAVA0245 JUnit TestCase with non-trivial constructor | |
| JAVA0246 | 0.00 | JAVA0246 JUnit assertXXX statement missing message parameter | |
| JAVA0247 | 0.00 | JAVA0247 JUnit 'setUp()' and 'tearDown()' should call super method | |
| JAVA0248 | 0.00 | JAVA0248 JUnit method 'setUp' or 'tearDown' with incorrect signature | |
| JAVA0249 | 0.00 | JAVA0249 JUnit TestCase 'suite()' should be declared static | |
| JAVA0250 | 0.00 | JAVA0250 JUnit TestCase declares testXXX method with incorrect signature | |
| JAVA0251 | 0.00 | JAVA0251 Use '%n' for line breaks in printf/format for platform independence | |
| JAVA0252 | 0.00 | JAVA0252 'enum' is a Java 1.5 reserved word | |
| JAVA0253 | 0.00 | JAVA0253 Not all enum constants consumed in switch statement | |
| JAVA0254 | 2.00 | JAVA0254 Use enhanced for loop construct instead of Iterator | |
| JAVA0255 | 0.00 | JAVA0255 Result of method invocation not used | |
| JAVA0256 | 0.00 | JAVA0256 Assignment of external collection/array to field | |
| JAVA0257 | 0.00 | JAVA0257 Use of 'Constant Interface' anti-pattern | |
| JAVA0258 | 0.00 | JAVA0258 Implement Iterable for foreach compatibility | |
| JAVA0259 | 0.00 | JAVA0259 Return of collection/array field | |
| JAVA0260 | 0.00 | JAVA0260 Use 'enum' instead of Enumerated Type pattern | |
| JAVA0261 | 0.00 | JAVA0261 Use specialized Enum collection types | |
| JAVA0262 | 0.00 | JAVA0262 Use of char in integer context | |
| JAVA0263 | 0.00 | JAVA0263 Long literal ends with 'l' instead of 'L' | |
| JAVA0264 | 0.00 | JAVA0264 Integer math in long context - check for overflow | |
| JAVA0265 | 0.00 | JAVA0265 Use of Throwable.printStackTrace() | |
| JAVA0266 | 0.00 | JAVA0266 Use of System.out | |
| JAVA0267 | 0.00 | JAVA0267 Use of System.err | |
| JAVA0269 | 0.00 | JAVA0269 Contents of StringBuffer never used | |
| JAVA0270 | 0.00 | JAVA0270 Use Java 5.0 enhanced for loop construct to iterate over all elements in an array | |
| JAVA0271 | 0.00 | JAVA0271 Minimize use of on-demand (.*) static imports | |
| JAVA0272 | 0.00 | JAVA0272 Thread.run() called | |
| JAVA0273 | 0.00 | JAVA0273 Non-final derivative of Thread calls start() in constructor | |
| JAVA0274 | 1.00 | JAVA0274 Serializable class has a synchronized readObject() | |
| JAVA0275 | 0.00 | JAVA0275 Serializable class has a synchronized writeObject() and no other synchronized methods | |
| JAVA0276 | 0.00 | JAVA0276 Unnecessary use of String constructor | |
| JAVA0277 | 1.00 | JAVA0277 Iterator.next() implementation does not throw NoSuchElementException | |
| JAVA0278 | 0.00 | JAVA0278 Unnecessary use of Boolean constructor | |
| JAVA0279 | 0.00 | JAVA0279 Serialization method readObject or readObjectNoData calls an overridable method | |
| JAVA0280 | 0.00 | JAVA0280 IllegalMonitorStateException caught | |
| JAVA0281 | 0.00 | JAVA0281 Iterator.next() not called in loop | |
| JAVA0282 | 0.00 | JAVA0282 Call to Iterator.next() in loop which does not test Iterator.hasNext() | |
| JAVA0283 | 0.00 | JAVA0283 Control variable not updated in loop body | |
| JAVA0284 | 0.00 | JAVA0284 Explicit garbage collection | |
| JAVA0285 | 0.00 | JAVA0285 Dereference of potentially null variable | |
| JAVA0286 | 0.00 | JAVA0286 Dereference of null variable | |
| JAVA0287 | 0.00 | JAVA0287 Unnecessary null check | |
| JAVA0288 | 0.00 | JAVA0288 Inconsistent null check | |
| LINES | 976.00 | Number of lines in the source file | |
| LINE_COMMENT | 21.00 | Number of line comments | |
| LOC | 646.00 | Lines of code | |
| LOGICAL_LINES | 341.00 | Number of statements | |
| LOOPS | 13.00 | Number of loops | |
| NEST_DEPTH | 5.00 | Maximum nesting depth | |
| OPERANDS | 1416.00 | Number of operands | |
| OPERATORS | 2753.00 | Number of operators | |
| PARAMS | 69.00 | Number of formal parameter declarations | |
| PROGRAM_LENGTH | 4169.00 | Halstead program length | |
| PROGRAM_VOCAB | 334.00 | Halstead program vocabulary | |
| PROGRAM_VOLUME | 0.00 | Halstead program volume | |
| RETURNS | 114.00 | Number of return points from functions | |
| SIZE | 24507.00 | Size of the file in bytes | |
| UNIQUE_OPERANDS | 276.00 | Number of unique operands | |
| UNIQUE_OPERATORS | 58.00 | Number of unique operators | |
| WHITESPACE | 110.00 | Number of whitespace lines | |