001: /* ====================================================================
002: Licensed to the Apache Software Foundation (ASF) under one or more
003: contributor license agreements. See the NOTICE file distributed with
004: this work for additional information regarding copyright ownership.
005: The ASF licenses this file to You under the Apache License, Version 2.0
006: (the "License"); you may not use this file except in compliance with
007: the License. You may obtain a copy of the License at
008:
009: http://www.apache.org/licenses/LICENSE-2.0
010:
011: Unless required by applicable law or agreed to in writing, software
012: distributed under the License is distributed on an "AS IS" BASIS,
013: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: See the License for the specific language governing permissions and
015: limitations under the License.
016: ==================================================================== */
017:
018: package org.apache.poi.util;
019:
020: import java.util.*;
021:
022: /**
023: * A List of int's; as full an implementation of the java.util.List
024: * interface as possible, with an eye toward minimal creation of
025: * objects
026: *
027: * the mimicry of List is as follows:
028: * <ul>
029: * <li> if possible, operations designated 'optional' in the List
030: * interface are attempted
031: * <li> wherever the List interface refers to an Object, substitute
032: * int
033: * <li> wherever the List interface refers to a Collection or List,
034: * substitute IntList
035: * </ul>
036: *
037: * the mimicry is not perfect, however:
038: * <ul>
039: * <li> operations involving Iterators or ListIterators are not
040: * supported
041: * <li> remove(Object) becomes removeValue to distinguish it from
042: * remove(int index)
043: * <li> subList is not supported
044: * </ul>
045: *
046: * @author Marc Johnson
047: */
048:
049: public class IntList {
050: private int[] _array;
051: private int _limit;
052: private int fillval = 0;
053: private static final int _default_size = 128;
054:
055: /**
056: * create an IntList of default size
057: */
058:
059: public IntList() {
060: this (_default_size);
061: }
062:
063: public IntList(final int initialCapacity) {
064: this (initialCapacity, 0);
065: }
066:
067: /**
068: * create a copy of an existing IntList
069: *
070: * @param list the existing IntList
071: */
072:
073: public IntList(final IntList list) {
074: this (list._array.length);
075: System.arraycopy(list._array, 0, _array, 0, _array.length);
076: _limit = list._limit;
077: }
078:
079: /**
080: * create an IntList with a predefined initial size
081: *
082: * @param initialCapacity the size for the internal array
083: */
084:
085: public IntList(final int initialCapacity, int fillvalue) {
086: _array = new int[initialCapacity];
087: if (fillval != 0) {
088: fillval = fillvalue;
089: fillArray(fillval, _array, 0);
090: }
091: _limit = 0;
092: }
093:
094: private void fillArray(int val, int[] array, int index) {
095: for (int k = index; k < array.length; k++) {
096: array[k] = val;
097: }
098: }
099:
100: /**
101: * add the specfied value at the specified index
102: *
103: * @param index the index where the new value is to be added
104: * @param value the new value
105: *
106: * @exception IndexOutOfBoundsException if the index is out of
107: * range (index < 0 || index > size()).
108: */
109:
110: public void add(final int index, final int value) {
111: if (index > _limit) {
112: throw new IndexOutOfBoundsException();
113: } else if (index == _limit) {
114: add(value);
115: } else {
116:
117: // index < limit -- insert into the middle
118: if (_limit == _array.length) {
119: growArray(_limit * 2);
120: }
121: System.arraycopy(_array, index, _array, index + 1, _limit
122: - index);
123: _array[index] = value;
124: _limit++;
125: }
126: }
127:
128: /**
129: * Appends the specified element to the end of this list
130: *
131: * @param value element to be appended to this list.
132: *
133: * @return true (as per the general contract of the Collection.add
134: * method).
135: */
136:
137: public boolean add(final int value) {
138: if (_limit == _array.length) {
139: growArray(_limit * 2);
140: }
141: _array[_limit++] = value;
142: return true;
143: }
144:
145: /**
146: * Appends all of the elements in the specified collection to the
147: * end of this list, in the order that they are returned by the
148: * specified collection's iterator. The behavior of this
149: * operation is unspecified if the specified collection is
150: * modified while the operation is in progress. (Note that this
151: * will occur if the specified collection is this list, and it's
152: * nonempty.)
153: *
154: * @param c collection whose elements are to be added to this
155: * list.
156: *
157: * @return true if this list changed as a result of the call.
158: */
159:
160: public boolean addAll(final IntList c) {
161: if (c._limit != 0) {
162: if ((_limit + c._limit) > _array.length) {
163: growArray(_limit + c._limit);
164: }
165: System.arraycopy(c._array, 0, _array, _limit, c._limit);
166: _limit += c._limit;
167: }
168: return true;
169: }
170:
171: /**
172: * Inserts all of the elements in the specified collection into
173: * this list at the specified position. Shifts the element
174: * currently at that position (if any) and any subsequent elements
175: * to the right (increases their indices). The new elements will
176: * appear in this list in the order that they are returned by the
177: * specified collection's iterator. The behavior of this
178: * operation is unspecified if the specified collection is
179: * modified while the operation is in progress. (Note that this
180: * will occur if the specified collection is this list, and it's
181: * nonempty.)
182: *
183: * @param index index at which to insert first element from the
184: * specified collection.
185: * @param c elements to be inserted into this list.
186: *
187: * @return true if this list changed as a result of the call.
188: *
189: * @exception IndexOutOfBoundsException if the index is out of
190: * range (index < 0 || index > size())
191: */
192:
193: public boolean addAll(final int index, final IntList c) {
194: if (index > _limit) {
195: throw new IndexOutOfBoundsException();
196: }
197: if (c._limit != 0) {
198: if ((_limit + c._limit) > _array.length) {
199: growArray(_limit + c._limit);
200: }
201:
202: // make a hole
203: System.arraycopy(_array, index, _array, index + c._limit,
204: _limit - index);
205:
206: // fill it in
207: System.arraycopy(c._array, 0, _array, index, c._limit);
208: _limit += c._limit;
209: }
210: return true;
211: }
212:
213: /**
214: * Removes all of the elements from this list. This list will be
215: * empty after this call returns (unless it throws an exception).
216: */
217:
218: public void clear() {
219: _limit = 0;
220: }
221:
222: /**
223: * Returns true if this list contains the specified element. More
224: * formally, returns true if and only if this list contains at
225: * least one element e such that o == e
226: *
227: * @param o element whose presence in this list is to be tested.
228: *
229: * @return true if this list contains the specified element.
230: */
231:
232: public boolean contains(final int o) {
233: boolean rval = false;
234:
235: for (int j = 0; !rval && (j < _limit); j++) {
236: if (_array[j] == o) {
237: rval = true;
238: }
239: }
240: return rval;
241: }
242:
243: /**
244: * Returns true if this list contains all of the elements of the
245: * specified collection.
246: *
247: * @param c collection to be checked for containment in this list.
248: *
249: * @return true if this list contains all of the elements of the
250: * specified collection.
251: */
252:
253: public boolean containsAll(final IntList c) {
254: boolean rval = true;
255:
256: if (this != c) {
257: for (int j = 0; rval && (j < c._limit); j++) {
258: if (!contains(c._array[j])) {
259: rval = false;
260: }
261: }
262: }
263: return rval;
264: }
265:
266: /**
267: * Compares the specified object with this list for equality.
268: * Returns true if and only if the specified object is also a
269: * list, both lists have the same size, and all corresponding
270: * pairs of elements in the two lists are equal. (Two elements e1
271: * and e2 are equal if e1 == e2.) In other words, two lists are
272: * defined to be equal if they contain the same elements in the
273: * same order. This definition ensures that the equals method
274: * works properly across different implementations of the List
275: * interface.
276: *
277: * @param o the object to be compared for equality with this list.
278: *
279: * @return true if the specified object is equal to this list.
280: */
281:
282: public boolean equals(final Object o) {
283: boolean rval = this == o;
284:
285: if (!rval && (o != null) && (o.getClass() == this .getClass())) {
286: IntList other = (IntList) o;
287:
288: if (other._limit == _limit) {
289:
290: // assume match
291: rval = true;
292: for (int j = 0; rval && (j < _limit); j++) {
293: rval = _array[j] == other._array[j];
294: }
295: }
296: }
297: return rval;
298: }
299:
300: /**
301: * Returns the element at the specified position in this list.
302: *
303: * @param index index of element to return.
304: *
305: * @return the element at the specified position in this list.
306: *
307: * @exception IndexOutOfBoundsException if the index is out of
308: * range (index < 0 || index >= size()).
309: */
310:
311: public int get(final int index) {
312: if (index >= _limit) {
313: throw new IndexOutOfBoundsException();
314: }
315: return _array[index];
316: }
317:
318: /**
319: * Returns the hash code value for this list. The hash code of a
320: * list is defined to be the result of the following calculation:
321: *
322: * <code>
323: * hashCode = 1;
324: * Iterator i = list.iterator();
325: * while (i.hasNext()) {
326: * Object obj = i.next();
327: * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
328: * }
329: * </code>
330: *
331: * This ensures that list1.equals(list2) implies that
332: * list1.hashCode()==list2.hashCode() for any two lists, list1 and
333: * list2, as required by the general contract of Object.hashCode.
334: *
335: * @return the hash code value for this list.
336: */
337:
338: public int hashCode() {
339: int hash = 0;
340:
341: for (int j = 0; j < _limit; j++) {
342: hash = (31 * hash) + _array[j];
343: }
344: return hash;
345: }
346:
347: /**
348: * Returns the index in this list of the first occurrence of the
349: * specified element, or -1 if this list does not contain this
350: * element. More formally, returns the lowest index i such that
351: * (o == get(i)), or -1 if there is no such index.
352: *
353: * @param o element to search for.
354: *
355: * @return the index in this list of the first occurrence of the
356: * specified element, or -1 if this list does not contain
357: * this element.
358: */
359:
360: public int indexOf(final int o) {
361: int rval = 0;
362:
363: for (; rval < _limit; rval++) {
364: if (o == _array[rval]) {
365: break;
366: }
367: }
368: if (rval == _limit) {
369: rval = -1; // didn't find it
370: }
371: return rval;
372: }
373:
374: /**
375: * Returns true if this list contains no elements.
376: *
377: * @return true if this list contains no elements.
378: */
379:
380: public boolean isEmpty() {
381: return _limit == 0;
382: }
383:
384: /**
385: * Returns the index in this list of the last occurrence of the
386: * specified element, or -1 if this list does not contain this
387: * element. More formally, returns the highest index i such that
388: * (o == get(i)), or -1 if there is no such index.
389: *
390: * @param o element to search for.
391: *
392: * @return the index in this list of the last occurrence of the
393: * specified element, or -1 if this list does not contain
394: * this element.
395: */
396:
397: public int lastIndexOf(final int o) {
398: int rval = _limit - 1;
399:
400: for (; rval >= 0; rval--) {
401: if (o == _array[rval]) {
402: break;
403: }
404: }
405: return rval;
406: }
407:
408: /**
409: * Removes the element at the specified position in this list.
410: * Shifts any subsequent elements to the left (subtracts one from
411: * their indices). Returns the element that was removed from the
412: * list.
413: *
414: * @param index the index of the element to removed.
415: *
416: * @return the element previously at the specified position.
417: *
418: * @exception IndexOutOfBoundsException if the index is out of
419: * range (index < 0 || index >= size()).
420: */
421:
422: public int remove(final int index) {
423: if (index >= _limit) {
424: throw new IndexOutOfBoundsException();
425: }
426: int rval = _array[index];
427:
428: System.arraycopy(_array, index + 1, _array, index, _limit
429: - index);
430: _limit--;
431: return rval;
432: }
433:
434: /**
435: * Removes the first occurrence in this list of the specified
436: * element (optional operation). If this list does not contain
437: * the element, it is unchanged. More formally, removes the
438: * element with the lowest index i such that (o.equals(get(i)))
439: * (if such an element exists).
440: *
441: * @param o element to be removed from this list, if present.
442: *
443: * @return true if this list contained the specified element.
444: */
445:
446: public boolean removeValue(final int o) {
447: boolean rval = false;
448:
449: for (int j = 0; !rval && (j < _limit); j++) {
450: if (o == _array[j]) {
451: if (j + 1 < _limit) {
452: System.arraycopy(_array, j + 1, _array, j, _limit
453: - j);
454: }
455: _limit--;
456: rval = true;
457: }
458: }
459: return rval;
460: }
461:
462: /**
463: * Removes from this list all the elements that are contained in
464: * the specified collection
465: *
466: * @param c collection that defines which elements will be removed
467: * from this list.
468: *
469: * @return true if this list changed as a result of the call.
470: */
471:
472: public boolean removeAll(final IntList c) {
473: boolean rval = false;
474:
475: for (int j = 0; j < c._limit; j++) {
476: if (removeValue(c._array[j])) {
477: rval = true;
478: }
479: }
480: return rval;
481: }
482:
483: /**
484: * Retains only the elements in this list that are contained in
485: * the specified collection. In other words, removes from this
486: * list all the elements that are not contained in the specified
487: * collection.
488: *
489: * @param c collection that defines which elements this set will
490: * retain.
491: *
492: * @return true if this list changed as a result of the call.
493: */
494:
495: public boolean retainAll(final IntList c) {
496: boolean rval = false;
497:
498: for (int j = 0; j < _limit;) {
499: if (!c.contains(_array[j])) {
500: remove(j);
501: rval = true;
502: } else {
503: j++;
504: }
505: }
506: return rval;
507: }
508:
509: /**
510: * Replaces the element at the specified position in this list
511: * with the specified element
512: *
513: * @param index index of element to replace.
514: * @param element element to be stored at the specified position.
515: *
516: * @return the element previously at the specified position.
517: *
518: * @exception IndexOutOfBoundsException if the index is out of
519: * range (index < 0 || index >= size()).
520: */
521:
522: public int set(final int index, final int element) {
523: if (index >= _limit) {
524: throw new IndexOutOfBoundsException();
525: }
526: int rval = _array[index];
527:
528: _array[index] = element;
529: return rval;
530: }
531:
532: /**
533: * Returns the number of elements in this list. If this list
534: * contains more than Integer.MAX_VALUE elements, returns
535: * Integer.MAX_VALUE.
536: *
537: * @return the number of elements in this IntList
538: */
539:
540: public int size() {
541: return _limit;
542: }
543:
544: /**
545: * Returns an array containing all of the elements in this list in
546: * proper sequence. Obeys the general contract of the
547: * Collection.toArray method.
548: *
549: * @return an array containing all of the elements in this list in
550: * proper sequence.
551: */
552:
553: public int[] toArray() {
554: int[] rval = new int[_limit];
555:
556: System.arraycopy(_array, 0, rval, 0, _limit);
557: return rval;
558: }
559:
560: /**
561: * Returns an array containing all of the elements in this list in
562: * proper sequence. Obeys the general contract of the
563: * Collection.toArray(Object[]) method.
564: *
565: * @param a the array into which the elements of this list are to
566: * be stored, if it is big enough; otherwise, a new array
567: * is allocated for this purpose.
568: *
569: * @return an array containing the elements of this list.
570: */
571:
572: public int[] toArray(final int[] a) {
573: int[] rval;
574:
575: if (a.length == _limit) {
576: System.arraycopy(_array, 0, a, 0, _limit);
577: rval = a;
578: } else {
579: rval = toArray();
580: }
581: return rval;
582: }
583:
584: private void growArray(final int new_size) {
585: int size = (new_size == _array.length) ? new_size + 1
586: : new_size;
587: int[] new_array = new int[size];
588:
589: if (fillval != 0) {
590: fillArray(fillval, new_array, _array.length);
591: }
592:
593: System.arraycopy(_array, 0, new_array, 0, _limit);
594: _array = new_array;
595: }
596: } // end public class IntList
|