Need Help with a Couple of Set Class Functions

[Merriak]

Hi there!

I've been working on a set class implementation but have gotten confused on certain parts of the code, specifically the functions erase, find and begin in the Set class. I'm pretty sure I am doing my begin function incorrectly, but I am stumped as to what it could be... I completely understand the inline erase function I have, but am confused with the second. Also completely confused on how the find function works in sets...

Note: This program runs in inorder traversal, so it will read from left node to root, to right node.

Here's the functions alone I am confused with:

template <class T>
void Set<T>::erase(const iterator & current)
{
    
}

template <class T>
typename Set<T>::iterator Set<T>::find(const T & element) const
{

}

template <class T>
typename Set<T>::iterator Set<T>::begin() const
{
    return iterator(root); //pretty sure this is incorrect, since this program reads in inorder traversal. 
//Shouldn't the first element of the set be a left node?
}

Here's the full .h file that I am working on:

#ifndef SET_H
#define SET_H

// Set.h - an implementation of Set using Node and Set_iterator

using namespace std;

template <class T> class Set;
template <class T> class Set_iterator;

template <class T>
class Node {
public:
	Node(): value(0), parent(0), leftChild(0), rightChild(0) { }
   Node(const T & x, Node * p, Node * lc, Node * rc): value(x), parent(p), leftChild(lc), rightChild(rc) { }
    // here copy constructor and assignment op don't make too much sense!
        Node(const Node & n): value(n.value), parent(0), leftChild(0), rightChild(0) { }
        Node & operator=(const Node & n) { value = n.value; return *this; }
    
	~Node() { delete leftChild; delete rightChild; } // this is very recursive, 
//delete also calls the destructor of the object it is deleting
    
	void insert(Node<T> * newNode); // this is a helper func for Set::insert()
	Node * find(const T & x);
	Node * merge(Node<T> * left, Node<T> * right);
protected:
	T value;
	Node * parent;
	Node * leftChild;
	Node * rightChild;
    
    friend class Set<T>;
    friend class Set_iterator<T>;
};

template <class T>
void Node<T>::insert(Node<T> * newNode)
{
    if(newNode->value <= value){
        if(leftChild != 0){
            leftChild->insert (newNode);
        }
        else{
            newNode->parent = this;
            leftChild = newNode;
        }
    }
    else{
        if(rightChild != 0){
            rightChild->insert (newNode);
        }
        else{
            newNode->parent = this;
            rightChild = newNode;
        }
    }
    
}
 
template <class T>
Node<T> * Node<T>::find(const T & element)
{
    if(element->value <= value){
        if(leftChild != 0){
            if(leftChild->value == element){;
                return *this;
            }
            else{
                return element;
            }
        }
        else{
            return element;
        }
    }
    else{
        if(rightChild != 0){
            if(rightChild->value == element){
                return *this;
            }
            else{
                return element;
            }
        }
        else{
            return element;
        }
    }
    return setIterator(this);
}

template <class T>
Node<T> * Node<T>::merge(Node<T> *left, Node<T> *right)
{
    if(left == 0){
        return right;
    }
    if(right == 0){
        return left;
    }
    Node<T> * child = merge(left, right->leftChild);
    child->parent = right;
    right->leftChild = child;
    return right;
}

template <class T>
class Set {
public:
	typedef Set_iterator<T> iterator;
    
	Set(): root(0), my_size(0) { }
    
	// the big three
	Set(const Set<T> & );
	~Set() { delete root; }
	Set operator=(const Set & );
    
	bool empty() const { return root == 0; }
	unsigned int size() const { return my_size; }
	void insert(const T & newElement); // return an iterator to x if it already exists,
// otherwise insert and return an iterator to x
	void erase(const iterator & current);
	void erase(const T & x) { root = remove(root, x); }
	unsigned int count(const T & x) const; // returns 1 or 0 because this is a set, not a multi-set
	iterator find(const T & x) const;
	iterator begin() const; // for in-order traversal
	iterator end() const { return iterator(0); }
protected:
	Node<T> * root;
	unsigned int my_size;
	Node<T> * remove(Node<T> *, const T &);
};

template <class T>
Set<T>::Set(const Set<T> & op)
{
    root = 0;
    for (iterator i = op.begin(); i != op.end(); ++i)
        insert(*i);
}

