BSTDict.cpp

#ifndef _BSTDICT_CPP
#define _BSTDICT_CPP

//BSTDict.cpp
#include "BSTDict.hpp"
#include <cassert>
#include <cstdlib> //for NULL
#include <iostream>

// An implementation of a dictionary ADT as a binary search tree (without balancing
// operations).
//
// The template type means that the dictionary will store elements with key type T, and
// data type T; and two elements of type T will be compared using the operator() of a
// Compare class.
//
// Compare() (elem1, elem2), which will return a number > 0 if elem1 is greater than
// elem2, 0 if elem1 is equal to elem2, and < 0 if elem1 is less than elem2. Note that
// this will NOT give the same result as directly comparing elem1 and elem2 as
// "elem1 > elem2" as it does not correspond to any overloaded operator>, operator==, or
// operator< defined by the type.

template <typename T, class Compare>
BSTDict<T, Compare>::BSTDict() {
    root = NULL;
}

template <typename T, class Compare>
BSTDict<T, Compare>::~BSTDict() {
    // Ideally, we would recursively traverse the tree to delete all the Nodes.  We'd also
    // need to keep track of whether or not to delete the data and key fields, which can
    // be very tricky (are there any other pointers to these fields?)  The newest C++ has
    // so-called smart pointers that will do this for you, but fortunately for us, in our
    // program we never need to delete a dictionary.

    // So, we'll just do nothing in the destructor.
}

template <typename T, class Compare>
bool BSTDict<T, Compare>::find(T key, T& pred) {
    return find_helper(root, key, pred);
}

template <typename T, class Compare>
void BSTDict<T, Compare>::add(T key, T pred) {
    /*// Determine where the Node will be added.
    Node** temp = &root; // A pointer to a pointer. :)
    while (*temp != NULL) {
        int compare = Compare()(key, (*temp)->key);
        if (compare < 0) {
            temp = &((*temp)->left);
        } else if (compare > 0) {
            temp = &((*temp)->right);
        } else {
            return; // The Node already exists.
        }
    }

    // Create the new Node.
    *temp = new Node();
    (*temp)->key = key;
    (*temp)->data = pred;*/

    Node*& temp = add_helper(root, key);
    temp = new Node();
    temp->key = key;
    temp->data = pred;
}

template <typename T, class Compare>
Node*& BSTDict<T, Compare>::add_helper(Node*& r, T key) {
    if (r == NULL) {
        return r;
    }

    int compare = Compare()(key, r->key);
    if (compare < 0) {
        return add_helper(r->left, key);
    } else if (compare > 0) {
        return add_helper(r->right, key);
    } else {
        return r;
    }
}

template <typename T, class Compare>
bool BSTDict<T, Compare>::find_helper(Node* r, T key, T& pred) {
    if (r == NULL) {
        return false; // No Node found
    }

    int compare = Compare()(key, r->key);
    if (compare < 0) {
        return find_helper(r->left, key, pred);
    } else if (compare > 0) {
        return find_helper(r->right, key, pred);
    } else {
        pred = r->data;
        return true;
    }
}

#endif