arrayheap.java

Standord Classifier实现了一个基于Java的最大熵分类器。用于模式识别

package edu.stanford.nlp.util;

import java.util.*;

/**
 *  ArrayHeap:
 *
 *  Heap implementation.  Values are all implicit in the comparator
 *  passed in on construction.  Decrease key is supported, though only
 *  lg(n).  Unlike the previous implementation of this class, this
 *  heap interprets the addition of an existing element as a "change
 *  key" which gets ignored unless it actually turns out to be a
 *  decrease key.  Note that in this implementation, changing the key
 *  of an object should trigger a change in the comparator's ordering
 *  for that object, but should NOT change the equality of that
 *  object.
 *
 *  @author Dan Klein
 *  @author Christopher Manning
 *  @version 1.2, 07/31/02
 */
public class ArrayHeap extends AbstractSet implements Heap {

  /**
   * A <code>HeapEntry</code> stores an object in the heap along with
   * its current location (array position) in the heap.
   *
   * @author <a href="mailto:[e-mail]">Dan Klein</a>
   * @version 1.2
   */
  private final class HeapEntry {
    public Object object;
    public int index;
  }

  /**
   * <code>indexToEntry</code> maps linear array locations (not
   * priorities) to heap entries.
   */
  private ArrayList indexToEntry;
  /**
   * <code>objectToEntry</code> maps heap objects to their heap
   * entries.
   */
  private Map objectToEntry;
  /**
   * <code>cmp</code> is the comparator passed on construction.
   */
  private Comparator cmp;

  // Primitive Heap Operations

  private int parent(final int index) {
    return (index-1)/2;
  }

  private int leftChild(final int index) {
    return index*2+1;
  }

  private int rightChild(final int index) {
    return index*2+2;
  }

  private HeapEntry parent(HeapEntry entry) {
    int index = entry.index;
    return (index > 0 ? (HeapEntry)indexToEntry.get((index-1)/2) : null);
  }

  private HeapEntry leftChild(HeapEntry entry) {
    int index = entry.index;
    int leftIndex = index*2+1;
    return (leftIndex < size() ? (HeapEntry)indexToEntry.get(leftIndex) : null);
  }

  private HeapEntry rightChild(HeapEntry entry) {
    int index = entry.index;
    int rightIndex = index*2+2;
    return (rightIndex < size() ? (HeapEntry)indexToEntry.get(rightIndex) : null);
  }

  private int compare(HeapEntry entryA, HeapEntry entryB) {
    return cmp.compare(entryA.object, entryB.object);
  }

  private void swap(HeapEntry entryA, HeapEntry entryB) {
    int indexA = entryA.index;
    int indexB = entryB.index;
    entryA.index = indexB;
    entryB.index = indexA;
    indexToEntry.set(indexA,entryB);
    indexToEntry.set(indexB,entryA);
  }

  /**
   * Remove the last element of the heap (last in the index array).
   * Do not call this on other entries; the last entry is only passed
   * in for efficiency.
   *
   * @param entry the last entry in the array
   */
  private void removeLast(HeapEntry entry) {
    indexToEntry.remove(entry.index);
    objectToEntry.remove(entry.object);
  }

  private HeapEntry getEntry(Object o) {
    HeapEntry entry = (HeapEntry)objectToEntry.get(o);
    if (entry == null) {
      entry = new HeapEntry();
      entry.index = size();
      entry.object = o;
      indexToEntry.add(entry);
      objectToEntry.put(o,entry);
    }
    return entry;
  }

  /** iterative heapify up: move item o at index up until correctly placed
   */
  private int heapifyUp(HeapEntry entry) {
    int numSwaps = 0;
    while (true) {
      if (entry.index == 0)
	break;
      HeapEntry parentEntry = parent(entry);
      if (compare(entry,parentEntry) >= 0)
	break;
      numSwaps++;
      swap(entry,parentEntry);
    }
    return numSwaps;
  }

