0001: /* TreeArray.java
0002:
0003: {{IS_NOTE
0004:
0005: Purpose: Red-black tree based array implementation of List interface.
0006: Description:
0007: History:
0008: 2001/5/9, Tom M. Yeh: Created.
0009:
0010: }}IS_NOTE
0011:
0012: Copyright (C) 2001 Potix Corporation. All Rights Reserved.
0013:
0014: {{IS_RIGHT
0015: This program is distributed under GPL Version 2.0 in the hope that
0016: it will be useful, but WITHOUT ANY WARRANTY.
0017: }}IS_RIGHT
0018: */
0019: package org.zkoss.util;
0020:
0021: import java.util.*;
0022:
0023: /**
0024: * Red-black tree based array implementation of List interface.
0025: * Unlike LinkedList, the random access by index is as fast as log(n).
0026: * Unlike ArrayList, the insertion is as fast as log(n). It is
0027: * a great compromise between randown and sequential access.
0028: *
0029: * <p>In additions, it extends the features by also implementing
0030: * ListX.
0031: *
0032: * <p>The deriving class might override newEntry if it also
0033: * extends RbEntry; override insert(RbEntry, RbEntry) for adding element;
0034: * override delete(RbEntry) for removing element; clear() for
0035: * clearing the whole list.
0036: *
0037: * <p>Also, RbEntry.setElement might be overrided if the deriving class
0038: * wants to do something when the set method is called.
0039: *
0040: * <p>The iterator method is designed such that next() will proceed correctly
0041: * even if getElement() throws an exception.
0042: *
0043: * <p>The original algorithm is invented by Henri Chen.
0044: *
0045: * @author tomyeh
0046: * @see ListX
0047: */
0048: public class TreeArray extends AbstractList implements ListX,
0049: Cloneable, java.io.Serializable {
0050: private static final long serialVersionUID = 20060622L;
0051:
0052: protected static final boolean RED = false;
0053: protected static final boolean BLACK = true;
0054:
0055: /**
0056: * Caller shall use AbstractList.Entry instead of RbEntry for
0057: * better portability.
0058: */
0059: protected static class RbEntry implements Entry {
0060: protected Object element; //use setElement and getElement
0061: protected int leftNum; //# of elements on its left sub-tree
0062: protected RbEntry left;
0063: protected RbEntry right;
0064: protected RbEntry parent;
0065: protected boolean color; //a black node
0066: protected boolean orphan = false; //not belonging to any list
0067:
0068: protected RbEntry(Object element) {
0069: this .element = element;
0070: }
0071:
0072: /**
0073: * Override it if you want to something when an element is retrieved.
0074: * All other parts that get element must invoke this method
0075: */
0076: public Object getElement() {
0077: return this .element;
0078: }
0079:
0080: /**
0081: * Override it if you want to do something when an element
0082: * is set. All other parts that set element will invoke this method.
0083: */
0084: public void setElement(Object element) {
0085: this .element = element;
0086: }
0087:
0088: public final boolean isOrphan() {
0089: return orphan;
0090: }
0091:
0092: protected final RbEntry nextEntry() {
0093: if (right != null)
0094: return right.leftMost();
0095: return firstRightAncestor();
0096: }
0097:
0098: public final Entry next() {
0099: return nextEntry();
0100: }
0101:
0102: protected final RbEntry previousEntry() {
0103: if (left != null)
0104: return left.rightMost();
0105: return firtLeftAncestor();
0106: }
0107:
0108: public final Entry previous() {
0109: return previousEntry();
0110: }
0111:
0112: //-- utilities --/
0113: /**
0114: * Gets the leftmost leaf of the specified subtree.
0115: * It is the entry with lowest index in the subtree.
0116: */
0117: protected final RbEntry leftMost() {
0118: for (RbEntry p = this ;; p = p.left)
0119: if (p.left == null)
0120: return p;
0121: }
0122:
0123: /**
0124: * Gets the rihtmost leaf of the specified subtree.
0125: * It is the entry with highest index in the subtree.
0126: */
0127: protected final RbEntry rightMost() {
0128: for (RbEntry p = this ;; p = p.right)
0129: if (p.right == null)
0130: return p;
0131: }
0132:
0133: /**
0134: * Gets the first ancestor at the left of the specified entry.
0135: * "At the left" we mean the returned ancesor's right is the entry
0136: * or its ancestor. It is also the first parent with lower index.
0137: */
0138: protected final RbEntry firtLeftAncestor() {
0139: for (RbEntry p = this ; p.parent != null; p = p.parent)
0140: if (p.parent.right == p)
0141: return p.parent;
0142: return null;
0143: }
0144:
0145: /**
0146: * Gets the first parent at the right of the specified entry.
0147: * "At the right" we mean the returned ancesor's right is the entry
0148: * or its ancestor. It is also the first parent with higer index.
0149: */
0150: protected final RbEntry firstRightAncestor() {
0151: for (RbEntry p = this ; p.parent != null; p = p.parent)
0152: if (p.parent.left == p)
0153: return p.parent;
0154: return null;
0155: }
0156:
0157: //It doesn't maintain the tree but reset itself as an orphan.
0158: private final void setOrphan() {
0159: orphan = true;
0160: left = right = parent = null;
0161: }
0162:
0163: /**
0164: * Called by TreeArray.clear to do clear recursively.
0165: * Since it always be invoked to clear the whole tree,
0166: * it doesn't have to maintain leftNum or other tree info.
0167: * <p>However, this.element is kept.
0168: */
0169: protected void clear() {
0170: if (left != null)
0171: left.clear();
0172: if (right != null)
0173: right.clear();
0174: setOrphan();
0175: }
0176: }//class RbEntry
0177:
0178: protected transient RbEntry _root = null;
0179: protected transient int _size = 0;
0180: protected transient int _hashCode = 0;
0181:
0182: public TreeArray() {
0183: }
0184:
0185: /** Constructor with a collection.
0186: * @param c the collection to add; null to ignore
0187: */
0188: public TreeArray(Collection c) {
0189: this ();
0190: if (c != null)
0191: addAll(c);
0192: }
0193:
0194: //-- its own extension --//
0195: /**
0196: * Adds an element by its natural ordering.
0197: * This array must be sorted into ascending order according to
0198: * the natural ordering. To sort, either sort
0199: * or add all elements by order.
0200: * <p>All elements are assumed to implement Comparable.
0201: */
0202: public final void addByOrder(Object element) {
0203: int j = search(element);
0204: if (j < 0)
0205: j = -j - 1;
0206: add(j, element);
0207: }
0208:
0209: /**
0210: * Adds an element by the specified comparator.
0211: * This array must be sorted into ascending order according to
0212: * the specified comparator. To sort, either sort
0213: * or add all elements by order.
0214: */
0215: public final void addByOrder(Object element, Comparator c) {
0216: int j = search(element, c);
0217: if (j < 0)
0218: j = -j - 1;
0219: add(j, element);
0220: }
0221:
0222: /**
0223: * Removes an element by its natural ordering.
0224: * This array must be sorted into ascending order according to
0225: * the natural ordering. To sort, either sort
0226: * or add all elements by order.
0227: * <p>All elements are assumed to implement Comparable.
0228: */
0229: public final boolean removeByOrder(Object element) {
0230: int j = search(element);
0231: if (j >= 0) {
0232: remove(j);
0233: return true;
0234: }
0235: return false;
0236: }
0237:
0238: /**
0239: * Removes an element by the specified comparator.
0240: * This array must be sorted into ascending order according to
0241: * the specified comparator. To sort, either sort
0242: * or add all elements by order.
0243: */
0244: public final boolean removeByOrder(Object element, Comparator c) {
0245: int j = search(element, c);
0246: if (j >= 0) {
0247: remove(j);
0248: return true;
0249: }
0250: return false;
0251: }
0252:
0253: /**
0254: * Adds all elements by their natural ordering.
0255: * This array must be sorted into ascending order according to
0256: * the natural ordering. To sort, either sort
0257: * or add all elements by order.
0258: * <p>All elements are assumed to implement Comparable.
0259: */
0260: public final void addAllByOrder(Collection cn) {
0261: for (Iterator it = cn.iterator(); it.hasNext();)
0262: addByOrder(it.next());
0263: }
0264:
0265: /**
0266: * Adds all elements by the specified comparator.
0267: * This array must be sorted into ascending order according to
0268: * the specified comparator. To sort, either sort
0269: * or add all elements by order.
0270: */
0271: public final void addAllByOrder(Collection cn, Comparator c) {
0272: for (Iterator it = cn.iterator(); it.hasNext();)
0273: addByOrder(it.next(), c);
0274: }
0275:
0276: /**
0277: * Searches an element by its natural ordering.
0278: * This array must be sorted into ascending order according to
0279: * the natural ordering. To sort, either sort
0280: * or add all elements by order, {@link #addByOrder(Object)}.
0281: *
0282: * <p>All elements are assumed to implement Comparable.
0283: * Note: the element argument of this method is passed as the argument
0284: * of the compareTo method. Thus, it is OK to pass any kind of object,
0285: * as long as the elements stored in this array is able to detect it.
0286: *
0287: * <p>For example, you might use a String to search the element,
0288: * and your element's compareTo shall be implemented as follows.
0289: *
0290: * <pre><code>public int compareTo(Object o) {
0291: * return o instanceof String ?
0292: * _name.compareTo((String)o):
0293: * _name.compareTo(((YourClass)o).getName());
0294: *}
0295: */
0296: public final int search(Object element) {
0297: return Collections.binarySearch(this , element);
0298: }
0299:
0300: /**
0301: * Searches an element by the specified comparator.
0302: * This array must be sorted into ascending order according to
0303: * the specified comparator. To sort, either sort
0304: * or add all elements by order, {@link #addByOrder(Object, Comparator)}.
0305: *
0306: * <p>All elements are assumed to implement Comparable.
0307: * Note: the element argument of this method is passed as the argument
0308: * of the compareTo method. Thus, it is OK to pass any kind of object,
0309: * as long as the elements stored in this array is able to detect it.
0310: */
0311: public final int search(Object element, Comparator c) {
0312: return Collections.binarySearch(this , element, c);
0313: }
0314:
0315: /**
0316: * Gets an element by its natural ordering.
0317: * It is a shortcut of get(search(element)).
0318: *
0319: * @see #search(Object)
0320: * @return null if not found
0321: */
0322: public final Object getByOrder(Object element) {
0323: int j = search(element);
0324: return j >= 0 ? get(j) : null;
0325: }
0326:
0327: /**
0328: * Gets an element by its natural ordering.
0329: * It is a shortcut of get(search(element, c)).
0330: *
0331: * @see #search(Object, Comparator)
0332: * @return null if not found
0333: */
0334: public final Object getByOrder(Object element, Comparator c) {
0335: int j = search(element, c);
0336: return j >= 0 ? get(j) : null;
0337: }
0338:
0339: /**
0340: * Sorts all elements ascendingly by the natural ordering.
0341: * <p>All elements are assumed to implement Comparable.
0342: */
0343: public final void sort() {
0344: Collections.sort(this );
0345: }
0346:
0347: /**
0348: * Sorts all elements ascendingly by the specified comparator.
0349: */
0350: public final void sort(Comparator c) {
0351: Collections.sort(this , c);
0352: }
0353:
0354: //-- overriding AbstractList --//
0355: public final int size() {
0356: return _size;
0357: }
0358:
0359: public final Object get(int index) {
0360: return getRbEntry(index).getElement();
0361: }
0362:
0363: public Object set(int index, Object element) {
0364: RbEntry p = getRbEntry(index);
0365: Object old = p.getElement();
0366: p.setElement(element);
0367: return old;
0368: }
0369:
0370: public void add(int index, Object element) {
0371: addEntry(index, element);
0372: }
0373:
0374: public Object remove(int index) {
0375: RbEntry p = getRbEntry(index);
0376: delete(p);
0377: return p.getElement();
0378: }
0379:
0380: public final Iterator iterator() {
0381: return listIterator();
0382: }
0383:
0384: public final ListIterator listIterator(int index) {
0385: return new Iter(index);
0386: }
0387:
0388: /**
0389: * Clears the whole list. Overrides it if the derived class has
0390: * other data to clear. Note it doesn't call removeEx.
0391: *
0392: * <p>Note clear actually invokes RbEntry.clear to do the real
0393: * cleanup. Deriving classes might override RbEntry.clear.
0394: */
0395: public void clear() {
0396: if (_root != null) {
0397: _root.clear();
0398: modCount++;
0399: _size = 0;
0400: _root = null;
0401: }
0402: }
0403:
0404: //-- overriding ListX --//
0405: protected final RbEntry getRbEntry(int index) {
0406: checkRange(index);
0407:
0408: int baseIndex = 0;
0409: RbEntry p = _root;
0410: do {
0411: int this Index = baseIndex + p.leftNum;
0412: if (index == this Index) {
0413: return p;
0414: } else if (index < this Index) {
0415: p = p.left;
0416: } else {
0417: baseIndex = this Index + 1;
0418: p = p.right;
0419: }
0420: } while (p != null); //it might be modified by someone else
0421: throw new ConcurrentModificationException();
0422: }
0423:
0424: public final Entry getEntry(int index) {
0425: return getRbEntry(index);
0426: }
0427:
0428: protected final int indexOfEntry(RbEntry p) {
0429: if (p.orphan)
0430: return -1;
0431:
0432: int v = p.leftNum;
0433: RbEntry lowParent = p.firtLeftAncestor();
0434: if (lowParent != null)
0435: v += indexOfEntry(lowParent) + 1;
0436: return v;
0437: }
0438:
0439: public final int indexOfEntry(Entry p) {
0440: return indexOfEntry((RbEntry) p);
0441: }
0442:
0443: public int hashCode() {
0444: if (_hashCode == 0)
0445: _hashCode = super .hashCode();
0446: return _hashCode;
0447: }
0448:
0449: //-- Extra features --//
0450: public final ListIterator entryIterator(int index) {
0451: return new EntryIter(index);
0452: }
0453:
0454: public final ListIterator entryIterator() {
0455: return new EntryIter(0);
0456: }
0457:
0458: /**
0459: * Creates an instance of RbEntry. Override it if necessary
0460: */
0461: protected RbEntry newEntry(Object element) {
0462: return new RbEntry(element);
0463: }
0464:
0465: public final Entry addEntry(Entry insertBefore, Object element) {
0466: return insert(checkNotOrphan(insertBefore), newEntry(element));
0467: }
0468:
0469: public final Entry addEntry(int index, Object element) {
0470: return insert(index, newEntry(element));
0471: }
0472:
0473: public final Entry addEntry(Object element) {
0474: return addEntry(_size, element);
0475: }
0476:
0477: public final void removeEntry(Entry p) {
0478: delete(checkNotOrphan(p));
0479: }
0480:
0481: public final Entry removeEntry(int index) {
0482: return delete(index);
0483: }
0484:
0485: //-- utilities --/
0486: /** Returns the first node. */
0487: protected final RbEntry first() {
0488: return _root == null ? null : _root.leftMost();
0489: }
0490:
0491: private static final boolean colorOf(RbEntry p) {
0492: return (p == null ? BLACK : p.color);
0493: }
0494:
0495: private static final RbEntry parentOf(RbEntry p) {
0496: return (p == null ? null : p.parent);
0497: }
0498:
0499: private static final void setColor(RbEntry p, boolean c) {
0500: if (p != null)
0501: p.color = c;
0502: }
0503:
0504: private static final RbEntry leftOf(RbEntry p) {
0505: return (p == null) ? null : p.left;
0506: }
0507:
0508: private static final RbEntry rightOf(RbEntry p) {
0509: return (p == null) ? null : p.right;
0510: }
0511:
0512: protected final RbEntry insert(int index, RbEntry p) {
0513: checkRangePlus(index); //index==_size is ok
0514: return insert(index < _size ? getRbEntry(index) : null, p);
0515: }
0516:
0517: private static final void changeAncestorLeftNum(RbEntry p, int diff) {
0518: for (; p.parent != null; p = p.parent)
0519: if (p.parent.left == p)
0520: p.parent.leftNum += diff;
0521: }
0522:
0523: /**
0524: * All add methods are done thru this method. Override it if necessary.
0525: *
0526: * <p>Note: p is inserted <b>before</b> insertBefore.
0527: */
0528: protected RbEntry insert(RbEntry insertBefore, final RbEntry p) {
0529: assert !p.orphan;
0530: if (_root == null) {
0531: _root = p;
0532: } else {
0533: if (insertBefore != null && insertBefore.left == null) {
0534: insertBefore.left = p;
0535: } else {
0536: insertBefore = insertBefore == null ? _root
0537: : insertBefore.left;
0538: insertBefore = insertBefore.rightMost();
0539: insertBefore.right = p;
0540: }
0541: p.parent = insertBefore;
0542:
0543: changeAncestorLeftNum(p, 1);
0544: }
0545:
0546: fixAfterInsert(p); //fix up for red-black rule
0547: incSize();
0548: return p;
0549: }
0550:
0551: private final void rotateLeft(RbEntry x) {
0552: RbEntry y = x.right;
0553: x.right = y.left;
0554: if (y.left != null)
0555: y.left.parent = x;
0556: y.parent = x.parent;
0557: if (x.parent == null)
0558: _root = y;
0559: else if (x.parent.left == x)
0560: x.parent.left = y;
0561: else
0562: x.parent.right = y;
0563: y.left = x;
0564: x.parent = y;
0565:
0566: y.leftNum += x.leftNum + 1;
0567: }
0568:
0569: private final void rotateRight(RbEntry y) {
0570: RbEntry x = y.left;
0571: y.left = x.right;
0572: if (x.right != null)
0573: x.right.parent = y;
0574: x.parent = y.parent;
0575: if (y.parent == null)
0576: _root = x;
0577: else if (y.parent.right == y)
0578: y.parent.right = x;
0579: else
0580: y.parent.left = x;
0581: x.right = y;
0582: y.parent = x;
0583:
0584: y.leftNum -= x.leftNum + 1;
0585: }
0586:
0587: private final void fixAfterInsert(RbEntry x) {
0588: x.color = RED;
0589: while (x != null && x != _root && x.parent.color == RED) {
0590: if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
0591: RbEntry y = rightOf(parentOf(parentOf(x)));
0592: if (colorOf(y) == RED) {
0593: setColor(parentOf(x), BLACK);
0594: setColor(y, BLACK);
0595: setColor(parentOf(parentOf(x)), RED);
0596: x = parentOf(parentOf(x));
0597: } else {
0598: if (x == rightOf(parentOf(x))) {
0599: x = parentOf(x);
0600: rotateLeft(x);
0601: }
0602: setColor(parentOf(x), BLACK);
0603: setColor(parentOf(parentOf(x)), RED);
0604: if (parentOf(parentOf(x)) != null)
0605: rotateRight(parentOf(parentOf(x)));
0606: }
0607: } else {
0608: RbEntry y = leftOf(parentOf(parentOf(x)));
0609: if (colorOf(y) == RED) {
0610: setColor(parentOf(x), BLACK);
0611: setColor(y, BLACK);
0612: setColor(parentOf(parentOf(x)), RED);
0613: x = parentOf(parentOf(x));
0614: } else {
0615: if (x == leftOf(parentOf(x))) {
0616: x = parentOf(x);
0617: rotateRight(x);
0618: }
0619: setColor(parentOf(x), BLACK);
0620: setColor(parentOf(parentOf(x)), RED);
0621: if (parentOf(parentOf(x)) != null)
0622: rotateLeft(parentOf(parentOf(x)));
0623: }
0624: }
0625: }//while
0626: _root.color = BLACK;
0627: }
0628:
0629: protected RbEntry delete(int index) {
0630: RbEntry p = getRbEntry(index);
0631: delete(p);
0632: return p;
0633: }
0634:
0635: /**
0636: * All remove methods are done thru this method. Override it if necessary.
0637: */
0638: protected void delete(RbEntry p) {
0639: assert !p.orphan;
0640: if (p.left != null && p.right != null)
0641: swapPosition(p.nextEntry(), p);
0642: //Make sure at least one of left or right is null by
0643: //swapping with next, whose left is null (right.leftMost)
0644:
0645: changeAncestorLeftNum(p, -1);
0646: decSize();
0647:
0648: RbEntry replacement = (p.left != null ? p.left : p.right);
0649: if (replacement != null) {
0650: replacement.parent = p.parent;
0651: if (p.parent == null)
0652: _root = replacement;
0653: else if (p == p.parent.left)
0654: p.parent.left = replacement;
0655: else
0656: p.parent.right = replacement;
0657:
0658: if (p.color == BLACK)
0659: fixAfterDelete(replacement);
0660: } else { // No children
0661: if (p.parent == null) // size==1
0662: _root = null;
0663: else if (p == p.parent.left)
0664: p.parent.left = null;
0665: else if (p == p.parent.right)
0666: p.parent.right = null;
0667: }
0668: p.setOrphan();
0669: }
0670:
0671: /**
0672: * Swap the linkages of two nodes in a tree. We cannot only swap the
0673: * element field because the binding of entry and element have to remain.
0674: */
0675: private final void swapPosition(RbEntry x, RbEntry y) {
0676: // Save initial values.
0677: RbEntry px = x.parent, lx = x.left, rx = x.right;
0678: RbEntry py = y.parent, ly = y.left, ry = y.right;
0679: boolean xWasLeftChild = px != null && x == px.left;
0680: boolean yWasLeftChild = py != null && y == py.left;
0681:
0682: // Swap, handling special cases of one being the other's parent.
0683: if (x == py) { // x was y's parent
0684: x.parent = y;
0685: if (yWasLeftChild) {
0686: y.left = x;
0687: y.right = rx;
0688: } else {
0689: y.right = x;
0690: y.left = lx;
0691: }
0692: } else {
0693: x.parent = py;
0694: if (py != null) {
0695: if (yWasLeftChild)
0696: py.left = x;
0697: else
0698: py.right = x;
0699: }
0700: y.left = lx;
0701: y.right = rx;
0702: }
0703:
0704: if (y == px) { // y was x's parent
0705: y.parent = x;
0706: if (xWasLeftChild) {
0707: x.left = y;
0708: x.right = ry;
0709: } else {
0710: x.right = y;
0711: x.left = ly;
0712: }
0713: } else {
0714: y.parent = px;
0715: if (px != null) {
0716: if (xWasLeftChild)
0717: px.left = y;
0718: else
0719: px.right = y;
0720: }
0721: x.left = ly;
0722: x.right = ry;
0723: }
0724:
0725: // Fix children's parent pointers
0726: if (x.left != null)
0727: x.left.parent = x;
0728: if (x.right != null)
0729: x.right.parent = x;
0730: if (y.left != null)
0731: y.left.parent = y;
0732: if (y.right != null)
0733: y.right.parent = y;
0734:
0735: // Swap colors
0736: boolean c = x.color;
0737: x.color = y.color;
0738: y.color = c;
0739:
0740: // Swap leftNum
0741: int v = x.leftNum;
0742: x.leftNum = y.leftNum;
0743: y.leftNum = v;
0744:
0745: // Check if root changed
0746: if (_root == x)
0747: _root = y;
0748: else if (_root == y)
0749: _root = x;
0750: }
0751:
0752: private void fixAfterDelete(RbEntry x) {
0753: while (x != _root && colorOf(x) == BLACK) {
0754: if (x == leftOf(parentOf(x))) {
0755: RbEntry sib = rightOf(parentOf(x));
0756:
0757: if (colorOf(sib) == RED) {
0758: setColor(sib, BLACK);
0759: setColor(parentOf(x), RED);
0760: rotateLeft(parentOf(x));
0761: sib = rightOf(parentOf(x));
0762: }
0763:
0764: if (colorOf(leftOf(sib)) == BLACK
0765: && colorOf(rightOf(sib)) == BLACK) {
0766: setColor(sib, RED);
0767: x = parentOf(x);
0768: } else {
0769: if (colorOf(rightOf(sib)) == BLACK) {
0770: setColor(leftOf(sib), BLACK);
0771: setColor(sib, RED);
0772: rotateRight(sib);
0773: sib = rightOf(parentOf(x));
0774: }
0775: setColor(sib, colorOf(parentOf(x)));
0776: setColor(parentOf(x), BLACK);
0777: setColor(rightOf(sib), BLACK);
0778: rotateLeft(parentOf(x));
0779: x = _root;
0780: }
0781: } else { // symmetric
0782: RbEntry sib = leftOf(parentOf(x));
0783:
0784: if (colorOf(sib) == RED) {
0785: setColor(sib, BLACK);
0786: setColor(parentOf(x), RED);
0787: rotateRight(parentOf(x));
0788: sib = leftOf(parentOf(x));
0789: }
0790:
0791: if (colorOf(rightOf(sib)) == BLACK
0792: && colorOf(leftOf(sib)) == BLACK) {
0793: setColor(sib, RED);
0794: x = parentOf(x);
0795: } else {
0796: if (colorOf(leftOf(sib)) == BLACK) {
0797: setColor(rightOf(sib), BLACK);
0798: setColor(sib, RED);
0799: rotateLeft(sib);
0800: sib = leftOf(parentOf(x));
0801: }
0802: setColor(sib, colorOf(parentOf(x)));
0803: setColor(parentOf(x), BLACK);
0804: setColor(leftOf(sib), BLACK);
0805: rotateRight(parentOf(x));
0806: x = _root;
0807: }
0808: }
0809: }
0810:
0811: setColor(x, BLACK);
0812: }
0813:
0814: protected final void incSize() {
0815: modCount++;
0816: _size++;
0817: }
0818:
0819: protected final void decSize() {
0820: modCount++;
0821: _size--;
0822: }
0823:
0824: protected final void checkRange(int index) {
0825: if (index >= _size || index < 0)
0826: indexOutOfBounds(index);
0827: }
0828:
0829: protected final void checkRangePlus(int index) {
0830: if (index > _size || index < 0)
0831: indexOutOfBounds(index);
0832: }
0833:
0834: protected final void indexOutOfBounds(int index) {
0835: throw new IndexOutOfBoundsException("Index: " + index
0836: + ", Size: " + _size);
0837: }
0838:
0839: /**
0840: * Converts and checks whether it is not orphan
0841: */
0842: protected final RbEntry checkNotOrphan(Entry entry) {
0843: RbEntry p = (RbEntry) entry;
0844: if (p.orphan)
0845: throw new IllegalStateException();
0846: return p;
0847: }
0848:
0849: private class EntryIter implements ListIterator {
0850: private RbEntry _cursor;
0851: private RbEntry _lastRet = null;
0852: private int _expectedModCount;
0853:
0854: private EntryIter(int index) {
0855: checkRangePlus(index); //index==_size is ok
0856:
0857: _cursor = index < _size ? getRbEntry(index) : null;
0858: _expectedModCount = modCount;
0859: }
0860:
0861: public final boolean hasNext() {
0862: checkComodification();
0863: return _cursor != null;
0864: }
0865:
0866: public Object next() {
0867: checkComodification();
0868:
0869: if (_cursor == null)
0870: throw new NoSuchElementException();
0871:
0872: _lastRet = _cursor;
0873: Object obj = _cursor;
0874: _cursor = _cursor.nextEntry();
0875: return obj;
0876: }
0877:
0878: public final boolean hasPrevious() {
0879: checkComodification();
0880: if (_cursor == null)
0881: return _size > 0;
0882: else
0883: return _cursor.previousEntry() != null;
0884: }
0885:
0886: public Object previous() {
0887: checkComodification();
0888:
0889: if (_cursor == null) {
0890: if (_size == 0)
0891: throw new NoSuchElementException();
0892: _cursor = getRbEntry(_size - 1);
0893: } else {
0894: RbEntry prev = _cursor.previousEntry();
0895: if (prev == null)
0896: throw new NoSuchElementException();
0897: _cursor = prev;
0898: }
0899: _lastRet = _cursor;
0900: return _cursor;
0901: }
0902:
0903: public final int nextIndex() {
0904: return _cursor == null ? _size : indexOfEntry(_cursor);
0905: }
0906:
0907: public final int previousIndex() {
0908: return _cursor == null ? _size - 1
0909: : indexOfEntry(_cursor) - 1;
0910: }
0911:
0912: public final void remove() {
0913: if (_lastRet == null)
0914: throw new IllegalStateException();
0915:
0916: checkComodification();
0917:
0918: if (_lastRet == _cursor)
0919: _cursor = _cursor.nextEntry();
0920:
0921: delete(_lastRet);
0922: _expectedModCount = modCount;
0923: _lastRet = null;
0924: }
0925:
0926: public final void set(Object obj) {
0927: if (_lastRet == null)
0928: throw new IllegalStateException();
0929:
0930: checkComodification();
0931:
0932: _lastRet.setElement(obj);
0933: //no need to update _expectdModCount here
0934: }
0935:
0936: public final Object get() {
0937: return _lastRet.getElement();
0938: }
0939:
0940: public final void add(Object obj) {
0941: checkComodification();
0942:
0943: insert(_cursor, newEntry(obj));
0944: _expectedModCount = modCount;
0945: }
0946:
0947: private final void checkComodification() {
0948: if (modCount != _expectedModCount)
0949: throw new ConcurrentModificationException();
0950: }
0951: }//EntryIter
0952:
0953: private class Iter extends EntryIter {
0954: private Iter(int index) {
0955: super (index);
0956: }
0957:
0958: public final Object next() {
0959: return ((RbEntry) super .next()).getElement();
0960: }
0961:
0962: public final Object previous() {
0963: return ((RbEntry) super .previous()).getElement();
0964: }
0965: }//Iter
0966:
0967: //-- cloneable --//
0968: public Object clone() {
0969: TreeArray clone;
0970: try {
0971: clone = (TreeArray) super .clone();
0972: } catch (CloneNotSupportedException e) {
0973: throw new InternalError();
0974: }
0975:
0976: //Put clone into "virgin" state
0977: clone._size = 0;
0978: clone._root = null;
0979: clone.modCount = 0;
0980:
0981: // Initialize clone with our elements
0982: for (RbEntry p = first(); p != null; p = p.nextEntry())
0983: clone.add(p.getElement());
0984:
0985: return clone;
0986: }
0987:
0988: //-- Serializable --//
0989: //NOTE: they must be declared as private
0990: private synchronized void writeObject(java.io.ObjectOutputStream s)
0991: throws java.io.IOException {
0992: s.defaultWriteObject();
0993:
0994: s.writeInt(_size);
0995:
0996: for (RbEntry p = first(); p != null; p = p.nextEntry())
0997: s.writeObject(p.getElement());
0998: }
0999:
1000: private synchronized void readObject(java.io.ObjectInputStream s)
1001: throws java.io.IOException, ClassNotFoundException {
1002: s.defaultReadObject();
1003:
1004: int size = s.readInt();
1005:
1006: for (int i = 0; i < size; i++)
1007: add(s.readObject());
1008: }
1009: }
|