BSTNode.h

// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition (C++)" by Clifford A. Shaffer.
// Source code Copyright (C) 2007-2011 by Clifford A. Shaffer.
// 1/26/22 pragma once modification by Prof Sipantzi
// This is the file to include for access to the complete binary node
// template implementation

#include "book.h"
#include "BinNode.h"

#pragma once

// Simple binary tree node implementation
template <typename Key, typename E>
class BSTNode : public BinNode<E> {
private:
    Key k;                  // The node's key
    E it;                   // The node's value
    BSTNode* lc;            // Pointer to left child
    BSTNode* rc;            // Pointer to right child

    /* Bitfield to store whether the lc and rc are threads
    0: LC RC
    1: LT RC
    2: LC RT
    3: LT RT
    Even    = LC
    Odd     = LT
    >1      = RT
    <=1     = RC */
    unsigned int threadBitField : 2;

public:
    // Two constructors -- with and without initial values
    BSTNode() { lc = rc = NULL; threadBitField = 0; }
    BSTNode(Key K, E e, BSTNode* l = NULL, BSTNode* r = NULL)
    {
        k = K; it = e; lc = l; rc = r;
    }
    ~BSTNode() {}             // Destructor

    // Functions to set and return the value and key
    E& element() { return it; }
    void setElement(const E& e) { it = e; }
    Key& key() { return k; }
    void setKey(const Key& K) { k = K; }

    // Functions to set and return the children
    inline BSTNode* left() const { return lc; }
    void setLeft(BinNode<E>* b) { lc = (BSTNode*)b; }
    inline BSTNode* right() const { return rc; }
    void setRight(BinNode<E>* b) { rc = (BSTNode*)b; }

    /* Returns ptr to the left child if it is not a thread, else returns NULL.
    Time Complexity = Constant, O(1) */
    inline BSTNode* safeLeft() const { return (getLThr()) ? NULL : left(); }

    /* Returns ptr to the right child if it is not a thread, else returns NULL.
    Time Complexity = Constant, O(1) */
    inline BSTNode* safeRight() const { return (getRThr()) ? NULL : right(); }

    // Thread boolean getters and setters
    
    /* Returns true if the left child is a thread.
    Time Complexity = Constant, O(1) */
    bool getLThr() const { 
        return (threadBitField % 2 == 1);// Return true if odd 
    }

    /* Returns true if the right child is a thread.
    Time Complexity = Constant, O(1) */
    bool getRThr() const { 
        return (threadBitField > 1);// Return true if greater than 1 
    }

    /* Sets the left thread bool to the parameter.
    Time Complexity = Constant, O(1) */
    void setLThr(bool b) { 
        if (threadBitField > 1)// 2 or 3
            if (b)
                threadBitField = 3;
            else
                threadBitField = 2;
        else// 0 or 1
            if (b)
                threadBitField = 1;
            else
                threadBitField = 0; 
    }// End of setLThr

    /* Sets the right thread bool to the parameter.
    Time Complexity = Constant, O(1) */
    void setRThr(bool b) {
        if (threadBitField % 2 == 0)// 0 or 2
            if (b)
                threadBitField = 2;
            else
                threadBitField = 0;
        else// 1 or 3
            if (b)
                threadBitField = 3;
            else
                threadBitField = 1; 
    }// End of setRThr

    // Return true if it is a leaf, false otherwise
    bool isLeaf() { return (lc == NULL) && (rc == NULL); }
};