text: /*
   * 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;
      }
  }
  