Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- template<typename Key, typename T>
- class Map{
- public:
- typedef Key key_type;
- typedef T map_type;
- typedef std::pair<Key,T> value_type;
- enum Color{
- RED,BLACK
- };
- struct Node{
- Color color;
- Node* prev;
- Node* next;
- Node* parent;
- Node* left;
- Node* right;
- value_type val;
- Node():prev(nullptr),next(nullptr),left(nullptr),right(nullptr),parent(nullptr),color(RED){}
- Node(value_type val_):Node(), val(val_){}
- };
- class iterator{
- public:
- Node* ptr;
- iterator() = delete;
- iterator(Node* ptr_):ptr(ptr_){}
- iterator(const iterator& it_){
- if(&this == it_)
- return;
- ptr = new Node(*(it_.ptr));
- }
- iterator& operator++(){
- ptr = ptr->next;
- return *this;
- }
- iterator operator++(int){
- iterator tmp = *this;
- operator++();
- return tmp;
- }
- iterator& operator--(){
- ptr = ptr->prev;
- return *this;
- }
- iterator operator--(int){
- iterator tmp = *this;
- operator--();
- return tmp;
- }
- value_type& operator*() const{
- return ptr->val;
- }
- Node* operator->() const{
- return ptr;
- }
- bool operator==(const iterator& rhs) const{
- return (ptr == rhs.ptr);
- }
- bool operator!=(const iterator& rhs) const{
- return !(*this == rhs);
- }
- };
- iterator begin(){
- return head->next;
- }
- iterator end(){
- return tail;
- }
- std::pair<iterator,bool> insert(const value_type& v){
- Node* newNode = new Node(v);
- std::pair<iterator,bool> p = _recursive_insert_(root,newNode);
- if(!p.second){
- delete newNode;
- }else {
- _repair_tree_(newNode);
- root = newNode;
- while (get_parent(root) != nullptr)
- root = get_parent(root);
- }
- return p;
- }
- private:
- Node* root;
- Node* head;
- Node* tail;
- Node* get_parent(Node* current){
- return (current->parent == nullptr ? nullptr : current->parent);
- }
- Node* get_most_right_node(Node* current){
- return(current->right == nullptr ? current : get_most_right_node(current->right));
- }
- Node* get_most_left_node(Node* current){
- return(current->left == nullptr ? current : get_most_left_node(current->right));
- }
- std::pair<iterator,bool> _recursive_insert_(Node* place, Node* who){
- if(place->val.first == who->val.first)
- return std::make_pair(iterator(place),false);
- if(place->val.first > who->val.first){
- if(place->left == nullptr) {
- place->left = who;
- who->parent = place;
- }else {
- return _recursive_insert_(place->left, who);
- }
- }
- else{
- if(place->right == nullptr) {
- place->right = who;
- who->parent = place;
- }else {
- return _recursive_insert_(place->right, who);
- }
- }
- who->color = RED;
- who->parent = get_parent(who);
- who->left = nullptr;
- who->right = nullptr;
- if(place->val.first > who->val.first){
- who->next = place;
- who->prev = get_most_right_node();
- }
- }
- };
- int main(){
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement