#pragma once
#include <iostream>
using namespace std;

class map_pair {
public:
	int key; // ключ
	int data; // значение

	map_pair() {

	}

	map_pair(int key, int s) {
		this->key = key;
		this->data = s;
	}

	//Сравнение ключей (<= >=) для создания мультимепа
	bool operator >(map_pair p) {
		return this->key >= p.key;
	}

	bool operator <(map_pair& p) {
		return this->key <= p.key;
	}

	friend ostream& operator <<(ostream& o, map_pair& p);
};
//для вывода элементов
ostream& operator <<(ostream& o, map_pair& p) {
	o << "{" << p.key << ", " << p.key << "} " << endl;
	return o;
}

template <typename T>
class map {
public:
	class node {
	public:
		node* right;
		node* left;
		map_pair key;

		node() {
			right = nullptr;
			left = nullptr;
		}

		node(map_pair& key) {
			this->key = key;
			right = nullptr;
			left = nullptr;
		}
	};

	node* root;

	map() {
		root = nullptr;
	}

	void Push(node* parent, map_pair& key) {
		if (key > parent->key) {
			if (parent->right == nullptr) {
				parent->right = new node(key);
			}
			else {
				push(parent->right, key);
			}
		}
		else {
			if (key < parent->key) {
				if (parent->left == nullptr) {
					parent->left = new node(key);
				}
				else {
					push(parent->left, key);
				}
			}
		}
	}

	void Push(map_pair& key) {
		if (root == nullptr)
			root = new node(key);
		else
			push(root, key);
	}

	void Print(node* parent) {
		if (parent->right != nullptr)
			print(parent->right);

		cout << parent->key;

		if (parent->left != nullptr)
			print(parent->left);
	}

	void Print() {
		print(root);
	}

    static node* findl(node* parent) {
        node* n = parent;

        while (n->left != NULL) {
            n = n->left;
        }

        return n;
    }

    static node* findr(node* parent) {
        node* n = parent;

        while (n->right != NULL) {
            n = n->right;
        }

        return n;
    }

    class iterator {
    public:
        node* current;
        stack<node*> s;

        iterator(node* n) {
            current = n;
        }

        void findn() {
            if (current->right != NULL) {
                s.push(current);
                current = map::findl(current->right);
            }
            else {
                node* parent = current->parent;

                if (!s.empty()) {

                    node* top = s.top();
                    while (top == parent) {
                        parent = top->parent;
                        s.pop();
                        if (s.empty())
                            break;
                        top = s.top();
                    }

                    current = parent;
                }
            }
        }

        bool operator !=(iterator other) {
            return current != other.current;
        }
        iterator operator++() {
            findn();
            return *this;
        }

        iterator operator++(int) {
            findn();
            return *this;
        }

        T operator *() {
            return current->key;
        }
    };

    iterator begin() {
        return iterator(findl(root));
    }

    iterator end() {
        return iterator(NULL);
    }
};