ShortList


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 short'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   *      short
34   * <li> wherever the List interface refers to a Collection or List,
35   *      substitute ShortList
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(short index)
44   * <li> subList is not supported
45   * </ul>
46   *
47   * @author Marc Johnson
48   */
49  
50  public class ShortList
51  {
52      private short[]          _array;
53      private int              _limit;
54      private static final int _default_size = 128;
55  
56      /**
57       * create an ShortList of default size
58       */
59  
60      public ShortList()
61      {
62          this(_default_size);
63      }
64  
65      /**
66       * create a copy of an existing ShortList
67       *
68       * @param list the existing ShortList
69       */
70  
71      public ShortList(final ShortList list)
72      {
73          this(list._array.length);
74          System.arraycopy(list._array, 0, _array, 0, _array.length);
75          _limit = list._limit;
76      }
77  
78      /**
79       * create an ShortList with a predefined initial size
80       *
81       * @param initialCapacity the size for the internal array
82       */
83  
84      public ShortList(final int initialCapacity)
85      {
86          _array = new short[ initialCapacity ];
87          _limit = 0;
88      }
89  
90      /**
91       * add the specfied value at the specified index
92       *
93       * @param index the index where the new value is to be added
94       * @param value the new value
95       *
96       * @exception IndexOutOfBoundsException if the index is out of
97       *            range (index < 0 || index > size()).
98       */
99  
100     public void add(final int index, final short value)
101     {
102         if (index > _limit)
103         {
104             throw new IndexOutOfBoundsException  ();
105         }
106         else if (index == _limit)
107         {
108             add(value);
109         }
110         else
111         {
112 
113             // index < limit -- insert into the middle
114             if (_limit == _array.length)
115             {
116                 growArray(_limit * 2);
117             }
118             System.arraycopy(_array, index, _array, index + 1,
119                              _limit - index);
120             _array[ index ] = value;
121             _limit++;
122         }
123     }
124 
125     /**
126      * Appends the specified element to the end of this list
127      *
128      * @param value element to be appended to this list.
129      *
130      * @return true (as per the general contract of the Collection.add
131      *         method).
132      */
133 
134     public boolean add(final short value)
135     {
136         if (_limit == _array.length)
137         {
138             growArray(_limit * 2);
139         }
140         _array[ _limit++ ] = value;
141         return true;
142     }
143 
144     /**
145      * Appends all of the elements in the specified collection to the
146      * end of this list, in the order that they are returned by the
147      * specified collection's iterator.  The behavior of this
148      * operation is unspecified if the specified collection is
149      * modified while the operation is in progress.  (Note that this
150      * will occur if the specified collection is this list, and it's
151      * nonempty.)
152      *
153      * @param c collection whose elements are to be added to this
154      *          list.
155      *
156      * @return true if this list changed as a result of the call.
157      */
158 
159     public boolean addAll(final ShortList c)
160     {
161         if (c._limit != 0)
162         {
163             if ((_limit + c._limit) > _array.length)
164             {
165                 growArray(_limit + c._limit);
166             }
167             System.arraycopy(c._array, 0, _array, _limit, c._limit);
168             _limit += c._limit;
169         }
170         return true;
171     }
172 
173     /**
174      * Inserts all of the elements in the specified collection into
175      * this list at the specified position.  Shifts the element
176      * currently at that position (if any) and any subsequent elements
177      * to the right (increases their indices).  The new elements will
178      * appear in this list in the order that they are returned by the
179      * specified collection's iterator.  The behavior of this
180      * operation is unspecified if the specified collection is
181      * modified while the operation is in progress.  (Note that this
182      * will occur if the specified collection is this list, and it's
183      * nonempty.)
184      *
185      * @param index index at which to insert first element from the
186      *              specified collection.
187      * @param c elements to be inserted into this list.
188      *
189      * @return true if this list changed as a result of the call.
190      *
191      * @exception IndexOutOfBoundsException if the index is out of
192      *            range (index < 0 || index > size())
193      */
194 
195     public boolean addAll(final int index, final ShortList c)
196     {
197         if (index > _limit)
198         {
199             throw new IndexOutOfBoundsException  ();
200         }
201         if (c._limit != 0)
202         {
203             if ((_limit + c._limit) > _array.length)
204             {
205                 growArray(_limit + c._limit);
206             }
207 
208             // make a hole
209             System.arraycopy(_array, index, _array, index + c._limit,
210                              _limit - index);
211 
212             // fill it in
213             System.arraycopy(c._array, 0, _array, index, c._limit);
214             _limit += c._limit;
215         }
216         return true;
217     }
218 
219     /**
220      * Removes all of the elements from this list.  This list will be
221      * empty after this call returns (unless it throws an exception).
222      */
223 
224     public void clear()
225     {
226         _limit = 0;
227     }
228 
229     /**
230      * Returns true if this list contains the specified element.  More
231      * formally, returns true if and only if this list contains at
232      * least one element e such that o == e
233      *
234      * @param o element whose presence in this list is to be tested.
235      *
236      * @return true if this list contains the specified element.
237      */
238 
239     public boolean contains(final short o)
240     {
241         boolean rval = false;
242 
243         for (int j = 0; !rval && (j < _limit); j++)
244         {
245             if (_array[ j ] == o)
246             {
247                 rval = true;
248             }
249         }
250         return rval;
251     }
252 
253     /**
254      * Returns true if this list contains all of the elements of the
255      * specified collection.
256      *
257      * @param c collection to be checked for containment in this list.
258      *
259      * @return true if this list contains all of the elements of the
260      *         specified collection.
261      */
262 
263     public boolean containsAll(final ShortList c)
264     {
265         boolean rval = true;
266 
267         if (this != c)
268         {
269             for (int j = 0; rval && (j < c._limit); j++)
270             {
271                 if (!contains(c._array[ j ]))
272                 {
273                     rval = false;
274                 }
275             }
276         }
277         return rval;
278     }
279 
280     /**
281      * Compares the specified object with this list for equality.
282      * Returns true if and only if the specified object is also a
283      * list, both lists have the same size, and all corresponding
284      * pairs of elements in the two lists are equal.  (Two elements e1
285      * and e2 are equal if e1 == e2.)  In other words, two lists are
286      * defined to be equal if they contain the same elements in the
287      * same order.  This definition ensures that the equals method
288      * works properly across different implementations of the List
289      * interface.
290      *
291      * @param o the object to be compared for equality with this list.
292      *
293      * @return true if the specified object is equal to this list.
294      */
295 
296     public boolean equals(final Object   o)
297     {
298         boolean rval = this == o;
299 
300         if (!rval && (o != null) && (o.getClass() == this.getClass()))
301         {
302             ShortList other = ( ShortList ) o;
303 
304             if (other._limit == _limit)
305             {
306 
307                 // assume match
308                 rval = true;
309                 for (int j = 0; rval && (j < _limit); j++)
310                 {
311                     rval = _array[ j ] == other._array[ j ];
312                 }
313             }
314         }
315         return rval;
316     }
317 
318     /**
319      * Returns the element at the specified position in this list.
320      *
321      * @param index index of element to return.
322      *
323      * @return the element at the specified position in this list.
324      *
325      * @exception IndexOutOfBoundsException if the index is out of
326      *            range (index < 0 || index >= size()).
327      */
328 
329     public short get(final int index)
330     {
331         if (index >= _limit)
332         {
333             throw new IndexOutOfBoundsException  ();
334         }
335         return _array[ index ];
336     }
337 
338     /**
339      * Returns the hash code value for this list.  The hash code of a
340      * list is defined to be the result of the following calculation:
341      *
342      * <code>
343      * hashCode = 1;
344      * Iterator i = list.iterator();
345      * while (i.hasNext()) {
346      *      Object obj = i.next();
347      *      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
348      * }
349      * </code>
350      *
351      * This ensures that list1.equals(list2) implies that
352      * list1.hashCode()==list2.hashCode() for any two lists, list1 and
353      * list2, as required by the general contract of Object.hashCode.
354      *
355      * @return the hash code value for this list.
356      */
357 
358     public int hashCode()
359     {
360         int hash = 0;
361 
362         for (int j = 0; j < _limit; j++)
363         {
364             hash = (31 * hash) + _array[ j ];
365         }
366         return hash;
367     }
368 
369     /**
370      * Returns the index in this list of the first occurrence of the
371      * specified element, or -1 if this list does not contain this
372      * element.  More formally, returns the lowest index i such that
373      * (o == get(i)), or -1 if there is no such index.
374      *
375      * @param o element to search for.
376      *
377      * @return the index in this list of the first occurrence of the
378      *         specified element, or -1 if this list does not contain
379      *         this element.
380      */
381 
382     public int indexOf(final short o)
383     {
384         int rval = 0;
385 
386         for (; rval < _limit; rval++)
387         {
388             if (o == _array[ rval ])
389             {
390                 break;
391             }
392         }
393         if (rval == _limit)
394         {
395             rval = -1;   // didn't find it
396         }
397         return rval;
398     }
399 
400     /**
401      * Returns true if this list contains no elements.
402      *
403      * @return true if this list contains no elements.
404      */
405 
406     public boolean isEmpty()
407     {
408         return _limit == 0;
409     }
410 
411     /**
412      * Returns the index in this list of the last occurrence of the
413      * specified element, or -1 if this list does not contain this
414      * element.  More formally, returns the highest index i such that
415      * (o == get(i)), or -1 if there is no such index.
416      *
417      * @param o element to search for.
418      *
419      * @return the index in this list of the last occurrence of the
420      *         specified element, or -1 if this list does not contain
421      *         this element.
422      */
423 
424     public int lastIndexOf(final short o)
425     {
426         int rval = _limit - 1;
427 
428         for (; rval >= 0; rval--)
429         {
430             if (o == _array[ rval ])
431             {
432                 break;
433             }
434         }
435         return rval;
436     }
437 
438     /**
439      * Removes the element at the specified position in this list.
440      * Shifts any subsequent elements to the left (subtracts one from
441      * their indices).  Returns the element that was removed from the
442      * list.
443      *
444      * @param index the index of the element to removed.
445      *
446      * @return the element previously at the specified position.
447      *
448      * @exception IndexOutOfBoundsException if the index is out of
449      *            range (index < 0 || index >= size()).
450      */
451 
452     public short remove(final int index)
453     {
454         if (index >= _limit)
455         {
456             throw new IndexOutOfBoundsException  ();
457         }
458         short rval = _array[ index ];
459 
460         System.arraycopy(_array, index + 1, _array, index, _limit - index);
461         _limit--;
462         return rval;
463     }
464 
465     /**
466      * Removes the first occurrence in this list of the specified
467      * element (optional operation).  If this list does not contain
468      * the element, it is unchanged.  More formally, removes the
469      * element with the lowest index i such that (o.equals(get(i)))
470      * (if such an element exists).
471      *
472      * @param o element to be removed from this list, if present.
473      *
474      * @return true if this list contained the specified element.
475      */
476 
477     public boolean removeValue(final short o)
478     {
479         boolean rval = false;
480 
481         for (int j = 0; !rval && (j < _limit); j++)
482         {
483             if (o == _array[ j ])
484             {
485                 System.arraycopy(_array, j + 1, _array, j, _limit - j);
486                 _limit--;
487                 rval = true;
488             }
489         }
490         return rval;
491     }
492 
493     /**
494      * Removes from this list all the elements that are contained in
495      * the specified collection
496      *
497      * @param c collection that defines which elements will be removed
498      *          from this list.
499      *
500      * @return true if this list changed as a result of the call.
501      */
502 
503     public boolean removeAll(final ShortList c)
504     {
505         boolean rval = false;
506 
507         for (int j = 0; j < c._limit; j++)
508         {
509             if (removeValue(c._array[ j ]))
510             {
511                 rval = true;
512             }
513         }
514         return rval;
515     }
516 
517     /**
518      * Retains only the elements in this list that are contained in
519      * the specified collection.  In other words, removes from this
520      * list all the elements that are not contained in the specified
521      * collection.
522      *
523      * @param c collection that defines which elements this set will
524      *          retain.
525      *
526      * @return true if this list changed as a result of the call.
527      */
528 
529     public boolean retainAll(final ShortList c)
530     {
531         boolean rval = false;
532 
533         for (int j = 0; j < _limit; )
534         {
535             if (!c.contains(_array[ j ]))
536             {
537                 remove(j);
538                 rval = true;
539             }
540             else
541             {
542                 j++;
543             }
544         }
545         return rval;
546     }
547 
548     /**
549      * Replaces the element at the specified position in this list
550      * with the specified element
551      *
552      * @param index index of element to replace.
553      * @param element element to be stored at the specified position.
554      *
555      * @return the element previously at the specified position.
556      *
557      * @exception IndexOutOfBoundsException if the index is out of
558      *            range (index < 0 || index >= size()).
559      */
560 
561     public short set(final int index, final short element)
562     {
563         if (index >= _limit)
564         {
565             throw new IndexOutOfBoundsException  ();
566         }
567         short rval = _array[ index ];
568 
569         _array[ index ] = element;
570         return rval;
571     }
572 
573     /**
574      * Returns the number of elements in this list. If this list
575      * contains more than Integer.MAX_VALUE elements, returns
576      * Integer.MAX_VALUE.
577      *
578      * @return the number of elements in this ShortList
579      */
580 
581     public int size()
582     {
583         return _limit;
584     }
585 
586     /**
587      * Returns an array containing all of the elements in this list in
588      * proper sequence.  Obeys the general contract of the
589      * Collection.toArray method.
590      *
591      * @return an array containing all of the elements in this list in
592      *         proper sequence.
593      */
594 
595     public short [] toArray()
596     {
597         short[] rval = new short[ _limit ];
598 
599         System.arraycopy(_array, 0, rval, 0, _limit);
600         return rval;
601     }
602 
603     /**
604      * Returns an array containing all of the elements in this list in
605      * proper sequence.  Obeys the general contract of the
606      * Collection.toArray(Object[]) method.
607      *
608      * @param a the array into which the elements of this list are to
609      *          be stored, if it is big enough; otherwise, a new array
610      *          is allocated for this purpose.
611      *
612      * @return an array containing the elements of this list.
613      */
614 
615     public short [] toArray(final short [] a)
616     {
617         short[] rval;
618 
619         if (a.length == _limit)
620         {
621             System.arraycopy(_array, 0, a, 0, _limit);
622             rval = a;
623         }
624         else
625         {
626             rval = toArray();
627         }
628         return rval;
629     }
630 
631     private void growArray(final int new_size)
632     {
633         int     size      = (new_size == _array.length) ? new_size + 1
634                                                         : new_size;
635         short[] new_array = new short[ size ];
636 
637         System.arraycopy(_array, 0, new_array, 0, _limit);
638         _array = new_array;
639     }
640 }   // end public class ShortList
641 
642
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags