PV8.cpp

template<class T, class U>
class Node
{
public:
    T key;
    U value;

    std::shared_ptr<Node<T, U>> left, right;

    Node() { }
    Node(const T& _key): key(_key){ }
    Node(const std::shared_ptr<Node<T, U>> &node)
    {
        key = node->key;
        value = node->value;

        if (node->left)
            node->left = std::make_shared<Node<T, U>>(Node<T, U>(node->left));
        if (node->right)
            node->right = std::make_shared<Node<T, U>>(Node<T, U>(node->right));
    }
    Node(const T &_key, const U &_val) :
        key(_key), value(_val), left(), right() { }

    U& Add(const T& _key)
    {
        if (_key < key)
            return (left = std::make_shared<Node<T, U>>(Node<T, U>(_key)))->value;
        else
            return (right = std::make_shared<Node<T, U>>(Node<T, U>(_key)))->value;
    }
};


template<class T, class U>
class BinStabloMapa : public Mapa<T, U>
{
private:
    std::shared_ptr<Node<T, U>> root;
    int count;
    typedef std::shared_ptr<Node<T, U>> NodePtr;
    U& findOrAdd(const T &key)
    {
        if (count == 0)
        {
            count = 1;
            root = std::make_shared<Node<T, U>>(Node<T, U>(key, U()));
            return root->value;
        }
        else if (root->key == key)
            return root->value;

        std::shared_ptr<Node<T, U>> current = root;
        std::shared_ptr<Node<T, U>> prev = root;

        while (current)
        {
            prev = current;
            if (key == current->key)
                return current->value;
            else if (key < current->key)
                current = current->left;
            else if (current->key < key)
                current = current->right;
        }
        count++;

        return prev->Add(key);
    }

    U findOrDefault(const T &key) const
    {
        if (count == 0)
            return U();
        else if (root->key == key)
            return root->value;

        std::shared_ptr<Node<T, U>> current = root;
        std::shared_ptr<Node<T, U>> prev = root;

        while (current)
        {
            prev = current;
            if (key == current->key)
                return current->value;
            if (key < current->key)
                current = current->left;
            else if (key > current->key)
                current = current->right;
        }

        return U();
    }

    bool remove(const T &key, NodePtr &current)
    {
        if (current && key < current->key)
            return remove(key, current->left);
        else if (current && current->key < key)
            return remove(key, current->right);
        else if (current && current->key == key)
        {
            if (!current->left)
                current = current->right;
            else if (!current->right)
                current = current->left;
            else
            {
                NodePtr next = current->left;
                while (next->right)
                    next = next->right;
                current->key = next->key;
                current->value = next->value;
                remove(next->key, current->left);
            }
            return true;
        }
        return false;
    }

public:
    BinStabloMapa() : root(), count(0) { }
    BinStabloMapa(BinStabloMapa<T, U>&&) = default;
    BinStabloMapa& operator =(BinStabloMapa<T, U>&&) = default;
    BinStabloMapa(const BinStabloMapa<T, U> &bs):root(bs.root) { count = bs.count; }
    BinStabloMapa& operator =(const BinStabloMapa<T, U>& bs)
    {
        if (this == &bs)
            return *this;
        count = bs.count;
        root = std::make_shared<Node<T, U>>(bs.root);
        return *this;
    }
    void obrisi() override { count = 0; root.reset(); }
    int brojElemenata() const override { return count; }
    U operator[](const T &key) const { return findOrDefault(key); }
    U& operator[](const T &key) override {
        return findOrAdd(key); }
    void obrisi(const T &key) override { count -= remove(key, root); }
};