Dictionary.cpp

//-----------------------------------------------------------------------------
// Christopher Vo, cvo5
// 2022 Winter CSE 101 PA 8
// Dictionary.cpp
// Implementation file for Dictionary ADT
// Dictionary is in the form of a RBT
//-----------------------------------------------------------------------------

#include "Dictionary.h"
#define RED 1
#define BLACK 0

#include "Dictionary.h"

// Private Constructor --------------------------------------------------------

// Node constructor
Dictionary::Node::Node(keyType k, valType v) {
    key = k;
    val = v;
    parent = left = right = nullptr;
    color = BLACK; // or should it be defaulted to RED?
}

// Helper Functions (Optional) ---------------------------------------------

// inOrderString()
// Appends a string representation of the tree rooted at R to string s. The
// string appended consists of: "key : value \n" for each key-value pair in
// tree R, arranged in order by keys.
void Dictionary::inOrderString(std::string& s, Node* R) const {
    if (R != nil) {
        inOrderString(s, R->left);

        // append
        std::string valueStr = std::to_string(R->val);
        s.append(R->key);
        s.append(" : ");
        s.append(valueStr);
        s.append("\n");

        inOrderString(s, R->right);
    }
}

// preOrderString()
// Appends a string representation of the tree rooted at R to s. The appended
// string consists of keys only, separated by "\n", with the order determined
// by a pre-order tree walk.
void Dictionary::preOrderString(std::string& s, Node* R) const {
    if (R != nil) {
        // append
        s.append(R->key);
        s.append("\n");

        preOrderString(s, R->left);
        preOrderString(s, R->right);
    }
}

// preOrderCopy()
// Recursively inserts a deep copy of the subtree rooted at R into this 
// Dictionary. Recursion terminates at N.
void Dictionary::preOrderCopy(Node* R, Node* N) {

    if (R != N) {
        // copy
        setValue(R->key, R->val);
        preOrderCopy(R->left, N);
        preOrderCopy(R->right, N);
    }

}

// i might be doing this wrong
// postOrderDelete()
// Deletes all Nodes in the subtree rooted at R, sets R to nil.
void Dictionary::postOrderDelete(Node* R) {
    // we go from last to root
    if (R != nil) {
        postOrderDelete(R->left);
        postOrderDelete(R->right);

        // delete
        delete R;
        R = nullptr;
    }
}

// search()
// Searches the subtree rooted at R for a Node with key==k. Returns
// the address of the Node if it exists, returns nil otherwise.
Dictionary::Node* Dictionary::search(Node* R, keyType k) const {

    // recursive
    if (R == nil || k == R->key) {
        return R;
    }
    else if (k < R->key) {
        return search(R->left, k);
    }
    else { // k > R->key
        return search(R->right, k);
    }
}

// findMin()
// If the subtree rooted at R is not empty, returns a pointer to the 
// leftmost Node in that subtree, otherwise returns nil.
Dictionary::Node* Dictionary::findMin(Node* R) {
    // non-recursive, just keep going left
    Node* N = R;

    if (R != nil) {
        while (N->left != nil) {
            N = N->left;
        }
    }
    return N;

}

// findMax()
// If the subtree rooted at R is not empty, returns a pointer to the 
// rightmost Node in that subtree, otherwise returns nil.
Dictionary::Node* Dictionary::findMax(Node* R) {
    // non-recursive, just keep going right
    Node* N = R;

    if (R != nil) {
        while (N->right != nil) {
            N = N->right;
        }
    }

    return N;

}

// findNext()
// If N does not point to the rightmost Node, returns a pointer to the
// Node after N in an in-order tree walk.  If N points to the rightmost 
// Node, or is nil, returns nil. 
Dictionary::Node* Dictionary::findNext(Node* N) {
    // find successor

    // case 1: N has right child
    if (N->right != nil) {
        return findMin(N->right);
    }

    // case 2: N doesn't have a right child
    // its successor is the first "right turn" going up the tree from N
    Node* y = N->parent;
    while (y != nil && N == y->right) {
        N = y;
        y = y->parent;
    }
    return y;
}

// findPrev()
// If N does not point to the leftmost Node, returns a pointer to the
// Node before N in an in-order tree walk.  If N points to the leftmost 
// Node, or is nil, returns nil.
Dictionary::Node* Dictionary::findPrev(Node* N) {
    // find predecessor (basically flip of findPrev)

    // case 1: N has left child
    if (N->left != nil) {
        return findMax(N->left);
    }

    // case 2: N doesn't have a left child
    // its successor is the first "left turn" going up the tree from N
    Node* y = N->parent;
    while (y != nil && N == y->left) {
        N = y;
        y = y->parent;
    }
    return y;
}

