#ifndef _APSET_H
#define _APSET_H

template <class itemType>
struct Node
{
    itemType info;
    Node<itemType> * left;
    Node<itemType> * right;
    
    Node(const itemType & val, 
         Node<itemType> * lchild, Node<itemType> * rchild)
         : info(val), left(lchild), right(rchild)
    { }
};

template <class itemType>
class apset
{
  public:
    apset();

    const apset<itemType> & operator = (const apset<itemType> & rhs);
    // accessors
    
    bool contains(const itemType & item) const;  // is item in the set?
    void print(ostream & output)         const;  // print all items
    int  size()                          const;  // # elements in set
    
    // mutators

    void add(const itemType & item);        // add item to set (no duplicates)
    void makeEmpty();                       // empty it out
    void remove(const itemType & item);

    // operators

    const apset<itemType>&
    operator *= (const apset<itemType> & rhs);   // intersection with
    const apset<itemType>&
    operator += (const apset<itemType> & rhs);   // union with

  private:

    Node<itemType> *
            find(Node<itemType> * root,
                 const itemType & item) const;  // pointer in root to item
            
    void unionHelp(Node<itemType> * rightRoot);
    void interHelp(apset<itemType> & result,
                   Node<itemType> * leftRoot,Node<itemType> * righRoot);
    Node<itemType> * myRoot;
    int              myCount;
};

#include "apset3.cpp"

#endif