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  ();
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  ();
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   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  ();
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  ();
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  ();
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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags