001/******************************************************************************
002 Copyright 2011 See AUTHORS file.
003
004 Licensed under the Apache License, Version 2.0 (the "License");
005 you may not use this file except in compliance with the License.
006 You may obtain a copy of the License at
007
008 http://www.apache.org/licenses/LICENSE-2.0
009
010 Unless required by applicable law or agreed to in writing, software
011 distributed under the License is distributed on an "AS IS" BASIS,
012 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 See the License for the specific language governing permissions and
014 limitations under the License.
015 */
016package squidpony.squidmath;
017
018import java.io.Serializable;
019import java.util.Arrays;
020
021/** A resizable, ordered or unordered short variable-length array. Avoids the boxing that occurs with {@code ArrayList<Short>}.
022 * If unordered, this class avoids a memory copy when removing elements (the last element is moved to the removed
023 * element's position). Used internally by CoordPacker, and unlikely to be used outside of it.
024 * <br>
025 * Was called IntArray in libGDX; to avoid confusion with the fixed-length primitive array type, VLA (variable-length
026 * array) was chosen as a different name. Also uses short instead of int, of course.
027 * Copied from LibGDX by Tommy Ettinger on 10/1/2015.
028 * @author Nathan Sweet */
029public class ShortVLA implements Serializable{
030    private static final long serialVersionUID = -2948161891082748626L;
031
032    public short[] items;
033    public int size;
034    public boolean ordered;
035
036    /** Creates an ordered array with a capacity of 16. */
037    public ShortVLA() {
038        this(true, 16);
039    }
040
041    /** Creates an ordered array with the specified capacity. */
042    public ShortVLA(int capacity) {
043        this(true, capacity);
044    }
045
046    /** @param ordered If false, methods that remove elements may change the order of other elements in the array, which avoids a
047     *           memory copy.
048     * @param capacity Any elements added beyond this will cause the backing array to be grown. */
049    public ShortVLA(boolean ordered, int capacity) {
050        this.ordered = ordered;
051        items = new short[capacity];
052    }
053
054    /** Creates a new array containing the elements in the specific array. The new array will be ordered if the specific array is
055     * ordered. The capacity is set to the number of elements, so any subsequent elements added will cause the backing array to be
056     * grown. */
057    public ShortVLA(ShortVLA array) {
058        ordered = array.ordered;
059        size = array.size;
060        items = new short[size];
061        System.arraycopy(array.items, 0, items, 0, size);
062    }
063
064    /** Creates a new ordered array containing the elements in the specified array. The capacity is set to the number of elements,
065     * so any subsequent elements added will cause the backing array to be grown. */
066    public ShortVLA(short[] array) {
067        this(true, array, 0, array.length);
068    }
069
070    /** Creates a new ordered array containing the elements in the specified array, converted to short. The capacity is set to
071     * the number of elements, so any subsequent elements added will cause the backing array to be grown. */
072    public ShortVLA(int[] array) {
073        this(true, array.length);
074        for (int i = 0; i < array.length; i++) {
075            items[size + i] = (short) array[i];
076        }
077        size += array.length;
078
079    }
080
081    /** Creates a new array containing the elements in the specified array. The capacity is set to the number of elements, so any
082     * subsequent elements added will cause the backing array to be grown.
083     * @param ordered If false, methods that remove elements may change the order of other elements in the array, which avoids a
084     *           memory copy.
085     */
086    public ShortVLA(boolean ordered, short[] array, int startIndex, int count) {
087        this(ordered, count);
088        size = count;
089        System.arraycopy(array, startIndex, items, 0, count);
090    }
091
092    public void add (short value) {
093        short[] items = this.items;
094        if (size == items.length) items = resize(Math.max(8, (int)(size * 1.75f)));
095        items[size++] = value;
096    }
097    
098    public void addAll (ShortVLA array) {
099        addAll(array, 0, array.size);
100    }
101
102    public void addAll (ShortVLA array, int offset, int length) {
103        if (offset + length > array.size)
104            throw new IllegalArgumentException("offset + length must be <= size: " + offset + " + " + length + " <= " + array.size);
105        addAll(array.items, offset, length);
106    }
107
108    public void addAll (short... array) {
109        addAll(array, 0, array.length);
110    }
111
112    public void addAll (short[] array, int offset, int length) {
113        short[] items = this.items;
114        int sizeNeeded = size + length;
115        if (sizeNeeded > items.length) items = resize(Math.max(8, (int)(sizeNeeded * 1.75f)));
116        System.arraycopy(array, offset, items, size, length);
117        size += length;
118    }
119
120    public void addAll (int[] array) {
121        short[] items = this.items;
122        int sizeNeeded = size + array.length;
123        if (sizeNeeded > items.length) items = resize(Math.max(8, (int)(sizeNeeded * 1.75f)));
124        for (int i = 0; i < array.length; i++) {
125            items[size + i] = (short) array[i];
126        }
127        size += array.length;
128    }
129
130    public void addRange (int start, int end) {
131        short[] items = this.items;
132        int sizeNeeded = size + end - start;
133        if (sizeNeeded > items.length) items = resize(Math.max(8, (int)(sizeNeeded * 1.75f)));
134        for(int r = start, i = size; r < end; r++, i++)
135        {
136            items[i] = (short)r;
137        }
138        size += end - start;
139    }
140
141    public void addFractionRange (int start, int end, int fraction) {
142        short[] items = this.items;
143        int sizeNeeded = size + (end - start) / fraction + 2;
144        if (sizeNeeded > items.length) items = resize(Math.max(8, (int)(sizeNeeded * 1.75f)));
145        for(int r = start, i = size; r < end; r = fraction * ((r / fraction) + 1), i++, size++)
146        {
147            items[i] = (short) r;
148        }
149    }
150
151    public short get (int index) {
152        if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size);
153        return items[index];
154    }
155
156    public void set (int index, short value) {
157        if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size);
158        items[index] = value;
159    }
160
161    /**
162     * Adds value to the item in the ShortVLA at index. Calling it "add" would overlap with the collection method.
163     * @param index
164     * @param value
165     */
166    public void incr (int index, short value) {
167        if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size);
168        items[index] += value;
169    }
170
171    public void mul (int index, short value) {
172        if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size);
173        items[index] *= value;
174    }
175
176    public void insert (int index, short value) {
177        if (index > size) throw new IndexOutOfBoundsException("index can't be > size: " + index + " > " + size);
178        short[] items = this.items;
179        if (size == items.length) items = resize(Math.max(8, (int)(size * 1.75f)));
180        if (ordered)
181            System.arraycopy(items, index, items, index + 1, size - index);
182        else
183            items[size] = items[index];
184        size++;
185        items[index] = value;
186    }
187
188    public void swap (int first, int second) {
189        if (first >= size) throw new IndexOutOfBoundsException("first can't be >= size: " + first + " >= " + size);
190        if (second >= size) throw new IndexOutOfBoundsException("second can't be >= size: " + second + " >= " + size);
191        short[] items = this.items;
192        short firstValue = items[first];
193        items[first] = items[second];
194        items[second] = firstValue;
195    }
196
197    public boolean contains (short value) {
198        int i = size - 1;
199        short[] items = this.items;
200        while (i >= 0)
201            if (items[i--] == value) return true;
202        return false;
203    }
204
205    public int indexOf (short value) {
206        short[] items = this.items;
207        for (int i = 0, n = size; i < n; i++)
208            if (items[i] == value) return i;
209        return -1;
210    }
211
212    public int lastIndexOf (short value) {
213        short[] items = this.items;
214        for (int i = size - 1; i >= 0; i--)
215            if (items[i] == value) return i;
216        return -1;
217    }
218
219    public boolean removeValue (short value) {
220        short[] items = this.items;
221        for (int i = 0, n = size; i < n; i++) {
222            if (items[i] == value) {
223                removeIndex(i);
224                return true;
225            }
226        }
227        return false;
228    }
229
230    /** Removes and returns the item at the specified index. */
231    public short removeIndex (int index) {
232        if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size);
233        short[] items = this.items;
234        short value = items[index];
235        size--;
236        if (ordered)
237            System.arraycopy(items, index + 1, items, index, size - index);
238        else
239            items[index] = items[size];
240        return value;
241    }
242
243    /** Removes the items between the specified indices, inclusive. */
244    public void removeRange (int start, int end) {
245        if (end >= size) throw new IndexOutOfBoundsException("end can't be >= size: " + end + " >= " + size);
246        if (start > end) throw new IndexOutOfBoundsException("start can't be > end: " + start + " > " + end);
247        short[] items = this.items;
248        int count = end - start + 1;
249        if (ordered)
250            System.arraycopy(items, start + count, items, start, size - (start + count));
251        else {
252            int lastIndex = size - 1;
253            for (int i = 0; i < count; i++)
254                items[start + i] = items[lastIndex - i];
255        }
256        size -= count;
257    }
258
259    /** Removes from this array all of elements contained in the specified array.
260     * @return true if this array was modified. */
261    public boolean removeAll (ShortVLA array) {
262        int size = this.size;
263        int startSize = size;
264        short[] items = this.items;
265        for (int i = 0, n = array.size; i < n; i++) {
266            short item = array.get(i);
267            for (int ii = 0; ii < size; ii++) {
268                if (item == items[ii]) {
269                    removeIndex(ii);
270                    size--;
271                    break;
272                }
273            }
274        }
275        return size != startSize;
276    }
277
278    /** Removes and returns the last item. */
279    public short pop () {
280        return items[--size];
281    }
282
283    /** Returns the last item. */
284    public short peek () {
285        return items[size - 1];
286    }
287
288    /** Returns the first item. */
289    public short first () {
290        if (size == 0) throw new IllegalStateException("IntVLA is empty.");
291        return items[0];
292    }
293
294    public void clear () {
295        size = 0;
296    }
297
298    /** Reduces the size of the backing array to the size of the actual items. This is useful to release memory when many items have
299     * been removed, or if it is known that more items will not be added.
300     * @return {@link #items} */
301    public short[] shrink () {
302        if (items.length != size) resize(size);
303        return items;
304    }
305
306    /** Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many
307     * items to avoid multiple backing array resizes.
308     * @return {@link #items} */
309    public short[] ensureCapacity (int additionalCapacity) {
310        int sizeNeeded = size + additionalCapacity;
311        if (sizeNeeded > items.length) resize(Math.max(8, sizeNeeded));
312        return items;
313    }
314
315    protected short[] resize (int newSize) {
316        short[] newItems = new short[newSize];
317        short[] items = this.items;
318        System.arraycopy(items, 0, newItems, 0, Math.min(size, newItems.length));
319        this.items = newItems;
320        return newItems;
321    }
322
323    public int[] asInts () {
324        int[] newItems = new int[size];
325        short[] items = this.items;
326        for (int i = 0; i < size; i++) {
327            newItems[i] = items[i] & 0xffff;
328        }
329        return newItems;
330    }
331
332    public void sort () {
333        Arrays.sort(items, 0, size);
334    }
335
336    public void reverse () {
337        short[] items = this.items;
338        for (int i = 0, lastIndex = size - 1, n = size / 2; i < n; i++) {
339            int ii = lastIndex - i;
340            short temp = items[i];
341            items[i] = items[ii];
342            items[ii] = temp;
343        }
344    }
345
346    /** Reduces the size of the array to the specified size. If the array is already smaller than the specified size, no action is
347     * taken. */
348    public void truncate (int newSize) {
349        if (size > newSize) size = newSize;
350    }
351
352
353    public short[] toArray () {
354        short[] array = new short[size];
355        System.arraycopy(items, 0, array, 0, size);
356        return array;
357    }
358
359    @Override
360        public int hashCode () {
361        if (!ordered) return super.hashCode();
362        short[] items = this.items;
363        int h = 1;
364        for (int i = 0, n = size; i < n; i++)
365            h = h * 31 + items[i];
366        return h;
367    }
368
369    @Override
370        public boolean equals (Object object) {
371        if (object == this) return true;
372        if (!ordered) return false;
373        if (!(object instanceof ShortVLA)) return false;
374        ShortVLA array = (ShortVLA)object;
375        if (!array.ordered) return false;
376        int n = size;
377        if (n != array.size) return false;
378        for (int i = 0; i < n; i++)
379            if (items[i] != array.items[i]) return false;
380        return true;
381    }
382
383    @Override
384        public String toString () {
385        if (size == 0) return "[]";
386        short[] items = this.items;
387        StringBuilder buffer = new StringBuilder(32);
388        buffer.append('[')
389                .append(items[0]);
390        for (int i = 1; i < size; i++) {
391            buffer.append(", ")
392                    .append(items[i]);
393        }
394        buffer.append(']');
395        return buffer.toString();
396    }
397
398    public String toString (String separator) {
399        if (size == 0) return "";
400        short[] items = this.items;
401        StringBuilder buffer = new StringBuilder(32);
402        buffer.append(items[0]);
403        for (int i = 1; i < size; i++) {
404            buffer.append(separator)
405                    .append(items[i]);
406        }
407        return buffer.toString();
408    }
409
410    /** @see #ShortVLA(short[]) */
411    public static ShortVLA with (short... array) {
412        return new ShortVLA(array);
413    }
414}