1    
2    /* ====================================================================
3     * The Apache Software License, Version 1.1
4     *
5     * Copyright (c) 2002 The Apache Software Foundation.  All rights
6     * reserved.
7     *
8     * Redistribution and use in source and binary forms, with or without
9     * modification, are permitted provided that the following conditions
10    * are met:
11    *
12    * 1. Redistributions of source code must retain the above copyright
13    *    notice, this list of conditions and the following disclaimer.
14    *
15    * 2. Redistributions in binary form must reproduce the above copyright
16    *    notice, this list of conditions and the following disclaimer in
17    *    the documentation and/or other materials provided with the
18    *    distribution.
19    *
20    * 3. The end-user documentation included with the redistribution,
21    *    if any, must include the following acknowledgment:
22    *       "This product includes software developed by the
23    *        Apache Software Foundation (http://www.apache.org/)."
24    *    Alternately, this acknowledgment may appear in the software itself,
25    *    if and wherever such third-party acknowledgments normally appear.
26    *
27    * 4. The names "Apache" and "Apache Software Foundation" and
28    *    "Apache POI" must not be used to endorse or promote products
29    *    derived from this software without prior written permission. For
30    *    written permission, please contact apache@apache.org.
31    *
32    * 5. Products derived from this software may not be called "Apache",
33    *    "Apache POI", nor may "Apache" appear in their name, without
34    *    prior written permission of the Apache Software Foundation.
35    *
36    * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37    * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38    * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39    * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40    * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41    * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42    * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43    * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44    * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45    * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46    * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47    * SUCH DAMAGE.
48    * ====================================================================
49    *
50    * This software consists of voluntary contributions made by many
51    * individuals on behalf of the Apache Software Foundation.  For more
52    * information on the Apache Software Foundation, please see
53    * <http://www.apache.org/>.
54    */
55   
56   package org.apache.poi.util;
57   
58   import java.util.*;
59   
60   /**
61    * A List of int's; as full an implementation of the java.util.List
62    * interface as possible, with an eye toward minimal creation of
63    * objects
64    *
65    * the mimicry of List is as follows:
66    * <ul>
67    * <li> if possible, operations designated 'optional' in the List
68    *      interface are attempted
69    * <li> wherever the List interface refers to an Object, substitute
70    *      int
71    * <li> wherever the List interface refers to a Collection or List,
72    *      substitute IntList
73    * </ul>
74    *
75    * the mimicry is not perfect, however:
76    * <ul>
77    * <li> operations involving Iterators or ListIterators are not
78    *      supported
79    * <li> remove(Object) becomes removeValue to distinguish it from
80    *      remove(int index)
81    * <li> subList is not supported
82    * </ul>
83    *
84    * @author Marc Johnson
85    */
86   
87   public class IntList
88   {
89       private int[]            _array;
90       private int              _limit;
91       private static final int _default_size = 128;
92   
93       /**
94        * create an IntList of default size
95        */
96   
97       public IntList()
98       {
99           this(_default_size);
100      }
101  
102      /**
103       * create a copy of an existing IntList
104       *
105       * @param list the existing IntList
106       */
107  
108      public IntList(final IntList list)
109      {
110          this(list._array.length);
111          System.arraycopy(list._array, 0, _array, 0, _array.length);
112          _limit = list._limit;
113      }
114  
115      /**
116       * create an IntList with a predefined initial size
117       *
118       * @param initialCapacity the size for the internal array
119       */
120  
121      public IntList(final int initialCapacity)
122      {
123          _array = new int[ initialCapacity ];
124          _limit = 0;
125      }
126  
127      /**
128       * add the specfied value at the specified index
129       *
130       * @param index the index where the new value is to be added
131       * @param value the new value
132       *
133       * @exception IndexOutOfBoundsException if the index is out of
134       *            range (index < 0 || index > size()).
135       */
136  
137      public void add(final int index, final int value)
138      {
139          if (index > _limit)
140          {
141              throw new IndexOutOfBoundsException();
142          }
143          else if (index == _limit)
144          {
145              add(value);
146          }
147          else
148          {
149  
150              // index < limit -- insert into the middle
151              if (_limit == _array.length)
152              {
153                  growArray(_limit * 2);
154              }
155              System.arraycopy(_array, index, _array, index + 1,
156                               _limit - index);
157              _array[ index ] = value;
158              _limit++;
159          }
160      }
161  
162      /**
163       * Appends the specified element to the end of this list
164       *
165       * @param value element to be appended to this list.
166       *
167       * @return true (as per the general contract of the Collection.add
168       *         method).
169       */
170  
171      public boolean add(final int value)
172      {
173          if (_limit == _array.length)
174          {
175              growArray(_limit * 2);
176          }
177          _array[ _limit++ ] = value;
178          return true;
179      }
180  
181      /**
182       * Appends all of the elements in the specified collection to the
183       * end of this list, in the order that they are returned by the
184       * specified collection's iterator.  The behavior of this
185       * operation is unspecified if the specified collection is
186       * modified while the operation is in progress.  (Note that this
187       * will occur if the specified collection is this list, and it's
188       * nonempty.)
189       *
190       * @param c collection whose elements are to be added to this
191       *          list.
192       *
193       * @return true if this list changed as a result of the call.
194       */
195  
196      public boolean addAll(final IntList c)
197      {
198          if (c._limit != 0)
199          {
200              if ((_limit + c._limit) > _array.length)
201              {
202                  growArray(_limit + c._limit);
203              }
204              System.arraycopy(c._array, 0, _array, _limit, c._limit);
205              _limit += c._limit;
206          }
207          return true;
208      }
209  
210      /**
211       * Inserts all of the elements in the specified collection into
212       * this list at the specified position.  Shifts the element
213       * currently at that position (if any) and any subsequent elements
214       * to the right (increases their indices).  The new elements will
215       * appear in this list in the order that they are returned by the
216       * specified collection's iterator.  The behavior of this
217       * operation is unspecified if the specified collection is
218       * modified while the operation is in progress.  (Note that this
219       * will occur if the specified collection is this list, and it's
220       * nonempty.)
221       *
222       * @param index index at which to insert first element from the
223       *              specified collection.
224       * @param c elements to be inserted into this list.
225       *
226       * @return true if this list changed as a result of the call.
227       *
228       * @exception IndexOutOfBoundsException if the index is out of
229       *            range (index < 0 || index > size())
230       */
231  
232      public boolean addAll(final int index, final IntList c)
233      {
234          if (index > _limit)
235          {
236              throw new IndexOutOfBoundsException();
237          }
238          if (c._limit != 0)
239          {
240              if ((_limit + c._limit) > _array.length)
241              {
242                  growArray(_limit + c._limit);
243              }
244  
245              // make a hole
246              System.arraycopy(_array, index, _array, index + c._limit,
247                               _limit - index);
248  
249              // fill it in
250              System.arraycopy(c._array, 0, _array, index, c._limit);
251              _limit += c._limit;
252          }
253          return true;
254      }
255  
256      /**
257       * Removes all of the elements from this list.  This list will be
258       * empty after this call returns (unless it throws an exception).
259       */
260  
261      public void clear()
262      {
263          _limit = 0;
264      }
265  
266      /**
267       * Returns true if this list contains the specified element.  More
268       * formally, returns true if and only if this list contains at
269       * least one element e such that o == e
270       *
271       * @param o element whose presence in this list is to be tested.
272       *
273       * @return true if this list contains the specified element.
274       */
275  
276      public boolean contains(final int o)
277      {
278          boolean rval = false;
279  
280          for (int j = 0; !rval && (j < _limit); j++)
281          {
282              if (_array[ j ] == o)
283              {
284                  rval = true;
285              }
286          }
287          return rval;
288      }
289  
290      /**
291       * Returns true if this list contains all of the elements of the
292       * specified collection.
293       *
294       * @param c collection to be checked for containment in this list.
295       *
296       * @return true if this list contains all of the elements of the
297       *         specified collection.
298       */
299  
300      public boolean containsAll(final IntList c)
301      {
302          boolean rval = true;
303  
304          if (this != c)
305          {
306              for (int j = 0; rval && (j < c._limit); j++)
307              {
308                  if (!contains(c._array[ j ]))
309                  {
310                      rval = false;
311                  }
312              }
313          }
314          return rval;
315      }
316  
317      /**
318       * Compares the specified object with this list for equality.
319       * Returns true if and only if the specified object is also a
320       * list, both lists have the same size, and all corresponding
321       * pairs of elements in the two lists are equal.  (Two elements e1
322       * and e2 are equal if e1 == e2.)  In other words, two lists are
323       * defined to be equal if they contain the same elements in the
324       * same order.  This definition ensures that the equals method
325       * works properly across different implementations of the List
326       * interface.
327       *
328       * @param o the object to be compared for equality with this list.
329       *
330       * @return true if the specified object is equal to this list.
331       */
332  
333      public boolean equals(final Object o)
334      {
335          boolean rval = this == o;
336  
337          if (!rval && (o != null) && (o.getClass() == this.getClass()))
338          {
339              IntList other = ( IntList ) o;
340  
341              if (other._limit == _limit)
342              {
343  
344                  // assume match
345                  rval = true;
346                  for (int j = 0; rval && (j < _limit); j++)
347                  {
348                      rval = _array[ j ] == other._array[ j ];
349                  }
350              }
351          }
352          return rval;
353      }
354  
355      /**
356       * Returns the element at the specified position in this list.
357       *
358       * @param index index of element to return.
359       *
360       * @return the element at the specified position in this list.
361       *
362       * @exception IndexOutOfBoundsException if the index is out of
363       *            range (index < 0 || index >= size()).
364       */
365  
366      public int get(final int index)
367      {
368          if (index >= _limit)
369          {
370              throw new IndexOutOfBoundsException();
371          }
372          return _array[ index ];
373      }
374  
375      /**
376       * Returns the hash code value for this list.  The hash code of a
377       * list is defined to be the result of the following calculation:
378       *
379       * <code>
380       * hashCode = 1;
381       * Iterator i = list.iterator();
382       * while (i.hasNext()) {
383       *      Object obj = i.next();
384       *      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
385       * }
386       * </code>
387       *
388       * This ensures that list1.equals(list2) implies that
389       * list1.hashCode()==list2.hashCode() for any two lists, list1 and
390       * list2, as required by the general contract of Object.hashCode.
391       *
392       * @return the hash code value for this list.
393       */
394  
395      public int hashCode()
396      {
397          int hash = 0;
398  
399          for (int j = 0; j < _limit; j++)
400          {
401              hash = (31 * hash) + _array[ j ];
402          }
403          return hash;
404      }
405  
406      /**
407       * Returns the index in this list of the first occurrence of the
408       * specified element, or -1 if this list does not contain this
409       * element.  More formally, returns the lowest index i such that
410       * (o == get(i)), or -1 if there is no such index.
411       *
412       * @param o element to search for.
413       *
414       * @return the index in this list of the first occurrence of the
415       *         specified element, or -1 if this list does not contain
416       *         this element.
417       */
418  
419      public int indexOf(final int o)
420      {
421          int rval = 0;
422  
423          for (; rval < _limit; rval++)
424          {
425              if (o == _array[ rval ])
426              {
427                  break;
428              }
429          }
430          if (rval == _limit)
431          {
432              rval = -1;   // didn't find it
433          }
434          return rval;
435      }
436  
437      /**
438       * Returns true if this list contains no elements.
439       *
440       * @return true if this list contains no elements.
441       */
442  
443      public boolean isEmpty()
444      {
445          return _limit == 0;
446      }
447  
448      /**
449       * Returns the index in this list of the last occurrence of the
450       * specified element, or -1 if this list does not contain this
451       * element.  More formally, returns the highest index i such that
452       * (o == get(i)), or -1 if there is no such index.
453       *
454       * @param o element to search for.
455       *
456       * @return the index in this list of the last occurrence of the
457       *         specified element, or -1 if this list does not contain
458       *         this element.
459       */
460  
461      public int lastIndexOf(final int o)
462      {
463          int rval = _limit - 1;
464  
465          for (; rval >= 0; rval--)
466          {
467              if (o == _array[ rval ])
468              {
469                  break;
470              }
471          }
472          return rval;
473      }
474  
475      /**
476       * Removes the element at the specified position in this list.
477       * Shifts any subsequent elements to the left (subtracts one from
478       * their indices).  Returns the element that was removed from the
479       * list.
480       *
481       * @param index the index of the element to removed.
482       *
483       * @return the element previously at the specified position.
484       *
485       * @exception IndexOutOfBoundsException if the index is out of
486       *            range (index < 0 || index >= size()).
487       */
488  
489      public int remove(final int index)
490      {
491          if (index >= _limit)
492          {
493              throw new IndexOutOfBoundsException();
494          }
495          int rval = _array[ index ];
496  
497          System.arraycopy(_array, index + 1, _array, index, _limit - index);
498          _limit--;
499          return rval;
500      }
501  
502      /**
503       * Removes the first occurrence in this list of the specified
504       * element (optional operation).  If this list does not contain
505       * the element, it is unchanged.  More formally, removes the
506       * element with the lowest index i such that (o.equals(get(i)))
507       * (if such an element exists).
508       *
509       * @param o element to be removed from this list, if present.
510       *
511       * @return true if this list contained the specified element.
512       */
513  
514      public boolean removeValue(final int o)
515      {
516          boolean rval = false;
517  
518          for (int j = 0; !rval && (j < _limit); j++)
519          {
520              if (o == _array[ j ])
521              {
522                  System.arraycopy(_array, j + 1, _array, j, _limit - j);
523                  _limit--;
524                  rval = true;
525              }
526          }
527          return rval;
528      }
529  
530      /**
531       * Removes from this list all the elements that are contained in
532       * the specified collection
533       *
534       * @param c collection that defines which elements will be removed
535       *          from this list.
536       *
537       * @return true if this list changed as a result of the call.
538       */
539  
540      public boolean removeAll(final IntList c)
541      {
542          boolean rval = false;
543  
544          for (int j = 0; j < c._limit; j++)
545          {
546              if (removeValue(c._array[ j ]))
547              {
548                  rval = true;
549              }
550          }
551          return rval;
552      }
553  
554      /**
555       * Retains only the elements in this list that are contained in
556       * the specified collection.  In other words, removes from this
557       * list all the elements that are not contained in the specified
558       * collection.
559       *
560       * @param c collection that defines which elements this set will
561       *          retain.
562       *
563       * @return true if this list changed as a result of the call.
564       */
565  
566      public boolean retainAll(final IntList c)
567      {
568          boolean rval = false;
569  
570          for (int j = 0; j < _limit; )
571          {
572              if (!c.contains(_array[ j ]))
573              {
574                  remove(j);
575                  rval = true;
576              }
577              else
578              {
579                  j++;
580              }
581          }
582          return rval;
583      }
584  
585      /**
586       * Replaces the element at the specified position in this list
587       * with the specified element
588       *
589       * @param index index of element to replace.
590       * @param element element to be stored at the specified position.
591       *
592       * @return the element previously at the specified position.
593       *
594       * @exception IndexOutOfBoundsException if the index is out of
595       *            range (index < 0 || index >= size()).
596       */
597  
598      public int set(final int index, final int element)
599      {
600          if (index >= _limit)
601          {
602              throw new IndexOutOfBoundsException();
603          }
604          int rval = _array[ index ];
605  
606          _array[ index ] = element;
607          return rval;
608      }
609  
610      /**
611       * Returns the number of elements in this list. If this list
612       * contains more than Integer.MAX_VALUE elements, returns
613       * Integer.MAX_VALUE.
614       *
615       * @return the number of elements in this IntList
616       */
617  
618      public int size()
619      {
620          return _limit;
621      }
622  
623      /**
624       * Returns an array containing all of the elements in this list in
625       * proper sequence.  Obeys the general contract of the
626       * Collection.toArray method.
627       *
628       * @return an array containing all of the elements in this list in
629       *         proper sequence.
630       */
631  
632      public int [] toArray()
633      {
634          int[] rval = new int[ _limit ];
635  
636          System.arraycopy(_array, 0, rval, 0, _limit);
637          return rval;
638      }
639  
640      /**
641       * Returns an array containing all of the elements in this list in
642       * proper sequence.  Obeys the general contract of the
643       * Collection.toArray(Object[]) method.
644       *
645       * @param a the array into which the elements of this list are to
646       *          be stored, if it is big enough; otherwise, a new array
647       *          is allocated for this purpose.
648       *
649       * @return an array containing the elements of this list.
650       */
651  
652      public int [] toArray(final int [] a)
653      {
654          int[] rval;
655  
656          if (a.length == _limit)
657          {
658              System.arraycopy(_array, 0, a, 0, _limit);
659              rval = a;
660          }
661          else
662          {
663              rval = toArray();
664          }
665          return rval;
666      }
667  
668      private void growArray(final int new_size)
669      {
670          int   size      = (new_size == _array.length) ? new_size + 1
671                                                        : new_size;
672          int[] new_array = new int[ size ];
673  
674          System.arraycopy(_array, 0, new_array, 0, _limit);
675          _array = new_array;
676      }
677  }   // end public class IntList
678  
679