//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MBN 07/18/89 -- Initial design and implementation
// Updated: MBN 08/11/89 -- Inherit from Generic
// Updated: DKM 11/05/89 -- Added avl_balance slot, num_subtrees member
//
// The Binary_Node class implements  nodes for binary trees  that have  no data
// slot.  This node class contains left and right subtree pointers.   Since the
// Binary_Node   class is  intended   for the  sole   use of  the parameterized
// Binary_Node<Type> class, all constructors and  methods are protected and the
// Binary_Tree class is declared as a friend class.
//
// The private data section contains two  pointers to Binary_Node  objects, one
// for the left subtree and one for the right subtree.  There are two protected
// constructors  for the class.   The first takes  no arguments and initializes
// the two pointers to  NULL.     The  second takes   a  reference  to  another
// Binary_Node object and duplicates its values.
//
// Methods are provided to determine if a node  is a  leaf or  the root of some
// subtree and implement member-wise assignment from one Binary_Node to another
// via the overloaded operator=.
//

#ifndef BASE_BINARY_NODEH			// If no definition for class
#define BASE_BINARY_NODEH

#ifndef GENERIC_H				// If no definition for class
#include <cool/Generic.h>				// include definition file
#endif

class Binary_Tree;				// Forward declaration of class

class Binary_Node : public Generic {
protected:
  friend class Binary_Tree;			// Binary_Tree class is friend

  Binary_Node* ltree;				// Left subtree pointer
  Binary_Node* rtree;				// Right subtree pointer
  int avl_balance;				// AVL balance for this node

  Binary_Node ();				// Simple constructor
  Binary_Node (const Binary_Node&);		// Constructor with reference
  ~Binary_Node ();				// Destructor

  inline Binary_Node* subtree (int);		// Return nth subtree of node
  inline int num_subtrees () CONST;		// Number of subtree slots
  Binary_Node& operator= (const Binary_Node&);	// Assignment 
  inline friend ostream& operator<< (ostream&, Binary_Node*); // Output
public:
  inline Boolean is_leaf () CONST;		// TRUE if node has no children
};

// subtree -- Get nth subtree of node (n is 0 based)
// Input:     int
// Output:    Binary_Node or NULL if no subtree

inline Binary_Node* Binary_Node::subtree (int n) {
  if (n == 0)
    return ltree;
  else if (n == 1)
    return rtree;
// should signal an error here ...
  else return NULL;
}



// is_leaf -- Determine if node has any children
// Input:     None
// Output:    TRUE if no children, else FALSE

inline Boolean Binary_Node::is_leaf () CONST {
  return ((this->ltree == NULL && this->rtree == NULL) ? TRUE : FALSE);
}

inline int Binary_Node::num_subtrees () CONST {
  return 2;
}

// operator<< -- Allow printing something for a pointer to a Binary Node
// Input:        Reference to output stream,  Binary_Node*
// Output:       Reference to output stream

inline ostream& operator<< (ostream& os, Binary_Node *b) {
  os << (long)b;				// cast as a long
  return os;					// Return output stream
}

#endif						// End BASE_BINARY_NODEH #if
