1 | /*
|
---|
2 | * 03/26/2004
|
---|
3 | *
|
---|
4 | * DynamicIntArray.java - Similar to an ArrayList, but holds ints instead
|
---|
5 | * of Objects.
|
---|
6 | *
|
---|
7 | * This library is distributed under a modified BSD license. See the included
|
---|
8 | * RSyntaxTextArea.License.txt file for details.
|
---|
9 | */
|
---|
10 | package org.fife.util;
|
---|
11 |
|
---|
12 | import java.io.Serializable;
|
---|
13 |
|
---|
14 |
|
---|
15 | /**
|
---|
16 | * Similar to a <code>java.util.ArrayList</code>, but specifically for
|
---|
17 | * <code>int</code>s. This is basically an array of integers that resizes
|
---|
18 | * itself (if necessary) when adding new elements.
|
---|
19 | *
|
---|
20 | * @author Robert Futrell
|
---|
21 | * @version 0.8
|
---|
22 | */
|
---|
23 | public class DynamicIntArray implements Serializable {
|
---|
24 |
|
---|
25 | /**
|
---|
26 | * The actual data.
|
---|
27 | */
|
---|
28 | private int[] data;
|
---|
29 |
|
---|
30 | /**
|
---|
31 | * The number of values in the array. Note that this is NOT the
|
---|
32 | * capacity of the array; rather, <code>size <= capacity</code>.
|
---|
33 | */
|
---|
34 | private int size;
|
---|
35 |
|
---|
36 |
|
---|
37 | /**
|
---|
38 | * Constructs a new array object with an initial capacity of 10.
|
---|
39 | */
|
---|
40 | public DynamicIntArray() {
|
---|
41 | this(10);
|
---|
42 | }
|
---|
43 |
|
---|
44 |
|
---|
45 | /**
|
---|
46 | * Constructs a new array object with a given initial capacity.
|
---|
47 | *
|
---|
48 | * @param initialCapacity The initial capacity.
|
---|
49 | * @throws IllegalArgumentException If <code>initialCapacity</code> is
|
---|
50 | * negative.
|
---|
51 | */
|
---|
52 | public DynamicIntArray(int initialCapacity) {
|
---|
53 | if (initialCapacity<0) {
|
---|
54 | throw new IllegalArgumentException("Illegal initialCapacity: "
|
---|
55 | + initialCapacity);
|
---|
56 | }
|
---|
57 | data = new int[initialCapacity];
|
---|
58 | size = 0;
|
---|
59 | }
|
---|
60 |
|
---|
61 |
|
---|
62 | /**
|
---|
63 | * Constructs a new array object from the given int array. The resulting
|
---|
64 | * <code>DynamicIntArray</code> will have an initial capacity of 110%
|
---|
65 | * the size of the array.
|
---|
66 | *
|
---|
67 | * @param intArray Initial data for the array object.
|
---|
68 | * @throws NullPointerException If <code>intArray</code> is
|
---|
69 | * <code>null</code>.
|
---|
70 | */
|
---|
71 | public DynamicIntArray(int[] intArray) {
|
---|
72 | size = intArray.length;
|
---|
73 | int capacity = (int)Math.min(size*110L/100, Integer.MAX_VALUE);
|
---|
74 | data = new int[capacity];
|
---|
75 | System.arraycopy(intArray,0, data,0, size); // source, dest, length.
|
---|
76 | }
|
---|
77 |
|
---|
78 |
|
---|
79 | /**
|
---|
80 | * Appends the specified <code>int</code> to the end of this array.
|
---|
81 | *
|
---|
82 | * @param value The <code>int</code> to be appended to this array.
|
---|
83 | */
|
---|
84 | public void add(int value) {
|
---|
85 | ensureCapacity(size + 1);
|
---|
86 | data[size++] = value;
|
---|
87 | }
|
---|
88 |
|
---|
89 |
|
---|
90 | /**
|
---|
91 | * Inserts all <code>int</code>s in the specified array into this array
|
---|
92 | * object at the specified location. Shifts the <code>int</code>
|
---|
93 | * currently at that position (if any) and any subsequent
|
---|
94 | * <code>int</code>s to the right (adds one to their indices).
|
---|
95 | *
|
---|
96 | * @param index The index at which the specified integer is to be
|
---|
97 | * inserted.
|
---|
98 | * @param intArray The array of <code>int</code>s to insert.
|
---|
99 | * @throws IndexOutOfBoundsException If <code>index</code> is less than
|
---|
100 | * zero or greater than <code>getSize()</code>.
|
---|
101 | * @throws NullPointerException If <code>intArray<code> is
|
---|
102 | * <code>null<code>.
|
---|
103 | */
|
---|
104 | public void add(int index, int[] intArray) {
|
---|
105 | if (index>size) {
|
---|
106 | throwException2(index);
|
---|
107 | }
|
---|
108 | int addCount = intArray.length;
|
---|
109 | ensureCapacity(size+addCount);
|
---|
110 | int moveCount = size - index;
|
---|
111 | if (moveCount>0)
|
---|
112 | System.arraycopy(data,index, data,index+addCount, moveCount);
|
---|
113 | System.arraycopy(data,index, intArray,0, moveCount);
|
---|
114 | size += addCount;
|
---|
115 | }
|
---|
116 |
|
---|
117 |
|
---|
118 | /**
|
---|
119 | * Inserts the specified <code>int</code> at the specified position in
|
---|
120 | * this array. Shifts the <code>int</code> currently at that position (if
|
---|
121 | * any) and any subsequent <code>int</code>s to the right (adds one to
|
---|
122 | * their indices).
|
---|
123 | *
|
---|
124 | * @param index The index at which the specified integer is to be
|
---|
125 | * inserted.
|
---|
126 | * @param value The <code>int</code> to be inserted.
|
---|
127 | * @throws IndexOutOfBoundsException If <code>index</code> is less than
|
---|
128 | * zero or greater than <code>getSize()</code>.
|
---|
129 | */
|
---|
130 | public void add(int index, int value) {
|
---|
131 | if (index>size) {
|
---|
132 | throwException2(index);
|
---|
133 | }
|
---|
134 | ensureCapacity(size+1);
|
---|
135 | System.arraycopy(data,index, data,index+1, size-index);
|
---|
136 | data[index] = value;
|
---|
137 | size++;
|
---|
138 | }
|
---|
139 |
|
---|
140 |
|
---|
141 | /**
|
---|
142 | * Removes all values from this array object. Capacity will remain the
|
---|
143 | * same.
|
---|
144 | */
|
---|
145 | public void clear() {
|
---|
146 | size = 0;
|
---|
147 | }
|
---|
148 |
|
---|
149 |
|
---|
150 | /**
|
---|
151 | * Returns whether this array contains a given integer. This method
|
---|
152 | * performs a linear search, so it is not optimized for performance.
|
---|
153 | *
|
---|
154 | * @param integer The <code>int</code> for which to search.
|
---|
155 | * @return Whether the given integer is contained in this array.
|
---|
156 | */
|
---|
157 | public boolean contains(int integer) {
|
---|
158 | for (int i=0; i<size; i++) {
|
---|
159 | if (data[i]==integer)
|
---|
160 | return true;
|
---|
161 | }
|
---|
162 | return false;
|
---|
163 | }
|
---|
164 |
|
---|
165 |
|
---|
166 | /**
|
---|
167 | * Makes sure that this <code>DynamicIntArray</code> instance can hold
|
---|
168 | * at least the number of elements specified. If it can't, then the
|
---|
169 | * capacity is increased.
|
---|
170 | *
|
---|
171 | * @param minCapacity The desired minimum capacity.
|
---|
172 | */
|
---|
173 | private final void ensureCapacity(int minCapacity) {
|
---|
174 | int oldCapacity = data.length;
|
---|
175 | if (minCapacity > oldCapacity) {
|
---|
176 | int[] oldData = data;
|
---|
177 | // Ensures we don't just keep increasing capacity by some small
|
---|
178 | // number like 1...
|
---|
179 | int newCapacity = (oldCapacity * 3)/2 + 1;
|
---|
180 | if (newCapacity < minCapacity)
|
---|
181 | newCapacity = minCapacity;
|
---|
182 | data = new int[newCapacity];
|
---|
183 | System.arraycopy(oldData,0, data,0, size);
|
---|
184 | }
|
---|
185 | }
|
---|
186 |
|
---|
187 |
|
---|
188 | /**
|
---|
189 | * Returns the <code>int</code> at the specified position in this array
|
---|
190 | * object.
|
---|
191 | *
|
---|
192 | * @param index The index of the <code>int</code> to return.
|
---|
193 | * @return The <code>int</code> at the specified position in this array.
|
---|
194 | * @throws IndexOutOfBoundsException If <code>index</code> is less than
|
---|
195 | * zero or greater than or equal to <code>getSize()</code>.
|
---|
196 | */
|
---|
197 | public int get(int index) {
|
---|
198 | // Small enough to be inlined, and throwException() is rarely called.
|
---|
199 | if (index>=size) {
|
---|
200 | throwException(index);
|
---|
201 | }
|
---|
202 | return data[index];
|
---|
203 | }
|
---|
204 |
|
---|
205 |
|
---|
206 | /**
|
---|
207 | * Returns the <code>int</code> at the specified position in this array
|
---|
208 | * object, without doing any bounds checking. You really should use
|
---|
209 | * {@link #get(int)} instead of this method.
|
---|
210 | *
|
---|
211 | * @param index The index of the <code>int</code> to return.
|
---|
212 | * @return The <code>int</code> at the specified position in this array.
|
---|
213 | */
|
---|
214 | public int getUnsafe(int index) {
|
---|
215 | // Small enough to be inlined.
|
---|
216 | return data[index];
|
---|
217 | }
|
---|
218 |
|
---|
219 |
|
---|
220 | /**
|
---|
221 | * Returns the number of <code>int</code>s in this array object.
|
---|
222 | *
|
---|
223 | * @return The number of <code>int</code>s in this array object.
|
---|
224 | */
|
---|
225 | public int getSize() {
|
---|
226 | return size;
|
---|
227 | }
|
---|
228 |
|
---|
229 |
|
---|
230 | /**
|
---|
231 | * Returns whether or not this array object is empty.
|
---|
232 | *
|
---|
233 | * @return Whether or not this array object contains no elements.
|
---|
234 | */
|
---|
235 | public boolean isEmpty() {
|
---|
236 | return size==0;
|
---|
237 | }
|
---|
238 |
|
---|
239 |
|
---|
240 | /**
|
---|
241 | * Removes the <code>int</code> at the specified location from this array
|
---|
242 | * object.
|
---|
243 | *
|
---|
244 | * @param index The index of the <code>int</code> to remove.
|
---|
245 | * @throws IndexOutOfBoundsException If <code>index</code> is less than
|
---|
246 | * zero or greater than or equal to <code>getSize()</code>.
|
---|
247 | */
|
---|
248 | public void remove(int index) {
|
---|
249 | if (index>=size) {
|
---|
250 | throwException(index);
|
---|
251 | }
|
---|
252 | int toMove = size - index - 1;
|
---|
253 | if (toMove>0) {
|
---|
254 | System.arraycopy(data,index+1, data,index, toMove);
|
---|
255 | }
|
---|
256 | --size;
|
---|
257 | }
|
---|
258 |
|
---|
259 |
|
---|
260 | /**
|
---|
261 | * Removes the <code>int</code>s in the specified range from this array
|
---|
262 | * object.
|
---|
263 | *
|
---|
264 | * @param fromIndex The index of the first <code>int</code> to remove.
|
---|
265 | * @param toIndex The index AFTER the last <code>int</code> to remove.
|
---|
266 | * @throws IndexOutOfBoundsException If either of <code>fromIndex</code>
|
---|
267 | * or <code>toIndex</code> is less than zero or greater than or
|
---|
268 | * equal to <code>getSize()</code>.
|
---|
269 | */
|
---|
270 | public void removeRange(int fromIndex, int toIndex) {
|
---|
271 | if (fromIndex>=size || toIndex>size) {
|
---|
272 | throwException3(fromIndex, toIndex);
|
---|
273 | }
|
---|
274 | int moveCount = size - toIndex;
|
---|
275 | System.arraycopy(data,toIndex, data,fromIndex, moveCount);
|
---|
276 | size -= (toIndex - fromIndex);
|
---|
277 | }
|
---|
278 |
|
---|
279 |
|
---|
280 | /**
|
---|
281 | * Sets the <code>int</code> value at the specified position in this
|
---|
282 | * array object.
|
---|
283 | *
|
---|
284 | * @param index The index of the <code>int</code> to set
|
---|
285 | * @param value The value to set it to.
|
---|
286 | * @throws IndexOutOfBoundsException If <code>index</code> is less than
|
---|
287 | * zero or greater than or equal to <code>getSize()</code>.
|
---|
288 | */
|
---|
289 | public void set(int index, int value) {
|
---|
290 | // Small enough to be inlined, and throwException() is rarely called.
|
---|
291 | if (index>=size) {
|
---|
292 | throwException(index);
|
---|
293 | }
|
---|
294 | data[index] = value;
|
---|
295 | }
|
---|
296 |
|
---|
297 |
|
---|
298 | /**
|
---|
299 | * Sets the <code>int</code> value at the specified position in this
|
---|
300 | * array object, without doing any bounds checking. You should use
|
---|
301 | * {@link #set(int, int)} instead of this method.
|
---|
302 | *
|
---|
303 | * @param index The index of the <code>int</code> to set
|
---|
304 | * @param value The value to set it to.
|
---|
305 | */
|
---|
306 | public void setUnsafe(int index, int value) {
|
---|
307 | // Small enough to be inlined.
|
---|
308 | data[index] = value;
|
---|
309 | }
|
---|
310 |
|
---|
311 |
|
---|
312 | /**
|
---|
313 | * Throws an exception. This method isolates error-handling code from
|
---|
314 | * the error-checking code, so that callers (e.g. {@link #get} and
|
---|
315 | * {@link #set}) can be both small enough to be inlined, as well as
|
---|
316 | * not usually make any expensive method calls (since their callers will
|
---|
317 | * usually not pass illegal arguments to them).
|
---|
318 | *
|
---|
319 | * See <a href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5103956">
|
---|
320 | * this Sun bug report</a> for more information.
|
---|
321 | *
|
---|
322 | * @param index The invalid index.
|
---|
323 | * @throws IndexOutOfBoundsException Always.
|
---|
324 | */
|
---|
325 | private final void throwException(int index)
|
---|
326 | throws IndexOutOfBoundsException {
|
---|
327 | throw new IndexOutOfBoundsException("Index " + index +
|
---|
328 | " not in valid range [0-" + (size-1) + "]");
|
---|
329 | }
|
---|
330 |
|
---|
331 |
|
---|
332 | /**
|
---|
333 | * Throws an exception. This method isolates error-handling code from
|
---|
334 | * the error-checking code, so that callers can be both small enough to be
|
---|
335 | * inlined, as well as not usually make any expensive method calls (since
|
---|
336 | * their callers will usually not pass illegal arguments to them).
|
---|
337 | *
|
---|
338 | * See <a href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5103956">
|
---|
339 | * this Sun bug report</a> for more information.
|
---|
340 | *
|
---|
341 | * @param index The invalid index.
|
---|
342 | * @throws IndexOutOfBoundsException Always.
|
---|
343 | */
|
---|
344 | private final void throwException2(int index)
|
---|
345 | throws IndexOutOfBoundsException {
|
---|
346 | throw new IndexOutOfBoundsException("Index " + index +
|
---|
347 | ", not in range [0-" + size + "]");
|
---|
348 | }
|
---|
349 |
|
---|
350 |
|
---|
351 | /**
|
---|
352 | * Throws an exception. This method isolates error-handling code from
|
---|
353 | * the error-checking code, so that callers can be both small enough to be
|
---|
354 | * inlined, as well as not usually make any expensive method calls (since
|
---|
355 | * their callers will usually not pass illegal arguments to them).
|
---|
356 | *
|
---|
357 | * See <a href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5103956">
|
---|
358 | * this Sun bug report</a> for more information.
|
---|
359 | *
|
---|
360 | * @param index The invalid index.
|
---|
361 | * @throws IndexOutOfBoundsException Always.
|
---|
362 | */
|
---|
363 | private final void throwException3(int fromIndex, int toIndex)
|
---|
364 | throws IndexOutOfBoundsException {
|
---|
365 | throw new IndexOutOfBoundsException("Index range [" +
|
---|
366 | fromIndex + ", " + toIndex +
|
---|
367 | "] not in valid range [0-" + (size-1) + "]");
|
---|
368 | }
|
---|
369 |
|
---|
370 |
|
---|
371 | } |
---|