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 buffer.append(items[0]); 390 for (int i = 1; i < size; i++) { 391 buffer.append(", "); 392 buffer.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 buffer.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}