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     * @exception 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     * @exception 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     * @exception 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     * @param value value to find
371     * @return index of value or -1
372     */
373    public int indexOf(int value) {
374        int ret = binarysearch(value);
375
376        return ret >= 0 ? ret : -1;
377
378    }
379
380    /**
381     * Performs a binary search on a sorted list, returning the index of
382     * the given value if it is present or
383     * {@code (-(insertion point) - 1)} if the value is not present.
384     * If the list is not sorted, then reverts to linear search and returns
385     * {@code -size()} if the element is not found.
386     *
387     * @param value value to find
388     * @return index of value or {@code (-(insertion point) - 1)} if the
389     * value is not present
390     */
391    public int binarysearch(int value) {
392        int sz = size;
393
394        if (!sorted) {
395            // Linear search.
396            for (int i = 0; i < sz; i++) {
397                if (values[i] == value) {
398                    return i;
399                }
400            }
401
402            return -sz;
403        }
404
405        /*
406         * Binary search. This variant does only one value comparison
407         * per iteration but does one more iteration on average than
408         * the variant that includes a value equality check per
409         * iteration.
410         */
411
412        int min = -1;
413        int max = sz;
414
415        while (max > (min + 1)) {
416            /*
417             * The guessIdx calculation is equivalent to ((min + max)
418             * / 2) but won't go wonky when min and max are close to
419             * Integer.MAX_VALUE.
420             */
421            int guessIdx = min + ((max - min) >> 1);
422            int guess = values[guessIdx];
423
424            if (value <= guess) {
425                max = guessIdx;
426            } else {
427                min = guessIdx;
428            }
429        }
430
431        if ((max != sz)) {
432            return (value == values[max]) ? max : (-max - 1);
433        } else {
434            return -sz - 1;
435        }
436    }
437
438
439    /**
440     * Returns whether or not the given value appears in the list.
441     * This will do a binary search if the list is sorted or a linear
442     * search if not.
443     *
444     * @see #sort
445     *
446     * @param value value to look for
447     * @return whether the list contains the given value
448     */
449    public boolean contains(int value) {
450        return indexOf(value) >= 0;
451    }
452}
453