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.io.InputStream; 010 import java.io.OutputStream; 011 import java.nio.ByteBuffer; 012 import java.nio.CharBuffer; 013 import java.nio.channels.FileChannel; 014 import java.nio.channels.ReadableByteChannel; 015 import java.nio.charset.Charset; 016 import java.util.BitSet; 017 018 /** 019 Efficient resizable auto-expanding list holding <code>byte</code> elements; implemented with arrays. 020 The API is intended for easy non-trivial high-throughput processing, 021 and (in an elegant and compact yet different form) provides all list and set functionality 022 of the java.util collections package, as well as a little more. 023 This API fills the gap between raw arrays (non-resizable), nio ByteBuffers (non-resizable) and 024 java.util.List and java.util.Set (resizable but not particularly useful for 025 <i>non-trivial high-throughput</i> processing on primitive types). 026 For example, this class is convenient to parse and/or assemble 027 variable-sized network messages if message lengths are a priori unknown. 028 <p> 029 Indexed element access is zero based: valid indexes range from 030 index <code>0</code> (inclusive) to index <code>list.size()</code> (exclusive). 031 Attempts to access out-of-range indexes will throw an {@link IndexOutOfBoundsException}. 032 <p> 033 <strong>Note that this implementation is not synchronized, hence not inherently thread safe.</strong> 034 <p> 035 Example usage: 036 <pre> 037 System.out.println(new ArrayByteList(new byte[] {0,1,2})); 038 039 // insert and replace 040 ArrayByteList demo = new ArrayByteList(new byte[] {0,1,2}); 041 demo.replace(0,0, new byte[] {4,5}); // insert 042 System.out.println(demo); // yields [4,5,0,1,2] 043 demo.replace(0,2, new byte[] {6,7,8,9}); 044 System.out.println(demo); // yields [6,7,8,9,0,1,2] 045 046 // sort, search and remove 047 System.out.println(demo.subList(1,3)); // yields [7,8] 048 demo.sort(true); 049 System.out.println(demo); 050 System.out.println(demo.binarySearch((byte) 7)); 051 demo.remove(4, 4+1); // remove elem at index 4 052 System.out.println(demo); 053 System.out.println(demo.binarySearch((byte) 7)); 054 055 // efficient file I/O 056 System.out.println(new ArrayByteList(0).add(new java.io.FileInputStream("/etc/passwd")).toString(null)); 057 new java.io.FileOutputStream("/tmp/test").write(demo.asArray(), 0, demo.size()); 058 System.out.println(new ArrayByteList(0).add(new java.io.FileInputStream("/tmp/test"))); 059 System.out.println(new ArrayByteList(0).add(new java.io.FileInputStream("/tmp/test").getChannel())); 060 061 // network I/O via stream 062 java.nio.charset.Charset charset = java.nio.charset.Charset.forName("ISO-8859-1"); 063 System.out.println(new ArrayByteList(0).add(new java.net.URL("http://www.google.com").openStream()).toString(charset)); 064 065 // simple HTTP via raw socket channel 066 java.nio.channels.SocketChannel channel = java.nio.channels.SocketChannel.open(); 067 channel.connect(new java.net.InetSocketAddress("www.google.com", 80)); 068 channel.write(new ArrayByteList("GET / HTTP/1.0" + "\r\n\r\n", charset).asByteBuffer()); 069 System.out.println(new ArrayByteList(0).add(channel).toString(charset)); 070 </pre> 071 <p> 072 Manipulating primitive values other than bytes is not directly 073 supported. However, this can be done via <code>asByteBuffer()</code> 074 along the following lines: 075 <pre> 076 // get and set 4 byte integer value at end of list: 077 list = ... 078 int val = list.asByteBuffer().getInt(list.size() - 4); 079 list.asByteBuffer().setInt(list.size() - 4, val * 10); 080 081 // append 8 byte double value: 082 list = ... 083 double elemToAdd = 1234.0; 084 list.replace(list.size(), list.size(), (byte)0, 8); // add 8 bytes at end 085 list.asByteBuffer().putDouble(list.size() - 8, elemToAdd); 086 087 // insert 8 byte double value at beginning: 088 list = ... 089 double elemToInsert = 1234.0; 090 list.replace(0, 0, 0, 8); // insert 8 bytes at beginning 091 list.asByteBuffer().putDouble(0, elemToInsert); 092 </pre> 093 This class requires JDK 1.4 or higher; otherwise it has zero dependencies. 094 Hence you can simply copy the file into your own project if minimal dependencies are desired. 095 <p> 096 Also note that the compiler can (and will) easily inline all methods, then optimize away. 097 In fact with the Sun jdk-1.4.2 server VM it is hard to measure any difference 098 to raw array manipulations at abstraction level zero. 099 100 @author whoschek@lbl.gov 101 @author $Author: hoschek3 $ 102 @version $Revision: 1.52 $, $Date: 2004/12/01 21:00:24 $ 103 */ 104 public final class ArrayByteList implements java.io.Serializable { 105 106 /** 107 * The array into which the elements of the list are stored. The 108 * capacity of the list is the length of this array. 109 */ 110 private transient byte[] elements; 111 112 /** 113 * The current number of elements contained in this list. 114 */ 115 private int size; 116 117 /** 118 * For compatibility across versions 119 */ 120 private static final long serialVersionUID = -6250350905005960078L; 121 122 /** 123 * The default charset is UTF-8, and fixed for interoperability. 124 * Note that the first 128 character codes of UTF-8, ISO-8859-1 and US-ASCII are identical. 125 * Hence these charsets are equivalent for most practical purposes. 126 * This charset is used on most operating systems (e.g. for system files, config files, log files, scripts, source code, etc.) 127 * Note that in Java UTF-8 and ISO-8859-1 always works since JDK support for it is required by the JDK spec. 128 */ 129 private static final Charset DEFAULT_CHARSET = Charset.forName("UTF-8"); 130 131 /** 132 * Constructs an empty list. 133 */ 134 public ArrayByteList() { 135 this(64); 136 } 137 138 /** 139 * Constructs an empty list with the specified initial capacity. 140 * 141 * @param initialCapacity 142 * the number of elements the receiver can hold without 143 * auto-expanding itself by allocating new internal memory. 144 */ 145 public ArrayByteList(int initialCapacity) { 146 elements = new byte[initialCapacity]; 147 size = 0; 148 } 149 150 /** 151 * Constructs a list SHARING the specified elements. The initial size and 152 * capacity of the list is the length of the backing array. 153 * <p> 154 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low, 155 * <b>the array is SHARED, not copied </b>. So if subsequently you modify 156 * the specified array directly via the [] operator, be sure you know what 157 * you're doing. 158 * <p> 159 * If you rather need copying behaviour, use 160 * <code>copy = new ArrayByteList(byte[] elems).copy()</code> or similar. 161 * <p> 162 * If you need a list containing a copy of <code>elems[from..to)</code>, use 163 * <code>list = new ArrayByteList(to-from).add(elems, from, to-from)</code> 164 * or <code>list = new ArrayByteList(ByteBuffer.wrap(elems, from, to-from))</code> 165 * or similar. 166 * 167 * @param elems 168 * the array backing the constructed list 169 */ 170 public ArrayByteList(byte[] elems) { 171 elements = elems; 172 size = elems.length; 173 } 174 175 /** 176 * Constructs a list containing a copy of the remaining buffer elements. The 177 * initial size and capacity of the list is <code>elems.remaining()</code>. 178 * 179 * @param elems 180 * the elements initially to be added to the list 181 */ 182 public ArrayByteList(ByteBuffer elems) { 183 this(elems.remaining()); 184 add(elems); 185 } 186 187 /** 188 * Constructs a list containing a copy of the encoded form of the given 189 * char sequence (String, StringBuffer, CharBuffer, etc). 190 * 191 * @param str 192 * the string to convert. 193 * @param charset 194 * the charset to convert with (e.g. <code>Charset.forName("US-ASCII")</code>, 195 * <code>Charset.forName("ISO-8859-1")</code>). 196 * If <code>null</code> uses <code>Charset.forName("UTF-8")</code> as the default charset. 197 */ 198 public ArrayByteList(CharSequence str, Charset charset) { 199 this(getCharset(charset).encode(CharBuffer.wrap(str))); 200 } 201 202 /** 203 * Appends the specified element to the end of this list. 204 * 205 * @param elem 206 * element to be appended to this list. 207 * @return <code>this</code> (for chaining convenience only) 208 */ 209 public ArrayByteList add(byte elem) { 210 if (size == elements.length) ensureCapacity(size + 1); 211 elements[size++] = elem; 212 return this; 213 // equally correct alternative impl: insert(size, elem); 214 } 215 216 /** 217 * Appends the elements in the range <code>[offset..offset+length)</code> to the end of this list. 218 * 219 * @param elems the elements to be appended 220 * @param offset the offset of the first element to add (inclusive) 221 * @param length the number of elements to add 222 * @return <code>this</code> (for chaining convenience only) 223 * @throws IndexOutOfBoundsException if indexes are out of range. 224 */ 225 public ArrayByteList add(byte[] elems, int offset, int length) { 226 if (offset < 0 || length < 0 || offset + length > elems.length) 227 throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", elems.length: " + elems.length); 228 ensureCapacity(size + length); 229 System.arraycopy(elems, offset, this.elements, size, length); 230 size += length; 231 return this; 232 // equally correct alternative impl: replace(size, size, elems, offset, length); 233 } 234 235 /** 236 * Appends the specified elements to the end of this list. 237 * 238 * @param elems 239 * elements to be appended. 240 * @return <code>this</code> (for chaining convenience only) 241 */ 242 public ArrayByteList add(ArrayByteList elems) { 243 replace(size, size, elems); 244 return this; 245 } 246 247 /** 248 * Appends the remaining buffer elements to the end of this list. 249 * 250 * @param elems 251 * elements to be appended. 252 * @return <code>this</code> (for chaining convenience only) 253 */ 254 public ArrayByteList add(ByteBuffer elems) { 255 int length = elems.remaining(); 256 ensureCapacity(size + length); 257 elems.get(this.elements, size, length); 258 size += length; 259 return this; 260 // equally correct alternative impl: replace(size, size, elems, elems.remaining()); 261 } 262 263 /** 264 * Appends the encoded form of the given char sequence (String, StringBuffer, CharBuffer, etc). 265 * 266 * @param str 267 * the string to convert. 268 * @param charset 269 * the charset to convert with (e.g. <code>Charset.forName("US-ASCII")</code>, 270 * <code>Charset.forName("ISO-8859-1")</code>). 271 * If <code>null</code> uses <code>Charset.forName("UTF-8")</code> as the default charset. 272 * @return <code>this</code> (for chaining convenience only) 273 */ 274 public ArrayByteList add(CharSequence str, Charset charset) { 275 return add(getCharset(charset).encode(CharBuffer.wrap(str))); 276 } 277 278 /** 279 * Appends the remaining elements of the stream to the end of this list, 280 * reading until end-of-stream. Finally closes the stream. Note that the 281 * implementation is efficient even if the input stream is not a buffered 282 * stream. 283 * 284 * @param elems 285 * the input stream to read from. 286 * @return <code>this</code> (for chaining convenience only) 287 * @throws IOException 288 * if an I/O error occurs. 289 */ 290 public ArrayByteList add(InputStream elems) throws IOException { 291 // Note that our algo is correct and efficient even if 292 // the input stream implements available() in weird or buggy ways. 293 try { 294 ensureCapacity(size + 1 + Math.max(0, elems.available())); 295 int n; 296 while ((n = elems.read(elements, size, elements.length - size)) >= 0) { 297 size += n; 298 // increasingly make room for next read (and defensively 299 // ensure we don't spin loop, attempting to read zero bytes per iteration) 300 ensureCapacity(size + Math.max(1, elems.available())); 301 } 302 } 303 finally { 304 if (elems != null) elems.close(); 305 } 306 return this; 307 } 308 309 /** 310 * Appends the remaining elements of the channel to the end of this list, 311 * reading until end-of-stream. Finally closes the channel. 312 * 313 * @param elems 314 * the channel to read from. 315 * @return <code>this</code> (for chaining convenience only) 316 * @throws IOException 317 * if an I/O error occurs. 318 */ 319 public ArrayByteList add(ReadableByteChannel elems) throws IOException { 320 try { 321 int remaining = 8192; 322 if (elems instanceof FileChannel) { // we can be more efficient 323 long rem = ((FileChannel) elems).size() - ((FileChannel) elems).position(); 324 if (size + 1 + rem > Integer.MAX_VALUE) throw new IllegalArgumentException("File channel too large (2 GB limit exceeded)"); 325 remaining = (int) rem; 326 } 327 ensureCapacity(size + 1 + remaining); 328 int n; 329 while ((n = elems.read(ByteBuffer.wrap(elements, size, elements.length - size))) >= 0) { 330 size += n; 331 // increasingly make room for next read (and defensively 332 // ensure we don't spin loop, attempting to read zero bytes per iteration) 333 ensureCapacity(size + 1); 334 } 335 } 336 finally { 337 if (elems != null) elems.close(); 338 } 339 return this; 340 } 341 342 /** 343 * Returns the elements currently stored, including invalid elements between 344 * size and capacity, if any. 345 * <p> 346 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low, 347 * <b>the array is SHARED, not copied </b>. So if subsequently you modify the 348 * returned array directly via the [] operator, be sure you know what you're 349 * doing. 350 * 351 * @return the elements currently stored. 352 */ 353 public byte[] asArray() { 354 return elements; 355 } 356 357 /** 358 * Returns a buffer SHARING elements with the receiver. The buffer will 359 * have the default NIO byte order, which is ByteOrder.BIG_ENDIAN. 360 * <p> 361 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low, 362 * <b>the array is SHARED, not copied </b>. So if subsequently you modify the 363 * returned buffer, be sure you know what you're doing. 364 */ 365 public ByteBuffer asByteBuffer() { 366 return ByteBuffer.wrap(elements, 0, size); 367 } 368 369 /** 370 * Creates and returns an unsynchronized output stream that appends to this 371 * SHARED backing byte list. Useful if legacy code requires adapting to a 372 * stream based interface. Note: This is more efficient and 373 * straighforward than using a {@link java.io.ByteArrayOutputStream}. 374 * <p> 375 * Writing to the stream means adding (appending) elements to the end of the 376 * (auto-expanding) backing list. 377 * <p> 378 * Closing the stream has no effect. The stream's methods can be called 379 * after the stream has been closed without generating an IOException. In 380 * fact the stream implementation never ever throws an IOException. 381 * <p> 382 * If your legacy code requires adapting to an {@link InputStream} instead, 383 * simply use the non-copying {@link java.io.ByteArrayInputStream}, for example as in 384 * <code>new java.io.ByteArrayInputStream(list.asArray(), 0, list.size())</code>. 385 * 386 * @return the stream 387 */ 388 public OutputStream asOutputStream() { 389 return new OutputStream() { 390 public void write(int b) { 391 add((byte) b); 392 } 393 public void write(byte b[], int off, int len) { 394 add(b, off, len); 395 } 396 }; 397 } 398 399 /** 400 * Searches the list for the specified value using the binary search 401 * algorithm. The list <strong>must </strong> be sorted (as by the 402 * <code>sort</code> method) prior to making this call. If it is not sorted, 403 * the results are undefined. If the list contains multiple elements with 404 * the specified value, there is no guarantee which one will be found. 405 * 406 * @param key 407 * the value to be searched for. 408 * @return index of the search key, if it is contained in the list; 409 * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The 410 * <i>insertion point </i> is defined as the point at which the key 411 * would be inserted into the list: the index of the first element 412 * greater than the key, or <code>list.size()</code>, if all elements 413 * in the list are less than the specified key. Note that this 414 * guarantees that the return value will be >= 0 if and only if 415 * the key is found. 416 * @see #sort(boolean) 417 */ 418 public int binarySearch(byte key) { 419 int low = 0; 420 int high = size - 1; 421 422 while (low <= high) { 423 int mid = (low + high) >> 1; // >> 1 is equivalent to divide by 2 424 byte midVal = elements[mid]; 425 426 if (midVal < key) 427 low = mid + 1; 428 else if (midVal > key) 429 high = mid - 1; 430 else 431 return mid; // key found 432 } 433 return -(low + 1); // key not found. 434 } 435 436 /** 437 * Removes all elements but keeps the current capacity; Afterwards 438 * <code>size()</code> will yield zero. 439 * 440 * @return <code>this</code> (for chaining convenience only) 441 */ 442 public ArrayByteList clear() { 443 size = 0; 444 return this; 445 // equally correct alternative impl: remove(0, size); 446 } 447 448 /** 449 * Constructs and returns a new list that is a deep copy of the receiver. 450 * 451 * @return a deep copy of the receiver. 452 */ 453 public ArrayByteList copy() { 454 return new ArrayByteList(toArray()); 455 } 456 457 /** 458 * Compares the specified Object with the receiver. Returns true if and only 459 * if the specified Object is also a list of the same type, both Lists 460 * have the same size, and all corresponding pairs of elements in the two 461 * Lists are identical. In other words, two Lists are defined to be equal if 462 * they contain the same elements in the same order. 463 * 464 * @param otherObj 465 * the Object to be compared for equality with the receiver. 466 * @return true if the specified Object is equal to the receiver. 467 */ 468 public boolean equals(Object otherObj) { 469 if (this == otherObj) return true; 470 if (!(otherObj instanceof ArrayByteList)) return false; 471 ArrayByteList other = (ArrayByteList) otherObj; 472 if (size != other.size) return false; 473 return indexOf(0, size, other) >= 0; 474 } 475 476 /** 477 * Ensures that the receiver can hold at least the specified number of 478 * elements without needing to allocate new internal memory. If necessary, 479 * allocates new internal memory and increases the capacity of the receiver. 480 * 481 * @param minCapacity 482 * the desired minimum capacity. 483 */ 484 public void ensureCapacity(int minCapacity) { 485 if (minCapacity > elements.length) { 486 int newCapacity = Math.max(minCapacity, (elements.length * 3) / 2 + 1); 487 elements = subArray(0, size, newCapacity); 488 } 489 } 490 491 /** 492 * Finds all matching sublists in the range <code>[from..to)</code> and 493 * replaces them with the given replacement. A sublist matches if it is 494 * equal to the given pattern. The pattern must have a size greater than 495 * zero. The replacement can have any size. 496 * Examples: 497 * <pre> 498 * [a,b,c,d,b,c].findReplace(0,6, [b,c], [x,y,z]) --> [a,x,y,z,d,x,y,z] 499 * [a,b,c,d,b,c].findReplace(0,6, [b,c], []) --> [a,d] 500 * </pre> 501 * 502 * @param from the index of the first element to search (inclusive) 503 * @param to the index of the last element to search (exclusive). 504 * @param pattern the sublist to search for 505 * @param replacement the elements to replace the found sublists 506 * @return the number of sublists found matching the pattern 507 * @throws IndexOutOfBoundsException if indexes are out of range. 508 * @throws IllegalArgumentException if pattern.size() == 0. 509 */ 510 public int findReplace(int from, int to, ArrayByteList pattern, ArrayByteList replacement) { 511 checkRange(from, to); 512 if (pattern.size == 0) throw new IllegalArgumentException("pattern size must be > 0"); 513 int n = 0; 514 while ((from = indexOf(from, to, pattern)) >= 0) { 515 if (pattern != replacement) { // do more than just counting matches 516 replace(from, from + pattern.size, replacement); 517 to += replacement.size - pattern.size; 518 } 519 from += replacement.size; 520 n++; 521 } 522 return n; 523 } 524 525 /** 526 * Returns the element at the specified index. 527 * 528 * @param index 529 * index of element to return. 530 * @throws IndexOutOfBoundsException if index is out of range. 531 */ 532 public byte get(int index) { 533 checkIndex(index); 534 return elements[index]; 535 } 536 537 /** 538 * Returns the hash code value for this list. The algorithm ensures that 539 * <code>list1.equals(list2)</code> implies that 540 * <code>list1.hashCode()==list2.hashCode()</code> for any two lists, 541 * <code>list1</code> and <code>list2</code>, as required by the general 542 * contract of <code>Object.hashCode</code>. 543 * <p> 544 * Warning: run time complexity is O(N) 545 * 546 * @return the hash code value for this list. 547 * @see Object#hashCode() 548 * @see Object#equals(Object) 549 * @see #equals(Object) 550 * @see java.util.List#hashCode() 551 */ 552 public int hashCode() { 553 int hashCode = 1; 554 byte[] elems = elements; 555 for (int i = size; --i >= 0; ) 556 hashCode = 31*hashCode + elems[i]; 557 return hashCode; 558 } 559 560 /** 561 * Returns the index of the first occurrence of the given sublist within 562 * the range <code>this[from..to)</code>. 563 * Returns <code>-1</code> if the receiver does not contain such a sublist. 564 * Examples: 565 * <pre> 566 * [a,b,c,d,e,b,c,d].indexOf(0,8, [b,c,d]) --> 1 567 * [a,b,c,d,e].indexOf(0,5, [b,c,d]) --> 1 568 * [a,b,c,d,e].indexOf(1,4, [b,c,d]) --> 1 569 * [a,b,c,d,e].indexOf(0,5, [x,y]) --> -1 570 * [a,b,c,d,e].indexOf(0,3, [b,c,d]) --> -1 571 * [a].indexOf(0,1, [a,b,c]) --> -1 572 * [a,b,c,d,e].indexOf(2,3, []) --> 2 // empty sublist is always found 573 * [].indexOf(0,0, []) --> 0 574 * </pre> 575 * 576 * @param from 577 * the leftmost search index within the receiver, inclusive. 578 * @param to 579 * the rightmost search index within the receiver, exclusive. 580 * @param subList 581 * the sublist to search for. 582 * @return the index of the first occurrence of the sublist in the receiver; 583 * returns <code>-1</code> if the sublist is not found. 584 * @throws IndexOutOfBoundsException 585 * if indexes are out of range 586 */ 587 public int indexOf(int from, int to, ArrayByteList subList) { 588 // brute-force algorithm, but very efficiently implemented 589 checkRange(from, to); 590 byte[] elems = elements; 591 byte[] subElems = subList.elements; 592 593 int subsize = subList.size; 594 to -= subsize; 595 while (from <= to) { 596 int i = subsize; 597 int j = from + subsize; 598 while (--i >= 0 && elems[--j] == subElems[i]) { // compare from right to left 599 ; 600 } 601 if (i < 0) return from; // found 602 from++; 603 } 604 return -1; // not found 605 } 606 607 /** 608 * Returns the index of the first occurrence of the specified element within 609 * the range <code>[from..to)</code>. Returns <code>-1</code> if the 610 * receiver does not contain such an element. 611 * 612 * @param from 613 * the leftmost search index, inclusive. 614 * @param to 615 * the rightmost search index, exclusive. 616 * @param elem 617 * element to search for. 618 * @return the index of the first occurrence of the element in the receiver; 619 * returns <code>-1</code> if the element is not found. 620 * @throws IndexOutOfBoundsException 621 * if indexes are out of range 622 */ 623 public int indexOf(int from, int to, byte elem) { 624 checkRange(from, to); 625 byte[] elems = elements; 626 for (int i = from; i < to; i++) { 627 if (elem == elems[i]) return i; //found 628 } 629 return -1; //not found 630 } 631 632 /** 633 * Returns the index of the last occurrence of the given sublist within 634 * the range <code>this[from..to)</code>. 635 * Returns <code>-1</code> if the receiver does not contain such a sublist. 636 * Examples: 637 * <pre> 638 * [a,b,c,d,e,b,c,d].lastIndexOf(0,8, [b,c,d]) --> 5 639 * [a,b,c,d,e].lastIndexOf(0,5, [b,c,d]) --> 1 640 * [a,b,c,d,e].lastIndexOf(1,4, [b,c,d]) --> 1 641 * [a,b,c,d,e].lastIndexOf(0,5, [x,y]) --> -1 642 * [a,b,c,d,e].lastIndexOf(0,3, [b,c,d]) --> -1 643 * [a].lastIndexOf(0,1, [a,b,c]) --> -1 644 * [a,b,c,d,e].lastIndexOf(2,3, []) --> 3 // empty sublist is always found 645 * [].lastIndexOf(0,0, []) --> 0 646 * </pre> 647 * 648 * @param from 649 * the leftmost search index within the receiver, inclusive. 650 * @param to 651 * the rightmost search index within the receiver, exclusive. 652 * @param subList 653 * the sublist to search for. 654 * @return the index of the last occurrence of the sublist in the receiver; 655 * returns <code>-1</code> if the sublist is not found. 656 * @throws IndexOutOfBoundsException 657 * if indexes are out of range 658 */ 659 public int lastIndexOf(int from, int to, ArrayByteList subList) { 660 // brute-force algorithm, but very efficiently implemented 661 checkRange(from, to); 662 byte[] elems = elements; 663 byte[] subElems = subList.elements; 664 665 int subsize = subList.size; 666 from += subsize; 667 while (from <= to) { 668 int i = subsize; 669 int j = to; 670 while (--i >= 0 && elems[--j] == subElems[i]) { // compare from right to left 671 ; 672 } 673 if (i < 0) return to - subsize; // found 674 to--; 675 } 676 return -1; // not found 677 } 678 679 /** 680 * Removes the elements in the range <code>[from..to)</code>. Shifts any 681 * subsequent elements to the left. Keeps the current capacity. 682 * Note: To remove a single element use <code>remove(index, index+1)</code>. 683 * To remove all elements use <code>remove(0, list.size())</code>. 684 * 685 * @param from 686 * the index of the first element to removed (inclusive). 687 * @param to 688 * the index of the last element to removed (exclusive). 689 * @throws IndexOutOfBoundsException 690 * if indexes are out of range 691 */ 692 public void remove(int from, int to) { 693 shrinkOrExpand(from, to, 0); 694 // equally correct alternative impl: replace(from, to, 0, 0); 695 } 696 697 /** 698 * Removes from the receiver all elements that are contained in the 699 * specified other list. 700 * <p> 701 * Example: <code>[0,1,2,2,3,3,0].removeAll([2,1]) --> [0,3,3,0]</code> 702 * 703 * @param other 704 * the other list to test against (remains unmodified by this method). 705 * @return <code>true</code> if the receiver changed as a result of the 706 * call. 707 */ 708 public boolean removeAll(ArrayByteList other) { 709 // efficient implementation: O(N) 710 if (size == 0 || other.size() == 0) return false; //nothing to do 711 712 BitSet bitSet = new BitSet(256); 713 for (int i = 0; i < other.size; i++) { 714 bitSet.set(128 + other.elements[i]); 715 } 716 717 int j = 0; 718 for (int i = 0; i < size; i++) { 719 if (! bitSet.get(128 + elements[i])) { 720 elements[j++] = elements[i]; 721 } 722 } 723 724 boolean modified = (j != size); 725 size = j; 726 return modified; 727 } 728 729 /** 730 * The powerful work horse for all add/insert/replace/remove methods. 731 * One powerful efficient method does it all :-) 732 */ 733 private void shrinkOrExpand(int from, int to, int replacementSize) { 734 checkRange(from, to); 735 int diff = replacementSize - (to - from); 736 if (diff != 0) { 737 ensureCapacity(size + diff); 738 if (size - to > 0) { // check is for performance only (arraycopy is native method) 739 // diff > 0 shifts right, diff < 0 shifts left 740 System.arraycopy(elements, to, elements, to + diff, size - to); 741 } 742 size += diff; 743 } 744 } 745 746 /** 747 * Replaces all elements in the range <code>[from..to)</code> with the 748 * elements <code>replacement[offset..offset+length)</code>. The replacement can have any length. 749 * Increases (or decreases) the receiver's size by <code>length - (to - from)</code>. 750 * Use <code>from==to</code> to perform pure insertion. 751 * 752 * @param from the index of the first element to replace (inclusive) 753 * @param to the index of the last element to replace (exclusive). 754 * @param replacement the elements to replace the replaced elements 755 * @param offset the offset of the first replacing element (inclusive) 756 * @param length the number of replacing elements 757 * @throws IndexOutOfBoundsException if indexes are out of range. 758 */ 759 public void replace(int from, int to, byte[] replacement, int offset, int length) { 760 if (offset < 0 || length < 0 || offset + length > replacement.length) 761 throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", replacement.length: " + replacement.length); 762 shrinkOrExpand(from, to, length); 763 System.arraycopy(replacement, offset, this.elements, from, length); 764 } 765 766 /** 767 * Replaces all elements in the range <code>[from..to)</code> with the given replacement. 768 * The replacement can have any length. 769 * Increases (or decreases) the receiver's size by <code>replacement.size - (to - from)</code>. 770 * Use <code>from==to</code> to perform pure insertion. Examples: 771 * <pre> 772 * [a,b,c,d,e].replace(1,4, [x,y]) --> [a,x,y,e] 773 * [a,b].replace(1,1, [w,x,y,z]) --> [a,w,x,y,z,b] 774 * </pre> 775 * 776 * @param from the index of the first element to replace (inclusive) 777 * @param to the index of the last element to replace (exclusive). 778 * @param replacement the elements to replace the replaced elements 779 * @throws IndexOutOfBoundsException if indexes are out of range. 780 */ 781 public void replace(int from, int to, ArrayByteList replacement) { 782 shrinkOrExpand(from, to, replacement.size); 783 System.arraycopy(replacement.elements, 0, this.elements, from, replacement.size); 784 } 785 786 /** 787 * Replaces all elements in the range <code>[from..to)</code> with the given replacement. 788 * The replacement consists of 789 * <code>replacement[replacement.position() .. replacement.position() + replacementSize)</code>. 790 * Increases (or decreases) the receiver's size by <code>replacementSize - (to - from)</code>. 791 * Use <code>from==to</code> to perform pure insertion. Examples: 792 * <pre> 793 * [a,b,c,d,e].replace(1,4, [x,y], 2) --> [a,x,y,e] 794 * [a,b].replace(1,1, [w,x,y,z], 4) --> [a,w,x,y,z,b] 795 * </pre> 796 * There must hold: <code>0 < replacementSize <= replacement.remaining()</code>. 797 * 798 * @param from the index of the first element to replace (inclusive) 799 * @param to the index of the last element to replace (exclusive). 800 * @param replacement the elements to replace the replaced elements 801 * @param replacementSize the number of replacing elements 802 * @throws IndexOutOfBoundsException if indexes are out of range. 803 */ 804 public void replace(int from, int to, ByteBuffer replacement, int replacementSize) { 805 if (replacementSize < 0 || replacementSize > replacement.remaining()) 806 throw new IndexOutOfBoundsException("replacementSize: " + replacementSize); 807 shrinkOrExpand(from, to, replacementSize); 808 replacement.get(this.elements, from, replacementSize); 809 } 810 811 /** 812 * Replaces all elements in the range <code>[from..to)</code> with the given replacement. 813 * The replacement can have any length >= 0. 814 * Increases (or decreases) the receiver's size by <code>replacementSize - (to - from)</code>. 815 * Use <code>from==to</code> to perform pure insertion. Examples: 816 * <pre> 817 * [a,b,c,d,e].replace(1,4,x,4) --> [a,x,x,x,x,e] 818 * [a,b,c,d,e].replace(0,0,x,4) --> [x,x,x,x,a,b,c,d,e] 819 * </pre> 820 * 821 * @param from the index of the first element to replace (inclusive) 822 * @param to the index of the last element to replace (exclusive). 823 * @param replacement the elements to replace the replaced elements 824 * @param replacementSize the number of times <code>replacement</code> is to replace the replaced elements 825 * @throws IndexOutOfBoundsException if indexes are out of range. 826 */ 827 public void replace(int from, int to, byte replacement, int replacementSize) { 828 checkSize(replacementSize); 829 shrinkOrExpand(from, to, replacementSize); 830 while (replacementSize-- > 0) elements[from++] = replacement; 831 //java.util.Arrays.fill(this.elements, from, from + replacementSize, replacement); 832 } 833 834 /** 835 * Retains (keeps) only the elements in the receiver that are contained in 836 * the specified other list. In other words, removes from the receiver all 837 * of its elements that are not contained in the specified other list. 838 * <p> 839 * Example: <code>[0,1,2,2,3,1].retainAll([2,1]) --> [1,2,2,1]</code> 840 * <p> 841 * An efficient <i>set intersection</i> can be computed along the following lines: 842 * <pre> 843 * list1.sort(true); 844 * list2.sort(true); 845 * list1.retainAll(list2); 846 * System.out.println("list1.retainAll(list2) = " + list1); 847 * // as a convenient byproduct we now know if list2 is a SUBSET of list1: 848 * System.out.println("list1.containsAll(list2) = " + (list1.size() == list2.size())); 849 * </pre> 850 * 851 * @param other 852 * the other list to test against (remains unmodified by this method). 853 * @return <code>true</code> if the receiver changed as a result of the 854 * call. 855 */ 856 public boolean retainAll(ArrayByteList other) { 857 // efficient implementation: O(N) 858 if (size == 0) return false; 859 if (other.size() == 0) { 860 size = 0; 861 return true; 862 } 863 864 BitSet bitSet = new BitSet(256); 865 for (int i = 0; i < other.size; i++) { 866 bitSet.set(128 + other.elements[i]); 867 } 868 869 int j = 0; 870 for (int i = 0; i < size; i++) { 871 if (bitSet.get(128 + elements[i])) 872 elements[j++] = elements[i]; 873 } 874 875 boolean modified = (j != size); 876 size = j; 877 return modified; 878 } 879 880 /** 881 * Rotates (shifts) the elements in the range <code>[from..to)</code> by 882 * the specified distance. After calling this method, the element at index 883 * <code>i</code> will be the element previously at index 884 * <code>(i - distance)</code> mod <code>to-from</code>, for all values 885 * of <code>i</code> between <code>from</code> (inclusive) and 886 * <code>to</code>, exclusive. (This method has no effect on the size of 887 * the list.) Examples: 888 * 889 * <pre> 890 * [a, b, c, d, e].rotate(0, 5, 1) --> [e, a, b, c, d] 891 * [a, b, c, d, e].rotate(0, 5, 2) --> [d, e, a, b, c] 892 * [a, b, c, d, e].rotate(1, 4, -1) --> [a, c, d, b, e] 893 * </pre> 894 * 895 * <p> 896 * To move elements rightwards, use a positive shift distance. To move 897 * elements leftwards, use a negative shift distance. 898 * <p> 899 * Note that this method can usefully be applied to sublists to move one or 900 * more elements within a list while preserving the order of the remaining 901 * elements. 902 * <p> 903 * This implementation exchanges the first element into the location it 904 * should go, and then repeatedly exchanges the displaced element into the 905 * location it should go until a displaced element is swapped into the first 906 * element. If necessary, the process is repeated on the second and 907 * successive elements, until the rotation is complete. This algorithm is 908 * efficient: Time complexity is linear O(to-from), space complexity is 909 * constant O(1). 910 * 911 * @param from 912 * the index of the first element to rotate (inclusive) 913 * @param to 914 * the index of the last element to rotate (exclusive). 915 * @param distance 916 * the distance to rotate the list. There are no constraints on 917 * this value; for example it may be zero, negative, or greater than 918 * <code>to-from</code>. 919 * @throws IndexOutOfBoundsException 920 * if indexes are out of range. 921 * @see java.util.Collections#rotate(java.util.List, int) 922 */ 923 public void rotate(int from, int to, int distance) { 924 checkRange(from, to); 925 int length = to - from; 926 if (length == 0) return; 927 distance = distance % length; 928 if (distance < 0) distance += length; 929 if (distance == 0) return; 930 931 byte[] elems = elements; 932 for (int nMoved = 0; nMoved != length; from++) { 933 byte displaced = elems[from]; 934 int i = from; 935 do { 936 i += distance; 937 if (i >= to) i -= length; 938 939 byte tmp = elems[i]; 940 elems[i] = displaced; 941 displaced = tmp; 942 943 nMoved++; 944 } while (i != from); 945 } 946 } 947 948 /** 949 * Replaces the element at the specified index with the specified 950 * element. 951 * 952 * @param index 953 * index of element to replace. 954 * @param element 955 * element to be stored at the specified index. 956 * @throws IndexOutOfBoundsException 957 * if index is out of range. 958 */ 959 public void set(int index, byte element) { 960 checkIndex(index); 961 elements[index] = element; 962 // equally correct alternative impl: replace(index, index+1, element, 1); 963 } 964 965 /** 966 * Returns the number of contained elements. 967 * 968 * @return the number of elements contained in the receiver. 969 */ 970 public int size() { 971 return size; 972 } 973 974 /** 975 * Sorts the elements into ascending numerical order. For mathematical set 976 * operations, optionally removes duplicate elements before returning. 977 * Examples: 978 * <pre> 979 * [3,2,2,1].sort(false) --> [1,2,2,3] 980 * [3,2,2,1].sort(true) --> [1,2,3] 981 * </pre> 982 * 983 * @param removeDuplicates remove duplicate elements or keep them? 984 */ 985 public void sort(boolean removeDuplicates) { 986 if (size <= 60) { // heuristic threshold according to benchmarks (theory: N*logN = 2*256) 987 java.util.Arrays.sort(elements, 0, size); 988 if (removeDuplicates) removeDuplicates(); 989 } 990 else { 991 countSort(removeDuplicates); 992 } 993 } 994 995 /** efficient sort implementation: O(N) via frequency counts */ 996 private void countSort(boolean removeDuplicates) { 997 final int min = Byte.MIN_VALUE; 998 final int max = Byte.MAX_VALUE; 999 int[] counts = new int[max - min + 1]; // could use BitSet if removeDuplicates 1000 for (int i = size; --i >= 0; ) { 1001 counts[elements[i] - min]++; 1002 } 1003 1004 int j = 0; 1005 for (int i = min; i <= max; i++) { 1006 int k = counts[i - min]; 1007 if (removeDuplicates && k > 1) k = 1; 1008 while (--k >= 0) { 1009 elements[j++] = (byte) i; 1010 } 1011 } 1012 size = j; 1013 } 1014 1015 /** 1016 * [1,2,2,3,3,3] --> [1,2,3] 1017 * Assertion: list must be sorted prior to calling this method 1018 */ 1019 private void removeDuplicates() { 1020 int i = 0; 1021 int j = 0; 1022 while (j < size) { 1023 byte elem = elements[j++]; 1024 elements[i++] = elem; 1025 while (j < size && elements[j] == elem) j++; // skip duplicates 1026 } 1027 size = i; 1028 } 1029 1030 /** Small helper method eliminating redundancy. */ 1031 private byte[] subArray(int from, int length, int capacity) { 1032 byte[] subArray = new byte[capacity]; 1033 System.arraycopy(elements, from, subArray, 0, length); 1034 return subArray; 1035 } 1036 1037 /** 1038 * Constructs and returns a new list containing a copy of the elements in 1039 * the range <code>[from..to)</code>. 1040 * 1041 * @param from 1042 * the index of the first element (inclusive). 1043 * @param to 1044 * the index of the last element (exclusive). 1045 * @return a new list 1046 * @throws IndexOutOfBoundsException 1047 * if indexes are out of range 1048 */ 1049 public ArrayByteList subList(int from, int to) { 1050 checkRange(from, to); 1051 return new ArrayByteList(subArray(from, to - from, to - from)); 1052 } 1053 1054 /** 1055 * Returns a copied array of bytes containing all elements; the returned 1056 * array has length = this.size(). 1057 */ 1058 public byte[] toArray() { 1059 return subArray(0, size, size); 1060 } 1061 1062 /** 1063 * Returns a string representation, containing the numeric String 1064 * representation of each element. 1065 */ 1066 public String toString() { 1067 //return toList().toString(); 1068 StringBuffer buf = new StringBuffer(4*size); 1069 buf.append("["); 1070 for (int i = 0; i < size; i++) { 1071 buf.append(elements[i]); 1072 if (i < size-1) buf.append(", "); 1073 } 1074 buf.append("]"); 1075 return buf.toString(); 1076 } 1077 1078 /** 1079 * Returns a decoded string representation of all elements. 1080 * 1081 * @param charset 1082 * the charset to convert with (e.g. <code>Charset.forName("US-ASCII")</code>, 1083 * <code>Charset.forName("ISO-8859-1")</code>). 1084 * If <code>null</code> uses <code>Charset.forName("UTF-8")</code> as the default charset. 1085 */ 1086 public String toString(Charset charset) { 1087 return toString(0, size, charset); 1088 } 1089 1090 /** 1091 * Returns a decoded string representation of the bytes in the 1092 * given range <code>[from..to)</code>. 1093 * 1094 * @param from 1095 * the index of the first element (inclusive). 1096 * @param to 1097 * the index of the last element (exclusive). 1098 * @param charset 1099 * the charset to convert with (e.g. <code>Charset.forName("US-ASCII")</code>, 1100 * <code>Charset.forName("ISO-8859-1")</code>). 1101 * If <code>null</code> uses <code>Charset.forName("UTF-8")</code> as the default charset. 1102 * @throws IndexOutOfBoundsException 1103 * if indexes are out of range 1104 */ 1105 public String toString(int from, int to, Charset charset) { 1106 checkRange(from, to); 1107 return getCharset(charset).decode(ByteBuffer.wrap(this.elements, from, to-from)).toString(); 1108 } 1109 1110 /** 1111 * Trims the capacity of the receiver to be the receiver's current size; 1112 * Releases any superfluos internal memory. An application can use this 1113 * operation to minimize the storage of the receiver. 1114 */ 1115 public void trimToSize() { 1116 if (elements.length > size) { 1117 elements = subArray(0, size, size); 1118 } 1119 } 1120 1121 /** 1122 * Checks if the given index is in range. 1123 */ 1124 private void checkIndex(int index) { 1125 if (index >= size || index < 0) 1126 throw new IndexOutOfBoundsException("index: " + index 1127 + ", size: " + size); 1128 } 1129 1130 /** 1131 * Checks if the given range is within the contained array's bounds. 1132 */ 1133 private void checkRange(int from, int to) { 1134 if (from < 0 || from > to || to > size) 1135 throw new IndexOutOfBoundsException("from: " + from + ", to: " 1136 + to + ", size: " + size); 1137 } 1138 1139 /** 1140 * Checks if the given size is within bounds. 1141 */ 1142 private void checkSize(int newSize) { 1143 if (newSize < 0) 1144 throw new IndexOutOfBoundsException("newSize: " + newSize); 1145 } 1146 1147 /** 1148 * Returns the default charset if no charset is specified. 1149 */ 1150 private static Charset getCharset(Charset charset) { 1151 return charset == null ? DEFAULT_CHARSET : charset; 1152 } 1153 1154 /** efficient Serializable support. Example: 1155 ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream("/tmp/test")); 1156 out.writeObject(new ArrayByteList("hello world", null)); 1157 out.close(); 1158 1159 ObjectInputStream in = new ObjectInputStream(new FileInputStream("/tmp/test")); 1160 ArrayByteList list = (ArrayByteList) in.readObject(); 1161 in.close(); 1162 System.out.println(list.toString(null)); 1163 */ 1164 private void writeObject(java.io.ObjectOutputStream out) throws IOException { 1165 out.defaultWriteObject(); 1166 out.writeInt(elements.length); 1167 out.write(elements, 0, size); 1168 } 1169 1170 /** efficient Serializable support */ 1171 private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundException { 1172 in.defaultReadObject(); 1173 elements = new byte[in.readInt()]; 1174 in.readFully(elements, 0, size); 1175 } 1176 1177 // **************************************************************************** 1178 // following are some methods not deemed important enough or complex enough 1179 // to warrant interface bloat: 1180 // **************************************************************************** 1181 1182 // /** 1183 // * Appends the specified elements to the end of this list. 1184 // * <p> 1185 // * If you need to append <code>elems[from..to)</code>, use 1186 // * <code>list.add(new ArrayByteList(elems).subList(from, to))</code> 1187 // * or <code>list.add(ByteBuffer.wrap(elems, from, to-from))</code> 1188 // * or similar. 1189 // * 1190 // * @param elems 1191 // * elements to be appended. 1192 // * @return <code>this</code> (for chaining convenience only) 1193 // */ 1194 // public ArrayByteList add(byte[] elems) { 1195 // replace(size, size, elems); 1196 // return this; 1197 // } 1198 1199 // /** 1200 // * Lexicographically compares this object with the specified other object for order. Returns a 1201 // * negative integer, zero, or a positive integer as this object is less 1202 // * than, equal to, or greater than the specified other object. 1203 // * <p> 1204 // * If a negative integer <code>i</code> is returned, the index of the 1205 // * first differing element is <code>-(i+1)</code>. If a positive integer 1206 // * <code>i</code> is returned, the index of the first differing element is 1207 // * <code>i-1</code>. 1208 // * 1209 // * @param otherObj 1210 // * the Object to be compared. 1211 // * @return a negative integer, zero, or a positive integer as this object is 1212 // * less than, equal to, or greater than the specified other object. 1213 // * 1214 // * @throws ClassCastException 1215 // * if the specified object's type prevents it from being 1216 // * compared to this Object. 1217 // * @see Comparable 1218 // * @see String#compareTo(String) 1219 // */ 1220 // public int compareTo(Object otherObj) { 1221 // if (this == otherObj) return 0; 1222 // if (otherObj == null) throw new NullPointerException(); 1223 // if (!(otherObj instanceof ArrayByteList)) throw new ClassCastException(); 1224 // ArrayByteList other = (ArrayByteList) otherObj; 1225 // 1226 // int minSize = Math.min(size, other.size); 1227 // byte[] elems = elements; 1228 // byte[] otherElems = other.elements; 1229 // int i = 0; 1230 // for (; i < minSize; i++) { 1231 // if (elems[i] < otherElems[i]) return (-i) - 1; // this < other 1232 // else if (elems[i] > otherElems[i]) return i + 1; // this > other 1233 // } 1234 // if (other.size > minSize) return (-i) - 1; // this < other 1235 // if (size > minSize) return i + 1; // this > other 1236 // return 0; // equal 1237 // } 1238 1239 // /** 1240 // * Inserts the specified element before the specified index. Shifts the 1241 // * element currently at that index (if any) and any subsequent elements 1242 // * to the right. This is equivalent to <code>replace(index, index, elem, 1)</code>. 1243 // * 1244 // * @param index 1245 // * index before which the specified element is to be inserted 1246 // * @param elem 1247 // * element to insert. 1248 // * @throws IndexOutOfBoundsException if index is out of range. 1249 // */ 1250 // private void insert(int index, byte elem) { 1251 // replace(index, index, elem, 1); 1252 // } 1253 // 1254 // /** 1255 // * Inserts the specified elements before the specified index. Shifts the 1256 // * element currently at that index (if any) and any subsequent elements 1257 // * to the right. 1258 // * 1259 // * @param index 1260 // * index before which the specified elements are to be inserted 1261 // * @param elems 1262 // * elements to insert. 1263 // * @throws IndexOutOfBoundsException if index is out of range. 1264 // */ 1265 // private void insert(int index, byte[] elems) { 1266 // replace(index, index, elems); 1267 // } 1268 // 1269 // /** 1270 // * Inserts the specified elements before the specified index. Shifts the 1271 // * element currently at that index (if any) and any subsequent elements 1272 // * to the right. 1273 // * 1274 // * @param index 1275 // * index before which the specified elements are to be inserted 1276 // * @param elems 1277 // * elements to insert. 1278 // * @throws IndexOutOfBoundsException if index is out of range. 1279 // */ 1280 // private void insert(int index, ArrayByteList elems) { 1281 // replace(index, index, elems); 1282 // } 1283 // 1284 // /** 1285 // * Inserts the remaining buffer elements before the specified index. 1286 // * Shifts the element currently at that index (if any) and any subsequent 1287 // * elements to the right. 1288 // * 1289 // * @param index 1290 // * index before which the specified elements are to be inserted 1291 // * @param elems 1292 // * elements to insert. 1293 // * @throws IndexOutOfBoundsException if index is out of range. 1294 // */ 1295 // private void insert(int index, ByteBuffer elems) { 1296 // replace(index, index, elems); 1297 // } 1298 1299 // /** 1300 // * Returns the index of the last occurrence of the specified element within 1301 // * the range <code>[from..to)</code>. Returns <code>-1</code> if the 1302 // * receiver does not contain such an element. 1303 // * 1304 // * @param from 1305 // * the leftmost search index, inclusive. 1306 // * @param to 1307 // * the rightmost search index, exclusive. 1308 // * @param elem 1309 // * element to search for. 1310 // * @return the index of the last occurrence of the element in the receiver; 1311 // * returns <code>-1</code> if the element is not found. 1312 // * @throws IndexOutOfBoundsException 1313 // * if indexes are out of range. 1314 // */ 1315 // public int lastIndexOf(int from, int to, byte elem) { 1316 // checkRange(from, to); 1317 // byte[] elems = elements; 1318 // for (int i = to; --i >= from; ) { 1319 // if (elem == elems[i]) return i; //found 1320 // } 1321 // return -1; //not found 1322 // } 1323 1324 // /** 1325 // * Removes the element at the specified index. Shifts any subsequent 1326 // * elements to the left. Keeps the current capacity. 1327 // * 1328 // * @param index 1329 // * the index of the element to removed. 1330 // * @throws IndexOutOfBoundsException 1331 // * if index is out of range 1332 // */ 1333 // public void remove(int index) { 1334 // remove(index, index+1); 1335 // } 1336 1337 // /** 1338 // * Replaces all elements in the range <code>[from..to)</code> with the 1339 // * elements <code>replacement[offset..offset+length)</code>. The replacement can have any length. 1340 // * Increases (or decreases) the receiver's size by <code>length - (to - from)</code>. 1341 // * Use <code>from==to</code> to perform pure insertion. 1342 // * 1343 // * @param from the index of the first element to replace (inclusive) 1344 // * @param to the index of the last element to replace (exclusive). 1345 // * @param replacement the elements to replace the replaced elements 1346 // * @param offset the offset of the first replacing element (inclusive) 1347 // * @param length the number of replacing elements 1348 // * @throws IndexOutOfBoundsException if indexes are out of range. 1349 // */ 1350 // public void replace(int from, int to, byte[] replacement, int offset, int length) { 1351 // if (offset < 0 || length < 0 || offset + length > replacement.length) 1352 // throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", replacement.length: " + replacement.length); 1353 // //if (elements == replacement && length - (to - from) != 0) replacement = (byte[]) replacement.clone(); 1354 // shrinkOrExpand(from, to, length); 1355 // System.arraycopy(replacement, offset, this.elements, from, length); 1356 // } 1357 1358 // /** 1359 // * Reverses the order of elements in the range <code>[from..to)</code>. 1360 // * Last becomes first, second last becomes second first, and so on. 1361 // * <p> 1362 // * Example: <code>[a,b,c,d].reverse(0,4) --> [d,c,b,a]</code> 1363 // * 1364 // * @param from the index of the first element (inclusive) 1365 // * @param to the index of the last element (exclusive). 1366 // * @throws IndexOutOfBoundsException if indexes are out of range. 1367 // */ 1368 // public void reverse(int from, int to) { 1369 // checkRange(from, to); 1370 // byte[] elems = elements; 1371 // int middle = from + (to - from) / 2; 1372 // to--; 1373 // for ( ; from < middle; from++, to--) { // swap 1374 // byte tmp = elems[from]; 1375 // elems[from] = elems[to]; 1376 // elems[to] = tmp; 1377 // } 1378 // } 1379 1380 // /** 1381 // * Sets the size to the given new size, expanding the list capacity if 1382 // * necessary. 1383 // * <p> 1384 // * Capacity expansion introduces a new backing array. If the new 1385 // * size is greater than the current size the elements between the current 1386 // * size and the new size will become legally accessible but have undefined 1387 // * values. An application will typically want to set these elements to defined 1388 // * values immediately after this method returns. Note that 1389 // * <code>setSize(0)</code> effectively clears the list (as does 1390 // * <code>remove(0, list.size()</code>). 1391 // * 1392 // * @param newSize the new size. 1393 // * @return <code>this</code> (for chaining convenience only) 1394 // * @throws IndexOutOfBoundsException if new size is less than zero. 1395 // */ 1396 // public ArrayByteList setSize(int newSize) { 1397 // checkSize(newSize); 1398 // ensureCapacity(newSize); 1399 // // equivalent impl: shrinkOrExpand(0, size, newSize); 1400 // size = newSize; 1401 // return this; 1402 // } 1403 1404 // /** 1405 // * Returns a <code>java.util.ArrayList</code> containing a copy of all elements. 1406 // */ 1407 // public java.util.ArrayList toList() { 1408 // java.util.ArrayList list = new java.util.ArrayList(size); 1409 // for (int i = 0; i < size; i++) 1410 // list.add(new Byte(elements[i])); 1411 // return list; 1412 // } 1413 1414 // /** 1415 // * Creates and returns an unsynchronized input stream that reads from this 1416 // * SHARED backing byte list. Useful if legacy code requires adapting to a 1417 // * stream based interface. Note: This is much more efficient and 1418 // * straighforward than using a {@link java.io.ByteArrayInputStream}. 1419 // * <p> 1420 // * Reading from the stream increments an internal counter that keeps track 1421 // * of the next byte to be supplied by the stream's read method. Reading 1422 // * starts at list index 0; end-of-stream is reached on list index size(). 1423 // * Reading from the stream leaves the list unmodified (it does not remove 1424 // * elements). 1425 // * <p> 1426 // * Closing the stream has no effect. The stream's methods can be called 1427 // * after the stream has been closed without generating an IOException. In 1428 // * fact the stream implementation never ever throws an IOException. 1429 // * 1430 // * @return the stream 1431 // */ 1432 // public InputStream asInputStream() { 1433 // return new ListInputStream(); 1434 // } 1435 // 1436 // /** 1437 // * private class; implements/overrides methods of base stream class; 1438 // * well behaved even under weird interleaved list add() and/or remove(), 1439 // * but not under concurrent access, since unsynchronized. 1440 // */ 1441 // private class ListInputStream extends InputStream { 1442 // 1443 // private int pos = 0; 1444 // private int mark = 0; 1445 // 1446 // public int read() { 1447 // return pos < size ? (elements[pos++] & 0xff) : -1; 1448 // } 1449 // 1450 // public int read(byte b[], int off, int len) { 1451 // if (off < 0 || len < 0 || off + len > b.length) throw new IndexOutOfBoundsException(); 1452 // if (pos >= size) return -1; 1453 // if (pos + len > size) { 1454 // len = size - pos; 1455 // } 1456 // if (len <= 0) return 0; 1457 // System.arraycopy(elements, pos, b, off, len); 1458 // pos += len; 1459 // return len; 1460 // } 1461 // 1462 // public long skip(long n) { 1463 // if (pos + n > size) { 1464 // n = size - pos; 1465 // } 1466 // if (n < 0) return 0; 1467 // pos += n; 1468 // return n; 1469 // } 1470 // 1471 // public int available() { 1472 // return Math.max(0, size - pos); // safe even with list add() and/or remove() 1473 // } 1474 // 1475 // public boolean markSupported() { 1476 // return true; 1477 // } 1478 // 1479 // public void mark(int readlimit) { 1480 // mark = pos; 1481 // } 1482 // 1483 // public void reset() { 1484 // pos = mark; 1485 // } 1486 // 1487 // } 1488 1489 }