arrayintlist.java

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

/*
 * Copyright (c) 2003, The Regents of the University of California, through
 * Lawrence Berkeley National Laboratory (subject to receipt of any required
 * approvals from the U.S. Dept. of Energy). All rights reserved.
 */
package gov.lbl.dsd.sea.nio.util;

import java.io.IOException;
import java.nio.IntBuffer;

/**
Efficient resizable auto-expanding list holding <code>int</code> elements; implemented with arrays.
The API is intended for easy non-trivial high-throughput processing, 
and (in an elegant and compact yet different form) provides all list and set functionality 
of the java.util collections package, as well as a little more.
This API fills the gap between raw arrays (non-resizable), nio IntBuffers (non-resizable) and
java.util.List and java.util.Set (resizable but not particularly useful for 
<i>non-trivial high-throughput</i> processing on primitive types).
<p>
Indexed element access is zero based: valid indexes range from 
index <code>0</code> (inclusive) to index <code>list.size()</code> (exclusive).
Attempts to access out-of-range indexes will throw an {@link IndexOutOfBoundsException}.
<p>
<strong>Note that this implementation is not synchronized, hence not inherently thread safe.</strong>
<p>
Example usage:
<pre>
System.out.println(new ArrayIntList(new int[] {0,1,2}));
</pre>
<p>
This class requires JDK 1.4 or higher; otherwise it has zero dependencies. 
Hence you can simply copy the file into your own project if minimal dependencies are desired.
<p>
Also note that the compiler can (and will) easily inline all methods, then optimize away.
In fact with the Sun jdk-1.4.2 server VM it is hard to measure any difference 
to raw array manipulations at abstraction level zero.

@author [e-mail]
@author $Author: hoschek3 $
@version $Revision: 1.36 $, $Date: 2004/08/07 19:13:47 $
*/
public final class ArrayIntList implements java.io.Serializable {

	/**
	 * The array into which the elements of the list are stored. The
	 * capacity of the list is the length of this array.
	 */
	private transient int[] elements;

	/**
	 * The current number of elements contained in this list.
	 */
	private int size;

	/**
	 * For compatibility across versions
	 */
	private static final long serialVersionUID = 2982195016849084649L;	
		
	/**
	 * Constructs an empty list.
	 */
	public ArrayIntList() {
		this(10);
	}

	/**
	 * Constructs an empty list with the specified initial capacity.
	 * 
	 * @param initialCapacity
	 *            the number of elements the receiver can hold without
	 *            auto-expanding itself by allocating new internal memory.
	 */
	public ArrayIntList(int initialCapacity) {
		elements = new int[initialCapacity];
		size = 0;
	}

	/**
	 * Constructs a list SHARING the specified elements. The initial size and
	 * capacity of the list is the length of the backing array.
	 * <p>
	 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low,
	 * <b>the array is SHARED, not copied </b>. So if subsequently you modify the
	 * specified array directly via the [] operator, be sure you know what
	 * you're doing.
	 * <p>
	 * If you rather need copying behaviour, use
	 * <code>copy = new ArrayIntList(int[] elems).copy()</code> or similar.
	 * <p>
	 * If you need a list containing a copy of <code>elems[from..to)</code>, use
	 * <code>list = new ArrayIntList(to-from).add(elems, from, to-from)</code> 
	 * or <code>list = new ArrayIntList(IntBuffer.wrap(elems, from, to-from))</code>
	 * or similar.
	 * 
	 * @param elems
	 *            the array backing the constructed list
	 */
	public ArrayIntList(int[] elems) {
		elements = elems;
		size = elems.length;
	}

	/**
	 * Constructs a list containing a copy of the remaining buffer elements. The
	 * initial size and capacity of the list is <code>elems.remaining()</code>.
	 * 
	 * @param elems
	 *            the elements initially to be added to the list
	 */
	public ArrayIntList(IntBuffer elems) {
		this(elems.remaining());
		add(elems);
	}

