KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > ArrayList


1 /*
2  * Copyright 2007 Google Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5  * use this file except in compliance with the License. You may obtain a copy of
6  * the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13  * License for the specific language governing permissions and limitations under
14  * the License.
15  */
16 package java.util;
17
18 import com.google.gwt.core.client.JavaScriptObject;
19
20 /**
21  * See Sun's JDK 1.4 documentation for documentation.
22  *
23  * Differences between this implementation and JDK 1.4 <code>ArrayList</code>
24  * include capacity management and range checking.
25  * <p>
26  * <b>Capacity</b> There is no speed advantage to pre-allocating array sizes in
27  * JavaScript, so this implementation does not include any of the capacity and
28  * "growth increment" concepts in the standard ArrayList class. Although
29  * <code>ArrayList(int)</code> accepts a value for the intitial capacity of
30  * the array, this constructor simply delegates to <code>ArrayList()</code>.
31  * It is only present for compatibility with JDK 1.4's API.
32  * </p>
33  * <p>
34  * <b>Dual endedness</b> For increased performance, this implementation supports
35  * constant time insertion and deletion from either end.
36  * </p>
37  */
38 public class ArrayList extends AbstractList JavaDoc implements List JavaDoc, Cloneable JavaDoc,
39     RandomAccess JavaDoc {
40   /*
41    * Implementation notes:
42    * Currently if one uses an ArrayList as a ring buffer, adding from one end,
43    * and deleting from the other, the indexes will increase (or decrease)
44    * without ever being normalized. Back of the envelope calculations
45    * indicate that at 30 indexes per second, it will take a year of solid run
46    * time to chew through the billion indexes needed to get into trouble.
47    * Given that it seemed better not to rebalance than to charge everyone the
48    * extra code size the rebalancing code would represent.
49    */
50
51   protected static boolean equals(Object JavaDoc a, Object JavaDoc b) {
52     return (a == null ? b == null : a.equals(b));
53   }
54   /**
55    * This field holds the javascript array, and is not private to avoid Eclipse
56    * warnings.
57    */
58   transient JavaScriptObject array;
59   /**
60    * This field holds the last populated index of the array and is not private
61    * to avoid Eclipse warnings.
62    */
63   int endIndex;
64   /**
65    * This field holds the first populated index of the array and is not private
66    * to avoid Eclipse warnings.
67    */
68   int startIndex;
69
70   public ArrayList() {
71     initArray();
72   }
73
74   public ArrayList(Collection JavaDoc c) {
75     initArray();
76     addAll(c);
77   }
78
79   /**
80    * There is no speed advantage to pre-allocating array sizes in JavaScript,
81    * so the <code>intialCapacity</code> parameter is ignored. This constructor is
82    * only present for compatibility with JDK 1.4's API.
83    */
84   public ArrayList(int initialCapacity) {
85     // initialCapacity is ignored in JS implementation; this constructor is
86 // present for JDK 1.4 compatibility
87 this();
88   }
89
90   public native void add(int index, Object JavaDoc o) /*-{
91     var array = this.@java.util.ArrayList::array;
92     var endIndex = this.@java.util.ArrayList::endIndex;
93     var startIndex = this.@java.util.ArrayList::startIndex;
94     // This if is not an else if to call attention to the early return.
95     if (index + startIndex == endIndex) {
96       // If we are at the end simply set the next element to hold the value.
97       array[endIndex] = o;
98       this.@java.util.ArrayList::endIndex++;
99       return;
100     }
101     if (index == 0) {
102       // If we are adding at the beginning, simply set the new element, and
103       // move the beginning back.
104       array[--this.@java.util.ArrayList::startIndex] = o;
105       return;
106     }
107     
108     // Somewhere in the middle, so do range checking and the splice.
109     // Range checking, must be more permissive since one can add off the end.
110     this.@java.util.ArrayList::verifyIndexOneExtra(I)(index);
111     array.splice(index + startIndex, 0, o);
112     // The end of the array moved forward if we got here so record that.
113     this.@java.util.ArrayList::endIndex++;
114   }-*/;
115
116   public boolean add(Object JavaDoc o) {
117     add(size(),o);
118     return true;
119   }
120  
121   public void clear() {
122     setSize(0);
123   }
124   
125   public Object JavaDoc clone() {
126     return new ArrayList JavaDoc(this);
127   }
128
129   public boolean contains(Object JavaDoc o) {
130     return (indexOf(o) != -1);
131   }
132  
133   public native Object JavaDoc get(int index) /*-{
134     this.@java.util.ArrayList::verifyIndex(I)(index);
135     var startIndex = this.@java.util.ArrayList::startIndex;
136     return this.@java.util.ArrayList::array[index + startIndex];
137   }-*/;
138   
139   public int indexOf(Object JavaDoc o) {
140     return indexOf(o, 0);
141   }
142
143   public native boolean isEmpty() /*-{
144     return (this.@java.util.ArrayList::endIndex == this.@java.util.ArrayList::startIndex);
145   }-*/;
146
147   public int lastIndexOf(Object JavaDoc o) {
148      return lastIndexOf(o, size() - 1);
149   }
150
151   public Object JavaDoc remove(int index) {
152     Object JavaDoc old = get(index);
153     removeRange(index,index + 1);
154     return old;
155   }
156
157   public boolean remove(Object JavaDoc o) {
158     int i = indexOf(o);
159     if (i == -1) {
160       return false;
161     }
162     remove(i);
163     return true;
164   }
165
166   public native Object JavaDoc set(int index, Object JavaDoc o) /*-{
167     this.@java.util.ArrayList::verifyIndex(I)(index);
168     var array = this.@java.util.ArrayList::array;
169     var startIndex = this.@java.util.ArrayList::startIndex;
170     var old = array[index + startIndex];
171     array[index + startIndex] = o;
172     return old;
173   }-*/;
174
175   public native int size() /*-{
176     return this.@java.util.ArrayList::endIndex - this.@java.util.ArrayList::startIndex;
177   }-*/;
178   
179   protected native void removeRange(int fromIndex, int toIndex) /*-{
180     this.@java.util.ArrayList::verifyIndexOneExtra(I)(fromIndex);
181     this.@java.util.ArrayList::verifyIndexOneExtra(I)(toIndex);
182     var array = this.@java.util.ArrayList::array;
183     var startIndex = this.@java.util.ArrayList::startIndex;
184     var endIndex = this.@java.util.ArrayList::endIndex;
185     if (fromIndex == 0) {
186       // Chop off the beginning.
187       for (var i = startIndex; i < (toIndex + startIndex); i++) {
188         delete array[i];
189       }
190       this.@java.util.ArrayList::startIndex += (toIndex - fromIndex);
191     } else if (toIndex + startIndex == endIndex) {
192       // Chop off the end.
193       for (var i = (fromIndex + startIndex); i < endIndex; i++) {
194         delete array[i];
195       }
196       this.@java.util.ArrayList::endIndex = (fromIndex + startIndex);
197     } else {
198       // Splice from the middle.
199       var numToRemove = toIndex - fromIndex;
200       array.splice(fromIndex + startIndex, numToRemove);
201       this.@java.util.ArrayList::endIndex -= numToRemove;
202     }
203   }-*/;
204   
205   native int indexOf(Object JavaDoc o, int index) /*-{
206     var array = this.@java.util.ArrayList::array;
207     var startIndex = this.@java.util.ArrayList::startIndex;
208     var i = index + startIndex;
209     var endIndex = this.@java.util.ArrayList::endIndex;
210     while (i < endIndex) {
211       if (@java.util.ArrayList::equals(Ljava/lang/Object;Ljava/lang/Object;)(array[i],o)) {
212         return i - startIndex;
213       }
214       ++i;
215     }
216     return -1;
217   }-*/;
218   
219   /**
220    * Throws an <code>indexOutOfBoundsException</code>, and is not
221    * private to avoid eclipse warnings.
222    */
223   void indexOutOfBounds(int i) {
224     throw new IndexOutOfBoundsException JavaDoc("Size: " + this.size() + " Index: " + i);
225   }
226   
227   /**
228    * Computes the last index of an element given an offset, and is
229    * not private to avoid eclipse warnings.
230    */
231   native int lastIndexOf(Object JavaDoc o, int index) /*-{
232     var array = this.@java.util.ArrayList::array;
233     var startIndex = this.@java.util.ArrayList::startIndex;
234     var i = index + startIndex;
235     while (i >= startIndex) {
236       if (@java.util.ArrayList::equals(Ljava/lang/Object;Ljava/lang/Object;)(array[i],o)) {
237         return i - startIndex;
238       }
239       --i;
240     }
241     return -1;
242   }-*/;
243
244   /**
245    * This function sets the size of the array, and is used in Vector.
246    */
247   native void setSize(int newSize) /*-{
248     // Make sure to null fill any newly created slots (otherwise,
249     // get() can return 'undefined').
250     var endIndex = this.@java.util.ArrayList::endIndex;
251     var startIndex = this.@java.util.ArrayList::startIndex;
252     var array = this.@java.util.ArrayList::array;
253     var newEnd = newSize + startIndex;
254     for (var i = endIndex; i < newEnd; ++i) {
255       array[i] = null;
256     }
257
258     // Also make sure to clean up orphaned slots (or we'll end up
259     // leaving garbage uncollected).
260     for (var i = endIndex - 1; i >= newEnd; --i) {
261       delete array[i];
262     }
263     this.@java.util.ArrayList::endIndex = newEnd;
264   }-*/;
265   
266   native void verifyIndex(int index) /*-{
267     var endIndex = this.@java.util.ArrayList::endIndex;
268     var startIndex = this.@java.util.ArrayList::startIndex;
269     if (index < 0 || index + startIndex >= endIndex) {
270       this.@java.util.ArrayList::indexOutOfBounds(I)(index);
271     }
272   }-*/;
273   
274   native void verifyIndexOneExtra(int index) /*-{
275     var endIndex = this.@java.util.ArrayList::endIndex;
276     var startIndex = this.@java.util.ArrayList::startIndex;
277     if (index < 0 || index + startIndex > endIndex) {
278       this.@java.util.ArrayList::indexOutOfBounds(I)(index);
279     }
280   }-*/;
281  
282   private native void initArray() /*-{
283     this.@java.util.ArrayList::array = new Array();
284     var HALFWAY_INDEX = 1000000000; // Halfway through the address space
285     // Javascript arrays are sparse, so this wastes no space
286     this.@java.util.ArrayList::startIndex = HALFWAY_INDEX;
287     this.@java.util.ArrayList::endIndex = HALFWAY_INDEX;
288   }-*/;
289 }
290
Popular Tags