FileDocCategorySizeDatePackage
IntList.javaAPI DocAndroid 1.5 API11250Wed May 06 22:41:02 BST 2009com.android.dx.util

IntList

public final class IntList extends MutabilityControl
Simple list of ints.

Fields Summary
public static final IntList
EMPTY
non-null; immutable, no-element instance
private int[]
values
non-null; array of elements
private int
size
>= 0; current size of the list
private boolean
sorted
whether the values are currently sorted
Constructors Summary
public IntList()
Constructs an empty instance with a default initial capacity.

        this(4);
    
public IntList(int initialCapacity)
Constructs an empty instance.

param
initialCapacity >= 0; initial capacity of the list

        super(true);

        try {
            values = new int[initialCapacity];
        } catch (NegativeArraySizeException ex) {
            // Translate the exception.
            throw new IllegalArgumentException("size < 0");
        }

        size = 0;
        sorted = true;
    
Methods Summary
public voidadd(int value)
Adds an element to the end of the list. This will increase the list's capacity if necessary.

param
value the value to add

        throwIfImmutable();

        growIfNeeded();

        values[size++] = value;

        if (sorted && (size > 1)) {
            sorted = (value >= values[size - 2]);
        }
    
public intbinarysearch(int value)
Performs a binary search on a sorted list, returning the index of the given value if it is present or (-(insertion point) - 1) if the value is not present. If the list is not sorted, then reverts to linear search and returns -size() if the element is not found.

param
value value to find
return
index of value or (-(insertion point) - 1) if the value is not present

        int sz = size;

        if (!sorted) {
            // Linear search.
            for (int i = 0; i < sz; i++) {
                if (values[i] == value) {
                    return i;
                }
            }

            return -sz;
        }

        /*
         * Binary search. This variant does only one value comparison
         * per iteration but does one more iteration on average than
         * the variant that includes a value equality check per
         * iteration.
         */

        int min = -1;
        int max = sz;

        while (max > (min + 1)) {
            /*
             * The guessIdx calculation is equivalent to ((min + max)
             * / 2) but won't go wonky when min and max are close to
             * Integer.MAX_VALUE.
             */
            int guessIdx = min + ((max - min) >> 1);
            int guess = values[guessIdx];

            if (value <= guess) {
                max = guessIdx;
            } else {
                min = guessIdx;
            }
        }

        if ((max != sz)) {
            return (value == values[max]) ? max : (-max - 1);
        } else {
            return -sz - 1;
        }
    
public booleancontains(int value)
Returns whether or not the given value appears in the list. This will do a binary search if the list is sorted or a linear search if not.

see
#sort
param
value value to look for
return
whether the list contains the given value

        return indexOf(value) >= 0;
    
public booleanequals(java.lang.Object other)
{@inheritDoc}

        if (other == this) {
            return true;
        }

        if (! (other instanceof IntList)) {
            return false;
        }

        IntList otherList = (IntList) other;

        if (sorted != otherList.sorted) {
            return false;
        }

        if (size != otherList.size) {
            return false;
        }

        for (int i = 0; i < size; i++) {
            if (values[i] != otherList.values[i]) {
                return false;
            }
        }

        return true;
    
public intget(int n)
Gets the indicated value.

param
n >= 0, < size(); which element
return
the indicated element's value

        if (n >= size) {
            throw new IndexOutOfBoundsException("n >= size()");
        }

        try {
            return values[n];
        } catch (ArrayIndexOutOfBoundsException ex) {
            // Translate exception.
            throw new IndexOutOfBoundsException("n < 0");
        }
    
private voidgrowIfNeeded()
Increases size of array if needed

        if (size == values.length) {
            // Resize.
            int[] newv = new int[size * 3 / 2 + 10];
            System.arraycopy(values, 0, newv, 0, size);
            values = newv;
        }
    
public inthashCode()
{@inheritDoc}

        int result = 0;

        for (int i = 0; i < size; i++) {
            result = (result * 31) + values[i];
        }

        return result;
    
public intindexOf(int value)
Returns the index of the given value, or -1 if the value does not appear in the list. This will do a binary search if the list is sorted or a linear search if not.

