package maze;

import java.util.NoSuchElementException;
import java.util.HashMap;
import java.util.Iterator;
import graph.ReachableSet;
import graph.Handle;
import graph.MultiNode;

/** A reachable set for board mazes. */
public class ReachableHash implements ReachableSet {

  /** The hash map of MultiNodes, using Boards as keys. */
  private HashMap<Board, MultiNode> reach;

  /** Construct a reachable set. */
  public ReachableHash() {
    reach = (HashMap<Board, MultiNode>) new HashMap();
  }

  /** Clear the  reachable set. */
  public void clear() {
     reach.clear();
  }

  /** Gets the number of elements in the set. 
   *  @return size of set. */
  public int size() {
    return reach.size();
  }

  /** Returns the item in the specified position in the reachable set.
   *  This is an O(n) operation, since we need to iterate through the set
   *  to get to the particular index.
   *  @param index the index of the item to return.
   *  @return the item at the specified position in this set.
   *  @throws IndexOutOfBoundsException if the index is out of range. */
  public MultiNode get(int index) {
    if (index < 0 || index >= reach.size())
      throw new IndexOutOfBoundsException("Index: "+index);
    MultiNode res = null;
    Iterator<MultiNode> it = reach.values().iterator();
    int count = index;
    while (it.hasNext()) {
      res = it.next();
      if (count == 0) {
        break;
      }
      count--;
    }
    return (MultiNode) res;
  }


  /** Gets a matching multinode from within the table (if any).
   *  @param m the multinode to match.
   *  @return the matching multinode (or null). */
  public MultiNode get(MultiNode m) {
    return reach.get((Board) m.getData());
  }

  /** Adds an item to the reachable set if it is not already
   *  present.  This will NOT add duplicate items to the list.
   *  Duplicate items are identified in terms of the
   *  to the argument m's equals method.
   *  @param m the item to be added.
   *  @return true if the item is added, otherwise false.  */
  public boolean add(MultiNode m) {
    boolean res = (get(m) == null);
    if (res) {
      reach.put((Board) m.getData(), m);
    }
    return res;
  }

  /** Adds an item to the reachable set if it is not already
   *  present.  This will NOT add duplicate items to the list.
   *  Duplicate items are identified in terms of the
   *  to the argument m's equals method.  The node prev is added
   *  without duplicates to the backwards links of m, or to the
   *  node which matches m that is already on the list.
   *  If prev == null it is ignored.
   *  @param prev an item which has a forward link to the
   *         new item m.
   *  @param m the item to be added.
   *  @return true if the item is added, otherwise false.  */
  public boolean add(MultiNode prev, MultiNode m) {
    MultiNode r = get(m);
    if (r == null) {
      reach.put((Board) m.getData(), m);
      m.addBwd(prev);
    } else {
      r.addBwd(prev);
    }
    return (r==null);
  }
  
  /** Search the table for any multinode which satisfies the handle.
   *  @param h the handle for recognizing goal states.
   *  @return the first multinode found to satisfy the handle (or null) */
  public MultiNode find(Handle h) {
    
    MultiNode res = null;
    Iterator<MultiNode> it = reach.values().iterator();
    while (it.hasNext()) {
      res = it.next();
      if (h.matches(res.getData()))
        return res;
    }
    return null;
  }

  /** An iterator over all multinodes in the set.
   *  @return the iterator. */
  public Iterator<MultiNode> iterator() {
    return reach.values().iterator();
  }

}