1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package net.sf.collections15.list;
17
18 import java.util.AbstractList;
19 import java.util.Collection;
20 import java.util.ConcurrentModificationException;
21 import java.util.Iterator;
22 import java.util.ListIterator;
23 import java.util.NoSuchElementException;
24
25 import net.sf.collections15.OrderedIterator;
26
27
28 /***
29 * A <code>List</code> implementation that is optimised for fast insertions and
30 * removals at any index in the list.
31 * <p>
32 * This list implementation utilises a tree structure internally to ensure that
33 * all insertions and removals are O(log n). This provides much faster performance
34 * than both an <code>ArrayList</code> and a <code>LinkedList</code> where elements
35 * are inserted and removed repeatedly from anywhere in the list.
36 * <p>
37 * The following relative performance statistics are indicative of this class:
38 * <pre>
39 * get add insert iterate remove
40 * TreeList 3 5 1 2 1
41 * ArrayList 1 1 40 1 40
42 * LinkedList 5800 1 350 2 325
43 * </pre>
44 * <code>ArrayList</code> is a good general purpose list implementation.
45 * It is faster than <code>TreeList</code> for most operations except inserting
46 * and removing in the middle of the list. <code>ArrayList</code> also uses less
47 * memory as <code>TreeList</code> uses one object per entry.
48 * <p>
49 * <code>LinkedList</code> is rarely a good choice of implementation.
50 * <code>TreeList</code> is almost always a good replacement for it, although it
51 * does use sligtly more memory.
52 *
53 * @since Commons Collections 3.1
54 * @version $Revision: 1.1 $ $Date: 2005/05/03 22:45:38 $
55 *
56 * @author Joerg Schmuecker
57 * @author Stephen Colebourne
58 */
59 public class TreeList<E> extends AbstractList<E> {
60
61
62
63
64
65 /*** The root node in the AVL tree */
66 private AVLNode<E> root;
67
68 /*** The current size of the list */
69 private int size;
70
71
72 /***
73 * Constructs a new empty list.
74 */
75 public TreeList() {
76 super();
77 }
78
79 /***
80 * Constructs a new empty list that copies the specified list.
81 *
82 * @param coll the collection to copy
83 * @throws NullPointerException if the collection is null
84 */
85 public TreeList(Collection<E> coll) {
86 super();
87 addAll(coll);
88 }
89
90
91 /***
92 * Gets the element at the specified index.
93 *
94 * @param index the index to retrieve
95 * @return the element at the specified index
96 */
97 public E get(int index) {
98 checkInterval(index, 0, size() - 1);
99 return root.get(index).getValue();
100 }
101
102 /***
103 * Gets the current size of the list.
104 *
105 * @return the current size
106 */
107 public int size() {
108 return size;
109 }
110
111 /***
112 * Gets an iterator over the list.
113 *
114 * @return an iterator over the list
115 */
116 public Iterator<E> iterator() {
117
118 return listIterator(0);
119 }
120
121 /***
122 * Gets a ListIterator over the list.
123 *
124 * @return the new iterator
125 */
126 public ListIterator<E> listIterator() {
127
128 return listIterator(0);
129 }
130
131 /***
132 * Gets a ListIterator over the list.
133 *
134 * @param fromIndex the index to start from
135 * @return the new iterator
136 */
137 public ListIterator<E> listIterator(int fromIndex) {
138
139
140 checkInterval(fromIndex, 0, size());
141 return new TreeListIterator<E>(this, fromIndex);
142 }
143
144 /***
145 * Searches for the index of an object in the list.
146 *
147 * @return the index of the object, -1 if not found
148 */
149 public int indexOf(Object object) {
150
151 if (root == null) {
152 return -1;
153 }
154 return root.indexOf(object, root.relativePosition);
155 }
156
157 /***
158 * Searches for the presence of an object in the list.
159 *
160 * @return true if the object is found
161 */
162 public boolean contains(Object object) {
163 return (indexOf(object) >= 0);
164 }
165
166 /***
167 * Converts the list into an array.
168 *
169 * @return the list as an array
170 */
171 public Object[] toArray() {
172
173 Object[] array = new Object[size()];
174 if (root != null) {
175 root.toArray(array, root.relativePosition);
176 }
177 return array;
178 }
179
180
181 /***
182 * Adds a new element to the list.
183 *
184 * @param index the index to add before
185 * @param obj the element to add
186 */
187 public void add(int index, E obj) {
188 modCount++;
189 checkInterval(index, 0, size());
190 if (root == null) {
191 root = new AVLNode<E>(index, obj, null, null);
192 } else {
193 root = root.insert(index, obj);
194 }
195 size++;
196 }
197
198 /***
199 * Sets the element at the specified index.
200 *
201 * @param index the index to set
202 * @param obj the object to store at the specified index
203 * @return the previous object at that index
204 * @throws IndexOutOfBoundsException if the index is invalid
205 */
206 public E set(int index, E obj) {
207 checkInterval(index, 0, size() - 1);
208 AVLNode<E> node = root.get(index);
209 E result = node.value;
210 node.setValue(obj);
211 return result;
212 }
213
214 /***
215 * Removes the element at the specified index.
216 *
217 * @param index the index to remove
218 * @return the previous object at that index
219 */
220 public E remove(int index) {
221 modCount++;
222 checkInterval(index, 0, size() - 1);
223 E result = get(index);
224 root = root.remove(index);
225 size--;
226 return result;
227 }
228
229 /***
230 * Clears the list, removing all entries.
231 */
232 public void clear() {
233 modCount++;
234 root = null;
235 size = 0;
236 }
237
238
239 /***
240 * Checks whether the index is valid.
241 *
242 * @param index the index to check
243 * @param startIndex the first allowed index
244 * @param endIndex the last allowed index
245 * @throws IndexOutOfBoundsException if the index is invalid
246 */
247 private void checkInterval(int index, int startIndex, int endIndex) {
248 if (index < startIndex || index > endIndex) {
249 throw new IndexOutOfBoundsException("Invalid index:" + index + ", size=" + size());
250 }
251 }
252
253
254 /***
255 * Implements an AVLNode which keeps the offset updated.
256 * <p>
257 * This node contains the real work.
258 * TreeList is just there to implement {@link java.util.List}.
259 * The nodes don't know the index of the object they are holding. They
260 * do know however their position relative to their parent node.
261 * This allows to calculate the index of a node while traversing the tree.
262 * <p>
263 * The Faedelung calculation stores a flag for both the left and right child
264 * to indicate if they are a child (false) or a link as in linked list (true).
265 */
266 static class AVLNode<T> {
267 /*** The left child node or the predecessor if {@link #leftIsPrevious}.*/
268 private AVLNode<T> left;
269 /*** Flag indicating that left reference is not a subtree but the predecessor. */
270 private boolean leftIsPrevious;
271 /*** The right child node or the successor if {@link #rightIsNext}. */
272 private AVLNode<T> right;
273 /*** Flag indicating that right reference is not a subtree but the successor. */
274 private boolean rightIsNext;
275 /*** How many levels of left/right are below this one. */
276 private int height;
277 /*** The relative position, root holds absolute position. */
278 private int relativePosition;
279 /*** The stored element. */
280 private T value;
281
282 /***
283 * Constructs a new node with a relative position.
284 *
285 * @param relativePosition the relative position of the node
286 * @param obj the value for the ndoe
287 * @param rightFollower the node with the value following this one
288 * @param leftFollower the node with the value leading this one
289 */
290 private AVLNode(int relativePosition, T obj, AVLNode<T> rightFollower, AVLNode<T> leftFollower) {
291 this.relativePosition = relativePosition;
292 value = obj;
293 rightIsNext = true;
294 leftIsPrevious = true;
295 right = rightFollower;
296 left = leftFollower;
297 }
298
299 /***
300 * Gets the value.
301 *
302 * @return the value of this node
303 */
304 T getValue() {
305 return value;
306 }
307
308 /***
309 * Sets the value.
310 *
311 * @param obj the value to store
312 */
313 void setValue(T obj) {
314 this.value = obj;
315 }
316
317 /***
318 * Locate the element with the given index relative to the
319 * offset of the parent of this node.
320 */
321 AVLNode<T> get(int index) {
322 int indexRelativeToMe = index - relativePosition;
323
324 if (indexRelativeToMe == 0) {
325 return this;
326 }
327
328 AVLNode<T> nextNode = ((indexRelativeToMe < 0) ? getLeftSubTree() : getRightSubTree());
329 if (nextNode == null) {
330 return null;
331 }
332 return nextNode.get(indexRelativeToMe);
333 }
334
335 /***
336 * Locate the index that contains the specified object.
337 */
338 int indexOf(Object object, int index) {
339 if (getLeftSubTree() != null) {
340 int result = left.indexOf(object, index + left.relativePosition);
341 if (result != -1) {
342 return result;
343 }
344 }
345 if (value == null ? value == object : value.equals(object)) {
346 return index;
347 }
348 if (getRightSubTree() != null) {
349 return right.indexOf(object, index + right.relativePosition);
350 }
351 return -1;
352 }
353
354 /***
355 * Stores the node and its children into the array specified.
356 *
357 * @param array the array to be filled
358 * @param index the index of this node
359 */
360 void toArray(Object[] array, int index) {
361 array[index] = value;
362 if (getLeftSubTree() != null) {
363 left.toArray(array, index + left.relativePosition);
364 }
365 if (getRightSubTree() != null) {
366 right.toArray(array, index + right.relativePosition);
367 }
368 }
369
370 /***
371 * Gets the next node in the list after this one.
372 *
373 * @return the next node
374 */
375 AVLNode<T> next() {
376 if (rightIsNext || right == null) {
377 return right;
378 }
379 return right.min();
380 }
381
382 /***
383 * Gets the node in the list before this one.
384 *
385 * @return the previous node
386 */
387 AVLNode<T> previous() {
388 if (leftIsPrevious || left == null) {
389 return left;
390 }
391 return left.max();
392 }
393
394 /***
395 * Inserts a node at the position index.
396 *
397 * @param index is the index of the position relative to the position of
398 * the parent node.
399 * @param obj is the object to be stored in the position.
400 */
401 AVLNode<T> insert(int index, T obj) {
402 int indexRelativeToMe = index - relativePosition;
403
404 if (indexRelativeToMe <= 0) {
405 return insertOnLeft(indexRelativeToMe, obj);
406 } else {
407 return insertOnRight(indexRelativeToMe, obj);
408 }
409 }
410
411 private AVLNode<T> insertOnLeft(int indexRelativeToMe, T obj) {
412 AVLNode<T> ret = this;
413
414 if (getLeftSubTree() == null) {
415 setLeft(new AVLNode<T>(-1, obj, this, left), null);
416 } else {
417 setLeft(left.insert(indexRelativeToMe, obj), null);
418 }
419
420 if (relativePosition >= 0) {
421 relativePosition++;
422 }
423 ret = balance();
424 recalcHeight();
425 return ret;
426 }
427
428 private AVLNode<T> insertOnRight(int indexRelativeToMe, T obj) {
429 AVLNode<T> ret = this;
430
431 if (getRightSubTree() == null) {
432 setRight(new AVLNode<T>(+1, obj, right, this), null);
433 } else {
434 setRight(right.insert(indexRelativeToMe, obj), null);
435 }
436 if (relativePosition < 0) {
437 relativePosition--;
438 }
439 ret = balance();
440 recalcHeight();
441 return ret;
442 }
443
444
445 /***
446 * Gets the left node, returning null if its a faedelung.
447 */
448 private AVLNode<T> getLeftSubTree() {
449 return (leftIsPrevious ? null : left);
450 }
451
452 /***
453 * Gets the right node, returning null if its a faedelung.
454 */
455 private AVLNode<T> getRightSubTree() {
456 return (rightIsNext ? null : right);
457 }
458
459 /***
460 * Gets the rightmost child of this node.
461 *
462 * @return the rightmost child (greatest index)
463 */
464 private AVLNode<T> max() {
465 return (getRightSubTree() == null) ? this : right.max();
466 }
467
468 /***
469 * Gets the leftmost child of this node.
470 *
471 * @return the leftmost child (smallest index)
472 */
473 private AVLNode<T> min() {
474 return (getLeftSubTree() == null) ? this : left.min();
475 }
476
477 /***
478 * Removes the node at a given position.
479 *
480 * @param index is the index of the element to be removed relative to the position of
481 * the parent node of the current node.
482 */
483 AVLNode<T> remove(int index) {
484 int indexRelativeToMe = index - relativePosition;
485
486 if (indexRelativeToMe == 0) {
487 return removeSelf();
488 }
489 if (indexRelativeToMe > 0) {
490 setRight(right.remove(indexRelativeToMe), right.right);
491 if (relativePosition < 0) {
492 relativePosition++;
493 }
494 } else {
495 setLeft(left.remove(indexRelativeToMe), left.left);
496 if (relativePosition > 0) {
497 relativePosition--;
498 }
499 }
500 recalcHeight();
501 return balance();
502 }
503
504 private AVLNode<T> removeMax() {
505 if (getRightSubTree() == null) {
506 return removeSelf();
507 }
508 setRight(right.removeMax(), right.right);
509 if (relativePosition < 0) {
510 relativePosition++;
511 }
512 recalcHeight();
513 return balance();
514 }
515
516 private AVLNode<T> removeMin() {
517 if (getLeftSubTree() == null) {
518 return removeSelf();
519 }
520 setLeft(left.removeMin(), left.left);
521 if (relativePosition > 0) {
522 relativePosition--;
523 }
524 recalcHeight();
525 return balance();
526 }
527
528 private AVLNode<T> removeSelf() {
529 if (getRightSubTree() == null && getLeftSubTree() == null)
530 return null;
531 if (getRightSubTree() == null) {
532 if (relativePosition > 0) {
533 left.relativePosition += relativePosition + (relativePosition > 0 ? 0 : 1);
534 }
535 left.max().setRight(null, right);
536 return left;
537 }
538 if (getLeftSubTree() == null) {
539 right.relativePosition += relativePosition - (relativePosition < 0 ? 0 : 1);
540 right.min().setLeft(null, left);
541 return right;
542 }
543
544 if (heightRightMinusLeft() > 0) {
545 AVLNode<T> rightMin = right.min();
546 value = rightMin.value;
547 if (leftIsPrevious) {
548 left = rightMin.left;
549 }
550 right = right.removeMin();
551 if (relativePosition < 0) {
552 relativePosition++;
553 }
554 } else {
555 AVLNode<T> leftMax = left.max();
556 value = leftMax.value;
557 if (rightIsNext) {
558 right = leftMax.right;
559 }
560 left = left.removeMax();
561 if (relativePosition > 0) {
562 relativePosition--;
563 }
564 }
565 recalcHeight();
566 return this;
567 }
568
569
570 /***
571 * Balances according to the AVL algorithm.
572 */
573 private AVLNode<T> balance() {
574 switch (heightRightMinusLeft()) {
575 case 1 :
576 case 0 :
577 case -1 :
578 return this;
579 case -2 :
580 if (left.heightRightMinusLeft() > 0) {
581 setLeft(left.rotateLeft(), null);
582 }
583 return rotateRight();
584 case 2 :
585 if (right.heightRightMinusLeft() < 0) {
586 setRight(right.rotateRight(), null);
587 }
588 return rotateLeft();
589 default :
590 throw new RuntimeException("tree inconsistent!");
591 }
592 }
593
594 /***
595 * Gets the relative position.
596 */
597 private int getOffset(AVLNode<T> node) {
598 if (node == null) {
599 return 0;
600 }
601 return node.relativePosition;
602 }
603
604 /***
605 * Sets the relative position.
606 */
607 private int setOffset(AVLNode<T> node, int newOffest) {
608 if (node == null) {
609 return 0;
610 }
611 int oldOffset = getOffset(node);
612 node.relativePosition = newOffest;
613 return oldOffset;
614 }
615
616 /***
617 * Sets the height by calculation.
618 */
619 private void recalcHeight() {
620 height = Math.max(
621 getLeftSubTree() == null ? -1 : getLeftSubTree().height,
622 getRightSubTree() == null ? -1 : getRightSubTree().height) + 1;
623 }
624
625 /***
626 * Returns the height of the node or -1 if the node is null.
627 */
628 private int getHeight(AVLNode<T> node) {
629 return (node == null ? -1 : node.height);
630 }
631
632 /***
633 * Returns the height difference right - left
634 */
635 private int heightRightMinusLeft() {
636 return getHeight(getRightSubTree()) - getHeight(getLeftSubTree());
637 }
638
639 private AVLNode<T> rotateLeft() {
640 AVLNode<T> newTop = right;
641 AVLNode<T> movedNode = getRightSubTree().getLeftSubTree();
642
643 int newTopPosition = relativePosition + getOffset(newTop);
644 int myNewPosition = -newTop.relativePosition;
645 int movedPosition = getOffset(newTop) + getOffset(movedNode);
646
647 setRight(movedNode, newTop);
648 newTop.setLeft(this, null);
649
650 setOffset(newTop, newTopPosition);
651 setOffset(this, myNewPosition);
652 setOffset(movedNode, movedPosition);
653 return newTop;
654 }
655
656 private AVLNode<T> rotateRight() {
657 AVLNode<T> newTop = left;
658 AVLNode<T> movedNode = getLeftSubTree().getRightSubTree();
659
660 int newTopPosition = relativePosition + getOffset(newTop);
661 int myNewPosition = -newTop.relativePosition;
662 int movedPosition = getOffset(newTop) + getOffset(movedNode);
663
664 setLeft(movedNode, newTop);
665 newTop.setRight(this, null);
666
667 setOffset(newTop, newTopPosition);
668 setOffset(this, myNewPosition);
669 setOffset(movedNode, movedPosition);
670 return newTop;
671 }
672
673 private void setLeft(AVLNode<T> node, AVLNode<T> previous) {
674 leftIsPrevious = (node == null);
675 left = (leftIsPrevious ? previous : node);
676 recalcHeight();
677 }
678
679 private void setRight(AVLNode<T> node, AVLNode<T> next) {
680 rightIsNext = (node == null);
681 right = (rightIsNext ? next : node);
682 recalcHeight();
683 }
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737 /***
738 * Used for debugging.
739 */
740 public String toString() {
741 return "AVLNode(" + relativePosition + "," + (left != null) + "," + value +
742 "," + (getRightSubTree() != null) + ", faedelung " + rightIsNext + " )";
743 }
744 }
745
746 /***
747 * A list iterator over the linked list.
748 */
749 static class TreeListIterator<T> implements ListIterator<T>, OrderedIterator<T> {
750 /*** The parent list */
751 protected final TreeList<T> parent;
752 /***
753 * The node that will be returned by {@link #next()}. If this is equal
754 * to {@link AbstractLinkedList#header} then there are no more values to return.
755 */
756 protected AVLNode<T> next;
757 /***
758 * The index of {@link #next}.
759 */
760 protected int nextIndex;
761 /***
762 * The last node that was returned by {@link #next()} or {@link
763 * #previous()}. Set to <code>null</code> if {@link #next()} or {@link
764 * #previous()} haven't been called, or if the node has been removed
765 * with {@link #remove()} or a new node added with {@link #add(Object)}.
766 * Should be accessed through {@link #getLastNodeReturned()} to enforce
767 * this behaviour.
768 */
769 protected AVLNode<T> current;
770 /***
771 * The index of {@link #current}.
772 */
773 protected int currentIndex;
774 /***
775 * The modification count that the list is expected to have. If the list
776 * doesn't have this count, then a
777 * {@link java.util.ConcurrentModificationException} may be thrown by
778 * the operations.
779 */
780 protected int expectedModCount;
781
782 /***
783 * Create a ListIterator for a list.
784 *
785 * @param parent the parent list
786 * @param fromIndex the index to start at
787 */
788 protected TreeListIterator(TreeList<T> parent, int fromIndex) throws IndexOutOfBoundsException {
789 super();
790 this.parent = parent;
791 this.expectedModCount = parent.modCount;
792 this.next = (parent.root == null ? null : parent.root.get(fromIndex));
793 this.nextIndex = fromIndex;
794 }
795
796 /***
797 * Checks the modification count of the list is the value that this
798 * object expects.
799 *
800 * @throws ConcurrentModificationException If the list's modification
801 * count isn't the value that was expected.
802 */
803 protected void checkModCount() {
804 if (parent.modCount != expectedModCount) {
805 throw new ConcurrentModificationException();
806 }
807 }
808
809 public boolean hasNext() {
810 return (nextIndex < parent.size());
811 }
812
813 public T next() {
814 checkModCount();
815 if (!hasNext()) {
816 throw new NoSuchElementException("No element at index " + nextIndex + ".");
817 }
818 if (next == null) {
819 next = parent.root.get(nextIndex);
820 }
821 T value = next.getValue();
822 current = next;
823 currentIndex = nextIndex++;
824 next = next.next();
825 return value;
826 }
827
828 public boolean hasPrevious() {
829 return (nextIndex > 0);
830 }
831
832 public T previous() {
833 checkModCount();
834 if (!hasPrevious()) {
835 throw new NoSuchElementException("Already at start of list.");
836 }
837 if (next == null) {
838 next = parent.root.get(nextIndex - 1);
839 } else {
840 next = next.previous();
841 }
842 T value = next.getValue();
843 current = next;
844 currentIndex = --nextIndex;
845 return value;
846 }
847
848 public int nextIndex() {
849 return nextIndex;
850 }
851
852 public int previousIndex() {
853 return nextIndex() - 1;
854 }
855
856 public void remove() {
857 checkModCount();
858 if (current == null) {
859 throw new IllegalStateException();
860 }
861 parent.remove(currentIndex);
862 current = null;
863 currentIndex = -1;
864 nextIndex--;
865 expectedModCount++;
866 }
867
868 public void set(T obj) {
869 checkModCount();
870 if (current == null) {
871 throw new IllegalStateException();
872 }
873 current.setValue(obj);
874 }
875
876 public void add(T obj) {
877 checkModCount();
878 parent.add(nextIndex, obj);
879 current = null;
880 currentIndex = -1;
881 nextIndex++;
882 expectedModCount++;
883 }
884 }
885
886 }