  /** On the assumption that
   *  leftChild(entry) and rightChild(entry) satisfy the heap property,
   *  make sure that the heap at entry satisfies this property by possibly
   *  percolating the element o downwards.  I've replaced the obvious 
   *  recursive formulation with an iterative one to gain (marginal) speed
   */
  private void heapifyDown(HeapEntry entry) {
    int size = size();

    HeapEntry currentEntry = entry;
    HeapEntry minEntry = null;

    do {
      minEntry = currentEntry;

      HeapEntry leftEntry = leftChild(currentEntry);
      if (leftEntry != null) {
	if (compare(minEntry, leftEntry) > 0) {
	  minEntry = leftEntry;
	}
      }

      HeapEntry rightEntry = rightChild(currentEntry);
      if (rightEntry != null) {
	if (compare(minEntry, rightEntry) > 0) {
	  minEntry = rightEntry;
	}
      }

      if (minEntry != currentEntry) {
	// Swap min and current
	swap(minEntry, currentEntry);
	// at start of next loop, we set currentIndex to largestIndex
	// this indexation now holds current, so it is unchanged
      }
    } while (minEntry != currentEntry);
    // System.err.println("Done with heapify down");
    // verify();
  }


  /**
   * Finds the object with the minimum key, removes it from the heap,
   * and returns it.
   *
   * @return the object with minimum key
   */
  public Object extractMin() {
    if (isEmpty())
      throw new NoSuchElementException();
    HeapEntry minEntry = (HeapEntry)indexToEntry.get(0);
    int lastIndex = size()-1;
    if (lastIndex > 0) {
      HeapEntry lastEntry = (HeapEntry)indexToEntry.get(lastIndex);
      swap(lastEntry,minEntry);
      removeLast(minEntry);
      heapifyDown(lastEntry);
    } else {
      removeLast(minEntry);
    }
    return minEntry.object;
  }

  /**
   * Finds the object with the minimum key and returns it, without
   * modifying the heap.
   *
   * @return the object with minimum key
   */
  public Object min() {
    HeapEntry minEntry = (HeapEntry)indexToEntry.get(0);
    return minEntry.object;
  }

  /**
   * Adds an object to the heap.  If the object is already in the heap
   * with worse score, this acts as a decrease key.  If the object is
   * already present, with better score, it will NOT cause an
   * "increase key".
   *
   * @param o an <code>Object</code> value
   */
  public boolean add(Object o) {
    decreaseKey(o);
    return true;
  }

  /**
   * Changes the position of an element o in the heap based on a
   * change in the ordering of o.  If o's key has actually increased,
   * it will do nothing, particularly not an "increase key".
   *
   * @param o an <code>Object</code> value
   * @return the number of swaps done on decrease.
   */
  public int decreaseKey(Object o) {
    HeapEntry entry = getEntry(o);
    if (o != entry.object)
      if (cmp.compare(o, entry.object) < 0)
	entry.object = o;
    return heapifyUp(entry);
  }

  /**
   * Checks if the heap is empty.
   *
   * @return a <code>boolean</code> value
   */
  public boolean isEmpty() {
    return indexToEntry.isEmpty();
  }

  /**
   * Get the number of elements in the heap.
   *
   * @return an <code>int</code> value
   */
  public int size() {
    return indexToEntry.size();
  }

  public Iterator iterator() {
    Heap tempHeap = new ArrayHeap(cmp, size());
    List tempList = new ArrayList(size());
    for (Iterator i = objectToEntry.keySet().iterator(); i.hasNext();) {
      tempHeap.add(i.next());
    }
    while (! tempHeap.isEmpty()) {
      tempList.add(tempHeap.extractMin());
    }
    return tempList.iterator();
  }

  /**
   * Clears the heap.  Equivalent to calling extractMin repeatedly
   * (but faster).
   *
   */
  public void clear() {
    indexToEntry.clear();
    objectToEntry.clear(); 
  }

  public void dump() {
    for (int j = 0; j < indexToEntry.size(); j++) {
      System.err.println(" "+j+" "+((Scored)((HeapEntry)indexToEntry.get(j)).object).score());
    }
  }

  public void verify() {
    for (int i = 0; i < indexToEntry.size(); i++) {
      if (i != 0) {
	// check ordering
	if (compare((HeapEntry)indexToEntry.get(i), (HeapEntry)indexToEntry.get(parent(i))) < 0) {
	  System.err.println("Error in the ordering of the heap! ("+i+")");
	  dump();
	  System.exit(0);
	}
      }
      // check placement
      if (i != ((HeapEntry)indexToEntry.get(i)).index)
	System.err.println("Error in placement in the heap!");
    }
  }

  /** The objects added will be ordered using the <code>Comparator</code>.
   */
  public ArrayHeap(Comparator cmp) {
    this.cmp = cmp;
    indexToEntry = new ArrayList();
    objectToEntry = new HashMap();
  }

  public ArrayHeap(Comparator cmp, int initCapacity) {
    this.cmp = cmp;
    indexToEntry = new ArrayList(initCapacity);
    objectToEntry = new HashMap(initCapacity);
  }

}