arrayheap.java

Java数据结构开发包

  }
  

  // instance method(s) from Container
  
  /**
   * time complexity = worst-case O(1)
   */
  public Container newContainer () { 
    return new ArrayHeap(comp_,shrink_); 
  }

  
  /**
   * time complexity = worst-case O(1)
   */
  public Object replaceElement (Accessor a, Object elem) {
    AHLocator ahLoc = checkContained(a);

    // replace the element
    Object returnElem = ahLoc.element();
    ahLoc.setElement(elem);
    elementsArray_ = null;

    return returnElem;
  }

  
  // instance method(s) from InspectableContainer

  /**
   * time complexity = worst-case O(1)
   */
  public boolean contains (Accessor a) {
    if (a == null)
      throw new InvalidAccessorException("The accessor is null.");
    else if (!(a instanceof AHLocator))
      return false;
    else
      return ((AHLocator)a).container() == this;
  }


  /**
   * Cached for constant factor efficiency. If the container has not
   * been structurally modified and no element 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 elements () {
    if (elementsArray_ == null) {
      elementsArray_ = new Object[size_];
      for (int i = 1; i <= size_; i++)
	elementsArray_[i-1] = array_[i].element();
    }
    return new ArrayObjectIterator(elementsArray_);
  }

  
  /**
   * time complexity = worst-case O(1)
   */
  public boolean isEmpty () {
    return size_ == 0;
  }

  
  /**
   * time complexity = worst-case O(1)
   */
  public int size () {
    return size_;
  }


  // instance method(s) from java.lang.Object
  
  /**
   * time complexity = worst-case O(n)
   */
  public String toString () {
    return ToString.stringfor(this);
  }


  // non-interface instance method(s)

  /**
   * Creates an InspectableBinaryTree snapshot view of the heap.
   *
   * time complexity = worst-case O(n)
   *
   * @return the inspectable binary tree snapshot view
   * @exception EmptyContainerException if the prority queue is empty
   */
  public InspectableBinaryTree inspectableBinaryTree () {
    Sequence s = new NodeSequence();
    BinaryTree bt = new NodeBinaryTree();
    s.insertLast(bt.root());
    for (int i = 1; i < size_+1; i++) {
      Position p = (Position)s.removeFirst();
      bt.replaceElement(p,array_[i]);
      bt.expandExternal(p);
      s.insertLast(bt.leftChild(p));
      s.insertLast(bt.rightChild(p));
    }
//     while (!s.isEmpty()) {
//       Position p = (Position)s.removeFirst();
//       bt.replaceElement(p,Container.NULL);
//     }
    return bt;
  }

  
  /**
   * Compares the key at index i1 with that at index i2.
   */
  private int compare (int i1, int i2) {
    return comp_.compare(array_[i1].key(),array_[i2].key());
  }

  
  /**
   * Swaps the locators at index i1 with the one at index i2.
   */
  private void swap (int i1, int i2) {
    AHLocator temp = array_[i1];
    array_[i1] = array_[i2];
    array_[i1].setIndex(i1);
    array_[i2] = temp;
    array_[i2].setIndex(i2);
  }

  
  /**
   * Perform the upheap operation.  Swaps a (key,element) pair up
   * until the heap property has been restored.
   */
  private void upheap (int index) {
    array_[0] = array_[index];   // to avoid testing index > 1
    // while we are not at the root, and we are smaller than our
    // parent (at floor(index/2)), then swap us up and continue at the
    // higher level
    while (compare(index,index/2) < 0) {
      swap(index,index/2);
      index /= 2;
    }
    array_[0] = null;
  }

  
  /**
   * Performs the downheap operation.  Swaps a (key,element) pair down
   * until the heap property has been restored.
   */
  private void downheap (int index) {
    boolean even = (size_%2 == 0);
    boolean again = true;
    int candidate;

    if (even) {
      // to avoid the special case of the last leaf being a left child
      array_[size_+1] = array_[size_];
      size_++;
    }
      
    // While we are not at a leaf, and we are larger than either of our
    // children, sink down.  We may be at a leaf when going to the
    // right child would put us past the end of the array
    while (again && index <= (size_-1)/2) {
      int left = 2*index;   // left child index
      int right = 2*index+1;   // right child index
      if (compare(left,right) > 0)
	candidate = right;   // right is smaller than left
      else
	candidate = left;    // left is smaller than or equal to right
      if (compare(index,candidate) > 0) { 
	// candidate is smaller than index; it should be higher
	swap(index,candidate);   
	index = candidate;
      }
      else
	// candidate is greater than or equal to index, so we are done
	again = false;
    }

    if (even) {
      array_[size_] = null;
      size_--;
    } 
  }

  
  /** 
   * Makes sure the array is large enough; if not, double the capacity.
   */
  private void ensureCapacity (int size) {
    if (size >= array_.length) {
      if (array_.length <= maxGrowableCapacity) {
	AHLocator [] newArray = new AHLocator[array_.length*2];
	System.arraycopy(array_,1,newArray,1,array_.length-1);
	array_ = newArray;
      }
      else
	throw new FullContainerException("Maximum capacity of the priority"
					 +" queue exceeded.");
    }
  }

  
  /** 
   * Makes sure the load factor of the array is greater than
   * shrinkLoadFactor; if not, halve the capacity.
   */
  private void ensureLoadFactor () {
//     System.out.println((size_+1)+" "+array_.length+" "
// 		       +((float)(size_+1)/(float)array_.length));
//     System.out.flush();
    if (shrink_	&& size_+1 <= array_.length/shrinkLoadFactor) {
      // reduce the size
      AHLocator [] newArray = new AHLocator[array_.length/2];
      // copy the old array
      System.arraycopy(array_,1,newArray,1,size_);
      // throw away the old array and replace it with the new
      array_ = newArray;
    }
  }

  
  /**
   * Throws an exception if the container is empty.
   */
  private void checkEmpty () {
    if (isEmpty())
      throw new EmptyContainerException("ArrayHeap empty.");
  }

  
  /**
   * Throws an exception if key cannot be used by this container.
   */
  private void checkKey (Object key) {
    if (!comp_.isComparable(key))
      throw new InvalidKeyException(key+" not comparable by "+comp_+".");
  }

  
  /**
   * Throws an exception if key cannot be used by this container.
   */
  private AHLocator checkContained (Accessor a) {
    if (a == null)
      throw new InvalidAccessorException("The accessor is null.");
    else if (a instanceof AHLocator) {
      AHLocator ahLoc = (AHLocator)a;    
      if (ahLoc.container() == this)
	return ahLoc;
      else
	throw new InvalidAccessorException
	  (a+" not contained in this ArrayHeap.");
    }
    else
      throw new InvalidAccessorException("The accessor must extend"+
					 " AHLocator.");
  }


  // nested class(es)
  
  /**
   * The locator class for use within this heap.
   */
  private static class AHLocator implements Locator {

    // instance variable(s)
    
    private Object key_;
    private Object elem_;
    private int index_;
    private ArrayHeap container_;
    
    // constructor(s)

    private AHLocator (Object key, Object elem, int index,
		       ArrayHeap container) {
      key_ = key;
      elem_ = elem;
      index_ = index;
      container_ = container;
    }

    // instance method(s) from Locator

    public Object key () {
      return key_;
    }

    // instance method(s) from Accessor
    
    public Object element () {
      return elem_;
    }

    // instance method(s) from java.lang.Object
  
    public String toString () {
      return ToString.stringfor(this);
    }

    // non-interface instance methods
    
    private int index () {
      return index_;
    }
    
    private ArrayHeap container () {
      return container_;
    }

    private void setKey (Object key) {
      key_ = key;
    }
    
    private void setElement (Object elem) {
      elem_ = elem;
    }

    private void setIndex (int index) {
      index_ = index;
    }

    private void resetContainer () {
      container_ = null;
    }
    
  }   // end of class AHLocator
  
}   // end of class ArrayHeap