AVL_Tree

template <typename T>
struct KeySerializationTrait {
    static std::string Serialize(const T& t) { std::stringstream ss; ss << t; return ss.str(); }
    static T Deserialize(const std::string& str) { T tmp;  std::stringstream(str) >> tmp; return tmp; }
};

//////////////////////////////////////////////////////////////////////////

template <typename T>
struct FileTypeSerializationTrait
{
    static void Serialize(std::ostream& fileStream, const T& item) { fileStream << item; }
    static T Deserialize(std::istream& fileStream) { T tmp; fileStream >> tmp; return tmp; }
};

//////////////////////////////////////////////////////////////////////////

template <>
struct FileTypeSerializationTrait <std::string> {
    static void Serialize(std::ostream& fileStream, const std::string& str) {
        fileStream << str;
    }
    static std::string Deserialize(std::istream& fileStream) {
        return std::string((std::istreambuf_iterator<char>(fileStream)), std::istreambuf_iterator<char>());
    };
};

//////////////////////////////////////////////////////////////////////////


template <class Key, class mapped_type, class Compare = std::less<Key>>
class AVL_Tree
{
private:
    //struktura uzla stromu
    struct Tree_
    {
        Key key;
        std::string* addr;
        unsigned char height;
        Tree_* parent;
        Tree_* left;
        Tree_* right;
        Tree_(Key k, std::string* p) {
            key = k;
            addr = p;
            left = right = parent = 0;
            height = 1;
        }
        //ja mohl bych udelat get a set jako metody AVL_Tree za misto metod Tree_, ale  pro iterator bude jednoduse aby on mel v sobe pouze odkaz na uzel, nez odkaz na celou tridu AVL.
        mapped_type getValue()
        {
            std::string address = createAddres(*addr, KeySerializationTrait<Key>::Serialize(key));
            std::ifstream ifs(address);
            mapped_type tmp = FileTypeSerializationTrait<mapped_type>::Deserialize(ifs);
            ifs.close();
            return tmp;
        }
        void setValue(mapped_type a)
        {
            std::string address = createAddres(*addr, KeySerializationTrait<Key>::Serialize(key));
            std::ofstream ofs(address);
            FileTypeSerializationTrait<mapped_type>::Serialize(ofs, a);
            ofs.close();
        }
        ~Tree_()
        {

        }
    };

    //nazev slozky
    std::string dirName;
    //ukazatel na root
    Tree_ *root;
    //ukazatel na posledni spracovany uzel
    Tree_ *lastAction;
    //pocet uzlu ve dreve
    int count;
    //Comparator
    Compare comp;


public:
    //mohl bych udelat iteratory ven, ale v takovem pripade bych musel template delat taky
    class const_iterator;

    //iteratory
    class iterator
    {
    public:
        typedef iterator self_type;
        typedef std::pair<Key, mapped_type> value_type;
        typedef value_type& reference;
        typedef value_type* pointer;
        typedef std::forward_iterator_tag iterator_category;
        typedef int difference_type;
        value_type currPair;
        ///konstruktory
        iterator()
        {
            curr = nullptr;
        }

        iterator(Tree_ &n)
        {
            curr = &n;
            if (curr)
            {
                currPair = std::make_pair(curr->key, curr->getValue());
            }
        }

        //v mojem priklade iteratoru ne ma smysl delat 100% copy konstruktor, protoze v iteratoru mame ukazatel na uzel dreva. Se kterym potom pracujeme
        //kdy bych to potreboval, mohl bych zakazat kopy konstruktor  `iterator(const self_type& other)=delete`
        iterator(const self_type& other)
        {
            curr = other.curr;
            if (curr)
            {
                currPair = other.currPair;
            }
        }

        //move "rvalue reference" konstruktor
        iterator(self_type&& other)
        {
            curr = other.curr;
            other.curr = nullptr;
            if (curr)
            {
                currPair = other.currPair;
            }
        }

        //klasicky operator assigment , kdy bych to potreboval, mohl bych zakazat assigment  `self_type& operator=(const self_type& other)=delete`
        self_type& operator=(const self_type& other)
        {
            currPair = other.currPair;
            return *this;
        }

        //move assigment operator
        self_type& operator=(self_type&& other)
        {
            curr = other.curr;
            currPair = other.currPair;
            return *this;
        }
        ///operatory
        //prefix increment
        self_type& operator++() {
            if (curr)
                if (currPair.second != curr->getValue())
                    curr->setValue(currPair.second);
            curr = successor(); // point to next node
            if (curr)
                currPair = std::make_pair(curr->key, curr->getValue());
            return *this;
        }

        //postfix increment (it++)
        self_type operator++(int)
        {
            self_type old = *this;
            ++(*this);
            return old;
        }

        //reference
        reference operator*() {
            return currPair;
        }

        //pointer
        pointer operator->()
        {
            return &currPair;
        }

        //testovani podobnosty
        bool operator!=(self_type const & other) const {
            return this->curr != other.curr;
        }

        //operator dereference
        bool operator==(self_type const & other) const {
            return this->curr == other.curr;
        }

        //konvertovani do const iteratoru
        operator const_iterator() const { return const_iterator(*curr); }

        //kontrola ukazuje li nekam iterator, nebo prazdny
        bool isEmpty()
        {
            if (curr)
                return false;
            return true;
        }

    private:
        //uzel na ktery ukazuuje iterator
        Tree_* curr;

        //Successor
        Tree_* successor()
        {
            if (curr)
                if (curr->right != 0) {
                    curr = curr->right;
                    while (curr->left != 0)
                        curr = curr->left;
                }
                else {
                    Tree_* y = curr->parent;
                    if (y == nullptr)
                        return nullptr;
                    while (curr == y->right) {
                        curr = y;
                        y = y->parent;
                        if (y == nullptr)
                            return nullptr;
                    }
                    if (curr->right != y)
                        curr = y;
                }
                return curr;
        }
    };

    class const_iterator
    {
    public:
        typedef const_iterator self_type;
        typedef std::pair<Key, mapped_type> value_type;
        typedef const value_type& reference;
        typedef const value_type* pointer;
        typedef std::forward_iterator_tag iterator_category;
        typedef int difference_type;
        value_type currPair;
        ///konstruktory
        const_iterator()
        {
            curr = nullptr;
        }

        const_iterator(Tree_ &n)
        {
            curr = &n;
            if (curr)
            {
                currPair = std::make_pair(curr->key, curr->getValue());
            }
        }

        //v mojem priklade const_iterator ne ma smysl delat 100% copy konstruktor, protoze v iteratoru mame ukazatel na uzel dreva. Se kterym potom pracujeme
        //kdy bych to potreboval, mohl bych zakazat kopy konstruktor  `const_iterator(const self_type& other)=delete`
        const_iterator(const self_type& other)
        {
            curr = other.curr;
            if (curr)
            {
                currPair = other.currPair;
            }
        }

        //move "rvalue reference" konstruktor
        const_iterator(self_type&& other)
        {
            curr = other.curr;
            other.curr = nullptr;
            if (curr)
            {
                currPair = other.currPair;
            }
        }

        //klasicky operator assigment , kdy bych to potreboval, mohl bych zakazat assigment  `self_type& operator=(const self_type& other)=delete`
        self_type& operator=(const self_type& other)
        {
            currPair = other.currPair;
            retern *this;
        }

        //move assigment operator
        self_type& operator=(self_type&& other)
        {
            curr = other.curr;
            currPair = other.currPair;
            return *this;
        }
        ///operatory
        //prefix increment
        self_type& operator++() {
            if (curr)
                if (currPair.second != curr->getValue())
                    curr->setValue(currPair.second);
            curr = successor(); // point to next node
            if (curr)
                currPair = std::make_pair(curr->key, curr->getValue());
            return *this;
        }

        // postfix increment (it++)
        self_type operator++(int)
        {
            self_type old = *this;
            ++(*this);
            return old;
        }

        //reference
        reference operator*() const {
            return currPair;
        }

        //pointer
        pointer operator->()
        {
            return &currPair;
        }
        //testovani podobnosty
        bool operator!=(self_type const & other) const {
            return this->curr != other.curr;
        }

        //operator dereference
        bool operator==(self_type const & other) const {
            return this->curr == other.curr;
        }

        //konvertovani do iteratoru
        operator iterator() const { return iterator(*curr); }

        //kontrola ukazuje li nekam iterator, nebo prazdny
        bool isEmpty()
        {
            if (curr)
                return false;
            return true;
        }

    private:
        //uzel na ktery ukazuuje iterator
        Tree_* curr;

        //Successor
        Tree_* successor()
        {
            if (curr)
                if (curr->right != 0) {
                    curr = curr->right;
                    while (curr->left != 0)
                        curr = curr->left;
                }
                else {
                    Tree_* y = curr->parent;
                    if (y == nullptr)
                        return nullptr;
                    while (curr == y->right) {
                        curr = y;
                        y = y->parent;
                        if (y == nullptr)
                            return nullptr;
                    }
                    if (curr->right != y)
                        curr = y;
                }
                return curr;
        }
    };

    //konstruktory & destruktor
    AVL_Tree() :root(nullptr), count(0), dirName("") {};

    AVL_Tree(std::string dir)
    {
        root = lastAction = nullptr;
        dirName = dir;
        count = 0;
        path p(dirName);
        std::string stringKey;
        if (fs::exists(p))
            for (auto tmp : fs::directory_iterator(p)) {
                if (fs::is_regular_file(tmp)) {
                    stringKey = tmp.path().filename().string();
                    Key key = KeySerializationTrait<Key>::Deserialize(stringKey);
                    mapped_type value = getValue(stringKey);
                    insert(std::make_pair(key, value));
                }
            }
    }

    AVL_Tree(AVL_Tree const &oth) {
        if (this != &oth) {
            this->dirName = oth.dirName;
            this->count = oth.count;
            this->root = oth.root;
            this->lastAction = oth.lastAction;
        }
    }

    ~AVL_Tree()
    {
        eraseTree(root);
        lastAction = root = nullptr;
    }


    //orerator assigment
    AVL_Tree<Key, mapped_type, Compare>& operator=(const AVL_Tree<Key, mapped_type, Compare> &oth) {
        if (this != &oth) {
            this->dirName = oth.dirName;
            this->count = oth.count;
            this->root = oth.root;
            this->lastAction = oth.lastAction;
        }
        return this;
    }


    //iteratory
    iterator begin()
    {
        if (count)
        {
            return iterator(*findMin());
        }
        return iterator();
    }

    iterator end()
    {
        iterator it(*findMax());
        if (!it.isEmpty())
            it++;
        return it;
    }

    const_iterator cbegin()
    {

        if (count)
        {
            return const_iterator(*findMin());
        }
        return const_iterator();
    }

    const_iterator cend()
    {
        const_iterator it(*findMax());
        if (!it.isEmpty())
            it++;
        return it;
    }

    //gety
    std::string getDirName()
    {
        return dirName;
    }

    int getCount() {
        return count;
    }

    //metody
    Tree_& insert(std::pair<Key, mapped_type>  const & k) // вставка ключа k в дерево с корнем p
    {
        root = insert(root, k);
        return *lastAction;
    }

    Tree_* findMin() // поиск узла с минимальным ключом в дереве p
    {
        if (root)
            return root->left ? findMin(root->left) : root;
        else return 0;
    }

    Tree_* erase(Key const & k) // удаление ключа k из дерева p
    {
        Tree_* min;
        if (!root) return 0;
        if (comp(k, root->key))
            root->left = erase(root->left, k);
        else if (comp(root->key, k))
            root->right = erase(root->right, k);
        else //  k == p->key
        {
            Tree_* q = root->left;
            Tree_* r = root->right;
            if (r == 0)
            {
                removeAddr(dirName, root->key);
                delete root;
                count--;
                lastAction = nullptr;
                return root = 0;
            }
            min = findMin(r);
            min->right = eraseMin(r);
            min->left = q;
            min->parent = 0;
            removeAddr(dirName, root->key);
            delete root;
            setParents(min, 0);
            root = balance(min);
            count--;
            return root;
        }
        root = balance(root);
        return root;
    }

    Tree_* findKey(Key const & k)
    {
        Tree_ *p = root;
        while (p)
        {
            bool b = (!comp(k, p->key) && !comp(p->key, k));
            if (b)
                return p;
            if (comp(k, p->key))
                p = p->left;
            else
                p = p->right;
        }
        return nullptr;
    }

    Tree_* findMax()
    {
        Tree_ *p = root;
        if (p)
            while (p->right != nullptr)
                p = p->right;
        return p;
    }

private:
    //vrati string s addresou slozky+/+filename
    static std::string createAddres(std::string a, std::string b)
    {
        std::string address(a);
        address.append("/");
        address.append(b);
        return address;
    }

    //maze soubor podle adressy slozky a filename, ktery tady klic
    static void removeAddr(std::string addr, Key k)
    {
        std::string address = createAddres(addr, KeySerializationTrait<Key>::Serialize(k));
        fs::remove(address);
    }

    //vrati height
    unsigned char height(Tree_* p)
    {
        return p ? p->height : 0;
    }

    //spocita a vrati b faktor
    int bFactor(Tree_* p)
    {
        return height(p->right) - height(p->left);
    }

