skiplist.java

一个关于java 的常用工具包

package org.jutil.java.collections;


import java.util.AbstractCollection;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.util.Iterator;
import java.util.ConcurrentModificationException;


/**
 * <p>A collection which is actually a sorted list.</p>
 *
 * <p>A skiplist is a sorted list with an <b>average</b> <code>O(log(n))</code>
 * behavior for 
 * <a href="SkipList.html#add(java.lang.Object)"><code>add()</code></a> and
 * <a href="SkipList.html#remove(java.lang.Object)">remove()<code></code></a>. 
 * The worst case time complexity is <code>O(n)</code>.</p>
 * <p>A skiplist looks like a linked list, but the difference is that the cells
 * of a skiplist have a number of forward pointers. The number of forward 
 * pointers of a cell is called the <em>level</em> of that cell. 
 * The <a href="SkipList.html#leve()"><code>level</code></a> of a SkipList is 
 * the maximum of the levels of its cells. The level of a SkipList can not 
 * exceed its <a href="SkipList.html#getMaxLevel()">maximum level</a>.</p>
 *
 * <p>The i'th forward pointer of a cell points to the next cell of level 
 * &gt;= i, thus <em>skipping</em> a number of elements with level &lt;i. 
 * An example a skiplist is shown in the figure below.
 * The left cell is the header of the skiplist which contains 
 * <a href="SkipList.html#getMaxLeve()"><code>getMaxLevel()</code></a> forward
 * pointers (but is not included in the level count for the list). 
 * The crossed arrows point to the end of the list, indicating there is no 
 * next cell of level i. The light grey field at the bottom of each cell is a 
 * reference to the element that is represented by that cell. As you can see, 
 * multiple cells can reference the same object  because we are dealing with a
 * list.</p>
 *
 * <center>
 * 	<img src="doc-files/skiplist-example.png"/>
 * </center>
 *
 * <p>The elements of a SkipList are sorted using a 
 * <a href="http://java.sun.com/j2se/1.4/docs/api/index.html"><code>Comparator</code></a>,
 * which is given to the list at the time of construction.</p>
 *
 * <p>The level of a cell is a random number between 1 and 
 * <a href="SkipList.html#getMaxLevel()"><code>getMaxLevel()</code></a>. 
 * There is a fixed 
 * <a href="SkipList.html#getProbability()">probability<code></code></a> 
 * that a cell with a level  &gt;=i has a level &gt;=i+1 (unless of course 
 * i==<a href="SkipList.html#getMaxLevel()"><code>getMaxLevel()</code></a>).
 * It is the randomness that makes that a skiplist has an average 
 * <code>O(log(n))</code> 
 * <a href="SkipList.html#add(java.lang.Object)"><code>add()</code></a> and 
 * <a href="SkipList.html#remove(java.lang.Object)"><code>remove()</code></a> 
 * because only a fixed number of cells must be changed to insert of remove a 
 * cell (no structure has to be maintained).</p>
 * 
 * <p>With probability 0.25 the average number of forward pointers per element
 * is 1.333. A maximum level L will be efficient for a SkipList containing about
 * 4<sup>L</sup> elements. If you add much more elements than that, the number
 * of cell with the maximum level will increase, so searching an element 
 * will take longer. The default level is 8.</p>
 *
 * <p>For more information, go to 
 * <a href="ftp://ftp.cs.umd.edu/pub/skipLists">ftp://ftp.cs.umd.edu/pub/skipLists</a>.</p>
 *
 * @path    $Source: /cvsroot/org-jutil/jutil.org/src/org/jutil/java/collections/SkipList.java,v $
 * @version $Revision: 1.7 $
 * @date    $Date: 2002/07/21 17:56:59 $
 * @state   $State: Exp $
 * @author  Marko van Dooren
 * @author  Tom Schrijvers
 * @release $Name:  $
 */
public class SkipList extends AbstractCollection {

	/* The revision of this class */
	public final static String CVS_REVISION ="$Revision: 1.7 $";

 /*@ // FIXME
   @ // private behavior
	 @
 	 @ // post level() == 1;
	 @*/

	/**
	 * Initialize a new SkipList with the given comparator.
	 *
	 * @param comparator
	 *        The Comparator used to determine the order of the elements
	 *        in this SkipList.
	 */
 /*@
	 @ public behavior
	 @
	 @ pre comparator != null;
	 @
	 @ post getMaxLevel() == 8;
	 @ post size() == 0;
	 @ post getProbability() == 0.25;
	 @
	 @*/
	public SkipList(Comparator comparator) {
		this(8,comparator, 0.25f);
  }

