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 }