Thursday, August 11, 2022
HomeSoftware DevelopmentConstruct a customized Map utilizing Header file in C++

Construct a customized Map utilizing Header file in C++

[ad_1]

map.h

   

  

#embody <iostream>

utilizing namespace std;

  

class Map {

non-public:

    Map* iterator(int first)

    {

        

        

        

        Map* temp = root;

  

        

        

        whereas (temp != nullptr && 

               temp->first != first) {

  

            

            

            if (first < temp->first) {

                temp = temp->left;

            }

  

            

            else {

                temp = temp->proper;

            }

        }

        

        

        return temp;

    }

  

    

    

    

    

    const Map* iterator(int first) const

    {

        Map* temp = root;

        whereas (temp != nullptr 

               && temp->first != first) {

            if (first < temp->first) {

                temp = temp->left;

            }

            else {

                temp = temp->proper;

            }

        }

        return temp;

    }

  

    

    

    

    

    

    

    

    

    

    const int search(int first) const

    {

        const Map* temp = iterator(first);

        if (temp != nullptr) {

            return temp->second;

        }

        return 0;

    }

  

    

    

    

    Map* create(int first)

    {

        Map* newnode = (Map*)malloc(sizeof(Map));

        newnode->first = first;

        newnode->second = 0;

        newnode->left = nullptr;

        newnode->proper = nullptr;

        newnode->par = nullptr;

  

        

        

        

        

        newnode->depth = 1;

        return newnode;

    }

  

    

    

    

    

    void right_rotation(Map* x)

    {

        Map* y = x->left;

        x->left = y->proper;

        if (y->proper != nullptr) {

            y->right->par = x;

        }

        if (x->par != nullptr && x->par->proper == x) {

            x->par->proper = y;

        }

        else if (x->par != nullptr && x->par->left == x) {

            x->par->left = y;

        }

        y->par = x->par;

        y->proper = x;

        x->par = y;

    }

  

    

    

    void left_rotation(Map* x)

    {

        Map* y = x->proper;

        x->proper = y->left;

        if (y->left != nullptr) {

            y->left->par = x;

        }

        if (x->par != nullptr && x->par->left == x) {

            x->par->left = y;

        }

        else if (x->par != nullptr && x->par->proper == x) {

            x->par->proper = y;

        }

        y->par = x->par;

        y->left = x;

        x->par = y;

    }

  

    

    

    

  

    void helper(Map* node)

    {

        

        if (depthf(node->left) 

            - depthf(node->proper) > 1) {

  

            

            

            

            

            if (depthf(node->left->left)

                > depthf(node->left->proper)) {

                node->depth

                    = max(depthf(node->proper) + 1,

                          depthf(node->left->proper) + 1);

                node->left->depth

                    = max(depthf(node->left->left) + 1,

                          depthf(node) + 1);

                right_rotation(node);

            }

  

            

            

            

            

            else {

                node->left->depth = max(

                    depthf(node->left->left) + 1,

                    depthf(node->left->right->left) 

                    + 1);

                node->depth 

                    = max(depthf(node->proper) + 1,

                      depthf(node->left->right->proper) + 1);

                node->left->right->depth

                    = max(depthf(node) + 1,

                          depthf(node->left) + 1);

                left_rotation(node->left);

                right_rotation(node);

            }

        }

  

        

        else if (depthf(node->left) 

                 - depthf(node->proper) < -1) {

  

            

            

            

            if (depthf(node->right->proper)

                > depthf(node->right->left)) {

                node->depth

                    = max(depthf(node->left) + 1,

                          depthf(node->right->left) + 1);

                node->right->depth

                    = max(depthf(node->right->proper) + 1,

                          depthf(node) + 1);

                left_rotation(node);

            }

  

            

            

            

            

            else {

                node->right->depth = max(

                    depthf(node->right->proper) + 1,

                    depthf(node->right->left->proper) + 1);

                node->depth = max(

                    depthf(node->left) + 1,

                    depthf(node->right->left->left) + 1);

                node->right->left->depth

                    = max(depthf(node) + 1,

                          depthf(node->proper) + 1);

                right_rotation(node->proper);

                left_rotation(node);

            }

        }

    }

  

    

    void stability(Map* node)

    {

        whereas (node != root) {

            int d = node->depth;

            node = node->par;

            if (node->depth < d + 1) {

                node->depth = d + 1;

            }

            if (node == root

                && depthf(node->left) > 1) {

                if (depthf(node->left->left)

                    > depthf(node->left->proper)) {

                    root = node->left;

                }

                else {

                    root = node->left->proper;

                }

                helper(node);

                break;

            }

            else if (node == root

                     && depthf(node->left)

                                - depthf(node->proper)

                            < -1) {

                if (depthf(node->right->proper)

                    > depthf(node->right->left)) {

                    root = node->proper;

                }

                else {

                    root = node->right->left;

                }

                helper(node);

                break;

            }

            helper(node);

        }

    }

  

    

    

  

    int depthf(Map* node)

    {

        if (node == nullptr)

  

            

            return 0;

        return node->depth;

    }

  

    Map* insert(int first)

