source: other-projects/rsyntax-textarea/src/java/org/fife/util/DynamicIntArray.java@ 25584

Last change on this file since 25584 was 25584, checked in by davidb, 12 years ago

Initial cut an a text edit area for GLI that supports color syntax highlighting
File size: 11.1 KB
Line 
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 */
10package org.fife.util;
11
12import 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 */
23public 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 &lt;= 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}
Note: See TracBrowser for help on using the repository browser.