/*
    *  Licensed to the Apache Software Foundation (ASF) under one or more
    *  contributor license agreements.  See the NOTICE file distributed with
    *  this work for additional information regarding copyright ownership.
    *  The ASF licenses this file to You 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 org.apache.commons.compress.harmony.pack200;
  
  import java.util.Arrays;
  
  /**
   * IntList is based on {@link java.util.ArrayList}, but is written specifically for ints in order to reduce boxing and unboxing to Integers, reduce the memory
   * required and improve performance of pack200.
   */
  public class IntList {
  
      private int[] array;
      private int firstIndex;
      private int lastIndex;
      private int modCount;
  
      /**
       * Constructs a new instance of IntList with capacity for ten elements.
       */
      public IntList() {
          this(10);
      }
  
      /**
       * Constructs a new instance of IntList with the specified capacity.
       *
       * @param capacity the initial capacity of this IntList
       */
      public IntList(final int capacity) {
          if (capacity < 0) {
              throw new IllegalArgumentException();
          }
          firstIndex = lastIndex = 0;
          array = new int[capacity];
      }
  
      /**
       * Adds the specified object at the end of this IntList.
       *
       * @param object the object to add
       * @return true
       */
      public boolean add(final int object) {
          if (lastIndex == array.length) {
              growAtEnd(1);
          }
          array[lastIndex++] = object;
          modCount++;
          return true;
      }
  
      public void add(final int location, final int object) {
          final int size = lastIndex - firstIndex;
          if (0 < location && location < size) {
              if (firstIndex == 0 && lastIndex == array.length) {
                  growForInsert(location, 1);
              } else if (location < size / 2 && firstIndex > 0 || lastIndex == array.length) {
                  System.arraycopy(array, firstIndex, array, --firstIndex, location);
              } else {
                  final int index = location + firstIndex;
                  System.arraycopy(array, index, array, index + 1, size - location);
                  lastIndex++;
              }
              array[location + firstIndex] = object;
          } else if (location == 0) {
              if (firstIndex == 0) {
                  growAtFront(1);
              }
              array[--firstIndex] = object;
          } else if (location == size) {
              if (lastIndex == array.length) {
                  growAtEnd(1);
              }
              array[lastIndex++] = object;
          } else {
              throw new IndexOutOfBoundsException();
          }
  
          modCount++;
      }
  
      public void addAll(final IntList list) {
          growAtEnd(list.size());
          for (int i = 0; i < list.size(); i++) {
             add(list.get(i));
         }
     }
 
     public void clear() {
         if (firstIndex != lastIndex) {
             Arrays.fill(array, firstIndex, lastIndex, -1);
             firstIndex = lastIndex = 0;
             modCount++;
         }
     }
 
     public int get(final int location) {
         if (0 <= location && location < lastIndex - firstIndex) {
             return array[firstIndex + location];
         }
         throw new IndexOutOfBoundsException("" + location);
     }
 
     private void growAtEnd(final int required) {
         final int size = lastIndex - firstIndex;
         if (firstIndex >= required - (array.length - lastIndex)) {
             final int newLast = lastIndex - firstIndex;
             if (size > 0) {
                 System.arraycopy(array, firstIndex, array, 0, size);
             }
             firstIndex = 0;
             lastIndex = newLast;
         } else {
             int increment = size / 2;
             if (required > increment) {
                 increment = required;
             }
             if (increment < 12) {
                 increment = 12;
             }
             final int[] newArray = new int[size + increment];
             if (size > 0) {
                 System.arraycopy(array, firstIndex, newArray, 0, size);
                 firstIndex = 0;
                 lastIndex = size;
             }
             array = newArray;
         }
     }
 
     private void growAtFront(final int required) {
         final int size = lastIndex - firstIndex;
         if (array.length - lastIndex + firstIndex >= required) {
             final int newFirst = array.length - size;
             if (size > 0) {
                 System.arraycopy(array, firstIndex, array, newFirst, size);
             }
             firstIndex = newFirst;
             lastIndex = array.length;
         } else {
             int increment = size / 2;
             if (required > increment) {
                 increment = required;
             }
             if (increment < 12) {
                 increment = 12;
             }
             final int[] newArray = new int[size + increment];
             if (size > 0) {
                 System.arraycopy(array, firstIndex, newArray, newArray.length - size, size);
             }
             firstIndex = newArray.length - size;
             lastIndex = newArray.length;
             array = newArray;
         }
     }
 
     private void growForInsert(final int location, final int required) {
         final int size = lastIndex - firstIndex;
         int increment = size / 2;
         if (required > increment) {
             increment = required;
         }
         if (increment < 12) {
             increment = 12;
         }
         final int[] newArray = new int[size + increment];
         final int newFirst = increment - required;
         // Copy elements after location to the new array skipping inserted
         // elements
         System.arraycopy(array, location + firstIndex, newArray, newFirst + location + required, size - location);
         // Copy elements before location to the new array from firstIndex
         System.arraycopy(array, firstIndex, newArray, newFirst, location);
         firstIndex = newFirst;
         lastIndex = size + increment;
 
         array = newArray;
     }
 
     public void increment(final int location) {
         if (0 > location || location >= lastIndex - firstIndex) {
             throw new IndexOutOfBoundsException("" + location);
         }
         array[firstIndex + location]++;
     }
 
     public boolean isEmpty() {
         return lastIndex == firstIndex;
     }
 
     public int remove(final int location) {
         int result;
         final int size = lastIndex - firstIndex;
         if (0 > location || location >= size) {
             throw new IndexOutOfBoundsException();
         }
         if (location == size - 1) {
             result = array[--lastIndex];
             array[lastIndex] = 0;
         } else if (location == 0) {
             result = array[firstIndex];
             array[firstIndex++] = 0;
         } else {
             final int elementIndex = firstIndex + location;
             result = array[elementIndex];
             if (location < size / 2) {
                 System.arraycopy(array, firstIndex, array, firstIndex + 1, location);
                 array[firstIndex++] = 0;
             } else {
                 System.arraycopy(array, elementIndex + 1, array, elementIndex, size - location - 1);
                 array[--lastIndex] = 0;
             }
         }
         if (firstIndex == lastIndex) {
             firstIndex = lastIndex = 0;
         }
 
         modCount++;
         return result;
     }
 
     public int size() {
         return lastIndex - firstIndex;
     }
 
     public int[] toArray() {
         final int size = lastIndex - firstIndex;
         final int[] result = new int[size];
         System.arraycopy(array, firstIndex, result, 0, size);
         return result;
     }
 
 }