    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}, 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 addAll(final IntList list) {
    098        growAtEnd(list.size());
    099        for (int i = 0; i < list.size(); i++) {
    100            add(list.get(i));
    101        }
    102    }
    103
    104    public void clear() {
    105        if (firstIndex != lastIndex) {
    106            Arrays.fill(array, firstIndex, lastIndex, -1);
    107            firstIndex = lastIndex = 0;
    108            modCount++;
    109        }
    110    }
    111
    112    public int get(final int location) {
    113        if (0 <= location && location < (lastIndex - firstIndex)) {
    114            return array[firstIndex + location];
    115        }
    116        throw new IndexOutOfBoundsException("" + location);
    117    }
    118
    119    private void growAtEnd(final int required) {
    120        final int size = lastIndex - firstIndex;
    121        if (firstIndex >= required - (array.length - lastIndex)) {
    122            final int newLast = lastIndex - firstIndex;
    123            if (size > 0) {
    124                System.arraycopy(array, firstIndex, array, 0, size);
    125            }
    126            firstIndex = 0;
    127            lastIndex = newLast;
    128        } else {
    129            int increment = size / 2;
    130            if (required > increment) {
    131                increment = required;
    132            }
    133            if (increment < 12) {
    134                increment = 12;
    135            }
    136            final int[] newArray = new int[size + increment];
    137            if (size > 0) {
    138                System.arraycopy(array, firstIndex, newArray, 0, size);
    139                firstIndex = 0;
    140                lastIndex = size;
    141            }
    142            array = newArray;
    143        }
    144    }
    145
    146    private void growAtFront(final int required) {
    147        final int size = lastIndex - firstIndex;
    148        if (array.length - lastIndex + firstIndex >= required) {
    149            final int newFirst = array.length - size;
    150            if (size > 0) {
    151                System.arraycopy(array, firstIndex, array, newFirst, size);
    152            }
    153            firstIndex = newFirst;
    154            lastIndex = array.length;
    155        } else {
    156            int increment = size / 2;
    157            if (required > increment) {
    158                increment = required;
    159            }
    160            if (increment < 12) {
    161                increment = 12;
    162            }
    163            final int[] newArray = new int[size + increment];
    164            if (size > 0) {
    165                System.arraycopy(array, firstIndex, newArray, newArray.length - size, size);
    166            }
    167            firstIndex = newArray.length - size;
    168            lastIndex = newArray.length;
    169            array = newArray;
    170        }
    171    }
    172
    173    private void growForInsert(final int location, final int required) {
    174        final int size = lastIndex - firstIndex;
    175        int increment = size / 2;
    176        if (required > increment) {
    177            increment = required;
    178        }
    179        if (increment < 12) {
    180            increment = 12;
    181        }
    182        final int[] newArray = new int[size + increment];
    183        final int newFirst = increment - required;
    184        // Copy elements after location to the new array skipping inserted
    185        // elements
    186        System.arraycopy(array, location + firstIndex, newArray, newFirst + location + required, size - location);
    187        // Copy elements before location to the new array from firstIndex
    188        System.arraycopy(array, firstIndex, newArray, newFirst, location);
    189        firstIndex = newFirst;
    190        lastIndex = size + increment;
    191
    192        array = newArray;
    193    }
    194
    195    public void increment(final int location) {
    196        if ((0 > location) || (location >= (lastIndex - firstIndex))) {
    197            throw new IndexOutOfBoundsException("" + location);
    198        }
    199        array[firstIndex + location]++;
    200    }
    201
    202    public boolean isEmpty() {
    203        return lastIndex == firstIndex;
    204    }
    205
    206    public int remove(final int location) {
    207        int result;
    208        final int size = lastIndex - firstIndex;
    209        if ((0 > location) || (location >= size)) {
    210            throw new IndexOutOfBoundsException();
    211        }
    212        if (location == size - 1) {
    213            result = array[--lastIndex];
    214            array[lastIndex] = 0;
    215        } else if (location == 0) {
    216            result = array[firstIndex];
    217            array[firstIndex++] = 0;
    218        } else {
    219            final int elementIndex = firstIndex + location;
    220            result = array[elementIndex];
    221            if (location < size / 2) {
    222                System.arraycopy(array, firstIndex, array, firstIndex + 1, location);
    223                array[firstIndex++] = 0;
    224            } else {
    225                System.arraycopy(array, elementIndex + 1, array, elementIndex, size - location - 1);
    226                array[--lastIndex] = 0;
    227            }
    228        }
    229        if (firstIndex == lastIndex) {
    230            firstIndex = lastIndex = 0;
    231        }
    232
    233        modCount++;
    234        return result;
    235    }
    236
    237    public int size() {
    238        return lastIndex - firstIndex;
    239    }
    240
    241    public int[] toArray() {
    242        final int size = lastIndex - firstIndex;
    243        final int[] result = new int[size];
    244        System.arraycopy(array, firstIndex, result, 0, size);
    245        return result;
    246    }
    247
    248}