View Javadoc
1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one or more
3    *  contributor license agreements.  See the NOTICE file distributed with
4    *  this work for additional information regarding copyright ownership.
5    *  The ASF licenses this file to You under the Apache License, Version 2.0
6    *  (the "License"); you may not use this file except in compliance with
7    *  the License.  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  package org.apache.commons.compress.harmony.pack200;
18  
19  import java.util.Arrays;
20  
21  /**
22   * IntList is based on {@link java.util.ArrayList}, but is written specifically for ints in order to reduce boxing and unboxing to Integers, reduce the memory
23   * required and improve performance of pack200.
24   */
25  public class IntList {
26  
27      private int[] array;
28      private int firstIndex;
29      private int lastIndex;
30      private int modCount;
31  
32      /**
33       * Constructs a new instance of IntList with capacity for ten elements.
34       */
35      public IntList() {
36          this(10);
37      }
38  
39      /**
40       * Constructs a new instance of IntList with the specified capacity.
41       *
42       * @param capacity the initial capacity of this IntList
43       */
44      public IntList(final int capacity) {
45          if (capacity < 0) {
46              throw new IllegalArgumentException();
47          }
48          firstIndex = lastIndex = 0;
49          array = new int[capacity];
50      }
51  
52      /**
53       * Adds the specified object at the end of this IntList.
54       *
55       * @param object the object to add
56       * @return true
57       */
58      public boolean add(final int object) {
59          if (lastIndex == array.length) {
60              growAtEnd(1);
61          }
62          array[lastIndex++] = object;
63          modCount++;
64          return true;
65      }
66  
67      public void add(final int location, final int object) {
68          final int size = lastIndex - firstIndex;
69          if (0 < location && location < size) {
70              if (firstIndex == 0 && lastIndex == array.length) {
71                  growForInsert(location, 1);
72              } else if (location < size / 2 && firstIndex > 0 || lastIndex == array.length) {
73                  System.arraycopy(array, firstIndex, array, --firstIndex, location);
74              } else {
75                  final int index = location + firstIndex;
76                  System.arraycopy(array, index, array, index + 1, size - location);
77                  lastIndex++;
78              }
79              array[location + firstIndex] = object;
80          } else if (location == 0) {
81              if (firstIndex == 0) {
82                  growAtFront(1);
83              }
84              array[--firstIndex] = object;
85          } else if (location == size) {
86              if (lastIndex == array.length) {
87                  growAtEnd(1);
88              }
89              array[lastIndex++] = object;
90          } else {
91              throw new IndexOutOfBoundsException();
92          }
93  
94          modCount++;
95      }
96  
97      public void addAll(final IntList list) {
98          growAtEnd(list.size());
99          for (int i = 0; i < list.size(); i++) {
100             add(list.get(i));
101         }
102     }
103 
104     public void clear() {
105         if (firstIndex != lastIndex) {
106             Arrays.fill(array, firstIndex, lastIndex, -1);
107             firstIndex = lastIndex = 0;
108             modCount++;
109         }
110     }
111 
112     public int get(final int location) {
113         if (0 <= location && location < lastIndex - firstIndex) {
114             return array[firstIndex + location];
115         }
116         throw new IndexOutOfBoundsException("" + location);
117     }
118 
119     private void growAtEnd(final int required) {
120         final int size = lastIndex - firstIndex;
121         if (firstIndex >= required - (array.length - lastIndex)) {
122             final int newLast = lastIndex - firstIndex;
123             if (size > 0) {
124                 System.arraycopy(array, firstIndex, array, 0, size);
125             }
126             firstIndex = 0;
127             lastIndex = newLast;
128         } else {
129             int increment = size / 2;
130             if (required > increment) {
131                 increment = required;
132             }
133             if (increment < 12) {
134                 increment = 12;
135             }
136             final int[] newArray = new int[size + increment];
137             if (size > 0) {
138                 System.arraycopy(array, firstIndex, newArray, 0, size);
139                 firstIndex = 0;
140                 lastIndex = size;
141             }
142             array = newArray;
143         }
144     }
145 
146     private void growAtFront(final int required) {
147         final int size = lastIndex - firstIndex;
148         if (array.length - lastIndex + firstIndex >= required) {
149             final int newFirst = array.length - size;
150             if (size > 0) {
151                 System.arraycopy(array, firstIndex, array, newFirst, size);
152             }
153             firstIndex = newFirst;
154             lastIndex = array.length;
155         } else {
156             int increment = size / 2;
157             if (required > increment) {
158                 increment = required;
159             }
160             if (increment < 12) {
161                 increment = 12;
162             }
163             final int[] newArray = new int[size + increment];
164             if (size > 0) {
165                 System.arraycopy(array, firstIndex, newArray, newArray.length - size, size);
166             }
167             firstIndex = newArray.length - size;
168             lastIndex = newArray.length;
169             array = newArray;
170         }
171     }
172 
173     private void growForInsert(final int location, final int required) {
174         final int size = lastIndex - firstIndex;
175         int increment = size / 2;
176         if (required > increment) {
177             increment = required;
178         }
179         if (increment < 12) {
180             increment = 12;
181         }
182         final int[] newArray = new int[size + increment];
183         final int newFirst = increment - required;
184         // Copy elements after location to the new array skipping inserted
185         // elements
186         System.arraycopy(array, location + firstIndex, newArray, newFirst + location + required, size - location);
187         // Copy elements before location to the new array from firstIndex
188         System.arraycopy(array, firstIndex, newArray, newFirst, location);
189         firstIndex = newFirst;
190         lastIndex = size + increment;
191 
192         array = newArray;
193     }
194 
195     public void increment(final int location) {
196         if (0 > location || location >= lastIndex - firstIndex) {
197             throw new IndexOutOfBoundsException("" + location);
198         }
199         array[firstIndex + location]++;
200     }
201 
202     public boolean isEmpty() {
203         return lastIndex == firstIndex;
204     }
205 
206     public int remove(final int location) {
207         int result;
208         final int size = lastIndex - firstIndex;
209         if (0 > location || location >= size) {
210             throw new IndexOutOfBoundsException();
211         }
212         if (location == size - 1) {
213             result = array[--lastIndex];
214             array[lastIndex] = 0;
215         } else if (location == 0) {
216             result = array[firstIndex];
217             array[firstIndex++] = 0;
218         } else {
219             final int elementIndex = firstIndex + location;
220             result = array[elementIndex];
221             if (location < size / 2) {
222                 System.arraycopy(array, firstIndex, array, firstIndex + 1, location);
223                 array[firstIndex++] = 0;
224             } else {
225                 System.arraycopy(array, elementIndex + 1, array, elementIndex, size - location - 1);
226                 array[--lastIndex] = 0;
227             }
228         }
229         if (firstIndex == lastIndex) {
230             firstIndex = lastIndex = 0;
231         }
232 
233         modCount++;
234         return result;
235     }
236 
237     public int size() {
238         return lastIndex - firstIndex;
239     }
240 
241     public int[] toArray() {
242         final int size = lastIndex - firstIndex;
243         final int[] result = new int[size];
244         System.arraycopy(array, firstIndex, result, 0, size);
245         return result;
246     }
247 
248 }