/*
// transplant()
// Swaps the subtree at u with the subtree at v
// used in remove()
void Dictionary::transplant(Dictionary& D, Node* u, Node* v) {
    if (u->parent == nil) {
        D.root = v;
    }
    else if (u == u->parent->left) {
        u->parent->left = v;
    }
    else { // u == u->parent->right
        u->parent->right = v;
    }

    if (v != nil) {
        v->parent = u->parent;
    }

}
*/

// LeftRotate()
void Dictionary::LeftRotate(Node* N) {
    // set y
    Node* y = N->right;

    // turn y's left subtree into N's right subtree
    N->right = y->left;
    
    /* shouldn't be necessary if using sentinel nil node
    if (y->left != nil){
        y->left->parent = N;
    }
    */

    // link y's parent to N
    y->parent = N->parent;
    if (N->parent == nil){
        root = y;
    }
    else if (N == N->parent->left){
        N->parent->left = y;
    }
    else{
        N->parent->right = y;
    }

    // put N on y's left
    y->left = N;
    N->parent = y;
}

// RightRotate()
void Dictionary::RightRotate(Node* N) {
    // set y
    Node* y = N->left;

    // turn y's right subtree into N's left subtree
    N->left = y->right;

    /* shouldn't be necessary if using sentinel nil node
    if (y->right != nil){
        y->right->parent = N;
    }
    */

    // link y's parent to N
    y->parent = N->parent;
    if (N->parent == nil){
        root = y;
    }
    else if (N == N->parent->right){
        N->parent->right = y;
    }
    else{
        N->parent->left = y;
    }

    // put N on y's right
    y->right = N;
    N->parent = y;
}

// RB_InsertFixUP()
void Dictionary::RB_InsertFixUp(Node* N) {
    while (N->parent->color = RED){
        Node* y;
        if (N->parent == N->parent->left){
            y = N->parent->parent->right;

            // CASE 1
            if (y->color == RED){
                N->parent->color = BLACK;
                y->color = BLACK;
                N->parent->parent->color = RED;
                N = N->parent->parent;
            }
            else{

                // CASE 2 (convert to CASE 3 and fall through)
                if (N == N->parent->right){
                    N = N->parent;
                    LeftRotate(N);
                }

                // CASE 3
                N->parent->color = BLACK;
                N->parent->parent->color = RED;
                RightRotate(N->parent->parent);
            }
        }
        // mirrored cases
        else{
            y = N->parent->parent->left;

            // CASE 4
            if (y->color == RED){
                N->parent->color = BLACK;
                y->color = BLACK;
                N->parent->parent->color = RED;
                N = N->parent->parent;
            }
            else{

                // CASE 5 (convert to CASE 6 and fall through)
                if (N == N->parent->left){
                    N = N->parent;
                    RightRotate(N);
                }

                // CASE 6
                N->parent->color = BLACK;
                N->parent->parent->color = RED;
                LeftRotate(N->parent->parent);
            }
        }
    }

    // ALWAYS set root to black
    root->color = BLACK;
}

// RB_Transplant()
// swaps the subtrees at u with the subtree at v
// used in RB_Delete() and RB_DeleteFixUp()
void Dictionary::RB_Transplant(Node* u, Node* v) {
    if (u->parent == nil){
        root = v;
    }
    else if (u == u->parent->left){
        u->parent->left = v;
    }
    else{
        u->parent->right = v;
    }
    v->parent = u->parent;
}

// RB_DeleteFixUp()
void Dictionary::RB_DeleteFixUp(Node* N) {
    while (N != root && N->color == BLACK){
        if (N == N->parent->left){
            Node* w = N->parent->right;

            // CASE 1
            if (w->color == RED){
                w->color == BLACK;
                N->parent->color = RED;
                LeftRotate(N->parent);
                w = N->parent->right;
            }
            
            // CASE 2
            if (w->left->color == BLACK && w->right->color == BLACK){
                w->color = RED;
                N = N->parent;
            }
            else{

                // CASE 3 (convert to CASE 4 and fall through, i think)
                if (w->right->color == BLACK){
                    w->left->color = BLACK;
                    w->color = RED;
                    RightRotate(w);
                    w = N->parent->right;
                }

                // CASE 4
                w->color = N->parent->color;
                N->parent->color = BLACK;
                w->right->color = BLACK;
                LeftRotate(N->parent);
                N = root;
            }
        }

        // mirror cases
        else{ // N == N->parent->right
            Node* w = N->parent->left;

            // CASE 5
            if (w->color == RED){
                w->color == BLACK;
                N->parent->color = RED;
                RightRotate(N->parent);
                w = N->parent->left;
            }
            
            // CASE 6
            if (w->right->color == BLACK && w->left->color == BLACK){
                w->color = RED;
                N = N->parent;
            }
            else{

                // CASE 7 (convert to CASE 8 and fall through, i think)
                if (w->left->color == BLACK){
                    w->right->color = BLACK;
                    w->color = RED;
                    LeftRotate(w);
                    w = N->parent->left;
                }

                // CASE 8
                w->color = N->parent->color;
                N->parent->color = BLACK;
                w->left->color = BLACK;
                RightRotate(N->parent);
                N = root;
            }
        }
    }

    // ALWAYS end by turning N black
    N->color = BLACK;
}