    //upravi height
    void fixHeight(Tree_* p)
    {
        unsigned char hl = height(p->left);
        unsigned char hr = height(p->right);
        p->height = (hl > hr ? hl : hr) + 1;
    }

    //hastaveni rodicu
    void setParents(Tree_* p, Tree_* q)
    {
        if (q)
        {
            q->parent = p->parent;
            p->parent = q;
        }
        if (p->left != nullptr)
            (p->left)->parent = p;
        if (p->right != nullptr)
            (p->right)->parent = p;
    }

    //R rotace
    Tree_* rotateRight(Tree_* p) // правый поворот вокруг p
    {
        Tree_* q = p->left;
        p->left = q->right;
        q->right = p;
        setParents(p, q);
        fixHeight(p);
        fixHeight(q);
        return q;
    }

    //L rotace
    Tree_* rotateLeft(Tree_* q) // левый поворот вокруг q
    {
        Tree_* p = q->right;
        q->right = p->left;
        p->left = q;
        setParents(q, p);
        fixHeight(q);
        fixHeight(p);
        return p;
    }

    //balansovani stromu
    Tree_* balance(Tree_* p) // балансировка узла p
    {
        fixHeight(p);
        if (bFactor(p) == 2)
        {
            if (bFactor(p->right) < 0)
                p->right = rotateRight(p->right);
            return rotateLeft(p);
        }
        if (bFactor(p) == -2)
        {
            if (bFactor(p->left) > 0)
                p->left = rotateLeft(p->left);
            return rotateRight(p);
        }
        return p; // балансировка не нужна
    }

    //privava do podstromu p , pair k
    Tree_* insert(Tree_*const & p, std::pair<Key, mapped_type> k) // вставка ключа k в дерево с корнем p
    {
        if (!p)
        {
            lastAction = new Tree_(k.first, &dirName);
            lastAction->setValue(k.second);
            count++;
            return lastAction;
        }
        if (comp(k.first, p->key))
        {
            p->left = insert(p->left, k);
            (p->left)->parent = p;
        }
        else
        {
            if (!(!comp(k.first, p->key) && !comp(p->key, k.first)))
            {
                p->right = insert(p->right, k);
                (p->right)->parent = p;
            }
            else//klic uz existoval
            {
                lastAction = p;
                lastAction->setValue(k.second);
                return lastAction;
            }
        }
        return balance(p);
    }

    //rekurzivne chleda minimalni key ve podstrome p
    Tree_* findMin(Tree_*const & p) // поиск узла с минимальным ключом в дереве p
    {
        return p->left ? findMin(p->left) : p;
    }

    //rekurzivne hleda a mahe k d podstrome p
    Tree_* erase(Tree_*const & p, Key k) // удаление ключа k из дерева p
    {
        if (!p) return 0;
        if (comp(k, p->key))
            p->left = erase(p->left, k);
        else if (comp(p->key, k))
        {
            p->right = erase(p->right, k);
        }
        else //  k == p->key
        {
            Tree_* q = p->left;
            Tree_* r = p->right;
            if (!r)
            {
                if (q)
                {
                    q->parent = p->parent;
                }
                removeAddr(dirName, p->key);
                delete p;
                count--;
                return q;
            }
            Tree_* min = findMin(r);
            min->right = eraseMin(r);
            min->left = q;
            min->parent = p->parent;
            setParents(min, 0);
            count--;
            removeAddr(dirName, p->key);
            delete p;
            return balance(min);
        }
        return balance(p);
    }

    //rekurzivne chleda minimalni key ve podstrome p a maze ho
    Tree_* eraseMin(Tree_* p) // удаление узла с минимальным ключом из дерева p
    {
        if (p->left == 0)
            return p->right;
        p->left = eraseMin(p->left);
        return balance(p);
    }

    //rekurzivne maze cele drevo
    void eraseTree(Tree_* a) {
        if (0 == a) return;
        eraseTree(a->left);
        eraseTree(a->right);
        delete a;
        count--;
    }

    //vraci , je li takovy klic ve stromu nebo ne
    bool keyExist(Tree_* p, Key k)
    {
        while (p) {
            if (!p)
            {
                return false;
            }
            if (p->key == k)
            {
                return true;
            }
            if (k < p->key)
                p = p->left;
            else
                p = p->right;
        }
    }

    //vrace value z souboru k
    mapped_type getValue(std::string key)
    {
        std::string address = createAddres(dirName, key);
        std::ifstream ifs(address);
        mapped_type tmp = FileTypeSerializationTrait<mapped_type>::Deserialize(ifs);
        ifs.close();
        return tmp;
    }
};