dexgen/util/IntList.java

/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dexgen.util;

import java.util.Arrays;

/**
 * Simple list of {@code int}s.
 */
public final class IntList extends MutabilityControl {
    /** {@code non-null;} immutable, no-element instance */
    public static final IntList EMPTY = new IntList(0);

    /** {@code non-null;} array of elements */
    private int[] values;

    /** {@code >= 0;} current size of the list */
    private int size;

    /** whether the values are currently sorted */
    private boolean sorted;

    static {
        EMPTY.setImmutable();
    }

    /**
     * Constructs a new immutable instance with the given element.
     *
     * @param value the sole value in the list
     */
    public static IntList makeImmutable(int value) {
        IntList result = new IntList(1);

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

        return result;
    }

    /**
     * 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
     */
    public static IntList makeImmutable(int value0, int value1) {
        IntList result = new IntList(2);

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

        return result;
    }

    /**
     * Constructs an empty instance with a default initial capacity.
     */
    public IntList() {
        this(4);
    }

    /**
     * Constructs an empty instance.
     *
     * @param initialCapacity {@code >= 0;} initial capacity of the list
     */
    public IntList(int initialCapacity) {
        super(true);

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

        size = 0;
        sorted = true;
    }

    /** {@inheritDoc} */
    @Override
    public int hashCode() {
        int result = 0;

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

        return result;
    }

    /** {@inheritDoc} */
    @Override
    public boolean equals(Object other) {
        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;
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        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();
    }

    /**
     * Gets the number of elements in this list.
     */
    public int size() {
        return size;
    }

    /**
     * Gets the indicated value.
     *
     * @param n {@code >= 0, < size();} which element
     * @return the indicated element's value
     */
    public int get(int n) {
        if (n >= size) {
            throw new IndexOutOfBoundsException("n >= size()");
        }

        try {
            return values[n];
        } catch (ArrayIndexOutOfBoundsException ex) {
            // Translate exception.
            throw new IndexOutOfBoundsException("n < 0");
        }
    }

    /**
     * Sets the value at the given index.
     *
     * @param n {@code >= 0, < size();} which element
     * @param value value to store
     */
    public void set(int n, int value) {
        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");
            }
        }
    }

    /**
     * Adds an element to the end of the list. This will increase the
     * list's capacity if necessary.
     *
     * @param value the value to add
     */
    public void add(int value) {
        throwIfImmutable();

        growIfNeeded();

        values[size++] = value;

        if (sorted && (size > 1)) {
            sorted = (value >= values[size - 2]);
        }
    }

    /**
     * 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 {@code >= 0, <=size();} index of where to insert
     * @param value value to insert
     */
    public void insert(int n, int value) {
        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]);
    }

    /**
     * Removes an element at a given index, shifting elements at greater
     * indicies down one.
     *
     * @param n  {@code >=0, < size();} index of element to remove
     */
    public void removeIndex(int n) {
        if (n >= size) {
            throw new IndexOutOfBoundsException("n >= size()");
        }

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

        // sort status is unchanged
    }

    /**
     * Increases size of array if needed
     */
    private void growIfNeeded() {
        if (size == values.length) {
            // Resize.
            int[] newv = new int[size * 3 / 2 + 10];
            System.arraycopy(values, 0, newv, 0, size);
            values = newv;
        }
    }

    /**
     * Returns the last element in the array without modifying the array
     *
     * @return last value in the array.
     * @exception IndexOutOfBoundsException if stack is empty.
     */
    public int top() {
        return get(size - 1);
    }

    /**
     * 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.
     */
    public int pop() {
        throwIfImmutable();

        int result;

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

        return result;
    }

    /**
     * Pops N elements off the end of the list and decreasing the size by N.
     *
     * @param n {@code >= 0;} number of elements to remove from end.
     * @exception IndexOutOfBoundsException if stack is smaller than N
     */
    public void pop(int n) {
        throwIfImmutable();

        size -= n;
    }

    /**
     * Shrinks the size of the list.
     *
     * @param newSize {@code >= 0;} the new size
     */
    public void shrink(int newSize) {
        if (newSize < 0) {
            throw new IllegalArgumentException("newSize < 0");
        }

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

        throwIfImmutable();

        size = newSize;
    }

    /**
     * Makes and returns a mutable copy of the list.
     *
     * @return {@code non-null;} an appropriately-constructed instance
     */
    public IntList mutableCopy() {
        int sz = size;
        IntList result = new IntList(sz);

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

        return result;
    }

    /**
     * Sorts the elements in the list in-place.
     */
    public void sort() {
        throwIfImmutable();

        if (!sorted) {
            Arrays.sort(values, 0, size);
            sorted = true;
        }
    }

    /**
     * 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
     */
    public int indexOf(int value) {
        int ret = binarysearch(value);

        return ret >= 0 ? ret : -1;

    }

    /**
     * Performs a binary search on a sorted list, returning the index of
     * the given value if it is present or
     * {@code (-(insertion point) - 1)} if the value is not present.
     * If the list is not sorted, then reverts to linear search and returns
     * {@code -size()} if the element is not found.
     *
     * @param value value to find
     * @return index of value or {@code (-(insertion point) - 1)} if the
     * value is not present
     */
    public int binarysearch(int value) {
        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;
        }
    }


    /**
     * 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
     */
    public boolean contains(int value) {
        return indexOf(value) >= 0;
    }
}