// RB_Delete()
void Dictionary::RB_Delete(Node* N) {
    Node* y = N;
    Node* x;
    int yOGColor = y->color;
    if (N->left == nil){
        x = N->right;
        RB_Transplant(N, N->left);
    }
    else if (N->right == nil){
        x = N->left;
        RB_Transplant(N, N->left);
    }
    else{
        y = findMin(N->right);
        yOGColor = y->color;
        x = y->right;
        if (y->parent == N){
            x->parent =y;
        }
        else{
            RB_Transplant(y, y->right);
            y->right = N->right;
            y->right->parent = y;
        }
        RB_Transplant(N, y);
        y->left = N->left;
        y->left->parent = y;
        y->color = N->color;
    }

    if (yOGColor == BLACK){
        RB_DeleteFixUp(x);
    }
}

// Class Constructors & Destructors ----------------------------------------

// Creates new Dictionary in the empty state. 
Dictionary::Dictionary() {
    // nil should never be read from
    nil = new Node(NIL, JUNKVAL);
    root = current = nil;
    num_pairs = 0;
}

// Copy constructor.
Dictionary::Dictionary(const Dictionary& D) {
    nil = new Node(NIL, JUNKVAL);

    root = current = nil;
    num_pairs = 0; // will be updated through preOrderCopy

    preOrderCopy(D.root, D.nil);
}

// Destructor
Dictionary::~Dictionary() {
    // call clear (which calls postOrderDelete)
    // delete nil, root, and current
    clear();

    // root = current = nil -> don't dare double free
    delete nil;
}


// Access functions --------------------------------------------------------

// size()
// Returns the size of this Dictionary.
int Dictionary::size() const {
    return num_pairs;
}

// contains()
// Returns true if there exists a pair such that key==k, and returns false
// otherwise.
bool Dictionary::contains(keyType k) const {
    return (search(root, k) != nil);
}

// getValue()
// Returns a reference to the value corresponding to key k.
// Pre: contains(k)
valType& Dictionary::getValue(keyType k) const {
    if (contains(k) == 0) {
        throw std::invalid_argument("Dictionary: getValue(): key " + k + " does not exist");
    }

    Node* N = search(root, k);
    return N->val;
}

// hasCurrent()
// Returns true if the current iterator is defined, and returns false 
// otherwise.
bool Dictionary::hasCurrent() const {
    return (current != nil);
}

// currentKey()
// Returns the current key.
// Pre: hasCurrent() 
keyType Dictionary::currentKey() const {
    if (hasCurrent() == 0) {
        throw std::out_of_range("Dictionary: currentKey(): current not defined");
    }

    return current->key;
}

// currentVal()
// Returns a reference to the current value.
// Pre: hasCurrent()
valType& Dictionary::currentVal() const {
    if (hasCurrent() == 0) {
        throw std::out_of_range("Dictionary: currentVal(): current not defined");
    }

    return current->val;
}


// Manipulation procedures -------------------------------------------------

// clear()
// Resets this Dictionary to the empty state, containing no pairs.
void Dictionary::clear() {
    if (size() != 0) {
        postOrderDelete(root);
        root = current = nil;
        num_pairs = 0;
    }
}

// setValue()
// If a pair with key==k exists, overwrites the corresponding value with v, 
// otherwise inserts the new pair (k, v).
void Dictionary::setValue(keyType k, valType v) {
    // search
    // if nil, insert
    // if not nil, overwrite

    // optimization: don't call search()
    // maybe if the node isn't found you want the parent of where it would be

    Node* y = nil;
    Node* x = root;
    Node* z = new Node(k, v);
    z->left = z->right = nil;

    // search for the right spot
    while (x != nil) {
        y = x;

        int result = z->key.compare(x->key);
        if (result == 0) { // key already exists -> overwrite
            x->val = v;
            delete z;
            z = nullptr;
            return;
        }
        else if (result < 0) {
            // z must belong on the left
            x = x->left;
        }
        else if (result > 0) { // z->key < x->key
            // z must belong on the right
            x = x->right;
        }

    }

    // only insert if we didn't overwrite
    z->parent = y;

    if (y == nil) { // tree is empty
        root = z;
    }
    else if (z->key < y->key) {
        y->left = z;
    }
    else {
        y->right = z;
    }

    num_pairs++;
}

