    001/*
    002 *  Licensed to the Apache Software Foundation (ASF) under one or more
    003 *  contributor license agreements.  See the NOTICE file distributed with
    004 *  this work for additional information regarding copyright ownership.
    005 *  The ASF licenses this file to You under the Apache License, Version 2.0
    006 *  (the "License"); you may not use this file except in compliance with
    007 *  the License.  You may obtain a copy of the License at
    008 *
    009 *     http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 *  Unless required by applicable law or agreed to in writing, software
    012 *  distributed under the License is distributed on an "AS IS" BASIS,
    013 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 *  See the License for the specific language governing permissions and
    015 *  limitations under the License.
    016 */
    017package org.apache.commons.compress.harmony.pack200;
    018
    019import java.util.Arrays;
    020
    021/**
    022 * IntList is based on <code>java.util.ArrayList</code>, but is written specifically for ints in order to reduce boxing
    023 * and unboxing to Integers, reduce the memory required and improve performance of pack200.
    024 */
    025public class IntList {
    026
    027    private int[] array;
    028    private int firstIndex;
    029    private int lastIndex;
    030    private int modCount;
    031
    032    /**
    033     * Constructs a new instance of IntList with capacity for ten elements.
    034     */
    035    public IntList() {
    036        this(10);
    037    }
    038
    039    /**
    040     * Constructs a new instance of IntList with the specified capacity.
    041     *
    042     * @param capacity the initial capacity of this IntList
    043     */
    044    public IntList(final int capacity) {
    045        if (capacity < 0) {
    046            throw new IllegalArgumentException();
    047        }
    048        firstIndex = lastIndex = 0;
    049        array = new int[capacity];
    050    }
    051
    052    /**
    053     * Adds the specified object at the end of this IntList.
    054     *
    055     * @param object the object to add
    056     * @return true
    057     */
    058    public boolean add(final int object) {
    059        if (lastIndex == array.length) {
    060            growAtEnd(1);
    061        }
    062        array[lastIndex++] = object;
    063        modCount++;
    064        return true;
    065    }
    066
    067    public void add(final int location, final int object) {
    068        final int size = lastIndex - firstIndex;
    069        if (0 < location && location < size) {
    070            if (firstIndex == 0 && lastIndex == array.length) {
    071                growForInsert(location, 1);
    072            } else if ((location < size / 2 && firstIndex > 0) || lastIndex == array.length) {
    073                System.arraycopy(array, firstIndex, array, --firstIndex, location);
    074            } else {
    075                final int index = location + firstIndex;
    076                System.arraycopy(array, index, array, index + 1, size - location);
    077                lastIndex++;
    078            }
    079            array[location + firstIndex] = object;
    080        } else if (location == 0) {
    081            if (firstIndex == 0) {
    082                growAtFront(1);
    083            }
    084            array[--firstIndex] = object;
    085        } else if (location == size) {
    086            if (lastIndex == array.length) {
    087                growAtEnd(1);
    088            }
    089            array[lastIndex++] = object;
    090        } else {
    091            throw new IndexOutOfBoundsException();
    092        }
    093
    094        modCount++;
    095    }
    096
    097    public void clear() {
    098        if (firstIndex != lastIndex) {
    099            Arrays.fill(array, firstIndex, lastIndex, -1);
    100            firstIndex = lastIndex = 0;
    101            modCount++;
    102        }
    103    }
    104
    105    public int get(final int location) {
    106        if (0 <= location && location < (lastIndex - firstIndex)) {
    107            return array[firstIndex + location];
    108        }
    109        throw new IndexOutOfBoundsException("" + location);
    110    }
    111
    112    private void growAtEnd(final int required) {
    113        final int size = lastIndex - firstIndex;
    114        if (firstIndex >= required - (array.length - lastIndex)) {
    115            final int newLast = lastIndex - firstIndex;
    116            if (size > 0) {
    117                System.arraycopy(array, firstIndex, array, 0, size);
    118            }
    119            firstIndex = 0;
    120            lastIndex = newLast;
    121        } else {
    122            int increment = size / 2;
    123            if (required > increment) {
    124                increment = required;
    125            }
    126            if (increment < 12) {
    127                increment = 12;
    128            }
    129            final int[] newArray = new int[size + increment];
    130            if (size > 0) {
    131                System.arraycopy(array, firstIndex, newArray, 0, size);
    132                firstIndex = 0;
    133                lastIndex = size;
    134            }
    135            array = newArray;
    136        }
    137    }
    138
    139    private void growAtFront(final int required) {
    140        final int size = lastIndex - firstIndex;
    141        if (array.length - lastIndex + firstIndex >= required) {
    142            final int newFirst = array.length - size;
    143            if (size > 0) {
    144                System.arraycopy(array, firstIndex, array, newFirst, size);
    145            }
    146            firstIndex = newFirst;
    147            lastIndex = array.length;
    148        } else {
    149            int increment = size / 2;
    150            if (required > increment) {
    151                increment = required;
    152            }
    153            if (increment < 12) {
    154                increment = 12;
    155            }
    156            final int[] newArray = new int[size + increment];
    157            if (size > 0) {
    158                System.arraycopy(array, firstIndex, newArray, newArray.length - size, size);
    159            }
    160            firstIndex = newArray.length - size;
    161            lastIndex = newArray.length;
    162            array = newArray;
    163        }
    164    }
    165
    166    private void growForInsert(final int location, final int required) {
    167        final int size = lastIndex - firstIndex;
    168        int increment = size / 2;
    169        if (required > increment) {
    170            increment = required;
    171        }
    172        if (increment < 12) {
    173            increment = 12;
    174        }
    175        final int[] newArray = new int[size + increment];
    176        final int newFirst = increment - required;
    177        // Copy elements after location to the new array skipping inserted
    178        // elements
    179        System.arraycopy(array, location + firstIndex, newArray, newFirst + location + required, size - location);
    180        // Copy elements before location to the new array from firstIndex
    181        System.arraycopy(array, firstIndex, newArray, newFirst, location);
    182        firstIndex = newFirst;
    183        lastIndex = size + increment;
    184
    185        array = newArray;
    186    }
    187
    188    public void increment(final int location) {
    189        if ((0 > location) || (location >= (lastIndex - firstIndex))) {
    190            throw new IndexOutOfBoundsException("" + location);
    191        }
    192        array[firstIndex + location]++;
    193    }
    194
    195    public boolean isEmpty() {
    196        return lastIndex == firstIndex;
    197    }
    198
    199    public int remove(final int location) {
    200        int result;
    201        final int size = lastIndex - firstIndex;
    202        if ((0 > location) || (location >= size)) {
    203            throw new IndexOutOfBoundsException();
    204        }
    205        if (location == size - 1) {
    206            result = array[--lastIndex];
    207            array[lastIndex] = 0;
    208        } else if (location == 0) {
    209            result = array[firstIndex];
    210            array[firstIndex++] = 0;
    211        } else {
    212            final int elementIndex = firstIndex + location;
    213            result = array[elementIndex];
    214            if (location < size / 2) {
    215                System.arraycopy(array, firstIndex, array, firstIndex + 1, location);
    216                array[firstIndex++] = 0;
    217            } else {
    218                System.arraycopy(array, elementIndex + 1, array, elementIndex, size - location - 1);
    219                array[--lastIndex] = 0;
    220            }
    221        }
    222        if (firstIndex == lastIndex) {
    223            firstIndex = lastIndex = 0;
    224        }
    225
    226        modCount++;
    227        return result;
    228    }
    229
    230    public int size() {
    231        return lastIndex - firstIndex;
    232    }
    233
    234    public int[] toArray() {
    235        final int size = lastIndex - firstIndex;
    236        final int[] result = new int[size];
    237        System.arraycopy(array, firstIndex, result, 0, size);
    238        return result;
    239    }
    240
    241    public void addAll(final IntList list) {
    242        growAtEnd(list.size());
    243        for (int i = 0; i < list.size(); i++) {
    244            add(list.get(i));
    245        }
    246    }
    247
    248}