/*
 * Created on Mar 31, 2004
 *  
 */
package eightPuzzle;

import java.util.Vector;

/**
 * @author kgajos
 * 
 * Used to represent the open list (or the "fringe" as it is called in
 * AIMA) Ideally such a data structure should be implemented as a
 * heap-based priority queue but this simple implementation should
 * suffice for our purposes
 */
public class OpenList {

  protected Vector queue = new Vector();

  public OpenList() {
  }

  /**
   * Adds a new board to the open list and places it in the right
   * position in the queue based on its cost estimate; if a board that
   * looks like the new one already exists in the open list, it is
   * removed before the new one is added
   * 
   * @param board a board to be added
   */
  public void add(Board board) {
    if (contains(board))
      queue.remove(board);
    // append new element at the end if the queue is empty
    // or if the cost of the new board is larger than anything
    // we have seen
    if (queue.size() == 0
	|| board.getCostEstimate()
	>= ((Board) queue.lastElement()).getCostEstimate())
      queue.addElement(board);
    else { // find the right place to put it in
      for (int i = 0; i < queue.size(); i++) {
	if (board.getCostEstimate()
	    <= ((Board) queue.elementAt(i)).getCostEstimate()) {
	  queue.insertElementAt(board, i);
	  break;
	}
      }
    }
  }

  /**
   * Checks if the open list contains a board that looks just like the
   * one passed as an argument
   * 
   * @param board reference board
   * @return true if an identical board exists; false otherwise
   */
  public boolean contains(Board board) {
    return queue.contains(board);
  }

  public boolean isEmpty() {
    return queue.isEmpty();
  }
	
  /**
   * If the open list contains a board that looks just like the
   * argument, this method will tell you what cost estimate is
   * associated with that stored board
   * 
   * @param board reference board
   * @return the cost etimate associated with a corresponding board in the open list
   * or -1 if no corresponding board was found
   */
  public int getCostFor(Board board) {
    if (!contains(board))
      return -1;
    int index = queue.indexOf(board);
    return ((Board)queue.elementAt(index)).getCostEstimate();
  }

  /**
   * Returns the board with the smallest cost estimate and removes it from
   * the underlying data structure
   * 
   * @return the board with the smallest cost estimate or null if the list is
   *         empty
   */
  public Board removeFirst() {
    if (queue.size() == 0)
      return null;
    return (Board) queue.remove(0);
  }
	
  /**
   * Removes the board (or one that looks like it) from the open list
   * 
   * @param board board to be removed
   */
  public void remove(Board board) {
    queue.remove(board);
  }
}