KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > poi > util > IntList


1
2 /* ====================================================================
3    Copyright 2002-2004 Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16 ==================================================================== */

17         
18
19 package org.apache.poi.util;
20
21 import java.util.*;
22
23 /**
24  * A List of int's; as full an implementation of the java.util.List
25  * interface as possible, with an eye toward minimal creation of
26  * objects
27  *
28  * the mimicry of List is as follows:
29  * <ul>
30  * <li> if possible, operations designated 'optional' in the List
31  * interface are attempted
32  * <li> wherever the List interface refers to an Object, substitute
33  * int
34  * <li> wherever the List interface refers to a Collection or List,
35  * substitute IntList
36  * </ul>
37  *
38  * the mimicry is not perfect, however:
39  * <ul>
40  * <li> operations involving Iterators or ListIterators are not
41  * supported
42  * <li> remove(Object) becomes removeValue to distinguish it from
43  * remove(int index)
44  * <li> subList is not supported
45  * </ul>
46  *
47  * @author Marc Johnson
48  */

49
50 public class IntList
51 {
52     private int[] _array;
53     private int _limit;
54     private int fillval = 0;
55     private static final int _default_size = 128;
56
57     /**
58      * create an IntList of default size
59      */

60
61     public IntList()
62     {
63         this(_default_size);
64     }
65
66     public IntList(final int initialCapacity)
67     {
68         this(initialCapacity,0);
69     }
70     
71     
72     /**
73      * create a copy of an existing IntList
74      *
75      * @param list the existing IntList
76      */

77
78     public IntList(final IntList list)
79     {
80         this(list._array.length);
81         System.arraycopy(list._array, 0, _array, 0, _array.length);
82         _limit = list._limit;
83     }
84
85     /**
86      * create an IntList with a predefined initial size
87      *
88      * @param initialCapacity the size for the internal array
89      */

90
91     public IntList(final int initialCapacity, int fillvalue)
92     {
93         _array = new int[ initialCapacity ];
94         if (fillval != 0) {
95             fillval = fillvalue;
96             fillArray(fillval, _array, 0);
97         }
98         _limit = 0;
99     }
100
101     private void fillArray(int val, int[] array, int index) {
102       for (int k = index; k < array.length; k++) {
103         array[k] = val;
104       }
105     }
106     
107     /**
108      * add the specfied value at the specified index
109      *
110      * @param index the index where the new value is to be added
111      * @param value the new value
112      *
113      * @exception IndexOutOfBoundsException if the index is out of
114      * range (index < 0 || index > size()).
115      */

116
117     public void add(final int index, final int value)
118     {
119         if (index > _limit)
120         {
121             throw new IndexOutOfBoundsException JavaDoc();
122         }
123         else if (index == _limit)
124         {
125             add(value);
126         }
127         else
128         {
129
130             // index < limit -- insert into the middle
131
if (_limit == _array.length)
132             {
133                 growArray(_limit * 2);
134             }
135             System.arraycopy(_array, index, _array, index + 1,
136                              _limit - index);
137             _array[ index ] = value;
138             _limit++;
139         }
140     }
141
142     /**
143      * Appends the specified element to the end of this list
144      *
145      * @param value element to be appended to this list.
146      *
147      * @return true (as per the general contract of the Collection.add
148      * method).
149      */

150
151     public boolean add(final int value)
152     {
153         if (_limit == _array.length)
154         {
155             growArray(_limit * 2);
156         }
157         _array[ _limit++ ] = value;
158         return true;
159     }
160
161     /**
162      * Appends all of the elements in the specified collection to the
163      * end of this list, in the order that they are returned by the
164      * specified collection's iterator. The behavior of this
165      * operation is unspecified if the specified collection is
166      * modified while the operation is in progress. (Note that this
167      * will occur if the specified collection is this list, and it's
168      * nonempty.)
169      *
170      * @param c collection whose elements are to be added to this
171      * list.
172      *
173      * @return true if this list changed as a result of the call.
174      */

175
176     public boolean addAll(final IntList c)
177     {
178         if (c._limit != 0)
179         {
180             if ((_limit + c._limit) > _array.length)
181             {
182                 growArray(_limit + c._limit);
183             }
184             System.arraycopy(c._array, 0, _array, _limit, c._limit);
185             _limit += c._limit;
186         }
187         return true;
188     }
189
190     /**
191      * Inserts all of the elements in the specified collection into
192      * this list at the specified position. Shifts the element
193      * currently at that position (if any) and any subsequent elements
194      * to the right (increases their indices). The new elements will
195      * appear in this list in the order that they are returned by the
196      * specified collection's iterator. The behavior of this
197      * operation is unspecified if the specified collection is
198      * modified while the operation is in progress. (Note that this
199      * will occur if the specified collection is this list, and it's
200      * nonempty.)
201      *
202      * @param index index at which to insert first element from the
203      * specified collection.
204      * @param c elements to be inserted into this list.
205      *
206      * @return true if this list changed as a result of the call.
207      *
208      * @exception IndexOutOfBoundsException if the index is out of
209      * range (index < 0 || index > size())
210      */

211
212     public boolean addAll(final int index, final IntList c)
213     {
214         if (index > _limit)
215         {
216             throw new IndexOutOfBoundsException JavaDoc();
217         }
218         if (c._limit != 0)
219         {
220             if ((_limit + c._limit) > _array.length)
221             {
222                 growArray(_limit + c._limit);
223             }
224
225             // make a hole
226
System.arraycopy(_array, index, _array, index + c._limit,
227                              _limit - index);
228
229             // fill it in
230
System.arraycopy(c._array, 0, _array, index, c._limit);
231             _limit += c._limit;
232         }
233         return true;
234     }
235
236     /**
237      * Removes all of the elements from this list. This list will be
238      * empty after this call returns (unless it throws an exception).
239      */

240
241     public void clear()
242     {
243         _limit = 0;
244     }
245
246     /**
247      * Returns true if this list contains the specified element. More
248      * formally, returns true if and only if this list contains at
249      * least one element e such that o == e
250      *
251      * @param o element whose presence in this list is to be tested.
252      *
253      * @return true if this list contains the specified element.
254      */

255
256     public boolean contains(final int o)
257     {
258         boolean rval = false;
259
260         for (int j = 0; !rval && (j < _limit); j++)
261         {
262             if (_array[ j ] == o)
263             {
264                 rval = true;
265             }
266         }
267         return rval;
268     }
269
270     /**
271      * Returns true if this list contains all of the elements of the
272      * specified collection.
273      *
274      * @param c collection to be checked for containment in this list.
275      *
276      * @return true if this list contains all of the elements of the
277      * specified collection.
278      */

279
280     public boolean containsAll(final IntList c)
281     {
282         boolean rval = true;
283
284         if (this != c)
285         {
286             for (int j = 0; rval && (j < c._limit); j++)
287             {
288                 if (!contains(c._array[ j ]))
289                 {
290                     rval = false;
291                 }
292             }
293         }
294         return rval;
295     }
296
297     /**
298      * Compares the specified object with this list for equality.
299      * Returns true if and only if the specified object is also a
300      * list, both lists have the same size, and all corresponding
301      * pairs of elements in the two lists are equal. (Two elements e1
302      * and e2 are equal if e1 == e2.) In other words, two lists are
303      * defined to be equal if they contain the same elements in the
304      * same order. This definition ensures that the equals method
305      * works properly across different implementations of the List
306      * interface.
307      *
308      * @param o the object to be compared for equality with this list.
309      *
310      * @return true if the specified object is equal to this list.
311      */

312
313     public boolean equals(final Object JavaDoc o)
314     {
315         boolean rval = this == o;
316
317         if (!rval && (o != null) && (o.getClass() == this.getClass()))
318         {
319             IntList other = ( IntList ) o;
320
321             if (other._limit == _limit)
322             {
323
324                 // assume match
325
rval = true;
326                 for (int j = 0; rval && (j < _limit); j++)
327                 {
328                     rval = _array[ j ] == other._array[ j ];
329                 }
330             }
331         }
332         return rval;
333     }
334
335     /**
336      * Returns the element at the specified position in this list.
337      *
338      * @param index index of element to return.
339      *
340      * @return the element at the specified position in this list.
341      *
342      * @exception IndexOutOfBoundsException if the index is out of
343      * range (index < 0 || index >= size()).
344      */

345
346     public int get(final int index)
347     {
348         if (index >= _limit)
349         {
350             throw new IndexOutOfBoundsException JavaDoc();
351         }
352         return _array[ index ];
353     }
354
355     /**
356      * Returns the hash code value for this list. The hash code of a
357      * list is defined to be the result of the following calculation:
358      *
359      * <code>
360      * hashCode = 1;
361      * Iterator i = list.iterator();
362      * while (i.hasNext()) {
363      * Object obj = i.next();
364      * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
365      * }
366      * </code>
367      *
368      * This ensures that list1.equals(list2) implies that
369      * list1.hashCode()==list2.hashCode() for any two lists, list1 and
370      * list2, as required by the general contract of Object.hashCode.
371      *
372      * @return the hash code value for this list.
373      */

374
375     public int hashCode()
376     {
377         int hash = 0;
378
379         for (int j = 0; j < _limit; j++)
380         {
381             hash = (31 * hash) + _array[ j ];
382         }
383         return hash;
384     }
385
386     /**
387      * Returns the index in this list of the first occurrence of the
388      * specified element, or -1 if this list does not contain this
389      * element. More formally, returns the lowest index i such that
390      * (o == get(i)), or -1 if there is no such index.
391      *
392      * @param o element to search for.
393      *
394      * @return the index in this list of the first occurrence of the
395      * specified element, or -1 if this list does not contain
396      * this element.
397      */

398
399     public int indexOf(final int o)
400     {
401         int rval = 0;
402
403         for (; rval < _limit; rval++)
404         {
405             if (o == _array[ rval ])
406             {
407                 break;
408             }
409         }
410         if (rval == _limit)
411         {
412             rval = -1; // didn't find it
413
}
414         return rval;
415     }
416
417     /**
418      * Returns true if this list contains no elements.
419      *
420      * @return true if this list contains no elements.
421      */

422
423     public boolean isEmpty()
424     {
425         return _limit == 0;
426     }
427
428     /**
429      * Returns the index in this list of the last occurrence of the
430      * specified element, or -1 if this list does not contain this
431      * element. More formally, returns the highest index i such that
432      * (o == get(i)), or -1 if there is no such index.
433      *
434      * @param o element to search for.
435      *
436      * @return the index in this list of the last occurrence of the
437      * specified element, or -1 if this list does not contain
438      * this element.
439      */

440
441     public int lastIndexOf(final int o)
442     {
443         int rval = _limit - 1;
444
445         for (; rval >= 0; rval--)
446         {
447             if (o == _array[ rval ])
448             {
449                 break;
450             }
451         }
452         return rval;
453     }
454
455     /**
456      * Removes the element at the specified position in this list.
457      * Shifts any subsequent elements to the left (subtracts one from
458      * their indices). Returns the element that was removed from the
459      * list.
460      *
461      * @param index the index of the element to removed.
462      *
463      * @return the element previously at the specified position.
464      *
465      * @exception IndexOutOfBoundsException if the index is out of
466      * range (index < 0 || index >= size()).
467      */

468
469     public int remove(final int index)
470     {
471         if (index >= _limit)
472         {
473             throw new IndexOutOfBoundsException JavaDoc();
474         }
475         int rval = _array[ index ];
476
477         System.arraycopy(_array, index + 1, _array, index, _limit - index);
478         _limit--;
479         return rval;
480     }
481
482     /**
483      * Removes the first occurrence in this list of the specified
484      * element (optional operation). If this list does not contain
485      * the element, it is unchanged. More formally, removes the
486      * element with the lowest index i such that (o.equals(get(i)))
487      * (if such an element exists).
488      *
489      * @param o element to be removed from this list, if present.
490      *
491      * @return true if this list contained the specified element.
492      */

493
494     public boolean removeValue(final int o)
495     {
496         boolean rval = false;
497
498         for (int j = 0; !rval && (j < _limit); j++)
499         {
500             if (o == _array[ j ])
501             {
502                 if (j+1 < _limit) {
503                     System.arraycopy(_array, j + 1, _array, j, _limit - j);
504                 }
505                 _limit--;
506                 rval = true;
507             }
508         }
509         return rval;
510     }
511
512     /**
513      * Removes from this list all the elements that are contained in
514      * the specified collection
515      *
516      * @param c collection that defines which elements will be removed
517      * from this list.
518      *
519      * @return true if this list changed as a result of the call.
520      */

521
522     public boolean removeAll(final IntList c)
523     {
524         boolean rval = false;
525
526         for (int j = 0; j < c._limit; j++)
527         {
528             if (removeValue(c._array[ j ]))
529             {
530                 rval = true;
531             }
532         }
533         return rval;
534     }
535
536     /**
537      * Retains only the elements in this list that are contained in
538      * the specified collection. In other words, removes from this
539      * list all the elements that are not contained in the specified
540      * collection.
541      *
542      * @param c collection that defines which elements this set will
543      * retain.
544      *
545      * @return true if this list changed as a result of the call.
546      */

547
548     public boolean retainAll(final IntList c)
549     {
550         boolean rval = false;
551
552         for (int j = 0; j < _limit; )
553         {
554             if (!c.contains(_array[ j ]))
555             {
556                 remove(j);
557                 rval = true;
558             }
559             else
560             {
561                 j++;
562             }
563         }
564         return rval;
565     }
566
567     /**
568      * Replaces the element at the specified position in this list
569      * with the specified element
570      *
571      * @param index index of element to replace.
572      * @param element element to be stored at the specified position.
573      *
574      * @return the element previously at the specified position.
575      *
576      * @exception IndexOutOfBoundsException if the index is out of
577      * range (index < 0 || index >= size()).
578      */

579
580     public int set(final int index, final int element)
581     {
582         if (index >= _limit)
583         {
584             throw new IndexOutOfBoundsException JavaDoc();
585         }
586         int rval = _array[ index ];
587
588         _array[ index ] = element;
589         return rval;
590     }
591
592     /**
593      * Returns the number of elements in this list. If this list
594      * contains more than Integer.MAX_VALUE elements, returns
595      * Integer.MAX_VALUE.
596      *
597      * @return the number of elements in this IntList
598      */

599
600     public int size()
601     {
602         return _limit;
603     }
604
605     /**
606      * Returns an array containing all of the elements in this list in
607      * proper sequence. Obeys the general contract of the
608      * Collection.toArray method.
609      *
610      * @return an array containing all of the elements in this list in
611      * proper sequence.
612      */

613
614     public int [] toArray()
615     {
616         int[] rval = new int[ _limit ];
617
618         System.arraycopy(_array, 0, rval, 0, _limit);
619         return rval;
620     }
621
622     /**
623      * Returns an array containing all of the elements in this list in
624      * proper sequence. Obeys the general contract of the
625      * Collection.toArray(Object[]) method.
626      *
627      * @param a the array into which the elements of this list are to
628      * be stored, if it is big enough; otherwise, a new array
629      * is allocated for this purpose.
630      *
631      * @return an array containing the elements of this list.
632      */

633
634     public int [] toArray(final int [] a)
635     {
636         int[] rval;
637
638         if (a.length == _limit)
639         {
640             System.arraycopy(_array, 0, a, 0, _limit);
641             rval = a;
642         }
643         else
644         {
645             rval = toArray();
646         }
647         return rval;
648     }
649
650     private void growArray(final int new_size)
651     {
652         int size = (new_size == _array.length) ? new_size + 1
653                                                       : new_size;
654         int[] new_array = new int[ size ];
655         
656         if (fillval != 0) {
657           fillArray(fillval, new_array, _array.length);
658         }
659         
660         System.arraycopy(_array, 0, new_array, 0, _limit);
661         _array = new_array;
662     }
663 } // end public class IntList
664

665
Popular Tags