arrayheap.java

Java数据结构开发包

/*
  Copyright (c) 1999, 2000 Brown University, Providence, RI
  
                            All Rights Reserved
  
  Permission to use, copy, modify, and distribute this software and its
  documentation for any purpose other than its incorporation into a
  commercial product is hereby granted without fee, provided that the
  above copyright notice appear in all copies and that both that
  copyright notice and this permission notice appear in supporting
  documentation, and that the name of Brown University not be used in
  advertising or publicity pertaining to distribution of the software
  without specific, written prior permission.
  
  BROWN UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR ANY PARTICULAR PURPOSE.  IN NO EVENT SHALL BROWN
  UNIVERSITY BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  PERFORMANCE OF THIS SOFTWARE.
*/

package jdsl.core.ref;

import java.io.Serializable;
import jdsl.core.api.*;



/**
 * An array implementation of a heap.<p>
 *
 * The number of elements that can be stored in the array or in the
 * heap is called capacity.  The capacity of the heap is always the
 * capacity of the array minus one.  The initial capacity of the array
 * is the public constant defaultInitialCapacity (or the capacity
 * specified in the constructor); the maximum capacity of the array is
 * 2^30.  The capacity of the array is doubled when needed.  The load
 * factor of the array is the ratio of the number of elements stored
 * in the array to the capacity of the array.  If array-shrinking is
 * specified at construction time, the capacity of the array is halved
 * when the load factor of the array is less than or equal to 0.25.<p>
 *
 * A binary heap such as this one has O(log n) insert, remove, and
 * replaceKey, and O(1) min.<p>
 *
 * Internal ordering is maintained according to the order of the given
 * Comparator.  Of the Comparator methods, only
 * <code>compare(.)</code> is used.
 *
 * @version JDSL 2.1.1 
 * 
 * @author Mark Handy (mdh)
 * @author Benoit Hudson (bh)
 * @author Luca Vismara (lv)
 *
 * @see Comparator
 */
public class ArrayHeap implements PriorityQueue, Serializable {

  // class variable(s)

  public static final int defaultInitialCapacity = 8;
  private static final int maxGrowableCapacity = 1 << 29;  // = 2^29
  private static final int shrinkLoadFactor = 4;

  
  // instance variable(s)

  /**
   * @serial
   */
  private AHLocator [] array_;

  /**
   * @serial
   */
  private int size_;

  /**
   * The comparator used to prioritize the keys.
   * @serial
   */
  private Comparator comp_;

  /**
   * @serial
   */
  private boolean shrink_;

  /**
   * @serial
   */
  private Locator [] locatorsArray_ = null;

  /**
   * @serial
   */
  private Object [] keysArray_ = null;

  /**
   * @serial
   */
  private Object [] elementsArray_ = null;
  
  
  // constructor(s)
  
  /**
   * Creates a new heap.  The initial capacity of the array is of
   * defaultInitialCapacity elements.  The capacity is doubled when
   * needed, and halved when the load factor of the array is less than
   * or equal to 0.25.
   *
   * @param comp the comparator to be used for comparing keys
   *
   * @exception IllegalArgumentException if comp is null
   */
  public ArrayHeap (Comparator comp) throws IllegalArgumentException {
    init(comp,defaultInitialCapacity,true);
  }

  
  /**
   * Creates a new heap.  The initial capacity of the array is of
   * defaultInitialCapacity elements.  The capacity is doubled when
   * needed, and possibly halved when the load factor of the array is
   * less than or equal to 0.25.
   *
   * @param comp the comparator to be used for comparing keys
   * @param shrink indicates whether the array should be halved when
   * the load factor of the array is less than or equal to 0.25.
   *
   * @exception IllegalArgumentException if comp is null
   */
  public ArrayHeap (Comparator comp, boolean shrink)
    throws IllegalArgumentException {
    init(comp,defaultInitialCapacity,shrink);
  }

  
  /**
   * Creates a new heap.  The capacity is doubled when needed, and
   * possibly halved when the load factor of the array is less than or
   * equal to 0.25.
   *
   * @param comp the comparator to be used for comparing keys
   * @param initialCapacity the initial capacity of the array; must be
   * a power of 2 no greater than 2^30
   * @param shrink indicates whether the array should be halved when
   * the load factor of the array is less than or equal to 0.25.
   *
   * @exception IllegalArgumentException if comp is null or
   * initialCapacity is greater than 2^30
   */
  public ArrayHeap (Comparator comp, int initialCapacity, boolean shrink)
    throws IllegalArgumentException {
    if (initialCapacity > 2*maxGrowableCapacity)
      throw new IllegalArgumentException("The initial capacity must be no"
					 +" greater than 2^30.");
    else {
      // approximate initialCapacity with the closest power of 2
      // greater than initialCapacity; this could be done more
      // efficiently with a binary search on an array storing all the
      // powers of 2 between 1 and 2^30
      int ic = 1;
      while (ic < initialCapacity)
	ic <<= 1;
      init(comp,ic,shrink);
    }
  }

  
  /**
   * A service method for the constructors.
   */
  private void init (Comparator comp, int initialCapacity, boolean shrink)
    throws IllegalArgumentException {
    if (comp == null)
      throw new IllegalArgumentException("The comparator is null.");
    else
      comp_ = comp;
    array_ = new AHLocator[initialCapacity];
    size_ = 0;
    shrink_ = shrink;
  }


