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