1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.util;
18
19import java.util.Arrays;
20
21/**
22 * Simple list of {@code int}s.
23 */
24public final class IntList extends MutabilityControl {
25    /** {@code non-null;} immutable, no-element instance */
26    public static final IntList EMPTY = new IntList(0);
27
28    /** {@code non-null;} array of elements */
29    private int[] values;
30
31    /** {@code >= 0;} current size of the list */
32    private int size;
33
34    /** whether the values are currently sorted */
35    private boolean sorted;
36
37    static {
38        EMPTY.setImmutable();
39    }
40
41    /**
42     * Constructs a new immutable instance with the given element.
43     *
44     * @param value the sole value in the list
45     */
46    public static IntList makeImmutable(int value) {
47        IntList result = new IntList(1);
48
49        result.add(value);
50        result.setImmutable();
51
52        return result;
53    }
54
55    /**
56     * Constructs a new immutable instance with the given elements.
57     *
58     * @param value0 the first value in the list
59     * @param value1 the second value in the list
60     */
61    public static IntList makeImmutable(int value0, int value1) {
62        IntList result = new IntList(2);
63
64        result.add(value0);
65        result.add(value1);
66        result.setImmutable();
67
68        return result;
69    }
70
71    /**
72     * Constructs an empty instance with a default initial capacity.
73     */
74    public IntList() {
75        this(4);
76    }
77
78    /**
79     * Constructs an empty instance.
80     *
81     * @param initialCapacity {@code >= 0;} initial capacity of the list
82     */
83    public IntList(int initialCapacity) {
84        super(true);
85
86        try {
87            values = new int[initialCapacity];
88        } catch (NegativeArraySizeException ex) {
89            // Translate the exception.
90            throw new IllegalArgumentException("size < 0");
91        }
92
93        size = 0;
94        sorted = true;
95    }
96
97    /** {@inheritDoc} */
98    @Override
99    public int hashCode() {
100        int result = 0;
101
102        for (int i = 0; i < size; i++) {
103            result = (result * 31) + values[i];
104        }
105
106        return result;
107    }
108
109    /** {@inheritDoc} */
110    @Override
111    public boolean equals(Object other) {
112        if (other == this) {
113            return true;
114        }
115
116        if (! (other instanceof IntList)) {
117            return false;
118        }
119
120        IntList otherList = (IntList) other;
121
122        if (sorted != otherList.sorted) {
123            return false;
124        }
125
126        if (size != otherList.size) {
127            return false;
128        }
129
130        for (int i = 0; i < size; i++) {
131            if (values[i] != otherList.values[i]) {
132                return false;
133            }
134        }
135
136        return true;
137    }
138
139    /** {@inheritDoc} */
140    @Override
141    public String toString() {
142        StringBuffer sb = new StringBuffer(size * 5 + 10);
143
144        sb.append('{');
145
146        for (int i = 0; i < size; i++) {
147            if (i != 0) {
148                sb.append(", ");
149            }
150            sb.append(values[i]);
151        }
152
153        sb.append('}');
154
155        return sb.toString();
156    }
157
158    /**
159     * Gets the number of elements in this list.
160     */
161    public int size() {
162        return size;
163    }
164
165    /**
166     * Gets the indicated value.
167     *
168     * @param n {@code >= 0, < size();} which element
169     * @return the indicated element's value
170     */
171    public int get(int n) {
172        if (n >= size) {
173            throw new IndexOutOfBoundsException("n >= size()");
174        }
175
176        try {
177            return values[n];
178        } catch (ArrayIndexOutOfBoundsException ex) {
179            // Translate exception.
180            throw new IndexOutOfBoundsException("n < 0");
181        }
182    }
183
184    /**
185     * Sets the value at the given index.
186     *
187     * @param n {@code >= 0, < size();} which element
188     * @param value value to store
189     */
190    public void set(int n, int value) {
191        throwIfImmutable();
192
193        if (n >= size) {
194            throw new IndexOutOfBoundsException("n >= size()");
195        }
196
197        try {
198            values[n] = value;
199            sorted = false;
200        } catch (ArrayIndexOutOfBoundsException ex) {
201            // Translate the exception.
202            if (n < 0) {
203                throw new IllegalArgumentException("n < 0");
204            }
205        }
206    }
207
208    /**
209     * Adds an element to the end of the list. This will increase the
210     * list's capacity if necessary.
211     *
212     * @param value the value to add
213     */
214    public void add(int value) {
215        throwIfImmutable();
216
217        growIfNeeded();
218
219        values[size++] = value;
220
221        if (sorted && (size > 1)) {
222            sorted = (value >= values[size - 2]);
223        }
224    }
225
226    /**
227     * Inserts element into specified index, moving elements at and above
228     * that index up one. May not be used to insert at an index beyond the
229     * current size (that is, insertion as a last element is legal but
230     * no further).
231     *
232     * @param n {@code >= 0, <=size();} index of where to insert
233     * @param value value to insert
234     */
235    public void insert(int n, int value) {
236        if (n > size) {
237            throw new IndexOutOfBoundsException("n > size()");
238        }
239
240        growIfNeeded();
241
242        System.arraycopy (values, n, values, n+1, size - n);
243        values[n] = value;
244        size++;
245
246        sorted = sorted
247                && (n == 0 || value > values[n-1])
248                && (n == (size - 1) || value < values[n+1]);
249    }
250
251    /**
252     * Removes an element at a given index, shifting elements at greater
253     * indicies down one.
254     *
255     * @param n  {@code >=0, < size();} index of element to remove
256     */
257    public void removeIndex(int n) {
258        if (n >= size) {
259            throw new IndexOutOfBoundsException("n >= size()");
260        }
261
262        System.arraycopy (values, n + 1, values, n, size - n - 1);
263        size--;
264
265        // sort status is unchanged
266    }
267
268    /**
269     * Increases size of array if needed
270     */
271    private void growIfNeeded() {
272        if (size == values.length) {
273            // Resize.
274            int[] newv = new int[size * 3 / 2 + 10];
275            System.arraycopy(values, 0, newv, 0, size);
276            values = newv;
277        }
278    }
279
280    /**
281     * Returns the last element in the array without modifying the array
282     *
283     * @return last value in the array
284     * @throws IndexOutOfBoundsException if stack is empty
285     */
286    public int top() {
287        return get(size - 1);
288    }
289
290    /**
291     * Pops an element off the end of the list and decreasing the size by one.
292     *
293     * @return value from what was the last element
294     * @throws IndexOutOfBoundsException if stack is empty
295     */
296    public int pop() {
297        throwIfImmutable();
298
299        int result;
300
301        result = get(size-1);
302        size--;
303
304        return result;
305    }
306
307    /**
308     * Pops N elements off the end of the list and decreasing the size by N.
309     *
310     * @param n {@code >= 0;} number of elements to remove from end
311     * @throws IndexOutOfBoundsException if stack is smaller than N
312     */
313    public void pop(int n) {
314        throwIfImmutable();
315
316        size -= n;
317    }
318
319    /**
320     * Shrinks the size of the list.
321     *
322     * @param newSize {@code >= 0;} the new size
323     */
324    public void shrink(int newSize) {
325        if (newSize < 0) {
326            throw new IllegalArgumentException("newSize < 0");
327        }
328
329        if (newSize > size) {
330            throw new IllegalArgumentException("newSize > size");
331        }
332
333        throwIfImmutable();
334
335        size = newSize;
336    }
337
338    /**
339     * Makes and returns a mutable copy of the list.
340     *
341     * @return {@code non-null;} an appropriately-constructed instance
342     */
343    public IntList mutableCopy() {
344        int sz = size;
345        IntList result = new IntList(sz);
346
347        for (int i = 0; i < sz; i++) {
348            result.add(values[i]);
349        }
350
351        return result;
352    }
353
354    /**
355     * Sorts the elements in the list in-place.
356     */
357    public void sort() {
358        throwIfImmutable();
359
360        if (!sorted) {
361            Arrays.sort(values, 0, size);
362            sorted = true;
363        }
364    }
365
366    /**
367     * Returns the index of the given value, or -1 if the value does not
368     * appear in the list.  This will do a binary search if the list is
369     * sorted or a linear search if not.
370     *
371     * @param value value to find
372     * @return index of value or -1
373     */
374    public int indexOf(int value) {
375        int ret = binarysearch(value);
376
377        return ret >= 0 ? ret : -1;
378
379    }
380
381    /**
382     * Performs a binary search on a sorted list, returning the index of
383     * the given value if it is present or
384     * {@code (-(insertion point) - 1)} if the value is not present.
385     * If the list is not sorted, then reverts to linear search and returns
386     * {@code -size()} if the element is not found.
387     *
388     * @param value value to find
389     * @return index of value or {@code (-(insertion point) - 1)} if the
390     * value is not present
391     */
392    public int binarysearch(int value) {
393        int sz = size;
394
395        if (!sorted) {
396            // Linear search.
397            for (int i = 0; i < sz; i++) {
398                if (values[i] == value) {
399                    return i;
400                }
401            }
402
403            return -sz;
404        }
405
406        /*
407         * Binary search. This variant does only one value comparison
408         * per iteration but does one more iteration on average than
409         * the variant that includes a value equality check per
410         * iteration.
411         */
412
413        int min = -1;
414        int max = sz;
415
416        while (max > (min + 1)) {
417            /*
418             * The guessIdx calculation is equivalent to ((min + max)
419             * / 2) but won't go wonky when min and max are close to
420             * Integer.MAX_VALUE.
421             */
422            int guessIdx = min + ((max - min) >> 1);
423            int guess = values[guessIdx];
424
425            if (value <= guess) {
426                max = guessIdx;
427            } else {
428                min = guessIdx;
429            }
430        }
431
432        if ((max != sz)) {
433            return (value == values[max]) ? max : (-max - 1);
434        } else {
435            return -sz - 1;
436        }
437    }
438
439
440    /**
441     * Returns whether or not the given value appears in the list.
442     * This will do a binary search if the list is sorted or a linear
443     * search if not.
444     *
445     * @see #sort
446     *
447     * @param value value to look for
448     * @return whether the list contains the given value
449     */
450    public boolean contains(int value) {
451        return indexOf(value) >= 0;
452    }
453}
454