template <class T>
Set<T> Set<T>::operator=(const Set<T> & op)
{
    delete root;
    root = 0;
    for (iterator i = op.begin(); i != op.end(); ++i)
        insert(*i);
    return *this;
}

template <class T>
void Set<T>::insert(const T & newElement)
{
    //do not insert if already in set
    if (count(newElement) > 0){
        return;
    }
    //create a new node
    Node<T> * newNode = new Node<T> (newElement, 0, 0, 0);
    if(root == 0){
        root = newNode;
    }
    else{
        root->insert (newNode);
    }
}

template <class T>
void Set<T>::erase(const iterator & current)
{
    
}

template <class T>
unsigned int Set<T>::count(const T & x) const
{
    iterator looking = begin();
    int count = 0;
    
    for( ; looking != end(); looking++){
        count++;
    }
    return count;
}

template <class T>
typename Set<T>::iterator Set<T>::find(const T & element) const
{

}

template <class T>
typename Set<T>::iterator Set<T>::begin() const
{
    return iterator(root);
}

template <class T>
Node<T> * Set<T>::remove(Node<T> * current, const T & testElement)
{
    if(current != 0){
        Node<T> * pa = current->parent;
        if(testElement < current->value){
            current->leftChild = remove(current->leftChild, testElement);
        }
        else if(current->value < testElement){
            current->rightChild = remove(current->rightChild, testElement);
        }
        else {
            Node<T> * result = current->merge(remove(current->leftChild, testElement), current->rightChild);
            current->leftChild = current->rightChild = 0;
            delete current;
            if (result)
                result->parent = pa;
            return result;
        }
    }
}
    
template <class T>
class Set_iterator {
public:
	Set_iterator(): current(0) { }
	Set_iterator(Node<T> * newNode): current(newNode) { }
    
	bool operator==(Set_iterator it) const { return current == it.current; }
	bool operator!=(Set_iterator it) const { return current != it.current; }
	Set_iterator & operator++(); // inorder traversal, pre-increment
	Set_iterator operator++(int); // inorder traversal, post-increment
	T & operator*() { return current->value; }
	Set_iterator & operator=(Set_iterator<T> it) { current = it.current; return *this; }
protected:
	Node<T> * current;
    friend class Set<T>;
};

template <class T>
Set_iterator<T> & Set_iterator<T>::operator++()
{
    if(current->rightChild){
        current = current->rightChild;
        while(current->leftChild){
            current = current->leftChild;
        }
    }
    else{
        Node<T> * child = current;
        current = current->parent;
        while(current && current->rightChild == current){
            child = current;
            current = current->parent;
        }
    }
    return *this;
}

template <class T>
Set_iterator<T> Set_iterator<T>::operator++(int)
{
    Set_iterator<T> clone (*this);
    operator++ ();
    return clone;
}


#endif 

Here's the main file I am first testing with:

#include <iostream>
#include <cassert>
#include "set.h"

using namespace std;

main()
{
    Set<int> s;
    
    s.insert(10);
    s.insert(7);
    s.insert(6);
    s.insert(9);
    s.insert(8);
    s.insert(11);
    
    Set<int>::iterator i = s.find(7);
    s.erase(i);
    
    for (i = s.begin(); i != s.end(); i++)
        cout << *i << endl;
    
    cout << "All tests passed." << endl;
}

[Peter87]

The begin function should return the left-most leaf in the tree.

I think line 151 should be while(current && current->rightChild == child){.

The find should search for the element passed in to it, and if it is found an iterator to the element that was found in the set is returned. If it is not found end() is returned. At least that's how std::set::find works.

[Merriak]

Hmm, I tried modifying the while loop as you suggested but now get a segmentation fault.

Also how would I return the left-most left in the tree without access to the leftChild variable that's in class Node? Likewise, how do I set up the find function without the access to the Left and Right child variables?

[Peter87]

You do have access to leftChild because Set<T> is a friend of Node<T>.

[Merriak]

How come I keep getting 'undeclared variable' errors though, when trying to use say "leftChild" in a Set function?

[Peter87]

You need to use a Node<T> object to access leftChild. You can use root. Or if you don't want to access leftChild from Set<T> you can create a member function of Node<T> that returns the left most leaf.

[Merriak]

Alright, thank you Peter, I believe I got the find and begin functions now! :D

Anyone know how I would approach the erase function?