 /*@ // FIXME
	 @ // private behavior
	 @
	 @ // post level() == 1;
	 @*/
	/**
	 * Initialize a new SkipList with the given maximum level, comparator and
	 * probability.
	 *
	 * @param maxLevel
	 *        The maximum level of the nodes used internally by
	 *        this SkipList.
	 * @param comparator
	 *        The Comparator used to determine the order of the elements
	 *        in this SkipList.
	 * @param probability
	 *        The fraction of nodes of level >= i that has level >= i + 1
	 */
 /*@
	 @ public behavior
	 @
	 @ pre maxLevel >= 1;
	 @ pre comparator != null;
	 @ pre probability >= 0;
	 @ pre probability <= 1;
	 @
	 @ post getMaxLevel() == maxLevel;
	 @ post size() == 0;
	 @ post getProbability() == probability;
	 @*/
	public SkipList(int maxLevel, Comparator comparator, float probability) {
		_maxLevel = maxLevel;
		_head = new Object[maxLevel+1];
		_comparator = comparator;
		_probability = probability;
		_prng = new java.util.Random();
		_level = 1;
		_update = new Object[maxLevel][];
		_size = 0;
  }

	/**
	 * See superclass
	 */
	public String toString() {
		String result ="";
		Iterator iter = iterator();
		while(iter.hasNext()) {
			result += iter.next().toString();
    }
		return result;
  }
	
	/**
	 * See superclass
	 */
	public int size() {
		return _size;
  }

	/**
	 * See superclass
	 */
	public void clear() {
		// Clear the Head node, so all other nodes will be garbage collected.
		java.util.Arrays.fill(_head,0,_maxLevel,null);
		_level = 1;
		_size = 0;
  }
	
	/**
	 * See superclass
	 */
	public boolean contains(Object o) {
		try {
			Object[] dummy = search(o);
			return true;
		}
		catch(NoSuchElementException exc) {
			return false;
    }
	}

	/**
	 * Return the first object of this SkipList.
	 */
 /*@
	 @ public behavior
	 @
	 @ pre ! isEmpty();
	 @
	 @ post contains(\result);
	 @ post (\forall Object o; contains(o); 
	 @       getComparator().compare(\result,o)<=0);
	 @*/
	public Object getFirst() {
		return ((Object[]) _head[1])[0];
	}
	
	/**
	 * Return the level of this skiplist
	 */
 /*@
	 @ private behavior
	 @
	 @ post \result >= 1;
	 @ post \result <= getMaxLevel();
	 @*/
	private int level() {
		return _level;
  }

	/**
	 * Return the maximum level of this SkipList
	 */
 /*@
	 @ public behavior
	 @
	 @ post \result >= 1;
	 @*/
	public int getMaxLevel() {
		return _maxLevel;
  }

	/**
	 * Return the Comparator used to determine the order in which the
	 * elements are added to this SkipList.
	 */
 /*@
	 @ public behavior
	 @
	 @ post \result != null;
	 @*/
	public Comparator getComparator() {
		return _comparator;
  }
	
	/**
	 * Return the probability that a node of level >= i is a node
	 * of level >= i + 1
	 */
 /*@
	 @ public behavior
	 @
	 @ post \result >= 0;
	 @ post \result <= 1;
	 @*/
	public float getProbability() {
		return _probability;
  }

	
	/**
	 * Return the node starting this SkipList.
	 */
 /*@
	 @ private behavior
	 @
	 @ post \result != null;
	 @*/
	private Object[] getHead() {
		return _head;
  }

	/**
	 * Search for the InternalSkipListNode containing the given value
	 *
	 * @param o
	 *        The value to be looked for.
	 */
 /*@
	 @ private behavior
	 @
	 @ post getComparator().compare(\result[0], object) == 0;
	 @
	 @ signals (NoSuchElementException) (* The object is not in this SkipList *);
	 @*/
	private Object[] search(final Object object) throws NoSuchElementException {
		Object[] x = _head;
		final Comparator comparator = _comparator;
		int i=_level;
		// level = i
		// the 0-th element is reserved for the value
		do {
			Object[] node = (Object[])x[i];
			while ((node != null) && (comparator.compare(node[0],object) < 0)) {
				x = node;
				node = (Object[])x[i];
			}
			i--;
		} while (i>0);
		
		x = (Object[])x[1];
		if ((x == null) || (comparator.compare(x[0], object) != 0)) {
			throw new NoSuchElementException();
    }
		else {
			return x;
    }
  }
	
	/**
	 * See superclass
	 */
	public Iterator iterator() {
		return new SkipListIterator();
  }
	
	/**
	 * See superclass
	 **/
	public boolean add(final Object object) {
		Object[] x = _head;
		// Cache some frequently used instance variables as local
		// variables to increase speed.
		final Comparator comparator = _comparator;
		final java.util.Random prng = _prng;
		final int thisLevel = _level;
		int i = thisLevel;

		int level = 1;
		// @variant _maxLevel - level
		// @invariant level < _maxLevel
		// @invariant level >= 1;
		while ((prng.nextFloat() < _probability) && (level < _maxLevel)) {
			level++;
		}
		
		// Create a new node to insert.
		// Since this is not a set, we can do it in advance.
		Object[] newNode = new Object[level + 1];
		// Set to value of the new node to the given object.
		newNode[0]=object;
		
		// Check whether or not we've exceeded the current level of the list
		if(level > thisLevel) {
			// We did exceed it, so we must set the previously unused forward references
			// to the new node and adjust the level of the list.
			java.util.Arrays.fill(_head, thisLevel+1, level+1, newNode);
			_level = level;
		}
		else if (thisLevel>level) {