// GuestTree.h

#include "bool.h"
#include "GuestInfo.h"

struct TreeNode;
typedef TreeNode* NodePtr;

class GuestTree {
public:
  // ABSTRACTLY: a tree of guest
  // information records

  // Notation:
  // ValidNode(n) means added to self
  //   via BuildRoot, AppendLeft, or
  //   AppendRight
  // Contents(n) is information in node n
  // HasLeftChild(n) means
  //  node n has some left child, LC,
  //  AND ValidNode(LC)
  // HasRightChild(n) means
  //  node n has some right child, RC,
  //  AND ValidNode(RC)
  // IsLeaf(n) == NOT HasLeftChild(n)
  //              AND NOT HasRightChild(n)

GuestTree();
  // MODIFIES: self
  // POST: self is the empty tree

GuestTree(const GuestTree & gt);
  // MODIFIES: self
  // POST: self == gt && self and gt
  // do not share any storage.

~GuestTree();
  // MODIFIES: self
  // POST: all the storage for nodes
  // is returned to the system.

GuestTree& operator = (
		   const GuestTree & gt);
  // MODIFIES: self
  // POST: self == gt && self and gt
  // do not share any storage.

Boolean IsEmpty() const;
  // POST: FCTVAL == (tree has no nodes)

void BuildRoot( const GuestInfo & g );
  // PRE:  IsEmpty()
  // MODIFIES: self
  // POST: Tree has root node, call it R
  // && Contents(R) == g && IsLeaf(R)

NodePtr Root() const;
  // POST: FCTVAL == NULL, if IsEmpty()
  //    == pointer to root node, otherwise

void SetRoot(NodePtr ptr);
  // MODIFIES: self
  // POST: the root node of self is *ptr

#include "GuestTree.pri"
};


// The following manipulate nodes
// through pointers of type NodePtr

extern void AppendLeft( NodePtr ptr,
                 const GuestInfo & g );
  // PRE:  ValidNode(*ptr)
  // MODIFIES: *ptr
  // POST: The left child of *ptr, LC,
  // is a new node && ValidNode(LC)
  // && IsLeaf(LC) && Contents(LC) == g
  // NOTE: dangling pointers may occur
  // if HasLeftChild(*ptr<entry>)

extern void AppendRight( NodePtr ptr,
                  const GuestInfo & g );
  // PRE:  ValidNode(*ptr)
  // MODIFIES: *ptr 
  // POST: The right child of *ptr, RC,
  // is a new node && ValidNode(RC)
  // &&  IsLeaf(RC) && Contents(RC) == g
  // NOTE: Dangling pointers may occur
  // if HasRightChild(*ptr<entry>)

extern GuestInfo Data(NodePtr ptr);
  // PRE:  ValidNode(*ptr)
  // POST: FCTVAL == Contents(*ptr)

extern void Store( NodePtr ptr,
                   const GuestInfo & g );
  // PRE:  ValidNode(*ptr)
  // MODIFIES: *ptr
  // POST: Contents(*ptr) == g

extern NodePtr LChild(NodePtr ptr);
  // PRE:  ValidNode(*ptr)
  // POST: FCTVAL == NULL,
  //          if NOT HasLeftChild(*ptr)
  //  == pointer to left child of *ptr,
  //           otherwise

extern NodePtr RChild( NodePtr ptr );
  // PRE:  ValidNode(*ptr)
  // POST: FCTVAL == NULL,
  //          if NOT HasRightChild(*ptr)
  //   == pointer to right child of *ptr,
  //          otherwise

extern void SetLeft(NodePtr ptr,
		      NodePtr p);
  // PRE:  ValidNode(*ptr)
  // MODIFIES: ptr
  // POST: the left subtree of ptr is p

extern void SetRight(NodePtr ptr,
		      NodePtr p);
  // PRE:  ValidNode(*ptr)
  // MODIFIES: ptr
  // POST: the right subtree of ptr is p

extern Boolean IsLeaf( NodePtr ptr );
  // PRE:  ValidNode(*ptr)
  // POST: FCTVAL == IsLeaf(*ptr)

extern void DeleteLeaf( NodePtr& ptr );
  // PRE:  IsLeaf(*ptr<entry>)
  // MODIFIES: ptr
  // POST: *ptr<entry> removed from tree
  // && ptr is undefined && *ptr<entry>
  // is no longer allocated

extern void PrintInOrder( NodePtr ptr );
  // POST: information about the subtree
  // at ptr is printed to cout in order.