Advertisement
deushiro

Untitled

Jan 13th, 2021
803
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.62 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. template<typename Key, typename T>
  4. class Map{
  5. public:
  6.     typedef Key key_type;
  7.     typedef T map_type;
  8.     typedef std::pair<Key,T> value_type;
  9.  
  10.     enum Color{
  11.         RED,BLACK
  12.     };
  13.  
  14.     struct Node{
  15.         Color color;
  16.         Node* prev;
  17.         Node* next;
  18.         Node* parent;
  19.         Node* left;
  20.         Node* right;
  21.  
  22.         value_type val;
  23.  
  24.         Node():prev(nullptr),next(nullptr),left(nullptr),right(nullptr),parent(nullptr),color(RED){}
  25.         Node(value_type val_):Node(), val(val_){}
  26.     };
  27.     class iterator{
  28.     public:
  29.         Node* ptr;
  30.  
  31.         iterator() = delete;
  32.         iterator(Node* ptr_):ptr(ptr_){}
  33.         iterator(const iterator& it_){
  34.             if(&this == it_)
  35.                 return;
  36.             ptr = new Node(*(it_.ptr));
  37.         }
  38.         iterator& operator++(){
  39.             ptr = ptr->next;
  40.             return *this;
  41.         }
  42.         iterator operator++(int){
  43.             iterator tmp = *this;
  44.             operator++();
  45.             return tmp;
  46.         }
  47.         iterator& operator--(){
  48.             ptr = ptr->prev;
  49.             return *this;
  50.         }
  51.         iterator operator--(int){
  52.             iterator tmp = *this;
  53.             operator--();
  54.             return tmp;
  55.         }
  56.         value_type& operator*() const{
  57.             return ptr->val;
  58.         }
  59.         Node* operator->() const{
  60.             return ptr;
  61.         }
  62.         bool operator==(const iterator& rhs) const{
  63.             return (ptr == rhs.ptr);
  64.         }
  65.         bool operator!=(const iterator& rhs) const{
  66.             return !(*this == rhs);
  67.         }
  68.     };
  69.     iterator begin(){
  70.         return head->next;
  71.     }
  72.     iterator end(){
  73.         return tail;
  74.     }
  75.  
  76.     std::pair<iterator,bool> insert(const value_type& v){
  77.         Node* newNode = new Node(v);
  78.         std::pair<iterator,bool> p = _recursive_insert_(root,newNode);
  79.         if(!p.second){
  80.             delete newNode;
  81.         }else {
  82.             _repair_tree_(newNode);
  83.             root = newNode;
  84.             while (get_parent(root) != nullptr)
  85.                 root = get_parent(root);
  86.         }
  87.         return p;
  88.     }
  89.  
  90. private:
  91.     Node* root;
  92.     Node* head;
  93.     Node* tail;
  94.  
  95.     Node* get_parent(Node* current){
  96.         return (current->parent == nullptr ? nullptr : current->parent);
  97.     }
  98.     Node* get_most_right_node(Node* current){
  99.         return(current->right == nullptr ? current : get_most_right_node(current->right));
  100.     }
  101.     Node* get_most_left_node(Node* current){
  102.         return(current->left == nullptr ? current : get_most_left_node(current->right));
  103.     }
  104.  
  105.  
  106.  
  107.     std::pair<iterator,bool> _recursive_insert_(Node* place, Node* who){
  108.         if(place->val.first == who->val.first)
  109.             return std::make_pair(iterator(place),false);
  110.         if(place->val.first > who->val.first){
  111.             if(place->left == nullptr) {
  112.                 place->left = who;
  113.                 who->parent = place;
  114.             }else {
  115.                  return _recursive_insert_(place->left, who);
  116.             }
  117.         }
  118.         else{
  119.             if(place->right == nullptr) {
  120.                 place->right = who;
  121.                 who->parent = place;
  122.             }else {
  123.                 return _recursive_insert_(place->right, who);
  124.             }
  125.         }
  126.         who->color = RED;
  127.         who->parent = get_parent(who);
  128.         who->left = nullptr;
  129.         who->right = nullptr;
  130.         if(place->val.first > who->val.first){
  131.             who->next = place;
  132.             who->prev = get_most_right_node();
  133.         }
  134.  
  135.  
  136.     }
  137. };
  138.  
  139.  
  140. int main(){
  141.     return 0;
  142. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement