arraybytelist.java

sea是一个基于seda模式的实现。这个设计模式将系统分为很多stage。每个stage分布不同的任务（基于线程池）。通过任务流的方式提高系统的效率。

	 * <p>
	 * Writing to the stream means adding (appending) elements to the end of the
	 * (auto-expanding) backing list.
	 * <p>
	 * Closing the stream has no effect. The stream's methods can be called
	 * after the stream has been closed without generating an IOException. In
	 * fact the stream implementation never ever throws an IOException.
	 * <p>
	 * If your legacy code requires adapting to an {@link InputStream} instead, 
	 * simply use the non-copying {@link java.io.ByteArrayInputStream}, for example as in 
	 * <code>new java.io.ByteArrayInputStream(list.asArray(), 0, list.size())</code>.
	 * 
	 * @return the stream
	 */
	public OutputStream asOutputStream() {
		return new OutputStream() {			
			public void write(int b) {
				add((byte) b);
			}
			public void write(byte b[], int off, int len) {
				add(b, off, len);
			}
		};
	}
	
    /**
	 * Searches the list for the specified value using the binary search
	 * algorithm. The list <strong>must </strong> be sorted (as by the
	 * <code>sort</code> method) prior to making this call. If it is not sorted,
	 * the results are undefined. If the list contains multiple elements with
	 * the specified value, there is no guarantee which one will be found.
	 * 
	 * @param key
	 *            the value to be searched for.
	 * @return index of the search key, if it is contained in the list;
	 *         otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The
	 *         <i>insertion point </i> is defined as the point at which the key
	 *         would be inserted into the list: the index of the first element
	 *         greater than the key, or <code>list.size()</code>, if all elements
	 *         in the list are less than the specified key. Note that this
	 *         guarantees that the return value will be &gt;= 0 if and only if
	 *         the key is found.
	 * @see #sort(boolean)
	 */
	public int binarySearch(byte key) {
		int low = 0;
		int high = size - 1;

		while (low <= high) {
			int mid = (low + high) >> 1; // >> 1 is equivalent to divide by 2
			byte midVal = elements[mid];

			if (midVal < key)
				low = mid + 1;
			else if (midVal > key)
				high = mid - 1;
			else
				return mid; // key found
		}
		return -(low + 1); // key not found.
	}

    /**
	 * Removes all elements but keeps the current capacity; Afterwards
	 * <code>size()</code> will yield zero.
	 * 
	 * @return <code>this</code> (for chaining convenience only)
	 */
	public ArrayByteList clear() {
		size = 0;
		return this;
		// equally correct alternative impl: remove(0, size);
	}
		
	/**
	 * Constructs and returns a new list that is a deep copy of the receiver.
	 * 
	 * @return a deep copy of the receiver.
	 */
	public ArrayByteList copy() {
		return new ArrayByteList(toArray());
	}

	/**
	 * Compares the specified Object with the receiver. Returns true if and only
	 * if the specified Object is also a list of the same type, both Lists
	 * have the same size, and all corresponding pairs of elements in the two
	 * Lists are identical. In other words, two Lists are defined to be equal if
	 * they contain the same elements in the same order.
	 * 
	 * @param otherObj
	 *            the Object to be compared for equality with the receiver.
	 * @return true if the specified Object is equal to the receiver.
	 */
	public boolean equals(Object otherObj) { 
		if (this == otherObj) return true;
		if (!(otherObj instanceof ArrayByteList)) return false;
		ArrayByteList other = (ArrayByteList) otherObj;
		if (size != other.size) return false;
		return indexOf(0, size, other) >= 0;
	}

	/**
	 * Ensures that the receiver can hold at least the specified number of
	 * elements without needing to allocate new internal memory. If necessary,
	 * allocates new internal memory and increases the capacity of the receiver.
	 * 
	 * @param minCapacity
	 *            the desired minimum capacity.
	 */
	public void ensureCapacity(int minCapacity) {
		if (minCapacity > elements.length) {
			int newCapacity = Math.max(minCapacity, (elements.length * 3) / 2 + 1);
			elements = subArray(0, size, newCapacity);
		}
	}

	/**
	 * Finds all matching sublists in the range <code>[from..to)</code> and
	 * replaces them with the given replacement. A sublist matches if it is
	 * equal to the given pattern. The pattern must have a size greater than
	 * zero. The replacement can have any size. 
	 * Examples: 
	 * <pre>
	 * [a,b,c,d,b,c].findReplace(0,6, [b,c], [x,y,z]) --> [a,x,y,z,d,x,y,z]
	 * [a,b,c,d,b,c].findReplace(0,6, [b,c], []) --> [a,d]
	 * </pre>
	 * 
	 * @param from the index of the first element to search (inclusive)
	 * @param to   the index of the last element to search (exclusive).
	 * @param pattern the sublist to search for
	 * @param replacement the elements to replace the found sublists
	 * @return the number of sublists found matching the pattern
	 * @throws IndexOutOfBoundsException if indexes are out of range.
	 * @throws IllegalArgumentException if pattern.size() == 0.
	 */
	public int findReplace(int from, int to, ArrayByteList pattern, ArrayByteList replacement) {
		checkRange(from, to);
		if (pattern.size == 0) throw new IllegalArgumentException("pattern size must be > 0");
		int n = 0;
		while ((from = indexOf(from, to, pattern)) >= 0) {
			if (pattern != replacement) { // do more than just counting matches
				replace(from, from + pattern.size, replacement);
				to += replacement.size - pattern.size;
			}
			from += replacement.size;
			n++;
		}
		return n;
	}
	
	/**
	 * Returns the element at the specified index.
	 * 
	 * @param index
	 *            index of element to return.
	 * @throws IndexOutOfBoundsException if index is out of range.
	 */
	public byte get(int index) {
		checkIndex(index);
		return elements[index];
	}

	/**
	 * Returns the hash code value for this list. The algorithm ensures that
	 * <code>list1.equals(list2)</code> implies that
	 * <code>list1.hashCode()==list2.hashCode()</code> for any two lists,
	 * <code>list1</code> and <code>list2</code>, as required by the general
	 * contract of <code>Object.hashCode</code>.
	 * <p>
	 * Warning: run time complexity is O(N)
	 * 
	 * @return the hash code value for this list.
	 * @see Object#hashCode()
	 * @see Object#equals(Object)
	 * @see #equals(Object)
	 * @see java.util.List#hashCode()
	 */
	public int hashCode() {
		int hashCode = 1;
		byte[] elems = elements;
		for (int i = size; --i >= 0; )
			hashCode = 31*hashCode + elems[i];
		return hashCode;
	}

	/**
	 * Returns the index of the first occurrence of the given sublist within 
	 * the range <code>this[from..to)</code>.
	 * Returns <code>-1</code> if the receiver does not contain such a sublist.
	 * Examples:
	 * <pre> 
	 * [a,b,c,d,e,b,c,d].indexOf(0,8, [b,c,d]) --> 1
	 * [a,b,c,d,e].indexOf(0,5, [b,c,d]) --> 1
	 * [a,b,c,d,e].indexOf(1,4, [b,c,d]) --> 1
	 * [a,b,c,d,e].indexOf(0,5, [x,y])   --> -1
	 * [a,b,c,d,e].indexOf(0,3, [b,c,d]) --> -1
	 * [a].indexOf(0,1, [a,b,c]) --> -1
	 * [a,b,c,d,e].indexOf(2,3, []) --> 2 // empty sublist is always found
	 * [].indexOf(0,0, []) --> 0
	 * </pre>
	 * 
	 * @param from
	 *            the leftmost search index within the receiver, inclusive.
	 * @param to
	 *            the rightmost search index within the receiver, exclusive.
	 * @param subList
	 *            the sublist to search for.
	 * @return the index of the first occurrence of the sublist in the receiver;
	 *         returns <code>-1</code> if the sublist is not found.
	 * @throws IndexOutOfBoundsException
	 *             if indexes are out of range
	 */
	public int indexOf(int from, int to, ArrayByteList subList) {
		// brute-force algorithm, but very efficiently implemented
		checkRange(from, to);
		byte[] elems = elements;
		byte[] subElems = subList.elements;
		
		int subsize = subList.size;
		to -= subsize;
		while (from <= to) {
			int i = subsize;
			int j = from + subsize;
			while (--i >= 0 && elems[--j] == subElems[i]) { // compare from right to left
				;
			}
			if (i < 0) return from; // found
			from++;
		}
		return -1; // not found
	}
	
	/**
	 * Returns the index of the first occurrence of the specified element within
	 * the range <code>[from..to)</code>. Returns <code>-1</code> if the
	 * receiver does not contain such an element.
	 * 
	 * @param from
	 *            the leftmost search index, inclusive.
	 * @param to
	 *            the rightmost search index, exclusive.
	 * @param elem
	 *            element to search for.
	 * @return the index of the first occurrence of the element in the receiver;
	 *         returns <code>-1</code> if the element is not found.
	 * @throws IndexOutOfBoundsException
	 *             if indexes are out of range
	 */
	public int indexOf(int from, int to, byte elem) {
		checkRange(from, to);
		byte[] elems = elements;
		for (int i = from; i < to; i++) {
			if (elem == elems[i]) return i; //found
		}
		return -1; //not found
	}
	
	/**
	 * Returns the index of the last occurrence of the given sublist within 
	 * the range <code>this[from..to)</code>.
	 * Returns <code>-1</code> if the receiver does not contain such a sublist.
	 * Examples:
	 * <pre> 
	 * [a,b,c,d,e,b,c,d].lastIndexOf(0,8, [b,c,d]) --> 5
	 * [a,b,c,d,e].lastIndexOf(0,5, [b,c,d]) --> 1
	 * [a,b,c,d,e].lastIndexOf(1,4, [b,c,d]) --> 1
	 * [a,b,c,d,e].lastIndexOf(0,5, [x,y])   --> -1
	 * [a,b,c,d,e].lastIndexOf(0,3, [b,c,d]) --> -1
	 * [a].lastIndexOf(0,1, [a,b,c]) --> -1
	 * [a,b,c,d,e].lastIndexOf(2,3, []) --> 3 // empty sublist is always found
	 * [].lastIndexOf(0,0, []) --> 0
	 * </pre>
	 * 
	 * @param from
	 *            the leftmost search index within the receiver, inclusive.
	 * @param to
	 *            the rightmost search index within the receiver, exclusive.
	 * @param subList
	 *            the sublist to search for.
	 * @return the index of the last occurrence of the sublist in the receiver;
	 *         returns <code>-1</code> if the sublist is not found.
	 * @throws IndexOutOfBoundsException
	 *             if indexes are out of range
	 */
	public int lastIndexOf(int from, int to, ArrayByteList subList) {
		// brute-force algorithm, but very efficiently implemented
		checkRange(from, to);
		byte[] elems = elements;
		byte[] subElems = subList.elements;
		
		int subsize = subList.size;
		from += subsize;
		while (from <= to) {
			int i = subsize;
			int j = to;
			while (--i >= 0 && elems[--j] == subElems[i]) { // compare from right to left
				;
			}
			if (i < 0) return to - subsize; // found
			to--;
		}
		return -1; // not found
	}
	
	/**
	 * Removes the elements in the range <code>[from..to)</code>. Shifts any
	 * subsequent elements to the left.  Keeps the current capacity.
	 * Note: To remove a single element use <code>remove(index, index+1)</code>.
	 * To remove all elements use <code>remove(0, list.size())</code>.
	 * 
	 * @param from
	 *            the index of the first element to removed (inclusive).
	 * @param to
	 *            the index of the last element to removed (exclusive).
	 * @throws IndexOutOfBoundsException
	 *             if indexes are out of range
	 */
	public void remove(int from, int to) {
		shrinkOrExpand(from, to, 0);
		// equally correct alternative impl: replace(from, to, 0, 0); 
	}
	
	/**
	 * Removes from the receiver all elements that are contained in the
	 * specified other list.
	 * <p>
	 * Example: <code>[0,1,2,2,3,3,0].removeAll([2,1]) --> [0,3,3,0]</code>
	 * 
	 * @param other
	 *            the other list to test against (remains unmodified by this method).
	 * @return <code>true</code> if the receiver changed as a result of the
	 *         call.
	 */
	public boolean removeAll(ArrayByteList other) {
		// efficient implementation: O(N)
		if (size == 0 || other.size() == 0) return false; //nothing to do
		
		BitSet bitSet = new BitSet(256);
		for (int i = 0; i < other.size; i++) {
			bitSet.set(128 + other.elements[i]);
		}
		
		int j = 0;
		for (int i = 0; i < size; i++) {
			if (! bitSet.get(128 + elements[i])) {
				elements[j++] = elements[i];
			}
		}

		boolean modified = (j != size);
		size = j;
		return modified;
	}

	/**
	 * The powerful work horse for all add/insert/replace/remove methods.
	 * One powerful efficient method does it all :-)
	 */
	private void shrinkOrExpand(int from, int to, int replacementSize) {
		checkRange(from, to);
		int diff = replacementSize - (to - from);
		if (diff != 0) {
			ensureCapacity(size + diff);
			if (size - to > 0) { // check is for performance only (arraycopy is native method)
				// diff > 0 shifts right, diff < 0 shifts left
				System.arraycopy(elements, to, elements, to + diff, size - to);
			}
			size += diff;
		}
	}
	
	/**