scapegoat_tree.hpp

Go to the documentation of this file.

 
#ifndef SCAPEGOATTREE_SCAPEGOATTREE_HPP
#define SCAPEGOATTREE_SCAPEGOATTREE_HPP
 
#include <string>
#include <cmath>
#include "vector.hpp"
#include "stack.hpp"
#include "Node.hpp"
enum class OpType {
    Insert,     // Insertion of a single value
    Delete,     // Deletion of a single value
    BatchStart, // Marker for the beginning of a batch operation
    BatchEnd    // Marker for the end of a batch operation
};
 
template<typename T>
struct Command {
    OpType type; // Type of the operation
    T value;     // Value associated with the operation
};
 
template<typename T>
class ScapeGoatTree {
 
    using TreeNode = Node<T>;
    TreeNode* root{};
    int nNodes{};
    int rebuildCount = 0;
    Stack<Command<T>> undoStack;
    Stack<Command<T>> redoStack;
    bool isUndoing = false;
    int max_nodes = 0;
    double ALPHA = 2.0/3.0;
    // iterator class
    class iterator {
        TreeNode* curr;  // stores current node
 
    public:
        // constructor
        iterator(TreeNode* node) : curr(node) {}
 
        // dereference
        T& operator*() { return curr->value; }
 
        // pre-increment
        iterator& operator++() {
            curr = findSuccessor(curr);
            return *this;
        }
 
        // post-increment
        iterator operator++(int) {
            iterator temp = *this;
            ++(*this);
            return temp;
        }
 
        // comparison
        bool operator!=(const iterator& other) const { return curr != other.curr; }
    };
 
    static int findH(const TreeNode* node);
    static  unsigned int countN(const TreeNode* node);
    TreeNode* findTraitor(TreeNode* node);
    TreeNode* rebuildTree(int start,int end,TreeNode* parent_node,T* array);
    void inorderTraversal(const TreeNode*node, int &i,T*& array) const;
    static void postorderTraversal(const TreeNode* node);
    void preorderTraversal(const TreeNode* node);
    void displayPreOrder(const TreeNode* node, std::ostream& os);
    void displayInOrder(const TreeNode* node, std::ostream& os);
    void displayPostOrder(const TreeNode* node, std::ostream& os);
    [[nodiscard]] int getThreshold() const {return static_cast<int>(log(nNodes) / log(1/ALPHA));}
    void DeletionRebuild();
    bool areTreesEqual(const TreeNode* n1, const TreeNode* n2) const;
    void restructure_subtree(TreeNode *newNode);
    T sumHelper(TreeNode* node,T min,T max);
    void rangeHelper(TreeNode* node,T min,T max,Vector<T>& range);
    T kthSmallestHelper(TreeNode *node, int k) const;
  static TreeNode* findSuccessor(TreeNode* node);
 
 
 
 
public:
 
    ScapeGoatTree();
ScapeGoatTree(double alpha);
    void insert(T value);
 
    void insertBatch( const Vector<T> &values);
 
    bool deleteValue(T value);
 
    void deleteBatch(const Vector<T> &values);
 
    [[nodiscard]] bool search(const T & key) const;
    TreeNode* find_node(T& key) const;
 
    void clear();
    void undo();
    void redo();
    T sumInRange(T min, T max);
    T getMin();
    T getMax();
    Vector<T> valuesInRange(T min,T max);
    T getSuccessor(T value) const;
    T kthSmallest(int k) const;
    std::pair<ScapeGoatTree, ScapeGoatTree> split(T value);
    int updateSize(TreeNode*& node);
    void changeAlpha(const double alpha){if (alpha > 1 or alpha < 0.5)return; ALPHA=alpha;}
    [[nodiscard]] std::string isBalanced() const;
 
 
    const TreeNode* getRoot();
    iterator begin();
 
    static iterator end();
 
    ScapeGoatTree(const ScapeGoatTree &Otree);
 
    ScapeGoatTree(ScapeGoatTree&& other) noexcept;
 
    ~ScapeGoatTree();
 
    std::string displayPreOrder(); // for display
 
    std::string displayInOrder() ; // for display
 
    std::string displayPostOrder() ; // for display
 
    std::string displayLevels(); // for display
 
    bool operator[](T value) const;
 
    ScapeGoatTree operator+(const ScapeGoatTree &other) const;
 
    ScapeGoatTree& operator=(const ScapeGoatTree& other);
 
    ScapeGoatTree& operator=(ScapeGoatTree&& other) noexcept;
 
    ScapeGoatTree &operator=(int value);
 
    bool operator==(const ScapeGoatTree &tree) const;
 
    bool operator!=(const ScapeGoatTree &tree) const;
 
    bool operator!() const;
 
    void operator+(const T& value);
 
    bool operator-(const T& value);
 
    bool operator-=(const T& value);
 
    void operator+=(const T& value);
 
 
 
};
#include "scapegoat_tree.tpp"
 
#endif //SCAPEGOATTREE_SCAPEGOATTREE_HPP