// see apset3.h

template <class itemType>
apset<itemType>::apset()
    : myRoot(NULL),
      myCount(0)
{
    
}

template <class itemType>
Node<itemType> * copy(Node<itemType> * root)
{
    if (root == NULL) return NULL;
    else return
        new Node<itemType>(root->info,
                           copy(root->left),copy(root->right));
}

template <class itemType>
const apset<itemType> &
apset<itemType>::operator = (const apset<itemType> & rhs)
{
   myRoot = copy(rhs.myRoot);
   myCount = rhs.myCount;  
   return *this;  
}

template <class itemType>
bool apset<itemType>::contains(const itemType & item) const
{
    return find(myRoot,item) != NULL;
}

template <class itemType>
int apset<itemType>::size() const
{
    return myCount;
}

template <class itemType>
void apset<itemType>::print(ostream & output) const
{
    // not implemented
}

template <class itemType>
void apset<itemType>::add(const itemType & item)
{
    Node<itemType> * loc = find(myRoot,item);
    if (loc == NULL)
    {
	if (myRoot == NULL)
	{
	    myRoot = new Node<itemType>(item,NULL,NULL);
	    myCount++;
	    return;
	}
	// must have a root start there
	loc = myRoot;
	bool found = false;
	while (! found)
	{
	    if (item < loc->info)
	    {
		if (loc->left == NULL)
		{
		    loc->left = new Node<itemType>(item,NULL,NULL);
		    found = true;
		}
		else
		{
		    loc = loc->left;
		}
	    }
	    else
	    {
		if (loc->right == NULL)
		{
		    loc->right = new Node<itemType>(item,NULL,NULL);
		    found = true;
		}
		else
		{
		    loc = loc->right;
		}
	    }
	}
	myCount++;
    }
}

template <class itemType>
void apset<itemType>::remove(const itemType & item)
{
    // not implemented
}

template <class itemType>
void apset<itemType>::makeEmpty()
{
    myRoot = NULL;
    myCount = 0;
}

template <class itemType>
Node<itemType> * apset<itemType>::find(Node<itemType> * root,
                                       const itemType & item) const
{
    while (root != NULL)
    {
        if (item == root->info) return root;
        else if (item < root->info) root = root->left;
        else                        root = root->right;
    }
    return NULL;
}

template <class itemType>
const apset<itemType>&
apset<itemType>::operator *= (const apset<itemType> & rhs)
{
    apset<itemType> result;
    
    if (size() < rhs.size())
    {
        interHelp(result,rhs.myRoot,myRoot);
    }
    else
    {
		interHelp(result,myRoot,rhs.myRoot);
    }
    
    // swap roots so that when result goes
    // out of scope the destructor deletes
    // what used to be me
    
    Node<itemType> * temp = myRoot;
    myRoot = result.myRoot;
    result.myRoot = temp;
    myCount = result.myCount;
    return *this;
}

template <class itemType>
const apset<itemType>&
apset<itemType>::operator += (const apset<itemType> & rhs)
{
    unionHelp(rhs.myRoot);
    return *this;
}

template <class itemType>
void
apset<itemType>::unionHelp(Node<itemType> * rightRoot)
{
    if (rightRoot != NULL)
    {
        unionHelp(rightRoot->left);
        unionHelp(rightRoot->right);
        if (! contains(rightRoot->info))
        {
            add(rightRoot->info);
        } 
    }
}

template <class itemType>
void
apset<itemType>::interHelp(apset<itemType> & result,
                           Node<itemType> * leftRoot,
                           Node<itemType> * rightRoot)
{
    if (rightRoot != NULL)
    {
        interHelp(result,leftRoot,rightRoot->left);

        if (find(leftRoot,rightRoot->info) != NULL)
        {
            result.add(rightRoot->info);
        }  	
       
        interHelp(result,leftRoot,rightRoot->right);
        
    }
}