// remove()
// Deletes the pair for which key==k. If that pair is current, then current
// becomes undefined.
// Pre: contains(k).
void Dictionary::remove(keyType k) {
    if (contains(k) == 0) {
        throw std::invalid_argument("Dictionary: remove(): key " + k + " does not exist");
    }

    // search for the key k
    Node* N = search(root, k);

    // if removed Node is currrent, set it to undefined
    if (N == current) {
        current = nil;
    }

    // remove
    if (N->left == nil) {
        transplant(*this, N, N->right); // only right child
    }
    else if (N->right == nil) {
        transplant(*this, N, N->left);  // only left child
    }
    else {                              // 2 children, splice out successor, overwrite value
        Node* y = findMin(N->right);
        if (y->parent != N) {
            transplant(*this, y, y->right);
            y->right = N->right;
            y->right->parent = y;
        }

        transplant(*this, N, y);
        y->left = N->left;
        y->left->parent = y;
    }

    delete N;
    N = nullptr;

    num_pairs--;

}

// begin()
// If non-empty, places current iterator at the first (key, value) pair
// (as defined by the order operator < on keys), otherwise does nothing. 
void Dictionary::begin() {
    if (size() != 0) {
        current = findMin(root);
    }
}

// end()
// If non-empty, places current iterator at the last (key, value) pair
// (as defined by the order operator < on keys), otherwise does nothing. 
void Dictionary::end() {
    if (size() != 0) {
        current = findMax(root);
    }
}

// next()
// If the current iterator is not at the last pair, advances current 
// to the next pair (as defined by the order operator < on keys). If 
// the current iterator is at the last pair, makes current undefined.
// Pre: hasCurrent()
void Dictionary::next() {
    if (hasCurrent() == 0) {
        throw std::out_of_range("Dictionary: next(): current is undefined");
    }

    current = findNext(current);

}

// prev()
// If the current iterator is not at the first pair, moves current to  
// the previous pair (as defined by the order operator < on keys). If 
// the current iterator is at the first pair, makes current undefined.
// Pre: hasCurrent()
void Dictionary::prev() {
    if (hasCurrent() == 0) {
        throw std::out_of_range("Dictionary: prev(): current is undefined");
    }

    current = findPrev(current);
}


// Other Functions ---------------------------------------------------------

// to_string()
// Returns a string representation of this Dictionary. Consecutive (key, value)
// pairs are separated by a newline "\n" character, and the items key and value 
// are separated by the sequence space-colon-space " : ". The pairs are arranged 
// in order, as defined by the order operator <.
std::string Dictionary::to_string() const {
    std::string s;
    inOrderString(s, root);
    return s;
}

// pre_string()
// Returns a string consisting of all keys in this Dictionary. Consecutive
// keys are separated by newline "\n" characters. The key order is given
// by a pre-order tree walk.
std::string Dictionary::pre_string() const {
    std::string s;
    preOrderString(s, root);
    return s;
}

// equals()
// Returns true if and only if this Dictionary contains the same (key, value)
// pairs as Dictionary D.
bool Dictionary::equals(const Dictionary& D) const {

    // compare preOrderString (for structure) and inOrderString (for key-pairs)
    std::string A, B, C, E;

    this->preOrderString(A, this->root);
    D.preOrderString(B, D.root);
    this->inOrderString(C, this->root);
    D.inOrderString(E, D.root);

    return (A == B && C == E);
}


// Overloaded Operators ----------------------------------------------------

// operator<<()
// Inserts string representation of Dictionary D into stream, as defined by
// member function to_string().
std::ostream& operator<<(std::ostream& stream, Dictionary& D) {
    return stream << D.Dictionary::to_string();
}

// operator==()
// Returns true if and only if Dictionary A equals Dictionary B, as defined
// by member function equals(). 
bool operator==(const Dictionary& A, const Dictionary& B) {
    return A.equals(B);
}

// operator=()
// Overwrites the state of this Dictionary with state of D, and returns a
// reference to this Dictionary.
Dictionary& Dictionary::operator=(const Dictionary& D) {

    if (this != &D) {
        Dictionary temp = D;

        std::swap(nil, temp.nil);
        std::swap(root, temp.root);
        std::swap(current, temp.current);
        std::swap(num_pairs, temp.num_pairs);
    }

    return *this;
}