	/**
	 * Appends the specified element to the end of this list.
	 * 
	 * @param elem
	 *            element to be appended to this list.
	 * @return <code>this</code> (for chaining convenience only)
	 */
	public ArrayIntList add(int elem) {
		if (size == elements.length) ensureCapacity(size + 1);
		elements[size++] = elem;
		return this;
		// equally correct alternative impl: insert(size, elem);
	}

	/**
	 * Appends the elements in the range <code>[offset..offset+length)</code> to the end of this list.
	 * 
	 * @param elems the elements to be appended
	 * @param offset the offset of the first element to add (inclusive)
	 * @param length the number of elements to add
	 * @return <code>this</code> (for chaining convenience only)
	 * @throws IndexOutOfBoundsException if indexes are out of range.
	 */
	public ArrayIntList add(int[] elems, int offset, int length) {
		if (offset < 0 || length < 0 || offset + length > elems.length) 
			throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", elems.length: " + elems.length);
		ensureCapacity(size + length);
		System.arraycopy(elems, offset, this.elements, size, length);
		size += length;
		return this;
		// equally correct alternative impl: replace(size, size, elems, offset, length);
	}

	/**
	 * Appends the specified elements to the end of this list.
	 * 
	 * @param elems
	 *            elements to be appended.
	 * @return <code>this</code> (for chaining convenience only)
	 */
	public ArrayIntList add(ArrayIntList elems) {
		replace(size, size, elems);
		return this;
	}
	
	/**
	 * Appends the remaining buffer elements to the end of this list.
	 * 
	 * @param elems
	 *            elements to be appended.
	 * @return <code>this</code> (for chaining convenience only)
	 */
	public ArrayIntList add(IntBuffer elems) {
		int length = elems.remaining();
		ensureCapacity(size + length);
		elems.get(this.elements, size, length);
		size += length;
		return this;
		// equally correct alternative impl: replace(size, size, elems, elems.remaining());
	}
	
	/**
	 * Returns the elements currently stored, including invalid elements between
	 * size and capacity, if any.
	 * <p>
	 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low,
	 * <b>the array is SHARED, not copied </b>. So if subsequently you modify the
	 * returned array directly via the [] operator, be sure you know what you're
	 * doing.
	 * 
	 * @return the elements currently stored.
	 */
	public int[] asArray() {
		return elements;
	}

	/**
	 * Returns a buffer SHARING elements with the receiver. The buffer will
	 * have the default NIO byte order, which is ByteOrder.nativeOrder().
	 * <p>
	 * <b>WARNING: </b> For efficiency reasons and to keep memory usage low,
	 * <b>the array is SHARED, not copied </b>. So if subsequently you modify the
	 * returned buffer, be sure you know what you're doing.
	 */
	public IntBuffer asIntBuffer() {
		return IntBuffer.wrap(elements, 0, size);
	}

    /**
	 * Searches the list for the specified value using the binary search
	 * algorithm. The list <strong>must </strong> be sorted (as by the
	 * <tt>sort</tt> 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, <tt>(-(<i>insertion point</i>) - 1)</tt>. 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 <tt>list.size()</tt>, 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(int key) {
		int low = 0;
		int high = size - 1;

		while (low <= high) {
			int mid = (low + high) >> 1; // >> 1 is equivalent to divide by 2
			int 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 ArrayIntList 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 ArrayIntList copy() {
		return new ArrayIntList(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) { //delta
		if (this == otherObj) return true;
		if (!(otherObj instanceof ArrayIntList)) return false;
		ArrayIntList other = (ArrayIntList) 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, ArrayIntList pattern, ArrayIntList 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 int get(int index) {
		checkIndex(index);
		return elements[index];
	}

	/**
	 * Returns the hash code value for this list. The algorithm ensures that
	 * <tt>list1.equals(list2)</tt> implies that
	 * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
	 * <tt>list1</tt> and <tt>list2</tt>, as required by the general
	 * contract of <tt>Object.hashCode</tt>.
	 * <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;
		int[] 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