/**********************************************************************
 * Class Node serves as a definition of the states or nodes that are
 * generated during search. Application-level classes that are derived
 * from class Node must implement the following methods:
 *
 * operator==   Determines if 2 objects represent the same state
 *
 * display()    "Displays" the object (to cout)
 *
 * Expand()     Expands the node by generating all of its
 *              successors. The successors are stored in a list object
 *              (NList).
 **********************************************************************/
class Node
{
public:
  Node();
  void SetParent(Node* par) {parent = par;}
  Node* GetParent(void) const {return parent;}
  void SetDepth(unsigned d) {depth = d;}
  unsigned GetDepth(void) const {return depth;}
  virtual int operator<(const Node& other) const
    {return depth<other.depth;}

  virtual int operator==(const Node&) const = 0;
  virtual void display(void) const = 0;
  virtual NList& Expand(int) = 0;

private:
  Node* parent;
  unsigned depth;
};

/**********************************************************************
 * Class BestNode is derived from the class Node and defines nodes
 * that are generated during a heuristic search. These nodes are meant
 * to be placed in a sorted list based on their F-values; operator< is
 * overloaded to compare these, and so can be used in sorting/list
 * insertion. F is the sum of two costs: the node's depth (cost from
 * the start node to this node) and H, a heuristic estimate of getting
 * from this node to the goal. Application-level classes that are derived
 * from class BestNode must implement the following methods:
 *
 * EvalBoard()   This computes the heuristic estimate, which would
 *               then be set by SetH().
 **********************************************************************/
class BestNode : public Node
{
public:
  BestNode();
  int GetH(void) {return h;}
  int GetF(void) {return depth+h;}

  virtual int operator<(const Node& other) const
    {return GetF()<other.GetF();}

protected:
  virtual int EvalBoard(void) const = 0;
  void SetH(void) {h = EvalBoard();}

private:
  int h;
};

/**********************************************************************
 * An incomplete suggestion of a node class for the 8 puzzle
 **********************************************************************/
class PuzzleNode : public BestNode
{
public:
  PuzzleNode(const char*, int emptyX, int emptyY);
  PuzzleNode(const char*, int oldX, int oldY, int newX, int newY);

  // These three are the virtual functions which must be implemented
  int operator==(const PuzzleNode& other) const
    {return CompareBoard(other.board);}
  void display(void) const;
  NList* Expand(int);

protected:
  // These move the empty tile (the operators)
  PuzzleNode* MoveLeft(void) const;
  PuzzleNode* MoveRight(void) const;
  PuzzleNode* MoveUp(void) const;
  PuzzleNode* MoveDown(void) const;

  int CompareBoard(const char[3][3]) const;
  int EvalBoard(void) const;

private:
  int x, y;            // Empty tile location
  char board[3][3];
};


/**********************************************************************
 * Search is a base class for any kind of search (uninformed or
 * heuristic).  Other searches (breadth-first, depth-first) would be
 * subclassed from this. The behavior of the subclass search would be
 * determined by the implementation of the virtual method
 * add(). Search processes objects of class Node and its subclasses.
 * Application-level classes that are derived from class Search must
 * implement the following methods: 
 *
 * isGoal()  Determines if a node is a goal node.
 * 
 * add()     Adds the node to whatever internal data structure(s) are
 *           used by the particular search subclass.
 **********************************************************************/
class Search
{
public:
  Search(int maxB, Node* start, Node* goal) : b(maxB), goalNode(goal)
    {add(start);}
  virtual ~Search() {clear();}
  virtual int isGoal(const Node*) = 0;

  int generate(void);     // Generate the solution
  void display() const;   // Display the solution (to cout)

protected:
  void clear(void);       // Clear all storage
  virtual int add(Node*) = 0;

private:
  int b;
  Node* goalNode;
};


/**********************************************************************
 * An incomplete, sketchy suggestion of an A* search subclass 
 **********************************************************************/
class AStar : public Search
{
private:
  SortedNList open, closed;   // A sorted list of Nodes
};

/**********************************************************************
 * An incomplete, sketchy suggestion of an 8 puzzle class
 **********************************************************************/
class Puzzle : public AStar
{
public:
  Puzzle(PNode* start, PNode* goal);
};