IntList.java

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

}