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}