dx/src/com/android/dx/util/IntList.java - platform/dalvik2 - Git at Google

 /*
  * 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.dx.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
      * @throws 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
      * @throws 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
      * @throws 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;
     }
 }
	/*
	* 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.dx.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
	* @throws 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
	* @throws 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
	* @throws 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;
	}
	}