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 squidpony.StringKit; 019import squidpony.annotation.GwtIncompatible; 020 021import java.io.Serializable; 022import java.util.Arrays; 023 024/** A resizable, ordered or unordered variable-length int array. Avoids boxing that occurs with ArrayList of Integer. 025 * If unordered, this class avoids a memory copy when removing elements (the last element is moved to the removed 026 * element's position). 027 * <br> 028 * Was called IntArray in libGDX; to avoid confusion with the fixed-length primitive array type, VLA (variable-length 029 * array) was chosen as a different name. 030 * Copied from LibGDX by Tommy Ettinger on 10/1/2015. 031 * @author Nathan Sweet */ 032public class IntVLA implements Serializable, Cloneable { 033 private static final long serialVersionUID = -2948161891082748626L; 034 035 public int[] items; 036 public int size; 037 038 /** Creates an ordered array with a capacity of 16. */ 039 public IntVLA() { 040 this(16); 041 } 042 043 /** Creates an ordered array with the specified capacity. */ 044 public IntVLA(int capacity) { 045 items = new int[capacity]; 046 } 047 048 /** Creates a new array containing the elements in the specific array. The new array will be ordered if the specific array is 049 * ordered. The capacity is set to the number of elements, so any subsequent elements added will cause the backing array to be 050 * grown. */ 051 public IntVLA(IntVLA array) { 052 size = array.size; 053 items = new int[size]; 054 System.arraycopy(array.items, 0, items, 0, size); 055 } 056 057 /** Creates a new ordered array containing the elements in the specified array. The capacity is set to the number of elements, 058 * so any subsequent elements added will cause the backing array to be grown. */ 059 public IntVLA(int[] array) { 060 this(array, 0, array.length); 061 } 062 063 /** Creates a new array containing the elements in the specified array. The capacity is set to the number of elements, so any 064 * subsequent elements added will cause the backing array to be grown. 065 * @param array the int array to copy from 066 * @param startIndex the first index in array to copy from 067 * @param count the number of ints to copy from array into this IntVLA 068 */ 069 public IntVLA(int[] array, int startIndex, int count) { 070 this(count); 071 size = count; 072 System.arraycopy(array, startIndex, items, 0, count); 073 } 074 075 public void add (int value) { 076 int[] items = this.items; 077 if (size == items.length) items = resize(size << 1 | 8); 078 items[size++] = value; 079 } 080 081 public void addAll (IntVLA array) { 082 addAll(array, 0, array.size); 083 } 084 085 public void addAll (IntVLA array, int offset, int length) { 086 if (offset + length > array.size) 087 throw new IllegalArgumentException("offset + length must be <= size: " + offset + " + " + length + " <= " + array.size); 088 addAll(array.items, offset, length); 089 } 090 091 public void addAll(IntSet set) { 092 set.appendInto(this); 093 } 094 095 public void addAll (int... array) { 096 addAll(array, 0, array.length); 097 } 098 099 public void addAll (int[] array, int offset, int length) { 100 int[] items = this.items; 101 int sizeNeeded = size + length; 102 if (sizeNeeded > items.length) items = resize(sizeNeeded << 1 | 8); 103 System.arraycopy(array, offset, items, size, length); 104 size += length; 105 } 106 107 public void addRange (int start, int end) { 108 int[] items = this.items; 109 int sizeNeeded = size + end - start; 110 if (sizeNeeded > items.length) items = resize(sizeNeeded << 1 | 8); 111 for(int r = start, i = size; r < end; r++, i++) 112 { 113 items[i] = r; 114 } 115 size += end - start; 116 } 117 118 public void addFractionRange (int start, int end, int fraction) { 119 int[] items = this.items; 120 int sizeNeeded = size + (end - start) / fraction + 2; 121 if (sizeNeeded > items.length) items = resize(sizeNeeded << 1 | 8); 122 for(int r = start, i = size; r < end; r = fraction * ((r / fraction) + 1), i++, size++) 123 { 124 items[i] = r; 125 } 126 } 127 128 public int get (int index) { 129 if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size); 130 return items[index]; 131 } 132 133 public void set (int index, int value) { 134 if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size); 135 items[index] = value; 136 } 137 138 /** 139 * Adds value to the item in the IntVLA at index. Calling it "add" would overlap with the collection method. 140 * @param index the index of the item to add to 141 * @param value how much to add to the item at index (this may be negative, positive, or 0) 142 */ 143 public void incr (int index, int value) { 144 if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size); 145 items[index] += value; 146 } 147 148 public void mul (int index, int value) { 149 if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size); 150 items[index] *= value; 151 } 152 153 public void insert (int index, int value) { 154 if (index > size) throw new IndexOutOfBoundsException("index can't be > size: " + index + " > " + size); 155 int[] items = this.items; 156 if (size == items.length) items = resize(size << 1 | 8); 157 System.arraycopy(items, index, items, index + 1, size - index); 158 size++; 159 items[index] = value; 160 } 161 162 public void swap (int first, int second) { 163 if (first >= size) throw new IndexOutOfBoundsException("first can't be >= size: " + first + " >= " + size); 164 if (second >= size) throw new IndexOutOfBoundsException("second can't be >= size: " + second + " >= " + size); 165 int[] items = this.items; 166 int firstValue = items[first]; 167 items[first] = items[second]; 168 items[second] = firstValue; 169 } 170 171 /** 172 * Given an array or varargs of replacement indices for the values of this IntVLA, reorders this so the first item 173 * in the returned version is the same as {@code get(ordering[0])} (with some care taken for negative or too-large 174 * indices), the second item in the returned version is the same as {@code get(ordering[1])}, etc. 175 * <br> 176 * Negative indices are considered reversed distances from the end of ordering, so -1 refers to the same index as 177 * {@code ordering[ordering.length - 1]}. If ordering is smaller than this IntVLA, only the indices up to the 178 * length of ordering will be modified. If ordering is larger than this IntVLA, only as many indices will be 179 * affected as this IntVLA's size, and reversed distances are measured from the end of this IntVLA instead of the 180 * end of ordering. Duplicate values in ordering will produce duplicate values in the returned IntVLA. 181 * <br> 182 * This method modifies this IntVLA in-place and also returns it for chaining. 183 * 184 * @param ordering an array or varargs of int indices, where the nth item in ordering changes the nth item in this 185 * IntVLA to have the value currently in this IntVLA at the index specified by the value in ordering 186 * @return this for chaining, after modifying it in-place 187 */ 188 public IntVLA reorder (int... ordering) { 189 int ol; 190 if (ordering == null || (ol = Math.min(size, ordering.length)) == 0) 191 return this; 192 int[] items = this.items, alt = new int[ol]; 193 for (int i = 0; i < ol; i++) { 194 alt[i] = items[(ordering[i] % ol + ol) % ol]; 195 } 196 System.arraycopy(alt, 0, items, 0, ol); 197 return this; 198 } 199 200 public boolean contains (int value) { 201 int i = size - 1; 202 int[] items = this.items; 203 while (i >= 0) 204 if (items[i--] == value) return true; 205 return false; 206 } 207 208 /** 209 * Tries to find the first occurrence of {@code value} in this IntVLA, and returns the index that value appears at 210 * if it is present, or -1 if it is not present. 211 * @param value a value to search for in this 212 * @return the first index of value, if found, or -1 otherwise 213 */ 214 public int indexOf (int value) { 215 int[] items = this.items; 216 for (int i = 0, n = size; i < n; i++) 217 if (items[i] == value) return i; 218 return -1; 219 } 220 221 public int lastIndexOf (int value) { 222 int[] items = this.items; 223 for (int i = size - 1; i >= 0; i--) 224 if (items[i] == value) return i; 225 return -1; 226 } 227 228 /** 229 * Removes the first occurrence of the requested value, and returns the index it was removed at (-1 if not found) 230 * @param value a value in this IntVLA to remove 231 * @return the index the value was found and removed at, or -1 if it was not present 232 */ 233 public int removeValue (int value) { 234 int[] items = this.items; 235 for (int i = 0, n = size; i < n; i++) { 236 if (items[i] == value) { 237 removeIndex(i); 238 return i; 239 } 240 } 241 return -1; 242 } 243 244 /** Removes and returns the item at the specified index. */ 245 public int removeIndex (int index) { 246 if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size); 247 int[] items = this.items; 248 int value = items[index]; 249 size--; 250 System.arraycopy(items, index + 1, items, index, size - index); 251 return value; 252 } 253 254 /** Removes the items between the specified indices, inclusive. */ 255 public void removeRange (int start, int end) { 256 if (end >= size) throw new IndexOutOfBoundsException("end can't be >= size: " + end + " >= " + size); 257 if (start > end) throw new IndexOutOfBoundsException("start can't be > end: " + start + " > " + end); 258 int[] items = this.items; 259 int count = end - start + 1; 260 System.arraycopy(items, start + count, items, start, size - (start + count)); 261 size -= count; 262 } 263 264 /** Removes from this array all of elements contained in the specified array. 265 * @return true if this array was modified. */ 266 public boolean removeAll (IntVLA array) { 267 int size = this.size; 268 int startSize = size; 269 int[] items = this.items; 270 for (int i = 0, n = array.size; i < n; i++) { 271 int item = array.get(i); 272 for (int ii = 0; ii < size; ii++) { 273 if (item == items[ii]) { 274 removeIndex(ii); 275 size--; 276 break; 277 } 278 } 279 } 280 return size != startSize; 281 } 282 283 284 /** Moves the specified value to the first index and returns its previous index. If value is not present, this 285 * returns -1. 286 * @param value an int value that should already be in this IntVLA 287 * @return the previous index of value, or -1 if it was not present 288 */ 289 public int moveToFirst (int value) { 290 int[] items = this.items; 291 int index = indexOf(value); 292 if(index <= 0) return index; 293 System.arraycopy(items, 0, items, 1, index); 294 items[0] = value; 295 return index; 296 } 297 298 /** Moves the specified value to the last index and returns its previous index. If value is not present, this 299 * returns -1. 300 * @param value an int value that should already be in this IntVLA 301 * @return the previous index of value, or -1 if it was not present 302 */ 303 public int moveToLast (int value) { 304 int[] items = this.items; 305 int index = indexOf(value); 306 if(index == size - 1 || index == -1) return index; 307 System.arraycopy(items, index + 1, items, index, size - index - 1); 308 items[size - 1] = value; 309 return index; 310 } 311 312 /** Removes and returns the last item. */ 313 public int pop () { 314 return items[--size]; 315 } 316 317 /** Returns the last item. */ 318 public int peek () { 319 return items[size - 1]; 320 } 321 322 /** Returns the first item. */ 323 public int first () { 324 if (size == 0) throw new IllegalStateException("IntVLA is empty."); 325 return items[0]; 326 } 327 328 public void clear () { 329 size = 0; 330 } 331 332 /** Reduces the size of the backing array to the size of the actual items. This is useful to release memory when many items have 333 * been removed, or if it is known that more items will not be added. 334 * @return {@link #items} */ 335 public int[] shrink () { 336 if (items.length != size) resize(size); 337 return items; 338 } 339 340 /** Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many 341 * items to avoid multiple backing array resizes. 342 * @return {@link #items} */ 343 public int[] ensureCapacity (int additionalCapacity) { 344 int sizeNeeded = size + additionalCapacity; 345 if (sizeNeeded > items.length) resize(Math.max(8, sizeNeeded)); 346 return items; 347 } 348 349 /** Sets the array size, leaving any values beyond the current size undefined. 350 * @return {@link #items} */ 351 public int[] setSize (int newSize) { 352 if (newSize > items.length) resize(Math.max(8, newSize)); 353 size = newSize; 354 return items; 355 } 356 357 protected int[] resize (int newSize) { 358 int[] newItems = new int[newSize]; 359 int[] items = this.items; 360 System.arraycopy(items, 0, newItems, 0, Math.min(size, newItems.length)); 361 this.items = newItems; 362 return newItems; 363 } 364 365 public void sort () { 366 Arrays.sort(items, 0, size); 367 } 368 369 public void reverse () { 370 int[] items = this.items; 371 for (int i = 0, lastIndex = size - 1, n = size / 2; i < n; i++) { 372 int ii = lastIndex - i; 373 int temp = items[i]; 374 items[i] = items[ii]; 375 items[ii] = temp; 376 } 377 } 378 379 /** Reduces the size of the array to the specified size. If the array is already smaller than the specified size, no action is 380 * taken. */ 381 public void truncate (int newSize) { 382 if (size > newSize) size = newSize; 383 } 384 385 public int getRandomElement(IRNG random) 386 { 387 return items[random.nextInt(size)]; 388 } 389 390 /** 391 * Shuffles this IntVLA in place using the given IRNG. 392 * @param random an IRNG, such as an RNG, used to generate the shuffled order 393 * @return this object, modified, after shuffling 394 */ 395 public IntVLA shuffle(IRNG random) 396 { 397 int n = size; 398 for (int i = 0; i < n; i++) 399 { 400 swap(i + random.nextInt(n - i), i); 401 } 402 return this; 403 } 404 405 public int[] toArray () { 406 int[] array = new int[size]; 407 System.arraycopy(items, 0, array, 0, size); 408 return array; 409 } 410 411 public IntVLA copy() 412 { 413 return new IntVLA(this); 414 } 415 416 @GwtIncompatible 417 @Override 418 public Object clone() { 419 try { 420 IntVLA nx = (IntVLA) super.clone(); 421 nx.items = new int[items.length]; 422 System.arraycopy(items, 0, nx.items, 0, size); 423 return nx; 424 } catch (CloneNotSupportedException e) { 425 throw new InternalError(e + (e.getMessage() != null ? "; " + e.getMessage() : "")); 426 } 427 } 428 429 /** 430 * Hashes this IntVLA using {@link CrossHash.Water}, getting a 32-bit result. The same algorithm is used by 431 * {@link #hash64()}, just with different constants and a different final step here. 432 * @return a 32-bit hash code 433 */ 434 @Override 435 public int hashCode () { 436 return CrossHash.Water.hash(items, size); 437 } 438 439 /** 440 * Gets a low-to-mid-quality hash code quickly using the Wisp algorithm; you should prefer {@link #hashHive()} in 441 * code that needs to run on GWT, since that method avoids the long math that is expensive on GWT. You are fine 442 * using {@link #hashCode()} when you need quality and low collison rates; Wisp tends to collide too often on some 443 * data sets. 444 * @return a 32-bit hash code that has OK quality, but worse than {@link #hashCode()} 445 */ 446 public int hashWisp () { 447 int[] data = this.items; 448 long result = 0x9E3779B97F4A7C94L, a = 0x632BE59BD9B4E019L; 449 final int len = size; 450 for (int i = 0; i < len; i++) { 451 result += (a ^= 0x8329C6EB9E6AD3E3L * data[i]); 452 } 453 return (int)(result * (a | 1L) ^ (result >>> 27 | result << 37)); 454 } 455 456 /** 457 * Gets a mid-quality hash code using the 32-bit part of the Hive algorithm; this uses only int math and so is an 458 * excellent option on GWT. It is relatively slow on desktop platforms compared to {@link #hashCode()}, which uses 459 * a higher-quality and sometimes faster algorithm, but only has that speed advantage on 64-bit JVMs. 460 * {@link #hash64()} uses almost exactly the same algorithm as hashCode(), both in {@link CrossHash.Water}. 461 * @return a 32-bit hash code that should show very little bias toward any bits 462 */ 463 public int hashHive () { 464 final int[] data = this.items; 465 int result = 0x1A976FDF, z = 0x60642E25; 466 final int len = size; 467 for (int i = 0; i < len; i++) { 468 result ^= (z += (data[i] ^ 0xC3564E95) * 0x9E375); 469 z ^= (result = (result << 20 | result >>> 12)); 470 } 471 result += (z ^ z >>> 15 ^ 0xAE932BD5) * 0x632B9; 472 result = (result ^ result >>> 15) * 0xFF51D; 473 result = (result ^ result >>> 15) * 0xC4CEB; 474 return result ^ result >>> 15; 475 } 476 477 /** 478 * Hashes this IntVLA using {@link CrossHash.Water}, getting a 64-bit result. The same algorithm is used by 479 * {@link #hashCode()}, just with different constants and a different final step here. 480 * @return a 64-bit hash code 481 */ 482 public long hash64 () { 483 return CrossHash.Water.hash64(items, size); 484 } 485 486 @Override 487 public boolean equals (Object object) { 488 if (object == this) return true; 489 if (!(object instanceof IntVLA)) return false; 490 IntVLA array = (IntVLA)object; 491 int n = size; 492 if (n != array.size) return false; 493 for (int i = 0; i < n; i++) 494 if (items[i] != array.items[i]) return false; 495 return true; 496 } 497 498 @Override 499 public String toString () { 500 if (size == 0) return "[]"; 501 int[] items = this.items; 502 StringBuilder buffer = new StringBuilder(32); 503 buffer.append('['); 504 buffer.append(items[0]); 505 for (int i = 1; i < size; i++) { 506 buffer.append(", "); 507 buffer.append(items[i]); 508 } 509 buffer.append(']'); 510 return buffer.toString(); 511 } 512 513 public String toString (String separator) { 514 if (size == 0) return ""; 515 int[] items = this.items; 516 StringBuilder buffer = new StringBuilder(32); 517 buffer.append(items[0]); 518 for (int i = 1; i < size; i++) { 519 buffer.append(separator); 520 buffer.append(items[i]); 521 } 522 return buffer.toString(); 523 } 524 525 public static IntVLA deserializeFromString(String data) 526 { 527 int amount = StringKit.count(data, ","); 528 if (amount <= 0) return new IntVLA(); 529 IntVLA iv = new IntVLA(amount+1); 530 int dl = 1, idx = -dl, idx2; 531 for (int i = 0; i < amount; i++) { 532 iv.add(StringKit.intFromDec(data, idx+dl, idx = data.indexOf(",", idx+dl))); 533 } 534 if((idx2 = data.indexOf(",", idx+dl)) < 0) 535 { 536 iv.add(StringKit.intFromDec(data, idx+dl, data.length())); 537 } 538 else 539 { 540 iv.add(StringKit.intFromDec(data, idx+dl, idx2)); 541 } 542 return iv; 543 } 544 545 /** @see #IntVLA(int[]) */ 546 public static IntVLA with (int... array) { 547 return new IntVLA(array); 548 } 549 550 public boolean isEmpty() { 551 return size == 0; 552 } 553 554}