001 /* 002 * Copyright (c) 2003, The Regents of the University of California, through 003 * Lawrence Berkeley National Laboratory (subject to receipt of any required 004 * approvals from the U.S. Dept. of Energy). All rights reserved. 005 */ 006 package gov.lbl.dsd.sea.nio.util; 007 008 import java.io.IOException; 009 import java.nio.IntBuffer; 010 011 /** 012 Efficient resizable auto-expanding list holding <code>int</code> elements; implemented with arrays. 013 The API is intended for easy non-trivial high-throughput processing, 014 and (in an elegant and compact yet different form) provides all list and set functionality 015 of the java.util collections package, as well as a little more. 016 This API fills the gap between raw arrays (non-resizable), nio IntBuffers (non-resizable) and 017 java.util.List and java.util.Set (resizable but not particularly useful for 018 <i>non-trivial high-throughput</i> processing on primitive types). 019 <p> 020 Indexed element access is zero based: valid indexes range from 021 index <code>0</code> (inclusive) to index <code>list.size()</code> (exclusive). 022 Attempts to access out-of-range indexes will throw an {@link IndexOutOfBoundsException}. 023 <p> 024 <strong>Note that this implementation is not synchronized, hence not inherently thread safe.</strong> 025 <p> 026 Example usage: 027 <pre> 028 System.out.println(new ArrayIntList(new int[] {0,1,2})); 029 </pre> 030 <p> 031 This class requires JDK 1.4 or higher; otherwise it has zero dependencies. 032 Hence you can simply copy the file into your own project if minimal dependencies are desired. 033 <p> 034 Also note that the compiler can (and will) easily inline all methods, then optimize away. 035 In fact with the Sun jdk-1.4.2 server VM it is hard to measure any difference 036 to raw array manipulations at abstraction level zero. 037 038 @author whoschek@lbl.gov 039 @author $Author: hoschek3 $ 040 @version $Revision: 1.36 $, $Date: 2004/08/07 19:13:47 $ 041 */ 042 public final class ArrayIntList implements java.io.Serializable { 043 044 /** 045 * The array into which the elements of the list are stored. The 046 * capacity of the list is the length of this array. 047 */ 048 private transient int[] elements; 049 050 /** 051 * The current number of elements contained in this list. 052 */ 053 private int size; 054 055 /** 056 * For compatibility across versions 057 */ 058 private static final long serialVersionUID = 2982195016849084649L; 059 060 /** 061 * Constructs an empty list. 062 */ 063 public ArrayIntList() { 064 this(10); 065 } 066 067 /** 068 * Constructs an empty list with the specified initial capacity. 069 * 070 * @param initialCapacity 071 * the number of elements the receiver can hold without 072 * auto-expanding itself by allocating new internal memory. 073 */ 074 public ArrayIntList(int initialCapacity) { 075 elements = new int[initialCapacity]; 076 size = 0; 077 } 078 079 /** 080 * Constructs a list SHARING the specified elements. The initial size and 081 * capacity of the list is the length of the backing array. 082 * <p> 083 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low, 084 * <b>the array is SHARED, not copied </b>. So if subsequently you modify the 085 * specified array directly via the [] operator, be sure you know what 086 * you're doing. 087 * <p> 088 * If you rather need copying behaviour, use 089 * <code>copy = new ArrayIntList(int[] elems).copy()</code> or similar. 090 * <p> 091 * If you need a list containing a copy of <code>elems[from..to)</code>, use 092 * <code>list = new ArrayIntList(to-from).add(elems, from, to-from)</code> 093 * or <code>list = new ArrayIntList(IntBuffer.wrap(elems, from, to-from))</code> 094 * or similar. 095 * 096 * @param elems 097 * the array backing the constructed list 098 */ 099 public ArrayIntList(int[] elems) { 100 elements = elems; 101 size = elems.length; 102 } 103 104 /** 105 * Constructs a list containing a copy of the remaining buffer elements. The 106 * initial size and capacity of the list is <code>elems.remaining()</code>. 107 * 108 * @param elems 109 * the elements initially to be added to the list 110 */ 111 public ArrayIntList(IntBuffer elems) { 112 this(elems.remaining()); 113 add(elems); 114 } 115 116 /** 117 * Appends the specified element to the end of this list. 118 * 119 * @param elem 120 * element to be appended to this list. 121 * @return <code>this</code> (for chaining convenience only) 122 */ 123 public ArrayIntList add(int elem) { 124 if (size == elements.length) ensureCapacity(size + 1); 125 elements[size++] = elem; 126 return this; 127 // equally correct alternative impl: insert(size, elem); 128 } 129 130 /** 131 * Appends the elements in the range <code>[offset..offset+length)</code> to the end of this list. 132 * 133 * @param elems the elements to be appended 134 * @param offset the offset of the first element to add (inclusive) 135 * @param length the number of elements to add 136 * @return <code>this</code> (for chaining convenience only) 137 * @throws IndexOutOfBoundsException if indexes are out of range. 138 */ 139 public ArrayIntList add(int[] elems, int offset, int length) { 140 if (offset < 0 || length < 0 || offset + length > elems.length) 141 throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", elems.length: " + elems.length); 142 ensureCapacity(size + length); 143 System.arraycopy(elems, offset, this.elements, size, length); 144 size += length; 145 return this; 146 // equally correct alternative impl: replace(size, size, elems, offset, length); 147 } 148 149 /** 150 * Appends the specified elements to the end of this list. 151 * 152 * @param elems 153 * elements to be appended. 154 * @return <code>this</code> (for chaining convenience only) 155 */ 156 public ArrayIntList add(ArrayIntList elems) { 157 replace(size, size, elems); 158 return this; 159 } 160 161 /** 162 * Appends the remaining buffer elements to the end of this list. 163 * 164 * @param elems 165 * elements to be appended. 166 * @return <code>this</code> (for chaining convenience only) 167 */ 168 public ArrayIntList add(IntBuffer elems) { 169 int length = elems.remaining(); 170 ensureCapacity(size + length); 171 elems.get(this.elements, size, length); 172 size += length; 173 return this; 174 // equally correct alternative impl: replace(size, size, elems, elems.remaining()); 175 } 176 177 /** 178 * Returns the elements currently stored, including invalid elements between 179 * size and capacity, if any. 180 * <p> 181 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low, 182 * <b>the array is SHARED, not copied </b>. So if subsequently you modify the 183 * returned array directly via the [] operator, be sure you know what you're 184 * doing. 185 * 186 * @return the elements currently stored. 187 */ 188 public int[] asArray() { 189 return elements; 190 } 191 192 /** 193 * Returns a buffer SHARING elements with the receiver. The buffer will 194 * have the default NIO byte order, which is ByteOrder.nativeOrder(). 195 * <p> 196 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low, 197 * <b>the array is SHARED, not copied </b>. So if subsequently you modify the 198 * returned buffer, be sure you know what you're doing. 199 */ 200 public IntBuffer asIntBuffer() { 201 return IntBuffer.wrap(elements, 0, size); 202 } 203 204 /** 205 * Searches the list for the specified value using the binary search 206 * algorithm. The list <strong>must </strong> be sorted (as by the 207 * <tt>sort</tt> method) prior to making this call. If it is not sorted, 208 * the results are undefined. If the list contains multiple elements with 209 * the specified value, there is no guarantee which one will be found. 210 * 211 * @param key 212 * the value to be searched for. 213 * @return index of the search key, if it is contained in the list; 214 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 215 * <i>insertion point </i> is defined as the point at which the key 216 * would be inserted into the list: the index of the first element 217 * greater than the key, or <tt>list.size()</tt>, if all elements 218 * in the list are less than the specified key. Note that this 219 * guarantees that the return value will be >= 0 if and only if 220 * the key is found. 221 * @see #sort(boolean) 222 */ 223 public int binarySearch(int key) { 224 int low = 0; 225 int high = size - 1; 226 227 while (low <= high) { 228 int mid = (low + high) >> 1; // >> 1 is equivalent to divide by 2 229 int midVal = elements[mid]; 230 231 if (midVal < key) 232 low = mid + 1; 233 else if (midVal > key) 234 high = mid - 1; 235 else 236 return mid; // key found 237 } 238 return -(low + 1); // key not found. 239 } 240 241 /** 242 * Removes all elements but keeps the current capacity; Afterwards 243 * <code>size()</code> will yield zero. 244 * 245 * @return <code>this</code> (for chaining convenience only) 246 */ 247 public ArrayIntList clear() { 248 size = 0; 249 return this; 250 // equally correct alternative impl: remove(0, size); 251 } 252 253 /** 254 * Constructs and returns a new list that is a deep copy of the receiver. 255 * 256 * @return a deep copy of the receiver. 257 */ 258 public ArrayIntList copy() { 259 return new ArrayIntList(toArray()); 260 } 261 262 /** 263 * Compares the specified Object with the receiver. Returns true if and only 264 * if the specified Object is also a list of the same type, both Lists 265 * have the same size, and all corresponding pairs of elements in the two 266 * Lists are identical. In other words, two Lists are defined to be equal if 267 * they contain the same elements in the same order. 268 * 269 * @param otherObj 270 * the Object to be compared for equality with the receiver. 271 * @return true if the specified Object is equal to the receiver. 272 */ 273 public boolean equals(Object otherObj) { //delta 274 if (this == otherObj) return true; 275 if (!(otherObj instanceof ArrayIntList)) return false; 276 ArrayIntList other = (ArrayIntList) otherObj; 277 if (size != other.size) return false; 278 return indexOf(0, size, other) >= 0; 279 } 280 281 /** 282 * Ensures that the receiver can hold at least the specified number of 283 * elements without needing to allocate new internal memory. If necessary, 284 * allocates new internal memory and increases the capacity of the receiver. 285 * 286 * @param minCapacity 287 * the desired minimum capacity. 288 */ 289 public void ensureCapacity(int minCapacity) { 290 if (minCapacity > elements.length) { 291 int newCapacity = Math.max(minCapacity, (elements.length * 3) / 2 + 1); 292 elements = subArray(0, size, newCapacity); 293 } 294 } 295 296 /** 297 * Finds all matching sublists in the range <code>[from..to)</code> and 298 * replaces them with the given replacement. A sublist matches if it is 299 * equal to the given pattern. The pattern must have a size greater than 300 * zero. The replacement can have any size. 301 * Examples: 302 * <pre> 303 * [a,b,c,d,b,c].findReplace(0,6, [b,c], [x,y,z]) --> [a,x,y,z,d,x,y,z] 304 * [a,b,c,d,b,c].findReplace(0,6, [b,c], []) --> [a,d] 305 * </pre> 306 * 307 * @param from the index of the first element to search (inclusive) 308 * @param to the index of the last element to search (exclusive). 309 * @param pattern the sublist to search for 310 * @param replacement the elements to replace the found sublists 311 * @return the number of sublists found matching the pattern 312 * @throws IndexOutOfBoundsException if indexes are out of range. 313 * @throws IllegalArgumentException if pattern.size() == 0. 314 */ 315 public int findReplace(int from, int to, ArrayIntList pattern, ArrayIntList replacement) { 316 checkRange(from, to); 317 if (pattern.size == 0) throw new IllegalArgumentException("pattern size must be > 0"); 318 int n = 0; 319 while ((from = indexOf(from, to, pattern)) >= 0) { 320 if (pattern != replacement) { // do more than just counting matches 321 replace(from, from + pattern.size, replacement); 322 to += replacement.size - pattern.size; 323 } 324 from += replacement.size; 325 n++; 326 } 327 return n; 328 } 329 330 /** 331 * Returns the element at the specified index. 332 * 333 * @param index 334 * index of element to return. 335 * @throws IndexOutOfBoundsException if index is out of range. 336 */ 337 public int get(int index) { 338 checkIndex(index); 339 return elements[index]; 340 } 341 342 /** 343 * Returns the hash code value for this list. The algorithm ensures that 344 * <tt>list1.equals(list2)</tt> implies that 345 * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists, 346 * <tt>list1</tt> and <tt>list2</tt>, as required by the general 347 * contract of <tt>Object.hashCode</tt>. 348 * <p> 349 * Warning: run time complexity is O(N) 350 * 351 * @return the hash code value for this list. 352 * @see Object#hashCode() 353 * @see Object#equals(Object) 354 * @see #equals(Object) 355 * @see java.util.List#hashCode() 356 */ 357 public int hashCode() { 358 int hashCode = 1; 359 int[] elems = elements; 360 for (int i = size; --i >= 0; ) 361 hashCode = 31*hashCode + elems[i]; 362 return hashCode; 363 } 364 365 /** 366 * Returns the index of the first occurrence of the given sublist within 367 * the range <code>this[from..to)</code>. 368 * Returns <code>-1</code> if the receiver does not contain such a sublist. 369 * Examples: 370 * <pre> 371 * [a,b,c,d,e,b,c,d].indexOf(0,8, [b,c,d]) --> 1 372 * [a,b,c,d,e].indexOf(0,5, [b,c,d]) --> 1 373 * [a,b,c,d,e].indexOf(1,4, [b,c,d]) --> 1 374 * [a,b,c,d,e].indexOf(0,5, [x,y]) --> -1 375 * [a,b,c,d,e].indexOf(0,3, [b,c,d]) --> -1 376 * [a].indexOf(0,1, [a,b,c]) --> -1 377 * [a,b,c,d,e].indexOf(2,3, []) --> 2 // empty sublist is always found 378 * [].indexOf(0,0, []) --> 0 379 * </pre> 380 * 381 * @param from 382 * the leftmost search index within the receiver, inclusive. 383 * @param to 384 * the rightmost search index within the receiver, exclusive. 385 * @param subList 386 * the sublist to search for. 387 * @return the index of the first occurrence of the sublist in the receiver; 388 * returns <code>-1</code> if the sublist is not found. 389 * @throws IndexOutOfBoundsException 390 * if indexes are out of range 391 */ 392 public int indexOf(int from, int to, ArrayIntList subList) { 393 // brute-force algorithm, but very efficiently implemented 394 checkRange(from, to); 395 int[] elems = elements; 396 int[] subElems = subList.elements; 397 int subsize = subList.size; 398 to -= subsize; 399 while (from <= to) { 400 int i = subsize; 401 int j = from + subsize; 402 while (--i >= 0 && elems[--j] == subElems[i]) { // compare from right to left 403 ; 404 } 405 if (i < 0) return from; // found 406 from++; 407 } 408 return -1; // not found 409 } 410 411 /** 412 * Returns the index of the first occurrence of the specified element within 413 * the range <code>[from..to)</code>. Returns <code>-1</code> if the 414 * receiver does not contain such an element. 415 * 416 * @param from 417 * the leftmost search index, inclusive. 418 * @param to 419 * the rightmost search index, exclusive. 420 * @param elem 421 * element to search for. 422 * @return the index of the first occurrence of the element in the receiver; 423 * returns <code>-1</code> if the element is not found. 424 * @throws IndexOutOfBoundsException 425 * if indexes are out of range 426 */ 427 public int indexOf(int from, int to, int elem) { 428 checkRange(from, to); 429 int[] elems = elements; 430 for (int i = from; i < to; i++) { 431 if (elem == elems[i]) return i; //found 432 } 433 return -1; //not found 434 } 435 436 /** 437 * Returns the index of the last occurrence of the given sublist within 438 * the range <code>this[from..to)</code>. 439 * Returns <code>-1</code> if the receiver does not contain such a sublist. 440 * Examples: 441 * <pre> 442 * [a,b,c,d,e,b,c,d].lastIndexOf(0,8, [b,c,d]) --> 5 443 * [a,b,c,d,e].lastIndexOf(0,5, [b,c,d]) --> 1 444 * [a,b,c,d,e].lastIndexOf(1,4, [b,c,d]) --> 1 445 * [a,b,c,d,e].lastIndexOf(0,5, [x,y]) --> -1 446 * [a,b,c,d,e].lastIndexOf(0,3, [b,c,d]) --> -1 447 * [a].lastIndexOf(0,1, [a,b,c]) --> -1 448 * [a,b,c,d,e].lastIndexOf(2,3, []) --> 3 // empty sublist is always found 449 * [].lastIndexOf(0,0, []) --> 0 450 * </pre> 451 * 452 * @param from 453 * the leftmost search index within the receiver, inclusive. 454 * @param to 455 * the rightmost search index within the receiver, exclusive. 456 * @param subList 457 * the sublist to search for. 458 * @return the index of the last occurrence of the sublist in the receiver; 459 * returns <code>-1</code> if the sublist is not found. 460 * @throws IndexOutOfBoundsException 461 * if indexes are out of range 462 */ 463 public int lastIndexOf(int from, int to, ArrayIntList subList) { 464 // brute-force algorithm, but very efficiently implemented 465 checkRange(from, to); 466 int[] elems = elements; 467 int[] subElems = subList.elements; 468 469 int subsize = subList.size; 470 from += subsize; 471 while (from <= to) { 472 int i = subsize; 473 int j = to; 474 while (--i >= 0 && elems[--j] == subElems[i]) { // compare from right to left 475 ; 476 } 477 if (i < 0) return to - subsize; // found 478 to--; 479 } 480 return -1; // not found 481 } 482 483 /** 484 * Removes the elements in the range <code>[from..to)</code>. Shifts any 485 * subsequent elements to the left. Keeps the current capacity. 486 * Note: To remove a single element use <code>remove(index, index+1)</code>. 487 * To remove all elements use <code>remove(0, list.size())</code>. 488 * 489 * @param from 490 * the index of the first element to removed (inclusive). 491 * @param to 492 * the index of the last element to removed (exclusive). 493 * @throws IndexOutOfBoundsException 494 * if indexes are out of range 495 */ 496 public void remove(int from, int to) { 497 shrinkOrExpand(from, to, 0); 498 // equally correct alternative impl: replace(from, to, 0, 0); 499 } 500 501 /** 502 * Removes from the receiver all elements that are contained in the 503 * specified other list. 504 * <p> 505 * Example: <code>[0,1,2,2,3,3,0].removeAll([2,1]) --> [0,3,3,0]</code> 506 * <p> 507 * An efficient <i>asymmetric set difference</i> can be computed along the following lines: 508 * <pre> 509 * list1.sort(true); 510 * list2.sort(true); 511 * list1.removeAll(list2, true); 512 * System.out.println(list1); 513 * </pre> 514 * 515 * @param other 516 * the other list to test against (remains unmodified by this method). 517 * @param isOtherSorted 518 * true if the other list is already sorted ascending, false otherwise (being sorted improves performance). 519 * @return <code>true</code> if the receiver changed as a result of the 520 * call. 521 */ 522 public boolean removeAll(ArrayIntList other, boolean isOtherSorted) { 523 // time complexity is O(N log M) if sorted; O(N*M) otherwise 524 if (size == 0 || other.size() == 0) return false; //nothing to do 525 int limit = other.size(); 526 int j = 0; 527 528 for (int i = 0; i < size; i++) { 529 if (isOtherSorted ? other.binarySearch(elements[i]) < 0 : other.indexOf(0, limit, elements[i]) < 0) { 530 elements[j++] = elements[i]; 531 } 532 } 533 534 boolean modified = (j != size); 535 size = j; 536 return modified; 537 } 538 539 /** 540 * The powerful work horse for all add/insert/replace/remove methods. 541 * One powerful efficient method does it all :-) 542 */ 543 private void shrinkOrExpand(int from, int to, int replacementSize) { 544 checkRange(from, to); 545 int diff = replacementSize - (to - from); 546 if (diff != 0) { 547 ensureCapacity(size + diff); 548 if (size - to > 0) { // check is for performance only (arraycopy is native method) 549 // diff > 0 shifts right, diff < 0 shifts left 550 System.arraycopy(elements, to, elements, to + diff, size - to); 551 } 552 size += diff; 553 } 554 } 555 556 /** 557 * Replaces all elements in the range <code>[from..to)</code> with the 558 * elements <code>replacement[offset..offset+length)</code>. The replacement can have any length. 559 * Increases (or decreases) the receiver's size by <code>length - (to - from)</code>. 560 * Use <code>from==to</code> to perform pure insertion. 561 * 562 * @param from the index of the first element to replace (inclusive) 563 * @param to the index of the last element to replace (exclusive). 564 * @param replacement the elements to replace the replaced elements 565 * @param offset the offset of the first replacing element (inclusive) 566 * @param length the number of replacing elements 567 * @throws IndexOutOfBoundsException if indexes are out of range. 568 */ 569 public void replace(int from, int to, int[] replacement, int offset, int length) { 570 if (offset < 0 || length < 0 || offset + length > replacement.length) 571 throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", replacement.length: " + replacement.length); 572 shrinkOrExpand(from, to, length); 573 System.arraycopy(replacement, offset, this.elements, from, length); 574 } 575 576 /** 577 * Replaces all elements in the range <code>[from..to)</code> with the given replacement. 578 * The replacement can have any length. 579 * Increases (or decreases) the receiver's size by <code>replacement.size - (to - from)</code>. 580 * Use <code>from==to</code> to perform pure insertion. Examples: 581 * <pre> 582 * [a,b,c,d,e].replace(1,4, [x,y]) --> [a,x,y,e] 583 * [a,b].replace(1,1, [w,x,y,z]) --> [a,w,x,y,z,b] 584 * </pre> 585 * 586 * @param from the index of the first element to replace (inclusive) 587 * @param to the index of the last element to replace (exclusive). 588 * @param replacement the elements to replace the replaced elements 589 * @throws IndexOutOfBoundsException if indexes are out of range. 590 */ 591 public void replace(int from, int to, ArrayIntList replacement) { 592 shrinkOrExpand(from, to, replacement.size); 593 System.arraycopy(replacement.elements, 0, this.elements, from, replacement.size); 594 } 595 596 /** 597 * Replaces all elements in the range <code>[from..to)</code> with the given replacement. 598 * The replacement consists of 599 * <code>replacement[replacement.position() .. replacement.position() + replacementSize)</code>. 600 * Increases (or decreases) the receiver's size by <code>replacementSize - (to - from)</code>. 601 * Use <code>from==to</code> to perform pure insertion. Examples: 602 * <pre> 603 * [a,b,c,d,e].replace(1,4, [x,y], 2) --> [a,x,y,e] 604 * [a,b].replace(1,1, [w,x,y,z], 4) --> [a,w,x,y,z,b] 605 * </pre> 606 * There must hold: <code>0 < replacementSize <= replacement.remaining()</code>. 607 * 608 * @param from the index of the first element to replace (inclusive) 609 * @param to the index of the last element to replace (exclusive). 610 * @param replacement the elements to replace the replaced elements 611 * @param replacementSize the number of replacing elements 612 * @throws IndexOutOfBoundsException if indexes are out of range. 613 */ 614 public void replace(int from, int to, IntBuffer replacement, int replacementSize) { 615 if (replacementSize < 0 || replacementSize > replacement.remaining()) 616 throw new IndexOutOfBoundsException("replacementSize: " + replacementSize); 617 shrinkOrExpand(from, to, replacementSize); 618 replacement.get(this.elements, from, replacementSize); 619 } 620 621 /** 622 * Replaces all elements in the range <code>[from..to)</code> with the given replacement. 623 * The replacement can have any length >= 0. 624 * Increases (or decreases) the receiver's size by <code>replacementSize - (to - from)</code>. 625 * Use <code>from==to</code> to perform pure insertion. Examples: 626 * <pre> 627 * [a,b,c,d,e].replace(1,4,x,4) --> [a,x,x,x,x,e] 628 * [a,b,c,d,e].replace(0,0,x,4) --> [x,x,x,x,a,b,c,d,e] 629 * </pre> 630 * 631 * @param from the index of the first element to replace (inclusive) 632 * @param to the index of the last element to replace (exclusive). 633 * @param replacement the elements to replace the replaced elements 634 * @param replacementSize the number of times <code>replacement</code> is to replace the replaced elements 635 * @throws IndexOutOfBoundsException if indexes are out of range. 636 */ 637 public void replace(int from, int to, int replacement, int replacementSize) { 638 checkSize(replacementSize); 639 shrinkOrExpand(from, to, replacementSize); 640 while (replacementSize-- > 0) elements[from++] = replacement; 641 //java.util.Arrays.fill(this.elements, from, from + replacementSize, replacement); 642 } 643 644 /** 645 * Retains (keeps) only the elements in the receiver that are contained in 646 * the specified other list. In other words, removes from the receiver all 647 * of its elements that are not contained in the specified other list. 648 * <p> 649 * Example: <code>[0,1,2,2,3,1].retainAll([2,1]) --> [1,2,2,1]</code> 650 * <p> 651 * An efficient <i>set intersection</i> can be computed along the following lines: 652 * <pre> 653 * list1.sort(true); 654 * list2.sort(true); 655 * list1.retainAll(list2, true); 656 * System.out.println("list1.retainAll(list2) = " + list1); 657 * // as a convenient byproduct we now know if list2 is a SUBSET of list1: 658 * System.out.println("list1.containsAll(list2) = " + (list1.size() == list2.size())); 659 * // as a convenient byproduct we now know if list1 contains ANY element of list2: 660 * System.out.println("list1.containsAny(list2) = " + (list1.size() > 0)); 661 * </pre> 662 * 663 * @param other 664 * the other list to test against (remains unmodified by this method). 665 * @param isOtherSorted 666 * true if the other list is already sorted ascending, false otherwise (being sorted improves performance). 667 * @return <code>true</code> if the receiver changed as a result of the 668 * call. 669 */ 670 public boolean retainAll(ArrayIntList other, boolean isOtherSorted) { 671 // time complexity is O(N log M) if sorted; O(N*M) otherwise 672 if (size == 0) return false; 673 if (other.size() == 0) { 674 size = 0; 675 return true; 676 } 677 678 int limit = other.size(); 679 int j = 0; 680 for (int i = 0; i < size; i++) { 681 if (isOtherSorted ? other.binarySearch(elements[i]) >= 0 : other.indexOf(0, limit, elements[i]) >= 0) 682 elements[j++] = elements[i]; 683 } 684 685 boolean modified = (j != size); 686 size = j; 687 return modified; 688 } 689 690 /** 691 * Rotates (shifts) the elements in the range <code>[from..to)</code> by 692 * the specified distance. After calling this method, the element at index 693 * <code>i</code> will be the element previously at index 694 * <code>(i - distance)</code> mod <code>to-from</code>, for all values 695 * of <code>i</code> between <code>from</code> (inclusive) and 696 * <code>to</code>, exclusive. (This method has no effect on the size of 697 * the list.) Examples: 698 * 699 * <pre> 700 * [a, b, c, d, e].rotate(0, 5, 1) --> [e, a, b, c, d] 701 * [a, b, c, d, e].rotate(0, 5, 2) --> [d, e, a, b, c] 702 * [a, b, c, d, e].rotate(1, 4, -1) --> [a, c, d, b, e] 703 * </pre> 704 * 705 * <p> 706 * To move elements rightwards, use a positive shift distance. To move 707 * elements leftwards, use a negative shift distance. 708 * <p> 709 * Note that this method can usefully be applied to sublists to move one or 710 * more elements within a list while preserving the order of the remaining 711 * elements. 712 * <p> 713 * This implementation exchanges the first element into the location it 714 * should go, and then repeatedly exchanges the displaced element into the 715 * location it should go until a displaced element is swapped into the first 716 * element. If necessary, the process is repeated on the second and 717 * successive elements, until the rotation is complete. This algorithm is 718 * efficient: Time complexity is linear O(to-from), space complexity is 719 * constant O(1). 720 * 721 * @param from 722 * the index of the first element to rotate (inclusive) 723 * @param to 724 * the index of the last element to rotate (exclusive). 725 * @param distance 726 * the distance to rotate the list. There are no constraints on 727 * this value; for example it may be zero, negative, or greater than 728 * <code>to-from</code>. 729 * @throws IndexOutOfBoundsException 730 * if indexes are out of range. 731 * @see java.util.Collections#rotate(java.util.List, int) 732 */ 733 public void rotate(int from, int to, int distance) { 734 checkRange(from, to); 735 int length = to - from; 736 if (length == 0) return; 737 distance = distance % length; 738 if (distance < 0) distance += length; 739 if (distance == 0) return; 740 741 int[] elems = elements; 742 for (int nMoved = 0; nMoved != length; from++) { 743 int displaced = elems[from]; 744 int i = from; 745 do { 746 i += distance; 747 if (i >= to) i -= length; 748 749 int tmp = elems[i]; 750 elems[i] = displaced; 751 displaced = tmp; 752 753 nMoved++; 754 } while (i != from); 755 } 756 } 757 758 /** 759 * Replaces the element at the specified index with the specified 760 * element. 761 * 762 * @param index 763 * index of element to replace. 764 * @param element 765 * element to be stored at the specified index. 766 * @throws IndexOutOfBoundsException 767 * if index is out of range. 768 */ 769 public void set(int index, int element) { 770 checkIndex(index); 771 elements[index] = element; 772 // equally correct alternative impl: replace(index, index+1, element, 1); 773 } 774 775 /** 776 * Returns the number of contained elements. 777 * 778 * @return the number of elements contained in the receiver. 779 */ 780 public int size() { 781 return size; 782 } 783 784 /** 785 * Sorts the elements into ascending numerical order. For mathematical set 786 * operations, optionally removes duplicate elements before returning. 787 * Examples: 788 * <pre> 789 * [3,2,2,1].sort(false) --> [1,2,2,3] 790 * [3,2,2,1].sort(true) --> [1,2,3] 791 * </pre> 792 * 793 * @param removeDuplicates remove duplicate elements or keep them? 794 */ 795 public void sort(boolean removeDuplicates) { 796 final int maxWidth = 256 * 1024; // memory consumption threshold (also prevents int overflows in countSort()) 797 if (size > 60) { // performance threshold heuristic 798 // compute minimum and maximum values 799 int[] elems = elements; 800 int min = elems[0]; 801 int max = min; 802 for (int i = 1; i < size && max - min < maxWidth && max - min >= 0; i++) { // width < 0 on int overflow 803 int elem = elems[i]; 804 if (elem > max) max = elem; 805 else if (elem < min) min = elem; 806 } 807 808 int width = max - min; 809 if (width < maxWidth && width >= 0 ) { 810 int countSortEstimate = Math.max(width, size); // O(Max(width,N)) 811 double log2 = Math.log(size) / 0.6931471805599453; // O(N*log(N,base=2)) ; ln(2)=0.6931471805599453 812 double quickSortEstimate = size * log2; 813 if (countSortEstimate < quickSortEstimate) { 814 //System.out.println("using countSort.."); 815 countSort(removeDuplicates, min, max); 816 return; 817 } 818 } 819 } 820 821 // use quicksort if there is no more efficient alternative: 822 java.util.Arrays.sort(elements, 0, size); 823 if (removeDuplicates) removeDuplicates(); 824 } 825 826 /** efficient sort implementation: O(N) via frequency counts */ 827 private void countSort(boolean removeDuplicates, int min, int max) { 828 // countSort is most efficient on large lists that have values that are in a small [min,max] range 829 // assertion: max - min +1 does not yield int overflow 830 int[] counts = new int[max - min + 1]; // could use BitSet if removeDuplicates 831 for (int i = size; --i >= 0; ) { 832 counts[elements[i] - min]++; 833 } 834 835 int j = 0; 836 for (int i = min; i >= min && i <= max; i++) { // safe even with int overflow 837 int k = counts[i - min]; 838 if (removeDuplicates && k > 1) k = 1; 839 while (--k >= 0) { 840 elements[j++] = i; 841 } 842 } 843 size = j; 844 } 845 846 /** 847 * [1,2,2,3,3,3] --> [1,2,3] 848 * Assertion: list must be sorted prior to calling this method 849 */ 850 private void removeDuplicates() { 851 int i = 0; 852 int j = 0; 853 while (j < size) { 854 int elem = elements[j++]; 855 elements[i++] = elem; 856 while (j < size && elements[j] == elem) j++; // skip duplicates 857 } 858 size = i; 859 } 860 861 /** Small helper method eliminating redundancy. */ 862 private int[] subArray(int from, int length, int capacity) { 863 int[] subArray = new int[capacity]; 864 System.arraycopy(elements, from, subArray, 0, length); 865 return subArray; 866 } 867 868 /** 869 * Constructs and returns a new list containing a copy of the elements in 870 * the range <code>[from..to)</code>. 871 * 872 * @param from 873 * the index of the first element (inclusive). 874 * @param to 875 * the index of the last element (exclusive). 876 * @return a new list 877 * @throws IndexOutOfBoundsException 878 * if indexes are out of range 879 */ 880 public ArrayIntList subList(int from, int to) { 881 checkRange(from, to); 882 return new ArrayIntList(subArray(from, to - from, to - from)); 883 } 884 885 /** 886 * Returns a copied array of bytes containing all elements; the returned 887 * array has length = this.size(). 888 */ 889 public int[] toArray() { 890 return subArray(0, size, size); 891 } 892 893 /** 894 * Returns a string representation, containing the numeric String 895 * representation of each element. 896 */ 897 public String toString() { 898 //return toList().toString(); 899 StringBuffer buf = new StringBuffer(4*size); 900 buf.append("["); 901 for (int i = 0; i < size; i++) { 902 buf.append(elements[i]); 903 if (i < size-1) buf.append(", "); 904 } 905 buf.append("]"); 906 return buf.toString(); 907 } 908 909 /** 910 * Trims the capacity of the receiver to be the receiver's current size; 911 * Releases any superfluos internal memory. An application can use this 912 * operation to minimize the storage of the receiver. 913 */ 914 public void trimToSize() { 915 if (elements.length > size) { 916 elements = subArray(0, size, size); 917 } 918 } 919 920 /** 921 * Checks if the given index is in range. 922 */ 923 private void checkIndex(int index) { 924 if (index >= size || index < 0) 925 throw new IndexOutOfBoundsException("index: " + index 926 + ", size: " + size); 927 } 928 929 /** 930 * Checks if the given range is within the contained array's bounds. 931 */ 932 private void checkRange(int from, int to) { 933 if (from < 0 || from > to || to > size) 934 throw new IndexOutOfBoundsException("from: " + from + ", to: " 935 + to + ", size: " + size); 936 } 937 938 /** 939 * Checks if the given size is within bounds. 940 */ 941 private void checkSize(int newSize) { 942 if (newSize < 0) 943 throw new IndexOutOfBoundsException("newSize: " + newSize); 944 } 945 946 /** efficient Serializable support */ 947 private void writeObject(java.io.ObjectOutputStream out) throws IOException { 948 out.defaultWriteObject(); 949 out.writeInt(elements.length); 950 for (int i = 0; i < size; i++) { 951 out.writeInt(elements[i]); 952 } 953 } 954 955 /** efficient Serializable support */ 956 private void readObject(java.io.ObjectInputStream in) throws IOException, 957 ClassNotFoundException { 958 in.defaultReadObject(); 959 elements = new int[in.readInt()]; 960 for (int i = 0; i < size; i++) { 961 elements[i] = in.readInt(); 962 } 963 } 964 965 // **************************************************************************** 966 // following are some method not deemed a) important enough or b) complex enough 967 // to warrant interface bloat: 968 // **************************************************************************** 969 970 971 // /** 972 // * Appends the specified elements to the end of this list. 973 // * <p> 974 // * If you need to append <code>elems[from..to)</code>, use 975 // * <code>list.add(new ArrayIntList(elems).subList(from, to))</code> 976 // * or <code>list.add(IntBuffer.wrap(elems, from, to-from))</code> 977 // * or similar. 978 // * 979 // * @param elems 980 // * elements to be appended. 981 // * @return <code>this</code> (for chaining convenience only) 982 // */ 983 // public ArrayIntList add(int[] elems) { 984 // replace(size, size, elems); 985 // return this; 986 // } 987 // 988 // /** 989 // * Inserts the specified element before the specified index. Shifts the 990 // * element currently at that index (if any) and any subsequent elements 991 // * to the right. This is equivalent to <code>replace(index, index, elem, 1)</code>. 992 // * 993 // * @param index 994 // * index before which the specified element is to be inserted 995 // * @param elem 996 // * element to insert. 997 // * @throws IndexOutOfBoundsException if index is out of range. 998 // */ 999 // private void insert(int index, int elem) { 1000 // replace(index, index, elem, 1); 1001 // } 1002 // 1003 // /** 1004 // * Inserts the specified elements before the specified index. Shifts the 1005 // * element currently at that index (if any) and any subsequent elements 1006 // * to the right. 1007 // * 1008 // * @param index 1009 // * index before which the specified elements are to be inserted 1010 // * @param elems 1011 // * elements to insert. 1012 // * @throws IndexOutOfBoundsException if index is out of range. 1013 // */ 1014 // private void insert(int index, int[] elems) { 1015 // replace(index, index, elems); 1016 // } 1017 // 1018 // /** 1019 // * Inserts the specified elements before the specified index. Shifts the 1020 // * element currently at that index (if any) and any subsequent elements 1021 // * to the right. 1022 // * 1023 // * @param index 1024 // * index before which the specified elements are to be inserted 1025 // * @param elems 1026 // * elements to insert. 1027 // * @throws IndexOutOfBoundsException if index is out of range. 1028 // */ 1029 // private void insert(int index, ArrayIntList elems) { 1030 // replace(index, index, elems); 1031 // } 1032 // 1033 // /** 1034 // * Inserts the remaining buffer elements before the specified index. 1035 // * Shifts the element currently at that index (if any) and any subsequent 1036 // * elements to the right. 1037 // * 1038 // * @param index 1039 // * index before which the specified elements are to be inserted 1040 // * @param elems 1041 // * elements to insert. 1042 // * @throws IndexOutOfBoundsException if index is out of range. 1043 // */ 1044 // private void insert(int index, IntBuffer elems) { 1045 // replace(index, index, elems); 1046 // } 1047 1048 // /** 1049 // * Returns the index of the last occurrence of the specified element within 1050 // * the range <code>[from..to)</code>. Returns <code>-1</code> if the 1051 // * receiver does not contain such an element. 1052 // * 1053 // * @param from 1054 // * the leftmost search index, inclusive. 1055 // * @param to 1056 // * the rightmost search index, exclusive. 1057 // * @param elem 1058 // * element to search for. 1059 // * @return the index of the last occurrence of the element in the receiver; 1060 // * returns <code>-1</code> if the element is not found. 1061 // * @throws IndexOutOfBoundsException 1062 // * if indexes are out of range. 1063 // */ 1064 // public int lastIndexOf(int from, int to, int elem) { 1065 // checkRange(from, to); 1066 // int[] elems = elements; 1067 // for (int i = to; --i >= from; ) { 1068 // if (elem == elems[i]) return i; //found 1069 // } 1070 // return -1; //not found 1071 // } 1072 1073 // /** 1074 // * Removes the element at the specified index. Shifts any subsequent 1075 // * elements to the left. Keeps the current capacity. 1076 // * 1077 // * @param index 1078 // * the index of the element to removed. 1079 // * @throws IndexOutOfBoundsException 1080 // * if index is out of range 1081 // */ 1082 // public void remove(int index) { 1083 // remove(index, index+1); 1084 // } 1085 1086 // /** 1087 // * Reverses the order of elements in the range <code>[from..to)</code>. 1088 // * Last becomes first, second last becomes second first, and so on. 1089 // * <p> 1090 // * Example: <code>[a,b,c,d].reverse(0,4) --> [d,c,b,a]</code> 1091 // * 1092 // * @param from the index of the first element (inclusive) 1093 // * @param to the index of the last element (exclusive). 1094 // * @throws IndexOutOfBoundsException if indexes are out of range. 1095 // */ 1096 // public void reverse(int from, int to) { 1097 // checkRange(from, to); 1098 // int[] elems = elements; 1099 // int middle = from + (to - from) / 2; 1100 // to--; 1101 // for ( ; from < middle; from++, to--) { // swap 1102 // int tmp = elems[from]; 1103 // elems[from] = elems[to]; 1104 // elems[to] = tmp; 1105 // } 1106 // } 1107 1108 // /** 1109 // * Sets the size to the given new size, expanding the list capacity if 1110 // * necessary. 1111 // * <p> 1112 // * Capacity expansion introduces a new backing array. If the new 1113 // * size is greater than the current size the elements between the current 1114 // * size and the new size will become legally accessible but have undefined 1115 // * values. An application will typically want to set these elements to defined 1116 // * values immediately after this method returns. Note that 1117 // * <code>setSize(0)</code> effectively clears the list (as does 1118 // * <code>remove(0, list.size()</code>). 1119 // * 1120 // * @param newSize the new size. 1121 // * @return <code>this</code> (for chaining convenience only) 1122 // * @throws IndexOutOfBoundsException if new size is less than zero. 1123 // */ 1124 // public ArrayIntList setSize(int newSize) { 1125 // checkSize(newSize); 1126 // ensureCapacity(newSize); 1127 // // equivalent impl: shrinkOrExpand(0, size, newSize); 1128 // size = newSize; 1129 // return this; 1130 // } 1131 1132 // /** 1133 // * Returns a <code>java.util.ArrayList</code> containing a copy of all elements. 1134 // */ 1135 // public java.util.ArrayList toList() { 1136 // java.util.ArrayList list = new java.util.ArrayList(size); 1137 // for (int i = 0; i < size; i++) 1138 // list.add(new Integer(elements[i])); 1139 // return list; 1140 // } 1141 1142 }