1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.compress.harmony.pack200;
18
19 import java.util.Arrays;
20
21
22
23
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
34
35 public IntList() {
36 this(10);
37 }
38
39
40
41
42
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
54
55
56
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
185
186 System.arraycopy(array, location + firstIndex, newArray, newFirst + location + required, size - location);
187
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 }