arrayintlist.java

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

	 *            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, ArrayIntList subList) {
		// brute-force algorithm, but very efficiently implemented
		checkRange(from, to);
		int[] elems = elements;
		int[] 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, int elem) {
		checkRange(from, to);
		int[] 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, ArrayIntList subList) {
		// brute-force algorithm, but very efficiently implemented
		checkRange(from, to);
		int[] elems = elements;
		int[] 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>
	 * <p>
	 * An efficient <i>asymmetric set difference</i> can be computed along the following lines: 
	 * <pre>
	 * list1.sort(true);
	 * list2.sort(true);
	 * list1.removeAll(list2, true);
	 * System.out.println(list1);
	 * </pre>
	 * 
	 * @param other
	 *            the other list to test against (remains unmodified by this method).
	 * @param isOtherSorted
	 *            true if the other list is already sorted ascending, false otherwise (being sorted improves performance).
	 * @return <code>true</code> if the receiver changed as a result of the
	 *         call.
	 */
	public boolean removeAll(ArrayIntList other, boolean isOtherSorted) {
		// time complexity is O(N log M) if sorted; O(N*M) otherwise
		if (size == 0 || other.size() == 0) return false; //nothing to do
		int limit = other.size();
		int j = 0;

		for (int i = 0; i < size; i++) {
			if (isOtherSorted ? other.binarySearch(elements[i]) < 0 : other.indexOf(0, limit, elements[i]) < 0) {
				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;
		}
	}
	
	/**
	 * 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, int[] 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, ArrayIntList 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, IntBuffer 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, int 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, true);
	 * 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()));
	 * // as a convenient byproduct we now know if list1 contains ANY element of list2:
	 * System.out.println("list1.containsAny(list2) = " + (list1.size() > 0));
	 * </pre>
	 * 
	 * @param other
	 *            the other list to test against (remains unmodified by this method).
	 * @param isOtherSorted
	 *            true if the other list is already sorted ascending, false otherwise (being sorted improves performance).
	 * @return <code>true</code> if the receiver changed as a result of the
	 *         call.
	 */
	public boolean retainAll(ArrayIntList other, boolean isOtherSorted) {
		// time complexity is O(N log M) if sorted; O(N*M) otherwise
		if (size == 0) return false;
		if (other.size() == 0) {
			size = 0;
			return true;
		}

		int limit = other.size();
		int j = 0;
		for (int i = 0; i < size; i++) {
			if (isOtherSorted ? other.binarySearch(elements[i]) >= 0 : other.indexOf(0, limit, elements[i]) >= 0)
				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;

		int[] elems = elements;
		for (int nMoved = 0; nMoved != length; from++) {
			int displaced = elems[from];
			int i = from;
			do {
				i += distance;
				if (i >= to) i -= length;
				
				int 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