src/share/classes/java/util/ArrayDeque.java

Print this page




 104 
 105     /**
 106      * The index at which the next element would be added to the tail
 107      * of the deque (via addLast(E), add(E), or push(E)).
 108      */
 109     private transient int tail;
 110 
 111     /**
 112      * The minimum capacity that we'll use for a newly created deque.
 113      * Must be a power of 2.
 114      */
 115     private static final int MIN_INITIAL_CAPACITY = 8;
 116 
 117     // ******  Array allocation and resizing utilities ******
 118 
 119     /**
 120      * Allocate empty array to hold the given number of elements.
 121      *
 122      * @param numElements  the number of elements to hold
 123      */

 124     private void allocateElements(int numElements) {
 125         int initialCapacity = MIN_INITIAL_CAPACITY;
 126         // Find the best power of two to hold elements.
 127         // Tests "<=" because arrays aren't kept full.
 128         if (numElements >= initialCapacity) {
 129             initialCapacity = numElements;
 130             initialCapacity |= (initialCapacity >>>  1);
 131             initialCapacity |= (initialCapacity >>>  2);
 132             initialCapacity |= (initialCapacity >>>  4);
 133             initialCapacity |= (initialCapacity >>>  8);
 134             initialCapacity |= (initialCapacity >>> 16);
 135             initialCapacity++;
 136 
 137             if (initialCapacity < 0)   // Too many elements, must back off
 138                 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
 139         }
 140         elements = (E[]) new Object[initialCapacity];
 141     }
 142 
 143     /**
 144      * Double the capacity of this deque.  Call only when full, i.e.,
 145      * when head and tail have wrapped around to become equal.
 146      */
 147     private void doubleCapacity() {
 148         assert head == tail;
 149         int p = head;
 150         int n = elements.length;
 151         int r = n - p; // number of elements to the right of p
 152         int newCapacity = n << 1;
 153         if (newCapacity < 0)
 154             throw new IllegalStateException("Sorry, deque too big");
 155         Object[] a = new Object[newCapacity];

 156         System.arraycopy(elements, p, a, 0, r);
 157         System.arraycopy(elements, 0, a, r, p);
 158         elements = (E[])a;
 159         head = 0;
 160         tail = n;
 161     }
 162 
 163     /**
 164      * Copies the elements from our element array into the specified array,
 165      * in order (from first to last element in the deque).  It is assumed
 166      * that the array is large enough to hold all elements in the deque.
 167      *
 168      * @return its argument
 169      */
 170     private <T> T[] copyElements(T[] a) {
 171         if (head < tail) {
 172             System.arraycopy(elements, head, a, 0, size());
 173         } else if (head > tail) {
 174             int headPortionLen = elements.length - head;
 175             System.arraycopy(elements, head, a, 0, headPortionLen);
 176             System.arraycopy(elements, 0, a, headPortionLen, tail);
 177         }
 178         return a;
 179     }
 180 
 181     /**
 182      * Constructs an empty array deque with an initial capacity
 183      * sufficient to hold 16 elements.
 184      */

 185     public ArrayDeque() {
 186         elements = (E[]) new Object[16];
 187     }
 188 
 189     /**
 190      * Constructs an empty array deque with an initial capacity
 191      * sufficient to hold the specified number of elements.
 192      *
 193      * @param numElements  lower bound on initial capacity of the deque
 194      */
 195     public ArrayDeque(int numElements) {
 196         allocateElements(numElements);
 197     }
 198 
 199     /**
 200      * Constructs a deque containing the elements of the specified
 201      * collection, in the order they are returned by the collection's
 202      * iterator.  (The first element returned by the collection's
 203      * iterator becomes the first element, or <i>front</i> of the
 204      * deque.)


 776      *
 777      * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
 778      * The following code can be used to dump the deque into a newly
 779      * allocated array of <tt>String</tt>:
 780      *
 781      * <pre>
 782      *     String[] y = x.toArray(new String[0]);</pre>
 783      *
 784      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 785      * <tt>toArray()</tt>.
 786      *
 787      * @param a the array into which the elements of the deque are to
 788      *          be stored, if it is big enough; otherwise, a new array of the
 789      *          same runtime type is allocated for this purpose
 790      * @return an array containing all of the elements in this deque
 791      * @throws ArrayStoreException if the runtime type of the specified array
 792      *         is not a supertype of the runtime type of every element in
 793      *         this deque
 794      * @throws NullPointerException if the specified array is null
 795      */

 796     public <T> T[] toArray(T[] a) {
 797         int size = size();
 798         if (a.length < size)
 799             a = (T[])java.lang.reflect.Array.newInstance(
 800                     a.getClass().getComponentType(), size);
 801         copyElements(a);
 802         if (a.length > size)
 803             a[size] = null;
 804         return a;
 805     }
 806 
 807     // *** Object methods ***
 808 
 809     /**
 810      * Returns a copy of this deque.
 811      *
 812      * @return a copy of this deque
 813      */
 814     public ArrayDeque<E> clone() {
 815         try {




 104 
 105     /**
 106      * The index at which the next element would be added to the tail
 107      * of the deque (via addLast(E), add(E), or push(E)).
 108      */
 109     private transient int tail;
 110 
 111     /**
 112      * The minimum capacity that we'll use for a newly created deque.
 113      * Must be a power of 2.
 114      */
 115     private static final int MIN_INITIAL_CAPACITY = 8;
 116 
 117     // ******  Array allocation and resizing utilities ******
 118 
 119     /**
 120      * Allocate empty array to hold the given number of elements.
 121      *
 122      * @param numElements  the number of elements to hold
 123      */
 124     @SuppressWarnings("unchecked")
 125     private void allocateElements(int numElements) {
 126         int initialCapacity = MIN_INITIAL_CAPACITY;
 127         // Find the best power of two to hold elements.
 128         // Tests "<=" because arrays aren't kept full.
 129         if (numElements >= initialCapacity) {
 130             initialCapacity = numElements;
 131             initialCapacity |= (initialCapacity >>>  1);
 132             initialCapacity |= (initialCapacity >>>  2);
 133             initialCapacity |= (initialCapacity >>>  4);
 134             initialCapacity |= (initialCapacity >>>  8);
 135             initialCapacity |= (initialCapacity >>> 16);
 136             initialCapacity++;
 137 
 138             if (initialCapacity < 0)   // Too many elements, must back off
 139                 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
 140         }
 141         elements = (E[]) new Object[initialCapacity];
 142     }
 143 
 144     /**
 145      * Double the capacity of this deque.  Call only when full, i.e.,
 146      * when head and tail have wrapped around to become equal.
 147      */
 148     private void doubleCapacity() {
 149         assert head == tail;
 150         int p = head;
 151         int n = elements.length;
 152         int r = n - p; // number of elements to the right of p
 153         int newCapacity = n << 1;
 154         if (newCapacity < 0)
 155             throw new IllegalStateException("Sorry, deque too big");
 156         @SuppressWarnings("unchecked")
 157         E[] a = (E[]) new Object[newCapacity];
 158         System.arraycopy(elements, p, a, 0, r);
 159         System.arraycopy(elements, 0, a, r, p);
 160         elements = a;
 161         head = 0;
 162         tail = n;
 163     }
 164 
 165     /**
 166      * Copies the elements from our element array into the specified array,
 167      * in order (from first to last element in the deque).  It is assumed
 168      * that the array is large enough to hold all elements in the deque.
 169      *
 170      * @return its argument
 171      */
 172     private <T> T[] copyElements(T[] a) {
 173         if (head < tail) {
 174             System.arraycopy(elements, head, a, 0, size());
 175         } else if (head > tail) {
 176             int headPortionLen = elements.length - head;
 177             System.arraycopy(elements, head, a, 0, headPortionLen);
 178             System.arraycopy(elements, 0, a, headPortionLen, tail);
 179         }
 180         return a;
 181     }
 182 
 183     /**
 184      * Constructs an empty array deque with an initial capacity
 185      * sufficient to hold 16 elements.
 186      */
 187     @SuppressWarnings("unchecked")
 188     public ArrayDeque() {
 189         elements = (E[]) new Object[16];
 190     }
 191 
 192     /**
 193      * Constructs an empty array deque with an initial capacity
 194      * sufficient to hold the specified number of elements.
 195      *
 196      * @param numElements  lower bound on initial capacity of the deque
 197      */
 198     public ArrayDeque(int numElements) {
 199         allocateElements(numElements);
 200     }
 201 
 202     /**
 203      * Constructs a deque containing the elements of the specified
 204      * collection, in the order they are returned by the collection's
 205      * iterator.  (The first element returned by the collection's
 206      * iterator becomes the first element, or <i>front</i> of the
 207      * deque.)


 779      *
 780      * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
 781      * The following code can be used to dump the deque into a newly
 782      * allocated array of <tt>String</tt>:
 783      *
 784      * <pre>
 785      *     String[] y = x.toArray(new String[0]);</pre>
 786      *
 787      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 788      * <tt>toArray()</tt>.
 789      *
 790      * @param a the array into which the elements of the deque are to
 791      *          be stored, if it is big enough; otherwise, a new array of the
 792      *          same runtime type is allocated for this purpose
 793      * @return an array containing all of the elements in this deque
 794      * @throws ArrayStoreException if the runtime type of the specified array
 795      *         is not a supertype of the runtime type of every element in
 796      *         this deque
 797      * @throws NullPointerException if the specified array is null
 798      */
 799     @SuppressWarnings("unchecked")
 800     public <T> T[] toArray(T[] a) {
 801         int size = size();
 802         if (a.length < size)
 803             a = (T[])java.lang.reflect.Array.newInstance(
 804                     a.getClass().getComponentType(), size);
 805         copyElements(a);
 806         if (a.length > size)
 807             a[size] = null;
 808         return a;
 809     }
 810 
 811     // *** Object methods ***
 812 
 813     /**
 814      * Returns a copy of this deque.
 815      *
 816      * @return a copy of this deque
 817      */
 818     public ArrayDeque<E> clone() {
 819         try {