    {

        cnt++;

        Map* newnode = create(first);

        if (root == nullptr) {

            root = newnode;

            return root;

        }

        Map *temp = root, *prev = nullptr;

        whereas (temp != nullptr) {

            prev = temp;

            if (first < temp->first) {

                temp = temp->left;

            }

            else if (first > temp->first) {

                temp = temp->proper;

            }

            else {

                free(newnode);

                cnt--;

                return temp;

            }

        }

        if (first < prev->first) {

            prev->left = newnode;

        }

        else {

            prev->proper = newnode;

        }

        newnode->par = prev;

        stability(newnode);

        return newnode;

    }

  

    

    

    Map* inorderPredecessor(Map* head)

    {

        if (head == 0)

            return head;

        whereas (head->proper != 0) {

            head = head->proper;

        }

        return head;

    }

  

    

    

    Map* inorderSuccessor(Map* head)

    {

        if (head == 0)

            return head;

        whereas (head->left != 0) {

            head = head->left;

        }

        return head;

    }

  

public:

    

    

    static class Map* root;

    static int cnt;

  

    

    Map *left, *proper, *par;

    int first, second, depth;

  

    

    

    

    

    

    int& operator[](int key) { 

        return insert(key)->second; 

    }

  

    

    

    

    

    

    

  

    

    

  

    

    

    

  

    

    

    

    

    

    const int operator[](int key) const

    {

        return search(key);

    }

  

    

    

    int depend(int first)

    {

        Map* temp = iterator(first);

        if (temp != nullptr) {

            return 1;

        }

        return 0;

    }

  

    

    int dimension(void) { 

        return cnt; 

    }

  

    

    void erase(int first, Map* temp = root)

    {

        Map* prev = 0;

        cnt--;

        whereas (temp != 0 && 

               temp->first != first) {

            prev = temp;

            if (first < temp->first) {

                temp = temp->left;

            }

            else if (first > temp->first) {

                temp = temp->proper;

            }

        }

        if (temp == nullptr) {

            cnt++;

            return;

        }

        if (cnt == 0 && temp == root) {

            free(temp);

            root = nullptr;

            return;

        }

        Map* l 

            = inorderPredecessor(temp->left);

        Map* r 

            = inorderSuccessor(temp->proper);

        if (l == 0 && r == 0) {

            if (prev == 0) {

                root = 0;

            }

            else {

                if (prev->left == temp) {

                    prev->left = 0;

                }

                else {

                    prev->proper = 0;

                }

                free(temp);

                stability(prev);

            }

            return;

        }

        Map* begin;

        if (l != 0) {

            if (l == temp->left) {

                l->proper = temp->proper;

                if (l->proper != 0) {

                    l->right->par = l;

                }

                begin = l;

            }

            else {

                if (l->left != 0) {

                    l->left->par = l->par;

                }

                begin = l->par;

                l->par->proper = l->left;

                l->proper = temp->proper;

                l->par = 0;

                if (l->proper != 0) {

                    l->right->par = l;

                }

                l->left = temp->left;

                temp->left->par = l;

            }

            if (prev == 0) {

                root = l;

            }

            else {

                if (prev->left == temp) {

                    prev->left = l;

                    l->par = prev;

                }

                else {

                    prev->proper = l;

                    l->par = prev;

                }

                free(temp);

            }

            stability(begin);

            return;

        }

        else {

            if (r == temp->proper) {

                r->left = temp->left;

                if (r->left != 0) {

                    r->left->par = r;

                }

                begin = r;

            }

            else {

                if (r->proper != 0) {

                    r->right->par = r->par;

                }

                begin = r->par;

                r->par->left = r->proper;

                r->left = temp->left;

                r->par = 0;

                if (r->left != 0) {

                    r->left->par = r;

                }

                r->proper = temp->proper;

                temp->right->par = r;

            }

            if (prev == 0) {

                root = r;

            }

            else {

                if (prev->proper == temp) {

                    prev->proper = r;

                    r->par = prev;

                }

                else {

                    prev->left = r;

                    r->par = prev;

                }

                free(temp);

            }

            stability(begin);

            return;

        }

    }

    

    

    bool empty(void)

    {

        if (root == 0)

            return true;

        return false;

    }

    

    

    

    void replace(int first, int second)

    {

        Map* temp = iterator(first);

        if (temp != nullptr) {

            temp->second = second;

        }

    }

  

    

    

    

    

    void clear(void)

    {

        whereas (root != nullptr) {

            erase(root->first);

        }

    }

  

    

    void iterate(Map* head = root)

    {

        if (root == 0)

            return;

        if (head->left != 0) {

            iterate(head->left);

        }

        cout << head->first << ' ';

        if (head->proper != 0) {

            iterate(head->proper);

        }

    }

  

    

    

    Map* discover(int first) { 

        return iterator(first); 

    }

  

    

    

    void insert(int first, int second)

    {

        Map* temp = iterator(first);

        if (temp == nullptr) {

            insert(first)->second = second;

        }

        else {

            temp->second = second;

        }

    }

};

  

Map* Map::root = nullptr;

int Map::cnt = 0;

[ad_2]

RELATED ARTICLES

Most Popular

Recent Comments