arraybytelist.java

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

	 * Replaces all elements in the range <code>[from..to)</code> with the
	 * elements <code>replacement[offset..offset+length)</code>. The replacement can have any length.
	 * Increases (or decreases) the receiver's size by <code>length - (to - from)</code>.
	 * Use <code>from==to</code> to perform pure insertion.
	 * 
	 * @param from the index of the first element to replace (inclusive)
	 * @param to   the index of the last element to replace (exclusive).
	 * @param replacement the elements to replace the replaced elements
	 * @param offset the offset of the first replacing element (inclusive)
	 * @param length the number of replacing elements
	 * @throws IndexOutOfBoundsException if indexes are out of range.
	 */
	public void replace(int from, int to, byte[] replacement, int offset, int length) {
		if (offset < 0 || length < 0 || offset + length > replacement.length) 
			throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", replacement.length: " + replacement.length);
		shrinkOrExpand(from, to, length);
		System.arraycopy(replacement, offset, this.elements, from, length);
	}
	
	/**
	 * Replaces all elements in the range <code>[from..to)</code> with the given replacement.
	 * The replacement can have any length.
	 * Increases (or decreases) the receiver's size by <code>replacement.size - (to - from)</code>.
	 * Use <code>from==to</code> to perform pure insertion. Examples:
	 * <pre>
	 * [a,b,c,d,e].replace(1,4, [x,y]) --> [a,x,y,e]
	 * [a,b].replace(1,1, [w,x,y,z]) --> [a,w,x,y,z,b]
	 * </pre>
	 * 
	 * @param from the index of the first element to replace (inclusive)
	 * @param to   the index of the last element to replace (exclusive).
	 * @param replacement the elements to replace the replaced elements
	 * @throws IndexOutOfBoundsException if indexes are out of range.
	 */
	public void replace(int from, int to, ArrayByteList replacement) {
		shrinkOrExpand(from, to, replacement.size);
		System.arraycopy(replacement.elements, 0, this.elements, from, replacement.size);
	}
	
	/**
	 * Replaces all elements in the range <code>[from..to)</code> with the given replacement.
	 * The replacement consists of 
	 * <code>replacement[replacement.position() .. replacement.position() + replacementSize)</code>.
	 * Increases (or decreases) the receiver's size by <code>replacementSize - (to - from)</code>.
	 * Use <code>from==to</code> to perform pure insertion. Examples:
	 * <pre>
	 * [a,b,c,d,e].replace(1,4, [x,y], 2) --> [a,x,y,e]
	 * [a,b].replace(1,1, [w,x,y,z], 4) --> [a,w,x,y,z,b]
	 * </pre>
	 * There must hold: <code>0 &lt; replacementSize &lt;= replacement.remaining()</code>. 
	 * 
	 * @param from the index of the first element to replace (inclusive)
	 * @param to   the index of the last element to replace (exclusive).
	 * @param replacement the elements to replace the replaced elements
	 * @param replacementSize the number of replacing elements
	 * @throws IndexOutOfBoundsException if indexes are out of range.
	 */
	public void replace(int from, int to, ByteBuffer replacement, int replacementSize) {
		if (replacementSize < 0 || replacementSize > replacement.remaining()) 
			throw new IndexOutOfBoundsException("replacementSize: " + replacementSize);
		shrinkOrExpand(from, to, replacementSize);
		replacement.get(this.elements, from, replacementSize);
	}
	
	/**
	 * Replaces all elements in the range <code>[from..to)</code> with the given replacement.
	 * The replacement can have any length &gt;= 0.
	 * Increases (or decreases) the receiver's size by <code>replacementSize - (to - from)</code>.
	 * Use <code>from==to</code> to perform pure insertion. Examples:
	 * <pre>
	 * [a,b,c,d,e].replace(1,4,x,4) --> [a,x,x,x,x,e]
	 * [a,b,c,d,e].replace(0,0,x,4) --> [x,x,x,x,a,b,c,d,e]
	 * </pre>
	 * 
	 * @param from the index of the first element to replace (inclusive)
	 * @param to   the index of the last element to replace (exclusive).
	 * @param replacement the elements to replace the replaced elements
	 * @param replacementSize the number of times <code>replacement</code> is to replace the replaced elements
	 * @throws IndexOutOfBoundsException if indexes are out of range.
	 */
	public void replace(int from, int to, byte replacement, int replacementSize) {
		checkSize(replacementSize);
		shrinkOrExpand(from, to, replacementSize);
		while (replacementSize-- > 0) elements[from++] = replacement;
		//java.util.Arrays.fill(this.elements, from, from + replacementSize, replacement);
	}
	
	/**
	 * Retains (keeps) only the elements in the receiver that are contained in
	 * the specified other list. In other words, removes from the receiver all
	 * of its elements that are not contained in the specified other list.
	 * <p>
	 * Example: <code>[0,1,2,2,3,1].retainAll([2,1]) --> [1,2,2,1]</code>
	 * <p>
	 * An efficient <i>set intersection</i> can be computed along the following lines: 
	 * <pre>
	 * list1.sort(true);
	 * list2.sort(true);
	 * list1.retainAll(list2);
	 * System.out.println("list1.retainAll(list2) = " + list1);
	 * // as a convenient byproduct we now know if list2 is a SUBSET of list1:
	 * System.out.println("list1.containsAll(list2) = " + (list1.size() == list2.size()));
	 * </pre>
	 * 
	 * @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 retainAll(ArrayByteList other) {
		// efficient implementation: O(N)
		if (size == 0) return false;
		if (other.size() == 0) {
			size = 0;
			return true;
		}

		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;
	}
	
    /**
	 * Rotates (shifts) the elements in the range <code>[from..to)</code> by
	 * the specified distance. After calling this method, the element at index
	 * <code>i</code> will be the element previously at index
	 * <code>(i - distance)</code> mod <code>to-from</code>, for all values
	 * of <code>i</code> between <code>from</code> (inclusive) and
	 * <code>to</code>, exclusive. (This method has no effect on the size of
	 * the list.) Examples:
	 * 
	 * <pre>
	 *   [a, b, c, d, e].rotate(0, 5, 1)  --&gt; [e, a, b, c, d]
	 *   [a, b, c, d, e].rotate(0, 5, 2)  --&gt; [d, e, a, b, c]
	 *   [a, b, c, d, e].rotate(1, 4, -1) --&gt; [a, c, d, b, e]
	 * </pre>
	 * 
	 * <p>
	 * To move elements rightwards, use a positive shift distance. To move
	 * elements leftwards, use a negative shift distance.
	 * <p>
	 * Note that this method can usefully be applied to sublists to move one or
	 * more elements within a list while preserving the order of the remaining
	 * elements.
	 * <p>
	 * This implementation exchanges the first element into the location it
	 * should go, and then repeatedly exchanges the displaced element into the
	 * location it should go until a displaced element is swapped into the first
	 * element. If necessary, the process is repeated on the second and
	 * successive elements, until the rotation is complete. This algorithm is
	 * efficient: Time complexity is linear O(to-from), space complexity is
	 * constant O(1).
	 * 
	 * @param from
	 *            the index of the first element to rotate (inclusive)
	 * @param to
	 *            the index of the last element to rotate (exclusive).
	 * @param distance
	 *            the distance to rotate the list. There are no constraints on
	 *            this value; for example it may be zero, negative, or greater than
	 *            <code>to-from</code>.
	 * @throws IndexOutOfBoundsException
	 *             if indexes are out of range.
	 * @see java.util.Collections#rotate(java.util.List, int)
	 */
	public void rotate(int from, int to, int distance) {
		checkRange(from, to);
		int length = to - from;
		if (length == 0) return;
		distance = distance % length;
		if (distance < 0) distance += length;
		if (distance == 0) return;

		byte[] elems = elements;		
		for (int nMoved = 0; nMoved != length; from++) {
			byte displaced = elems[from];
			int i = from;
			do {
				i += distance;
				if (i >= to) i -= length;
				
				byte tmp = elems[i];
				elems[i] = displaced;
				displaced = tmp;

				nMoved++;
			} while (i != from);
		}
    }

	/**
	 * Replaces the element at the specified index with the specified
	 * element.
	 * 
	 * @param index
	 *            index of element to replace.
	 * @param element
	 *            element to be stored at the specified index.
	 * @throws IndexOutOfBoundsException
	 *             if index is out of range.
	 */
	public void set(int index, byte element) {
		checkIndex(index);
		elements[index] = element;
		// equally correct alternative impl: replace(index, index+1, element, 1); 
	}

	/**
	 * Returns the number of contained elements.
	 *
	 * @return  the number of elements contained in the receiver.
	 */
	public int size() {
		return size;
	}

	/**
	 * Sorts the elements into ascending numerical order. For mathematical set
	 * operations, optionally removes duplicate elements before returning.
	 * Examples:
	 * <pre>
	 * [3,2,2,1].sort(false) --> [1,2,2,3]
	 * [3,2,2,1].sort(true)  --> [1,2,3]
	 * </pre>
	 * 
	 * @param removeDuplicates remove duplicate elements or keep them?
	 */
	public void sort(boolean removeDuplicates) {
		if (size <= 60) { // heuristic threshold according to benchmarks (theory: N*logN = 2*256)
			java.util.Arrays.sort(elements, 0, size);
			if (removeDuplicates) removeDuplicates();
		}
		else {
			countSort(removeDuplicates);
		}
	}
	
	/** efficient sort implementation: O(N) via frequency counts */
	private void countSort(boolean removeDuplicates) {
		final int min = Byte.MIN_VALUE;
		final int max = Byte.MAX_VALUE;
		int[] counts = new int[max - min + 1]; // could use BitSet if removeDuplicates
		for (int i = size; --i >= 0; ) {
			counts[elements[i] - min]++;
		}
		
		int j = 0;
		for (int i = min; i <= max; i++) { 
			int k = counts[i - min];
			if (removeDuplicates && k > 1) k = 1;
			while (--k >= 0) {
				elements[j++] = (byte) i;
			}
		}
		size = j;
	}

	/**
	 * [1,2,2,3,3,3] --> [1,2,3] 
	 * Assertion: list must be sorted prior to calling this method
	 */
	private void removeDuplicates() {
		int i = 0;
		int j = 0;
		while (j < size) {
			byte elem = elements[j++];
			elements[i++] = elem;
			while (j < size && elements[j] == elem) j++; // skip duplicates
		}
		size = i;
	}
	
	/** Small helper method eliminating redundancy. */
	private byte[] subArray(int from, int length, int capacity) {
		byte[] subArray = new byte[capacity];
		System.arraycopy(elements, from, subArray, 0, length);
		return subArray;
	}

	/**
	 * Constructs and returns a new list containing a copy of the elements in
	 * the range <code>[from..to)</code>.
	 * 
	 * @param from
	 *            the index of the first element (inclusive).
	 * @param to
	 *            the index of the last element (exclusive).
	 * @return a new list
	 * @throws IndexOutOfBoundsException
	 *             if indexes are out of range
	 */
	public ArrayByteList subList(int from, int to) {
		checkRange(from, to);
		return new ArrayByteList(subArray(from, to - from, to - from));
	}

	/**
	 * Returns a copied array of bytes containing all elements; the returned
	 * array has length = this.size().
	 */
	public byte[] toArray() {
		return subArray(0, size, size);
	}

	/**
	 * Returns a string representation, containing the numeric String
	 * representation of each element.
	 */
	public String toString() {
		//return toList().toString();
		StringBuffer buf = new StringBuffer(4*size);
		buf.append("[");
		for (int i = 0; i < size; i++) {
			buf.append(elements[i]);
			if (i < size-1) buf.append(", ");
		}
		buf.append("]");
		return buf.toString();
	}

	/**
	 * Returns a decoded string representation of all elements.
	 * 
	 * @param charset
	 *            the charset to convert with (e.g. <code>Charset.forName("US-ASCII")</code>,
	 *            <code>Charset.forName("ISO-8859-1")</code>). 
	 *            If <code>null</code> uses <code>Charset.forName("UTF-8")</code> as the default charset.
	 */
	public String toString(Charset charset) {
		return toString(0, size, charset);
	}

	/**
	 * Returns a decoded string representation of the bytes in the
	 * given range <code>[from..to)</code>.
	 * 
	 * @param from
	 *            the index of the first element (inclusive).
	 * @param to
	 *            the index of the last element (exclusive).
	 * @param charset
	 *            the charset to convert with (e.g. <code>Charset.forName("US-ASCII")</code>,
	 *            <code>Charset.forName("ISO-8859-1")</code>). 
	 *            If <code>null</code> uses <code>Charset.forName("UTF-8")</code> as the default charset.
	 * @throws IndexOutOfBoundsException
	 *             if indexes are out of range
	 */
	public String toString(int from, int to, Charset charset) {
		checkRange(from, to);
		return getCharset(charset).decode(ByteBuffer.wrap(this.elements, from, to-from)).toString();
	}

	/**
	 * Trims the capacity of the receiver to be the receiver's current size;
	 * Releases any superfluos internal memory. An application can use this
	 * operation to minimize the storage of the receiver.
	 */
	public void trimToSize() {
		if (elements.length > size) {
			elements = subArray(0, size, size);
		}
	}