skiplistpq.java

一个关于java 的常用工具包

package org.jutil.java.collections;

import java.util.Comparator;
import java.util.Iterator;

/**
 * <p>A {@link org.jutil.java.collections.SkipList SkipList} based priority queue</p>
 *
 * @path    $Source: /cvsroot/org-jutil/jutil.org/src/org/jutil/java/collections/SkipListPQ.java,v $
 * @version $Revision: 1.4 $
 * @date    $Date: 2002/07/21 10:01:32 $
 * @state   $State: Exp $
 * @author  Tom Schrijvers
 * @author  Marko van Dooren
 * @release $Name:  $
 */
public class SkipListPQ extends AbstractPriorityQueue {

	/* The revision of this class */
	public final static String CVS_REVISION ="$Revision: 1.4 $";
		
	/**
	 * Initialize a new SkipListPQ with the given comparator.
	 *
	 * @param comparator
	 *        The comparator that is used to determine the order
	 *        of the added elements.
	 */
 /*@
	 @ public behavior
	 @
	 @ post size() == 0;
	 @ post getComparator() == comparator;
	 @*/
	public SkipListPQ(Comparator comparator) {
		list = new SkipList(10,comparator,0.25f);
	}

	/**
	 * <p>See superclass.</p>
	 *
	 * <p>average: <b>O(log(n))</b></p>
	 * <p>worst case: <b>O(n)</b></p>
	 */
	protected void addImpl(Object element) {
		list.add(element);
	}

	/**
	 * <p>See superclass.</p>
	 *
	 * <p><b>O(1)</b></p>
	 */
	public Object min() {
		return list.getFirst();
	}

	/**
	 * <p>See superclass.</p>
	 *
	 * <p><b>O(1)</b></p>
	 */
	public Object pop() {
		Object result = list.getFirst();
		list.removeFirst();
		return result;
	}

	/**
	 * <p>See superclass.</p>
	 */
	public int nbExplicitOccurrences(Object element) {
		return Collections.nbExplicitOccurrences(element, list);
	}

	/**
	 * <p>See superclass.</p>
	 */
	public int size() {
		return list.size();
	}

	/**
	 * <p>See superclass.</p>
	 */
	public Comparator getComparator() {
		return list.getComparator();
	}

	/**
	 * <p>See superclass.</p>
	 */
	public void clear() {
		list.clear();
	}

	/**
	  * See superclass.
	  */
	public Iterator iterator() {
		return list.iterator();
	}

	/**
	 * The SkipList that will hold all elements.
	 */
 /*@
	 @ private invariant list != null;
	 @*/
	private final SkipList list;
}
/*
 * <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>
 */