param
value value to find
return
index of value or -1

        int ret = binarysearch(value);

        return ret >= 0 ? ret : -1;

    
public voidinsert(int n, int value)
Inserts element into specified index, moving elements at and above that index up one. May not be used to insert at an index beyond the current size (that is, insertion as a last element is legal but no further).

param
n >=0 <=size(); index of where to insert
param
value value to insert

        if (n > size) {
            throw new IndexOutOfBoundsException("n > size()");
        }

        growIfNeeded();

        System.arraycopy (values, n, values, n+1, size - n);
        values[n] = value;
        size++;

        sorted = sorted
                && (n == 0 || value > values[n-1])
                && (n == (size - 1) || value < values[n+1]);
    
public static com.android.dx.util.IntListmakeImmutable(int value)
Constructs a new immutable instance with the given element.

param
value the sole value in the list


     
        EMPTY.setImmutable();
    
        IntList result = new IntList(1);

        result.add(value);
        result.setImmutable();

        return result;
    
public static com.android.dx.util.IntListmakeImmutable(int value0, int value1)
Constructs a new immutable instance with the given elements.

param
value0 the first value in the list
param
value1 the second value in the list

        IntList result = new IntList(2);

        result.add(value0);
        result.add(value1);
        result.setImmutable();

        return result;
    
public com.android.dx.util.IntListmutableCopy()
Makes and returns a mutable copy of the list.

return
non-null; an appropriately-constructed instance

        int sz = size;
        IntList result = new IntList(sz);

        for (int i = 0; i < sz; i++) {
            result.add(values[i]);
        }

        return result;
    
public intpop()
Pops an element off the end of the list and decreasing the size by one.

return
value from what was the last element.
exception
IndexOutOfBoundsException if stack is empty.

        throwIfImmutable();

        int result;

        result = get(size-1);
        size--;

        return result;    
    
public voidpop(int n)
Pops N elements off the end of the list and decreasing the size by N.

param
n >= 0; number of elements to remove from end.
exception
IndexOutOfBoundsException if stack is smaller than N

        throwIfImmutable();

        size -= n;
    
public voidremoveIndex(int n)
Removes an element at a given index, shifting elements at greater indicies down one.

param
n >=0 < size(); index of element to remove

        if (n >= size) {
            throw new IndexOutOfBoundsException("n >= size()");
        }

        System.arraycopy (values, n + 1, values, n, size - n - 1);
        size--;

        // sort status is unchanged
    
public voidset(int n, int value)
Sets the value at the given index.

param
n >= 0, < size(); which element
param
value value to store

        throwIfImmutable();

        if (n >= size) {
            throw new IndexOutOfBoundsException("n >= size()");
        }

        try {
            values[n] = value;
            sorted = false;
        } catch (ArrayIndexOutOfBoundsException ex) {
            // Translate the exception.
            if (n < 0) {
                throw new IllegalArgumentException("n < 0");
            }
        }
    
public voidshrink(int newSize)
Shrinks the size of the list.

param
newSize >= 0; the new size

        if (newSize < 0) {
            throw new IllegalArgumentException("newSize < 0");
        }

        if (newSize > size) {
            throw new IllegalArgumentException("newSize > size");
        }

        throwIfImmutable();

        size = newSize;
    
public intsize()
Gets the number of elements in this list.

        return size;
    
public voidsort()
Sorts the elements in the list in-place.

        throwIfImmutable();

        if (!sorted) {
            Arrays.sort(values, 0, size);
            sorted = true;
        }
    
public java.lang.StringtoString()
{@inheritDoc}

        StringBuffer sb = new StringBuffer(size * 5 + 10);

        sb.append('{");

        for (int i = 0; i < size; i++) {
            if (i != 0) {
                sb.append(", ");
            }
            sb.append(values[i]);
        }

        sb.append('}");

        return sb.toString();
    
public inttop()
Returns the last element in the array without modifying the array

return
last value in the array.
exception
IndexOutOfBoundsException if stack is empty.

        return get(size - 1);