Source code: com/virtuosotechnologies/lib/collections/RotatingArrayList.java
1 /*
2 ================================================================================
3
4 FILE: RotatingArrayList.java
5
6 PROJECT:
7
8 Virtuoso Utilities
9
10 CONTENTS:
11
12 Rotating array list
13
14 PROGRAMMERS:
15
16 Daniel Azuma (DA) <dazuma@kagi.com>
17
18 COPYRIGHT:
19
20 Copyright (C) 2003 Daniel Azuma (dazuma@kagi.com)
21
22 This program is free software; you can redistribute it and/or
23 modify it under the terms of the GNU General Public License as
24 published by the Free Software Foundation; either version 2
25 of the License, or (at your option) any later version.
26
27 This program is distributed in the hope that it will be useful,
28 but WITHOUT ANY WARRANTY; without even the implied warranty of
29 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 GNU General Public License for more details.
31
32 You should have received a copy of the GNU General Public
33 License along with this program; if not, write to
34 Free Software Foundation, Inc.
35 59 Temple Place, Suite 330
36 Boston, MA 02111-1307 USA
37
38 ================================================================================
39 */
40
41
42 package com.virtuosotechnologies.lib.collections;
43
44 import java.util.List;
45 import java.util.AbstractList;
46 import java.util.Collection;
47 import java.util.Iterator;
48 import java.util.AbstractList;
49 import java.io.Serializable;
50 import java.io.IOException;
51 import java.io.ObjectInputStream;
52 import java.io.ObjectOutputStream;
53
54
55 /**
56 * Rotating resizeable array implementation of the <tt>List</tt> interface.
57 * Implements all optional list operations, and permits all elements, including
58 * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
59 * this class provides methods to manipulate the size of the array that is
60 * used internally to store the list.
61 * <p>
62 * This class is roughly equivalent to ArrayList (and is based on the ArrayList
63 * implementation) with one important distinction. The add(index, object)
64 * method operates in amortized constant time rather than linear time when
65 * inserting at the beginning or end of a list, and the remove(index) method
66 * also operates in amortized constant time when removing from the beginning
67 * or end. This enables efficient use of this class in double-ended queues.
68 */
69 public class RotatingArrayList
70 extends AbstractList
71 implements
72 List,
73 Cloneable,
74 Serializable
75 {
76 /**
77 * The array buffer into which the elements of the ArrayList are stored.
78 * The capacity of the ArrayList is the length of this array buffer.
79 */
80 private transient Object elementData_[];
81
82 /**
83 * The size of the RotatingArrayList (the number of elements it contains).
84 */
85 private int size_;
86
87 /**
88 * Array index of the first element.
89 */
90 private transient int first_;
91
92 /**
93 * Array index of the last element, plus 1. But it wraps around, so
94 * it is never == elementData_.length.
95 */
96 private transient int last_;
97
98
99 /**
100 * Constructs an empty list with the specified initial capacity.
101 *
102 * @param initialCapacity the initial capacity of the list.
103 * @exception IllegalArgumentException if the specified initial capacity
104 * is negative
105 */
106 public RotatingArrayList(
107 int initialCapacity)
108 {
109 super();
110 if (initialCapacity < 0)
111 {
112 throw new IllegalArgumentException(
113 "Illegal Capacity: "+ initialCapacity);
114 }
115 this.elementData_ = new Object[initialCapacity];
116 first_ = last_ = size_ = 0;
117 }
118
119
120 /**
121 * Constructs an empty list.
122 */
123 public RotatingArrayList()
124 {
125 this(10);
126 }
127
128
129 /**
130 * Constructs a list containing the elements of the specified
131 * collection, in the order they are returned by the collection's
132 * iterator. The <tt>RotatingArrayList</tt> instance has an initial capacity
133 * of 110% the size of the specified collection.
134 *
135 * @param c the collection whose elements are to be placed into this list.
136 */
137 public RotatingArrayList(
138 Collection c)
139 {
140 size_ = c.size();
141 elementData_ = new Object[(size_*110)/100+1]; // Allow 10% room for growth
142 c.toArray(elementData_);
143 first_ = 0;
144 last_ = size_;
145 // Array length is always greater than size, so we don't need to worry
146 // about last_ == elementData_.length.
147 }
148
149
150 /**
151 * Private helper.
152 */
153 private int rotateIndex_(
154 int index)
155 {
156 while (index >= elementData_.length)
157 {
158 index -= elementData_.length;
159 }
160 while (index < 0)
161 {
162 index += elementData_.length;
163 }
164 return index;
165 }
166
167
168 /**
169 * Copies list into a given array
170 */
171 private void copyIntoArray_(
172 Object[] aArray)
173 {
174 if (size_ > 0)
175 {
176 if (last_ <= first_)
177 {
178 System.arraycopy(elementData_, first_, aArray, 0,
179 elementData_.length-first_);
180 System.arraycopy(elementData_, 0, aArray,
181 elementData_.length-first_, last_);
182 }
183 else
184 {
185 System.arraycopy(elementData_, first_, aArray, 0,
186 last_-first_);
187 }
188 }
189 }
190
191
192 /**
193 * Trims the capacity of this <tt>RotatingArrayList</tt> instance to be the
194 * list's current size. An application can use this operation to minimize
195 * the storage of a <tt>RotatingArrayList</tt> instance.
196 */
197 public void trimToSize()
198 {
199 modCount++;
200 int oldCapacity = elementData_.length;
201 if (size_ < oldCapacity)
202 {
203 Object[] newData = new Object[size_];
204 copyIntoArray_(newData);
205 first_ = 0;
206 last_ = 0;
207 elementData_ = newData;
208 }
209 }
210
211
212 /**
213 * Increases the capacity of this <tt>ArraRotatingArrayList</tt> instance, if
214 * necessary, to ensure that it can hold at least the number of elements
215 * specified by the minimum capacity argument.
216 *
217 * @param minCapacity the desired minimum capacity.
218 */
219 public void ensureCapacity(
220 int minCapacity)
221 {
222 modCount++;
223 int oldCapacity = elementData_.length;
224 if (minCapacity > oldCapacity)
225 {
226 // New capacity is >= minCapacity, but also ensure that we
227 // increase capacity by at least 50%
228 int newCapacity = (oldCapacity * 3)/2 + 1;
229 if (newCapacity < minCapacity)
230 {
231 newCapacity = minCapacity;
232 }
233 Object[] newData = new Object[newCapacity];
234 copyIntoArray_(newData);
235 first_ = 0;
236 last_ = size_;
237 elementData_ = newData;
238 }
239 }
240
241
242 /**
243 * Returns the number of elements in this list.
244 *
245 * @return the number of elements in this list.
246 */
247 public int size()
248 {
249 return size_;
250 }
251
252
253 /**
254 * Tests if this list has no elements.
255 *
256 * @return <tt>true</tt> if this list has no elements;
257 * <tt>false</tt> otherwise.
258 */
259 public boolean isEmpty()
260 {
261 return size_ == 0;
262 }
263
264
265 /**
266 * Returns <tt>true</tt> if this list contains the specified element.
267 *
268 * @param elem element whose presence in this List is to be tested.
269 */
270 public boolean contains(
271 Object elem)
272 {
273 return indexOf(elem) >= 0;
274 }
275
276
277 /**
278 * Searches for the first occurence of the given argument, testing
279 * for equality using the <tt>equals</tt> method.
280 *
281 * @param elem an object.
282 * @return the index of the first occurrence of the argument in this
283 * list; returns <tt>-1</tt> if the object is not found.
284 */
285 public int indexOf(
286 Object elem)
287 {
288 int curIndex = first_;
289 if (elem == null)
290 {
291 for (int i = 0; i < size_; i++)
292 {
293 if (elementData_[curIndex]==null)
294 {
295 return i;
296 }
297 ++curIndex;
298 if (curIndex == elementData_.length)
299 {
300 curIndex = 0;
301 }
302 }
303 }
304 else
305 {
306 for (int i = 0; i < size_; i++)
307 {
308 if (elem.equals(elementData_[curIndex]))
309 {
310 return i;
311 }
312 ++curIndex;
313 if (curIndex == elementData_.length)
314 {
315 curIndex = 0;
316 }
317 }
318 }
319 return -1;
320 }
321
322
323 /**
324 * Returns the index of the last occurrence of the specified object in
325 * this list.
326 *
327 * @param elem the desired element.
328 * @return the index of the last occurrence of the specified object in
329 * this list; returns -1 if the object is not found.
330 */
331 public int lastIndexOf(
332 Object elem)
333 {
334 int curIndex = last_;
335 if (elem == null)
336 {
337 for (int i = size_-1; i >= 0; --i)
338 {
339 --curIndex;
340 if (curIndex < 0)
341 {
342 curIndex = elementData_.length-1;
343 }
344 if (elementData_[curIndex]==null)
345 {
346 return i;
347 }
348 }
349 }
350 else
351 {
352 for (int i = size_-1; i >= 0; --i)
353 {
354 --curIndex;
355 if (curIndex < 0)
356 {
357 curIndex = elementData_.length-1;
358 }
359 if (elem.equals(elementData_[curIndex]))
360 {
361 return i;
362 }
363 }
364 }
365 return -1;
366 }
367
368
369 /**
370 * Returns a shallow copy of this <tt>RotatingArrayList</tt> instance. (The
371 * elements themselves are not copied.)
372 *
373 * @return a clone of this <tt>RotatingArrayList</tt> instance.
374 */
375 public Object clone()
376 {
377 return new RotatingArrayList(this);
378 }
379
380
381 /**
382 * Returns an array containing all of the elements in this list
383 * in the correct order.
384 *
385 * @return an array containing all of the elements in this list
386 * in the correct order.
387 */
388 public Object[] toArray()
389 {
390 Object[] result = new Object[size_];
391 copyIntoArray_(result);
392 return result;
393 }
394
395
396 /**
397 * Returns an array containing all of the elements in this list in the
398 * correct order. The runtime type of the returned array is that of the
399 * specified array. If the list fits in the specified array, it is
400 * returned therein. Otherwise, a new array is allocated with the runtime
401 * type of the specified array and the size of this list.<p>
402 *
403 * If the list fits in the specified array with room to spare (i.e., the
404 * array has more elements than the list), the element in the array
405 * immediately following the end of the collection is set to
406 * <tt>null</tt>. This is useful in determining the length of the list
407 * <i>only</i> if the caller knows that the list does not contain any
408 * <tt>null</tt> elements.
409 *
410 * @param a the array into which the elements of the list are to
411 * be stored, if it is big enough; otherwise, a new array of the
412 * same runtime type is allocated for this purpose.
413 * @return an array containing the elements of the list.
414 * @throws ArrayStoreException if the runtime type of a is not a supertype
415 * of the runtime type of every element in this list.
416 */
417 public Object[] toArray(
418 Object a[])
419 {
420 if (a.length < size_)
421 {
422 a = (Object[])java.lang.reflect.Array.newInstance(
423 a.getClass().getComponentType(), size_);
424 }
425
426 copyIntoArray_(a);
427
428 if (a.length > size_)
429 {
430 a[size_] = null;
431 }
432
433 return a;
434 }
435
436
437 // Positional Access Operations
438
439 /**
440 * Returns the element at the specified position in this list.
441 *
442 * @param index index of element to return.
443 * @return the element at the specified position in this list.
444 * @throws IndexOutOfBoundsException if index is out of range <tt>(index
445 * < 0 || index >= size())</tt>.
446 */
447 public Object get(
448 int index)
449 {
450 RangeCheck(index);
451
452 return elementData_[rotateIndex_(index+first_)];
453 }
454
455
456 /**
457 * Returns the element at the front of the list.
458 *
459 * @return the element at the front of this list.
460 * @throws IndexOutOfBoundsException if the list is empty
461 */
462 public Object getFirst()
463 {
464 return get(0);
465 }
466
467
468 /**
469 * Returns the element at the back of the list.
470 *
471 * @return the element at the back of this list.
472 * @throws IndexOutOfBoundsException if the list is empty
473 */
474 public Object getLast()
475 {
476 return get(size_-1);
477 }
478
479
480 /**
481 * Replaces the element at the specified position in this list with
482 * the specified element.
483 *
484 * @param index index of element to replace.
485 * @param element element to be stored at the specified position.
486 * @return the element previously at the specified position.
487 * @throws IndexOutOfBoundsException if index out of range
488 * <tt>(index < 0 || index >= size())</tt>.
489 */
490 public Object set(
491 int index,
492 Object element)
493 {
494 RangeCheck(index);
495
496 int realIndex = rotateIndex_(index+first_);
497 Object oldValue = elementData_[realIndex];
498 elementData_[realIndex] = element;
499 return oldValue;
500 }
501
502
503 /**
504 * Replaces the element at the front of this list with
505 * the specified element.
506 *
507 * @param element element to be stored at the front.
508 * @return the element previously at the the front.
509 * @throws IndexOutOfBoundsException if the list is empty.
510 */
511 public Object setFirst(
512 Object element)
513 {
514 return set(0, element);
515 }
516
517
518 /**
519 * Replaces the element at the back of this list with
520 * the specified element.
521 *
522 * @param element element to be stored at the back.
523 * @return the element previously at the back.
524 * @throws IndexOutOfBoundsException if the list is empty.
525 */
526 public Object setLast(
527 Object element)
528 {
529 return set(size_-1, element);
530 }
531
532
533 /**
534 * Appends the specified element to the end of this list.
535 *
536 * @param o element to be appended to this list.
537 * @return <tt>true</tt> (as per the general contract of Collection.add).
538 */
539 public boolean add(
540 Object o)
541 {
542 return addLast(o);
543 }
544
545
546 /**
547 * Appends the specified element to the back of this list.
548 *
549 * @param o element to be appended to this list.
550 * @return <tt>true</tt> (as per the general contract of Collection.add).
551 */
552 public boolean addLast(
553 Object o)
554 {
555 ensureCapacity(size_ + 1); // Increments modCount!!
556 elementData_[last_] = o;
557 ++last_;
558 if (last_ == elementData_.length)
559 {
560 last_ = 0;
561 }
562 ++size_;
563 return true;
564 }
565
566
567 /**
568 * Appends the specified element to the front of this list.
569 *
570 * @param o element to be appended to this list.
571 * @return <tt>true</tt> (as per the general contract of Collection.add).
572 */
573 public boolean addFirst(
574 Object o)
575 {
576 ensureCapacity(size_ + 1); // Increments modCount!!
577 --first_;
578 if (first_ == -1)
579 {
580 first_ = elementData_.length-1;
581 }
582 elementData_[first_] = o;
583 ++size_;
584 return true;
585 }
586
587
588 /**
589 * Inserts the specified element at the specified position in this
590 * list. Shifts the element currently at that position (if any) and
591 * any subsequent elements to the right (adds one to their indices).
592 *
593 * @param index index at which the specified element is to be inserted.
594 * @param element element to be inserted.
595 * @throws IndexOutOfBoundsException if index is out of range
596 * <tt>(index < 0 || index > size())</tt>.
597 */
598 public void add(
599 int index,
600 Object element)
601 {
602 if (index > size_ || index < 0)
603 {
604 throw new IndexOutOfBoundsException(
605 "Index: "+index+", Size: "+size_);
606 }
607 else if (index == 0)
608 {
609 addFirst(element);
610 }
611 else if (index == size_)
612 {
613 addLast(element);
614 }
615 else
616 {
617 ensureCapacity(size_+1); // Increments modCount!!
618 int realIndex = rotateIndex_(index+first_);
619 if (realIndex < first_ || first_ == 0)
620 {
621 // Push items towards back
622 System.arraycopy(elementData_, realIndex, elementData_,
623 realIndex+1, last_-realIndex);
624 ++last_;
625 if (last_ == elementData_.length)
626 {
627 last_ = 0;
628 }
629 }
630 else
631 {
632 // Push items towards front
633 System.arraycopy(elementData_, first_, elementData_,
634 first_-1, index);
635 --first_;
636 if (first_ == -1)
637 {
638 first_ = elementData_.length-1;
639 }
640 --realIndex; // Because first_ is now one less
641 // realIndex should never wrap around in this case, though.
642 }
643 elementData_[realIndex] = element;
644 ++size_;
645 }
646 }
647
648
649 /**
650 * Removes the element from the front of this list.
651 * Shifts any subsequent elements to the left (subtracts one from their
652 * indices).
653 *
654 * @return the element that was removed from the list.
655 * @throws IndexOutOfBoundsException if the list is empty.
656 */
657 public Object removeFirst()
658 {
659 if (size_ == 0)
660 {
661 throw new IndexOutOfBoundsException(
662 "Index: -1, Size: "+size_);
663 }
664 modCount++;
665 Object oldValue = elementData_[first_];
666 elementData_[first_] = null;
667 ++first_;
668 if (first_ == elementData_.length)
669 {
670 first_ = 0;
671 }
672 --size_;
673 return oldValue;
674 }
675
676
677 /**
678 * Removes the element from the back of this list.
679 *
680 * @return the element that was removed from the list.
681 * @throws IndexOutOfBoundsException if the list is empty.
682 */
683 public Object removeLast()
684 {
685 if (size_ == 0)
686 {
687 throw new IndexOutOfBoundsException(
688 "Index: 0, Size: "+size_);
689 }
690 modCount++;
691 --last_;
692 if (last_ == -1)
693 {
694 last_ = elementData_.length-1;
695 }
696 Object oldValue = elementData_[last_];
697 elementData_[last_] = null;
698 --size_;
699 return oldValue;
700 }
701
702
703 /**
704 * Removes the element at the specified position in this list.
705 * Shifts any subsequent elements to the left (subtracts one from their
706 * indices).
707 *
708 * @param index the index of the element to removed.
709 * @return the element that was removed from the list.
710 * @throws IndexOutOfBoundsException if index out of range <tt>(index
711 * < 0 || index >= size())</tt>.
712 */
713 public Object remove(
714 int index)
715 {
716 RangeCheck(index);
717 if (index == 0)
718 {
719 return removeFirst();
720 }
721 else if (index == size_-1)
722 {
723 return removeLast();
724 }
725 else
726 {
727 modCount++;
728 int realIndex = rotateIndex_(index+first_);
729 Object oldValue = elementData_[realIndex];
730 if (realIndex < first_)
731 {
732 // Pull from back
733 System.arraycopy(elementData_, realIndex+1, elementData_,
734 realIndex, last_-realIndex-1);
735 --last_;
736 if (last_ == -1)
737 {
738 last_ = elementData_.length-1;
739 }
740 elementData_[last_] = null; // Let gc do its work
741 }
742 else
743 {
744 // Pull from front
745 System.arraycopy(elementData_, first_, elementData_,
746 first_+1, index);
747 elementData_[first_] = null; // Let gc do its work
748 ++first_;
749 if (first_ == elementData_.length)
750 {
751 first_ = 0;
752 }
753 }
754 --size_;
755 return oldValue;
756 }
757 }
758
759
760 /**
761 * Removes all of the elements from this list. The list will
762 * be empty after this call returns.
763 */
764 public void clear()
765 {
766 modCount++;
767 // Let gc do its work
768 int curIndex = first_;
769 for (int i = 0; i < size_; i++)
770 {
771 elementData_[curIndex] = null;
772 ++curIndex;
773 if (curIndex == elementData_.length)
774 {
775 curIndex = 0;
776 }
777 }
778 size_ = first_ = last_ = 0;
779 }
780
781
782 /**
783 * Appends all of the elements in the specified Collection to the end of
784 * this list, in the order that they are returned by the
785 * specified Collection's Iterator. The behavior of this operation is
786 * undefined if the specified Collection is modified while the operation
787 * is in progress. (This implies that the behavior of this call is
788 * undefined if the specified Collection is this list, and this
789 * list is nonempty.)
790 *
791 * @param c the elements to be inserted into this list.
792 * @throws IndexOutOfBoundsException if index out of range <tt>(index
793 * < 0 || index > size())</tt>.
794 */
795 public boolean addAll(
796 Collection c)
797 {
798 return addAllLast(c);
799 }
800
801
802 /**
803 * Appends all of the elements in the specified Collection to the end of
804 * this list, in the order that they are returned by the
805 * specified Collection's Iterator. The behavior of this operation is
806 * undefined if the specified Collection is modified while the operation
807 * is in progress. (This implies that the behavior of this call is
808 * undefined if the specified Collection is this list, and this
809 * list is nonempty.)
810 *
811 * @param c the elements to be inserted into this list.
812 * @throws IndexOutOfBoundsException if index out of range <tt>(index
813 * < 0 || index > size())</tt>.
814 */
815 public boolean addAllLast(
816 Collection c)
817 {
818 int numNew = c.size();
819 if (numNew > 0)
820 {
821 ensureCapacity(size_ + numNew); // increments modCount!!
822 Iterator e = c.iterator();
823 for (int i=0; i<numNew; i++)
824 {
825 elementData_[last_] = e.next();
826 ++last_;
827 if (last_ == elementData_.length)
828 {
829 last_ = 0;
830 }
831 }
832 size_ += numNew;
833 }
834 return numNew != 0;
835 }
836
837
838 /**
839 * Appends all of the elements in the specified Collection to the
840 * beginning of this list, in the order that they are returned by the
841 * specified Collection's Iterator. The behavior of this operation is
842 * undefined if the specified Collection is modified while the operation
843 * is in progress. (This implies that the behavior of this call is
844 * undefined if the specified Collection is this list, and this
845 * list is nonempty.)
846 *
847 * @param c the elements to be inserted into this list.
848 * @throws IndexOutOfBoundsException if index out of range <tt>(index
849 * < 0 || index > size())</tt>.
850 */
851 public boolean addAllFirst(
852 Collection c)
853 {
854 int numNew = c.size();
855 if (numNew > 0)
856 {
857 ensureCapacity(size_ + numNew); // increments modCount!!
858 first_ -= numNew;
859 if (first_ < 0)
860 {
861 first_ += elementData_.length;
862 }
863 int index = first_;
864 Iterator e = c.iterator();
865 for (int i=0; i<numNew; i++)
866 {
867 elementData_[index] = e.next();
868 ++index;
869 if (index == elementData_.length)
870 {
871 index = 0;
872 }
873 }
874 size_ += numNew;
875 }
876 return numNew != 0;
877 }
878
879
880 /**
881 * Inserts all of the elements in the specified Collection into this
882 * list, starting at the specified position. Shifts the element
883 * currently at that position (if any) and any subsequent elements to
884 * the right (increases their indices). The new elements will appear
885 * in the list in the order that they are returned by the
886 * specified Collection's iterator.
887 *
888 * @param index index at which to insert first element
889 * from the specified collection.
890 * @param c elements to be inserted into this list.
891 * @throws IndexOutOfBoundsException if index out of range <tt>(index
892 * < 0 || index > size())</tt>.
893 */
894 public boolean addAll(
895 int index,
896 Collection c)
897 {
898 if (index > size_ || index < 0)
899 {
900 throw new IndexOutOfBoundsException(
901 "Index: "+index+", Size: "+size_);
902 }
903 else if (index == 0)
904 {
905 return addAllFirst(c);
906 }
907 else if (index == size_)
908 {
909 return addAllLast(c);
910 }
911 else
912 {
913 int numNew = c.size();
914 if (numNew > 0)
915 {
916 ensureCapacity(size_ + numNew); // increments modCount!!
917 int realIndex = rotateIndex_(index+first_);
918 if (last_ < first_)
919 {
920 // All free space is in one chunk because the wraparound is
921 // in the middle of the data
922 if (realIndex > first_)
923 {
924 // Push front
925 System.arraycopy(elementData_, first_, elementData_,
926 first_-numNew, index);
927 Iterator e = c.iterator();
928 for (int i=0; i<numNew; i++)
929 {
930 elementData_[realIndex-numNew+i] = e.next();
931 }
932 first_ -= numNew;
933 }
934 else
935 {
936 // Push back
937 System.arraycopy(elementData_, realIndex, elementData_,
938 realIndex+numNew, last_-realIndex);
939 Iterator e = c.iterator();
940 for (int i=0; i<numNew; i++)
941 {
942 elementData_[realIndex+i] = e.next();
943 }
944 last_ += numNew;
945 }
946 }
947 else
948 {
949 // Free space may be split between beginning and end
950 if (first_ >= numNew)
951 {
952 // There's room to push front
953 System.arraycopy(elementData_, first_, elementData_,
954 first_-numNew, index);
955 Iterator e = c.iterator();
956 for (int i=0; i<numNew; i++)
957 {
958 elementData_[realIndex-numNew+i] = e.next();
959 }
960 first_ -= numNew;
961 }
962 else if (elementData_.length-last_ >= numNew)
963 {
964 // There's room to push back
965 System.arraycopy(elementData_, realIndex, elementData_,
966 realIndex+numNew, last_-realIndex);
967 Iterator e = c.iterator();
968 for (int i=0; i<numNew; i++)
969 {
970 elementData_[realIndex+i] = e.next();
971 }
972 last_ += numNew;
973 if (last_ == elementData_.length)
974 {
975 last_ = 0;
976 }
977 }
978 else
979 {
980 // Push front to the beginning, and push back the rest.
981 System.arraycopy(elementData_, first_, elementData_,
982 0, index);
983 System.arraycopy(elementData_, realIndex, elementData_,
984 realIndex+(numNew-first_), last_-realIndex);
985 realIndex -= first_;
986 Iterator e = c.iterator();
987 for (int i=0; i<numNew; i++)
988 {
989 elementData_[realIndex+i] = e.next();
990 }
991 first_ = 0;
992 last_ = size_ + numNew;
993 if (last_ == elementData_.length)
994 {
995 last_ = 0;
996 }
997 }
998 }
999 size_ += numNew;
1000 }
1001 return numNew != 0;
1002 }
1003 }
1004
1005
1006 /**
1007 * Removes from this List the last <tt>num</tt> elements.
1008 * This call shortens the list by <tt>num</tt> elements.
1009 * (If <tt>num==0</tt>, this operation has no effect.)
1010 *
1011 * @param num number of elements to remove
1012 */
1013 public void removeLast(
1014 int num)
1015 {
1016 if (num < 0 || num > size_)
1017 {
1018 throw new IllegalArgumentException("Num: " + num + ", Size: " + size_);
1019 }
1020 ++modCount;
1021 for (int i=0; i<num; ++i)
1022 {
1023 --last_;
1024 if (last_ == -1)
1025 {
1026 last_ = elementData_.length-1;
1027 }
1028 elementData_[last_] = null;
1029 }
1030 size_ -= num;
1031 }
1032
1033
1034 /**
1035 * Removes from this List the first <tt>num</tt> elements. Shifts
1036 * all remaining elements to the left (reduces their index).
1037 * This call shortens the list by <tt>num</tt> elements.
1038 * (If <tt>num==0</tt>, this operation has no effect.)
1039 *
1040 * @param num number of elements to remove
1041 */
1042 public void removeFirst(
1043 int num)
1044 {
1045 if (num < 0 || num > size_)
1046 {
1047 throw new IllegalArgumentException("Num: " + num + ", Size: " + size_);
1048 }
1049 ++modCount;
1050 for (int i=0; i<num; ++i)
1051 {
1052 elementData_[first_] = null;
1053 ++first_;
1054 if (first_ == elementData_.length)
1055 {
1056 first_ = 0;
1057 }
1058 }
1059 size_ -= num;
1060 }
1061
1062
1063 /**
1064 * Removes from this List all of the elements whose index is between
1065 * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
1066 * elements to the left (reduces their index).
1067 * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
1068 * (If <tt>toIndex<=fromIndex</tt>, this operation has no effect.)
1069 * <p>
1070 * AbstractList.removeRange() is protected, but RotatingArrayList makes this
1071 * method public since it may be useful to clients.
1072 *
1073 * @param fromIndex index of first element to be removed.
1074 * @param toIndex index after last element to be removed.
1075 */
1076 public void removeRange(
1077 int fromIndex,
1078 int toIndex)
1079 {
1080 if (fromIndex > size_ || fromIndex < 0)
1081 {
1082 throw new IndexOutOfBoundsException(
1083 "From_Index: "+fromIndex+", Size: "+size_);
1084 }
1085 if (toIndex > size_ || toIndex < 0)
1086 {
1087 throw new IndexOutOfBoundsException(
1088 "To_Index: "+toIndex+", Size: "+size_);
1089 }
1090 if (toIndex < fromIndex)
1091 {
1092 // Silently interpret this as remove nothing
1093 toIndex = fromIndex;
1094 }
1095
1096 if (fromIndex == 0)
1097 {
1098 removeFirst(toIndex);
1099 }
1100 else if (toIndex == size_)
1101 {
1102 removeLast(size_-fromIndex);
1103 }
1104 else
1105 {
1106 ++modCount;
1107 int numRemoved = toIndex-fromIndex;
1108 if (numRemoved > 0)
1109 {
1110 int realFromIndex = rotateIndex_(fromIndex+first_);
1111 int realToIndex = rotateIndex_(toIndex+first_);
1112 if (last_ <= first_)
1113 {
1114 // All free space is in one chunk because the wraparound is
1115 // in the middle of the data
1116 if (realToIndex > first_ || realToIndex == 0)
1117 {
1118 // Pull from front
1119 System.arraycopy(elementData_, first_, elementData_,
1120 first_+numRemoved, fromIndex);
1121 for (int i=0; i<numRemoved; i++)
1122 {
1123 elementData_[first_+i] = null;
1124 }
1125 first_ += numRemoved;
1126 // first_ cannot wrap around, otherwise removeFirst() would have
1127 // been called instead
1128 }
1129 else if (realFromIndex < last_)
1130 {
1131 // Pull from back
1132 System.arraycopy(elementData_, realToIndex, elementData_,
1133 realFromIndex, last_-realToIndex);
1134 for (int i=-numRemoved; i<0; i++)
1135 {
1136 elementData_[last_+i] = null;
1137 }
1138 last_ -= numRemoved;
1139 // last_ cannot wrap around
1140 }
1141 else
1142 {
1143 // Wraparound is in the deletion range.
1144 // Pull some from front and some from back.
1145 int frontRemoved = elementData_.length-realFromIndex;
1146 int backRemoved = realToIndex;
1147 System.arraycopy(elementData_, first_, elementData_,
1148 first_+frontRemoved, fromIndex);
1149 for (int i=0; i<frontRemoved; i++)
1150 {
1151 elementData_[first_+i] = null;
1152 }
1153 first_ += frontRemoved;
1154 // first_ cannot wrap around, otherwise removeFirst() would have
1155 // been called instead
1156 System.arraycopy(elementData_, realToIndex, elementData_,
1157 0, last_-realToIndex);
1158 for (int i=-backRemoved; i<0; i++)
1159 {
1160 elementData_[last_+i] = null;
1161 }
1162 last_ -= backRemoved;
1163 // last_ cannot wrap around
1164 }
1165 }
1166 else
1167 {
1168 // Wraparound is in the free space. Pull from the shortest side.
1169 int frontPull = fromIndex;
1170 int backPull = last_-realToIndex;
1171 if (frontPull < backPull)
1172 {
1173 // Pull from front
1174 System.arraycopy(elementData_, first_, elementData_,
1175 first_+numRemoved, fromIndex);
1176 for (int i=0; i<numRemoved; i++)
1177 {
1178 elementData_[first_+i] = null;
1179 }
1180 first_ += numRemoved;
1181 // cannot wrap around
1182 }
1183 else
1184 {
1185 // Pull from back
1186 System.arraycopy(elementData_, realToIndex, elementData_,
1187 realFromIndex, last_-realToIndex);
1188 for (int i=-numRemoved; i<0; i++)
1189 {
1190 elementData_[last_+i] = null;
1191 }
1192 last_ -= numRemoved;
1193 // cannot wrap around
1194 }
1195 }
1196 size_ -= numRemoved;
1197 }
1198 }
1199 }
1200
1201
1202 /**
1203 * Check if the given index is in range. If not, throw an appropriate
1204 * runtime exception.
1205 */
1206 private void RangeCheck(
1207 int index)
1208 {
1209 if (index >= size_ || index < 0)
1210 {
1211 throw new IndexOutOfBoundsException(
1212 "Index: "+index+", Size: "+size_);
1213 }
1214 }
1215
1216
1217 /**
1218 * Save the state of the <tt>RotatingArrayList</tt> instance to a stream (that
1219 * is, serialize it).
1220 *
1221 * @serialData The length of the array backing the <tt>ArrayList</tt>
1222 * instance is emitted (int), followed by all of its elements
1223 * (each an <tt>Object</tt>) in the proper order.
1224 */
1225 private synchronized void writeObject(
1226 ObjectOutputStream s)
1227 throws
1228 IOException
1229 {
1230 // Write out element count, and any hidden stuff
1231 s.defaultWriteObject();
1232
1233 // Write out all elements in the proper order.
1234 for (int i=0; i<size_; i++)
1235 {
1236 s.writeObject(elementData_[rotateIndex_(i+first_)]);
1237 }
1238 }
1239
1240
1241 /**
1242 * Reconstitute the <tt>RotatingArrayList</tt> instance from a stream (that is,
1243 * deserialize it).
1244 */
1245 private synchronized void readObject(
1246 ObjectInputStream s)
1247 throws
1248 IOException,
1249 ClassNotFoundException
1250 {
1251 // Read in size, and any hidden stuff
1252 s.defaultReadObject();
1253
1254 // Allocate array
1255 elementData_ = new Object[size_];
1256
1257 // Read in all elements in the proper order.
1258 for (int i=0; i<size_; i++)
1259 {
1260 elementData_[i] = s.readObject();
1261 }
1262 first_ = last_ = 0;
1263 }
1264}
1265