skiplist.java

一个关于java 的常用工具包

			// In this case level was smaller than the list, we need to descend without
			// updating anything until we've reached level "level". From there we must
			// start updating (next loop).
			do {
				Object[] node = (Object[])x[i];
				while ((node != null) && (comparator.compare(node[0],object) < 0)) {
					x = node;
					node = (Object[])x[i];
				}
				i--;
			} while (i>level);
		}
		do {
			// Descend while updating.
			// Since we are sure we need to do this for at least one level (level 1), we use
			// a do-while construction to save us an unnecessary test.
			Object[] node = (Object[])x[i];
			while ((node != null) && (comparator.compare(node[0],object) < 0)) {
				x = node;
				node = (Object[])x[i];
			}
			newNode[i]=node;
			x[i]=newNode;
			i--;
		} while (i>0);
		_modCount++;
		_size++;
		return true;
	}

	/**
	 * Remove the first element of this SkipList.
	 */
 /*@
	 @ public behavior
	 @
	 @ pre ! isEmpty();
	 @
	 @ post (! \old(isEmpty())) ==> (size() == \old(size()) - 1);
	 @ post (! \old(isEmpty())) ==> (Collections.nbExplicitOccurrences(\old(getFirst()),this) ==
	 @                               \old(Collections.nbExplicitOccurrences(getFirst(),this)) - 1);
	 @*/
	public void removeFirst() {
		Object[] first = (Object[]) _head[1];
		// do nothing if this SkipList is empty.
		if(first != null) {
			_size--;
//		for (int i = 1; i < first.length ; i++) {
//			_head[i] = first[i];
//		}
			System.arraycopy(first,1,_head,1,first.length-1);
		}
	}
	
	private boolean remove(final Object object, final boolean removeAll) {
		boolean result = false;
		Object[] x = _head;
		// Cache some frequently used instance variables as local
		// variables to increase speed.
		final Comparator comparator = _comparator;
		final int thisLevel = _level;
		int i = thisLevel;
		//Object[][] update = new Object[thisLevel][];
		final Object[][] update = _update;;
		Object[] node = null;
		
		do {
			node = (Object[])x[i];
			while ((node != null) && (comparator.compare(node[0],object) < 0)) {
				x = node;
				node = (Object[])x[i];
			}
			i--;
			update[i]=x;
		} while (i>0);
		// remove the first node that equals the given object. Since
		// comparator.compare() == 0 must be consistent with equals.
		
		// if node == null , the given object wasn't found.
		if ((node != null) && (comparator.compare(node[0],object) == 0)) {
			// If we have to remove all occurrences, we need to search for 
			// the first node with a different value
			if(removeAll) {
				do {
					x = node;
					node = (Object[])x[i];
				} while ((node != null) && (comparator.compare(node[0],object) == 0));
				// At this point node is either null, or greater than object.
				// This means that x is the last node to be removed.
				node = x;
      }
			
			i = node.length-1;
			do {
				Object temp = node[i];
				x = update[i-1];
				x[i] = temp;
				i--;
				if((temp == null) && (x == _head)) {
					_level--;
				}
			} while(i > 0);
			result = true;
			_size--;
		}
		_modCount++;
		return result;
  }
	
	/**
	 * See superclass
	 */
	public boolean remove(final Object object) {
		return remove(object, false);
  }
	
	/**
	 * See superclass
	 */
	public boolean removeAll(final Object object) {
		return remove(object, true);
  }
	
	/**
	 * Return a random level between 1 and getMaxLevel(). The fraction
	 * of levels > = i that has level >= i+1 is getProbability().
	 */
 /*@
	 @ private behavior
	 @
	 @ post \result >= 1;
	 @ post \result <= getMaxLevel();
	 @*/
	private int randomLevel() {
		int level = 1;
		while ((_prng.nextFloat() < _probability) && (level < _maxLevel)) {
			level++;
    }
		return level;
	}


	/**
	 * <p>All elements in a SkipList are kept as nodes. Nodes are represented
	 * as object arrays for efficiency reasons. I tried an object-oriented
	 * cell design, but it was too slow.</p>
	 *
	 * <p>The nodes have the following structure :</p>
	 * <ul>
	 * 	<li>node[0] is a reference to the element contained in the node.</li>
	 *  <li>node[i] is the i'th forward pointer. It points to the next
	 * node of level >= i, or null if such a node does not exist (that
	 * means that the node itself is the last one of level >= i).</li>
	 * </ul>
	 *
	 * <p>The number of forward pointer is the level of the node, and is
	 * restricted by _maxLevel.</p>
	 */

	/**
	 * <p>The first node of this SkipList.</p>
	 */
 /*@
	 @ private invariant _head != null;
	 @*/
	private Object[] _head;

	/**
	 * <p>The maximum level an object can have in this SkipList.</p>
	 */
 /*@
	 @ private invariant _maxLevel >= 1;
	 @*/
	private int _maxLevel;
	
	/**
	 * <p>The Comparator that will determine the order of the elements
	 * in this SkipList.</p>
	 */
 /*@
	 @ private invariant _comparator != null;
	 @*/
	private Comparator _comparator;
	
	/**
	 * <p>The fraction of node of level i that have a level >= i.</p>
	 */
 /*@
	 @ private invariant _probability >= 0;
	 @ private invariant _probability <= 1;
	 @*/
	private float _probability;

	/**
	 * <p>The level of this node, being the maximum of the levels of all nodes.</p>
	 */
 /*@
	 @ private invariant _level >= 0;
	 @ private invariant _level <= _maxLevel;
	 @*/
	private int _level;
	
	/**
	 * </p>The update vector of the skiplist algorithm. It is kept as an 
	 * instance variable to prevent the construction of lots of array 
	 * which are thrown away immediately. It may of course only be used 
	 * by a single thread at a time. So either provide a locking mechanism, 
	 * or synchronize the entire methods that use it.</p>
	 * <p>Locking it, and only constructing a new array if _update is already
	 * in use is still a lot faster than creating a new one by default.</p>
	 *
	 * MVDMVDMVD: put this in a general optimization page or so
	 */
 /*@
	 @ private invariant _update != null;
	 @ private invariant _update.length == _level;
	 @*/
	private Object[][] _update;
	
	/**
	 * <p>The pseudo random number generator used to determine the level of a node.</p>
	 */
 /*@
	 @ private invariant _prng != null;
	 @*/
	private java.util.Random _prng;
	
	/**
	 * <p>The modcount of this SkipList. It is used by
	 * SkipListIterators in order to check whether or not
	 * concurrent modifications have happened.</p>
	 */
	private int _modCount = 0;
	
	/**
	 * <p>The size of this SkipList.</p>
	 */
 /*@
	 @ private invariant _size >= 0;
	 @*/
	private int _size;

	/**
	 * An iterator class for SkipLists
	 */
	private class SkipListIterator implements Iterator {
		
		/**
		 * Initialize a new SkipListIterator which is set to the start of the SkipList.
		 */
		public SkipListIterator() {
			_node = (Object[])SkipList.this._head[1];
			_lastRet = null;
    }
		
		/**
		 * See superclass
		 */
		public boolean hasNext() {
			return _node != null;
    }
		
		/**
		 * Check whether or not the SkipList was modified by someone else
		 * and throw a ConcurrentModificationException if that is the case.
		 */
	 /*@
		 @ private behavior
		 @
		 @ // Make sure that an exception must be thrown when a modification
		 @ // has happened.
		 @ post _expectedModCount == SkipList.this._modCount;
		 @
		 @ signals (ConcurrentModificationException) _expectedModCount != SkipList.this._modCount;
		 @*/
		private void checkForModification() throws ConcurrentModificationException {
			if (_expectedModCount != SkipList.this._modCount) {
				throw new ConcurrentModificationException();
      }
    }
		
		/**
		 * See superclass
		 */
		public Object next() {
			checkForModification();
			try {
				Object result = _node[0];
				// advance
				_lastRet=_node;
				_node = (Object[]) _node[1];
				return result;
			}
			catch(NullPointerException exc) {
				// first check to see if the exception originated because the next element
				// was removed between the check and the array access.
				// Sun does it in AbstractList, so we'll do it too.
				checkForModification();
				throw new NoSuchElementException();
      }
    }
		
		/**
		 * See superclass
		 */
		public void remove() {
			if(_lastRet == null) {
				throw new IllegalStateException();
      }
			checkForModification();
			SkipList.this.remove(_lastRet[0]);
			_lastRet = null;
			_expectedModCount = SkipList.this._modCount;
    }
		
		/**
		 * The node that will be returned on the next next() call.
		 */
		private Object[] _node;
		
		/**
		 * The node that has been returned by the last next() call.
		 */
		private Object[] _lastRet;

		/**
		 * The modcount of the SkipList.
		 */
		private int _expectedModCount = SkipList.this._modCount;
		
		
  }
	
}

/*<copyright>Copyright (C) 1997-2001. This software is copyrighted by
the people and entities mentioned after the "@author" tags above, on
behalf of the JUTIL.ORG Project. The copyright is dated by the dates
after the "@date" tags above. All rights reserved.
This software is published under the terms of the JUTIL.ORG Software
License version 1.1 or later, a copy of which has been included with
this distribution in the LICENSE file, which can also be found at
http://org-jutil.sourceforge.net/LICENSE. This software is distributed WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the JUTIL.ORG Software
License for more details.
For more information, please see http://org-jutil.sourceforge.net/</copyright>*/