  // instance method(s) from PriorityQueue

  /**
   * time complexity = worst-case O(1)
   */
  public Locator min () {
    checkEmpty();
    return array_[1];
  }


  /**
   * If array-shrinking is specified at construction time and the load
   * factor of the array is 0.25 after the removal, the capacity of
   * the array is halved by copying the elements into a new array.
   *
   * time complexity = worst-case O(log n) if array-shrinking is
   * specified at construction time, amortized O(log n) otherwise
   */
  public Object removeMin () {
    checkEmpty();

    // remove the locator
    AHLocator ahLoc = array_[1];
    ahLoc.resetContainer();

    size_--;
    if(!isEmpty()) {
      // fix the heap property: take the last element and put it
      // first, then downheap
      swap(1,size_+1);
      downheap(1);
    }
    array_[size_+1] = null;
    ensureLoadFactor();
    locatorsArray_ = null;
    keysArray_ = null;
    elementsArray_ = null;

    return ahLoc.element();
  }

  
  // instance method(s) from KeyBasedContainer

  /**
   * If the array is full, its capacity is doubled before the
   * insertion by copying the elements into a new array.
   *
   * time complexity = amortized O(log n)
   */
  public Locator insert (Object key, Object elem) {
    checkKey(key);
    ensureCapacity(size_+1);
    size_++;
    AHLocator ahLoc = new AHLocator(key,elem,size_,this);
    array_[size_] = ahLoc;
    upheap(size_);
    locatorsArray_ = null;
    keysArray_ = null;
    elementsArray_ = null;
    return ahLoc;
  }

  
  /**
   * If array-shrinking is specified at construction time and the load
   * factor of the array is 0.25 after the removal, the capacity of
   * the array is halved by copying the elements into a new array.
   *
   * time complexity = worst-case O(log n) if array-shrinking is
   * specified at construction time, amortized O(log n) otherwise
   */
  public void remove (Locator loc) {
    AHLocator ahLoc = checkContained(loc);
    int index = ahLoc.index();
    int oldsize = size_;

    // remove the old locator from the heap
    size_--;
    ahLoc.resetContainer();

    // now restore the heap properties
    if(index != oldsize) {
      // move the last-inserted key up, and put it in its right spot
      // (either upheap or downheap will do nothing)
      swap(index,oldsize);
      upheap(index);
      downheap(index);
    }
    array_[oldsize] = null;
    ensureLoadFactor();
    locatorsArray_ = null;
    keysArray_ = null;
    elementsArray_ = null;
  }

  
  /**
   * time complexity = worst-case O(log n)
   */
  public Object replaceKey (Locator loc, Object key) {
    AHLocator ahLoc = checkContained(loc);
    checkKey(key);
    int index = ahLoc.index();

    // replace the key
    Object returnKey = ahLoc.key();
    ahLoc.setKey(key);

    // restore the heap property (either upheap or downheap will do nothing)
    upheap(index);
    downheap(index);
    keysArray_ = null;

    return returnKey;
  }


  // instance method(s) from InspectableKeyBasedContainer

  /**
   * Cached for constant factor efficiency. If the container has not
   * been structurally modified and no key has been modified since the
   * last time this method was invoked, there is no need to copy the
   * elements in a new array.
   *
   * time complexity = worst-case O(n)
   */
  public ObjectIterator keys () {
    if (keysArray_ == null) {
      keysArray_ = new Object[size_];
      for (int i = 1; i <= size_; i++)
	keysArray_[i-1] = array_[i].key();
    }
    return new ArrayObjectIterator(keysArray_);
  }

  
  /**
   * Cached for constant factor efficiency. If the container has not
   * been structurally modified since the last time this method was
   * invoked, there is no need to copy the locators in a new array.
   *
   * time complexity = worst-case O(n)
   */
  public LocatorIterator locators () {
    if (locatorsArray_ == null) {
      locatorsArray_ = new Locator[size_];
      System.arraycopy(array_,1,locatorsArray_,0,size_);
    }
    return new ArrayLocatorIterator(locatorsArray_);