arrayintlist.java

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

	 *            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, int 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) {
		final int maxWidth = 256 * 1024; // memory consumption threshold (also prevents int overflows in countSort())
		if (size > 60) { // performance threshold heuristic
			// compute minimum and maximum values
			int[] elems = elements;
			int min = elems[0];
			int max = min;
			for (int i = 1; i < size && max - min < maxWidth && max - min >= 0; i++) { // width < 0 on int overflow
				int elem = elems[i];
				if (elem > max) max = elem;
				else if (elem < min) min = elem;
			}
			
			int width = max - min;
			if (width < maxWidth && width >= 0 ) {
				int countSortEstimate = Math.max(width, size); // O(Max(width,N))
				double log2 = Math.log(size) / 0.6931471805599453; // O(N*log(N,base=2)) ; ln(2)=0.6931471805599453
				double quickSortEstimate = size * log2; 
				if (countSortEstimate < quickSortEstimate) {
					//System.out.println("using countSort..");
					countSort(removeDuplicates, min, max);	
					return;
				}
			}
		}

		// use quicksort if there is no more efficient alternative:
		java.util.Arrays.sort(elements, 0, size);
		if (removeDuplicates) removeDuplicates();
	}
	
	/** efficient sort implementation: O(N) via frequency counts */
	private void countSort(boolean removeDuplicates, int min, int max) {
		// countSort is most efficient on large lists that have values that are in a small [min,max] range		
		// assertion: max - min +1 does not yield int overflow
		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 >= min && i <= max; i++) { // safe even with int overflow 
			int k = counts[i - min];
			if (removeDuplicates && k > 1) k = 1;
			while (--k >= 0) {
				elements[j++] = 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) {
			int elem = elements[j++];
			elements[i++] = elem;
			while (j < size && elements[j] == elem) j++; // skip duplicates
		}
		size = i;
	}
	
	/** Small helper method eliminating redundancy. */
	private int[] subArray(int from, int length, int capacity) {
		int[] subArray = new int[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 ArrayIntList subList(int from, int to) {
		checkRange(from, to);
		return new ArrayIntList(subArray(from, to - from, to - from));
	}

	/**
	 * Returns a copied array of bytes containing all elements; the returned
	 * array has length = this.size().
	 */
	public int[] 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();
	}

	/**
	 * 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);
		}
	}

	/**
	 * Checks if the given index is in range.
	 */
	private void checkIndex(int index) {
		if (index >= size || index < 0)
			throw new IndexOutOfBoundsException("index: " + index
						+ ", size: " + size);
	}

	/**
	 * Checks if the given range is within the contained array's bounds.
	 */
	private void checkRange(int from, int to) {
		if (from < 0 || from > to || to > size)
			throw new IndexOutOfBoundsException("from: " + from + ", to: "
						+ to + ", size: " + size);
	}

	/**
	 * Checks if the given size is within bounds.
	 */
	private void checkSize(int newSize) {
		if (newSize < 0)
			throw new IndexOutOfBoundsException("newSize: " + newSize);
	}

	/** efficient Serializable support */
	private void writeObject(java.io.ObjectOutputStream out) throws IOException {
		out.defaultWriteObject();
		out.writeInt(elements.length);
		for (int i = 0; i < size; i++) {
			out.writeInt(elements[i]);
		}
	}

	/** efficient Serializable support */
	private void readObject(java.io.ObjectInputStream in) throws IOException,
			ClassNotFoundException {
		in.defaultReadObject();
		elements = new int[in.readInt()];
		for (int i = 0; i < size; i++) {
			elements[i] = in.readInt();
		}
	}

	// **************************************************************************** 
	// following are some method not deemed a) important enough or b) complex enough
	// to warrant interface bloat:
	// **************************************************************************** 
		

//	/**
//	 * Appends the specified elements to the end of this list.
//	 * <p>
//	 * If you need to append <code>elems[from..to)</code>, use
//	 * <code>list.add(new ArrayIntList(elems).subList(from, to))</code> 
//	 * or <code>list.add(IntBuffer.wrap(elems, from, to-from))</code>
//	 * or similar.
//	 * 
//	 * @param elems
//	 *            elements to be appended.
//	 * @return <code>this</code> (for chaining convenience only)
//	 */
//	public ArrayIntList add(int[] elems) {
//		replace(size, size, elems);
//		return this;
//	}
//	
//	/**
//	 * Inserts the specified element before the specified index. Shifts the
//	 * element currently at that index (if any) and any subsequent elements
//	 * to the right. This is equivalent to <code>replace(index, index, elem, 1)</code>.
//	 * 
//	 * @param index
//	 *            index before which the specified element is to be inserted
//	 * @param elem
//	 *            element to insert.
//	 * @throws IndexOutOfBoundsException if index is out of range.
//	 */
//	private void insert(int index, int elem) {
//		replace(index, index, elem, 1);
//	}
//	
//	/**
//	 * Inserts the specified elements before the specified index. Shifts the
//	 * element currently at that index (if any) and any subsequent elements
//	 * to the right.
//	 * 
//	 * @param index
//	 *            index before which the specified elements are to be inserted
//	 * @param elems
//	 *            elements to insert.
//	 * @throws IndexOutOfBoundsException if index is out of range.
//	 */
//	private void insert(int index, int[] elems) {
//		replace(index, index, elems);
//	}
//	
//	/**
//	 * Inserts the specified elements before the specified index. Shifts the
//	 * element currently at that index (if any) and any subsequent elements
//	 * to the right.
//	 * 
//	 * @param index
//	 *            index before which the specified elements are to be inserted
//	 * @param elems
//	 *            elements to insert.
//	 * @throws IndexOutOfBoundsException if index is out of range.
//	 */
//	private void insert(int index, ArrayIntList elems) {
//		replace(index, index, elems);
//	}
//	
//	/**
//	 * Inserts the remaining buffer elements before the specified index.
//	 * Shifts the element currently at that index (if any) and any subsequent
//	 * elements to the right.
//	 * 
//	 * @param index
//	 *            index before which the specified elements are to be inserted
//	 * @param elems
//	 *            elements to insert.
//	 * @throws IndexOutOfBoundsException if index is out of range.
//	 */
//	private void insert(int index, IntBuffer elems) {
//		replace(index, index, elems);
//	}

//	/**
//	 * Returns the index of the last 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 last 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 lastIndexOf(int from, int to, int elem) {
//		checkRange(from, to);
//		int[] elems = elements;
//		for (int i = to; --i >= from; ) {
//			if (elem == elems[i]) return i; //found
//		}
//		return -1; //not found
//	}

//	/**
//	 * Removes the element at the specified index. Shifts any subsequent
//	 * elements to the left. Keeps the current capacity.
//	 * 
//	 * @param index
//	 *            the index of the element to removed.
//	 * @throws IndexOutOfBoundsException
//	 *             if index is out of range
//	 */
//	public void remove(int index) {
//		remove(index, index+1);
//	}

//	/**
//	 * Reverses the order of elements in the range <code>[from..to)</code>.
//	 * Last becomes first, second last becomes second first, and so on.
//	 * <p>
//	 * Example: <code>[a,b,c,d].reverse(0,4) --> [d,c,b,a]</code>
//	 * 
//	 * @param from the index of the first element (inclusive)
//	 * @param to the index of the last element (exclusive).
//	 * @throws IndexOutOfBoundsException if indexes are out of range.
//	 */
//	public void reverse(int from, int to) {
//		checkRange(from, to);
//		int[] elems = elements;		
//		int middle = from + (to - from) / 2;
//		to--;		
//		for ( ; from < middle; from++, to--) { // swap
//			int tmp = elems[from];
//			elems[from] = elems[to];
//			elems[to] = tmp;
//		}
//	}

//	/**
//	 * Sets the size to the given new size, expanding the list capacity if
//	 * necessary. 
//	 * <p>
//	 * Capacity expansion introduces a new backing array. If the new
//	 * size is greater than the current size the elements between the current
//	 * size and the new size will become legally accessible but have undefined
//	 * values. An application will typically want to set these elements to defined
//	 * values immediately after this method returns. Note that
//	 * <code>setSize(0)</code> effectively clears the list (as does
//	 * <code>remove(0, list.size()</code>).
//	 * 
//	 * @param newSize the new size.
//	 * @return <code>this</code> (for chaining convenience only)
//	 * @throws IndexOutOfBoundsException if new size is less than zero.
//	 */
//	public ArrayIntList setSize(int newSize) {
//		checkSize(newSize);
//		ensureCapacity(newSize);
//		// equivalent impl: shrinkOrExpand(0, size, newSize);
//		size = newSize;
//		return this;
//	}

//	/**
//	 * Returns a <code>java.util.ArrayList</code> containing a copy of all elements.
//	 */
//	public java.util.ArrayList toList() {
//		java.util.ArrayList list = new java.util.ArrayList(size);
//		for (int i = 0; i < size; i++)
//			list.add(new Integer(elements[i]));
//		return list;
//	}

}