#ifndef TREEMULTIMAP_INCLUDED
#define TREEMULTIMAP_INCLUDED

template <typename KeyType, typename ValueType>
class TreeMultimap
{
  public:

      // When you search for a particular key in the multimap, you receive an iterator object as the result
      // The iterator object can then be used to obtain all values that were associated with the searched-for key
      class Iterator
      {
      public:
          Iterator(std::vector<ValueType>* values = nullptr)
          {
              m_values = values;
              m_index = 0;
          }

          bool is_valid() const
          {
              if (m_values == nullptr || m_index >= m_values->size())
                  return false;

              return true;
          }

          ValueType& get_value() const
          {
              // Ask about throw and catch later
              if (is_valid())
                  // *m_values is the dereferenced vector being pointed to by m_values
                  return (*m_values)[m_index];
          }

          void advance()
          {
              if (is_valid())
                  m_index++;
          }

      private:
          std::vector<ValueType>* m_values;
          int m_index;
      };

    TreeMultimap()
    {
        m_root = nullptr;
    }

    ~TreeMultimap()
    {
        // Postfix deletion so that we simply delete all the leaves first

        delete_tree_multimap(m_root);
        
    }

    void insert(const KeyType& key, const ValueType& value)
    {
        KeyType key_copy = key;
        ValueType value_copy = value;

        // First insertion
        if (m_root == nullptr)
        {
            m_root = new Node(key_copy);
            m_root->values.push_back(value_copy);
            return;
        }

        Node* curr = m_root;
        for (;;)
        {
            // If the desired to add node has the same key value as the one being evaluated
            if (key_copy == curr->node_Key)
            {
                curr->values.push_back(value_copy);
                return;
            }

            // Desired to add node is less than the one being evaluated
            else if (key_copy < curr->node_Key)
            {
                // If the node being evaluated has a left branch, simply move to the left node to evaluate
                if (curr->left != nullptr)
                    // This now makes us go back to the beginning of the for loop
                    curr = curr->left;

                // If it doesn't, then we can add this node to the left branch
                else
                {
                    curr->left = new Node(key_copy);
                    curr->left->values.push_back(value_copy);
                    return;
                }
            }

            // Desired to add node is more than the one being evaluaed
            else
            {
                // Same concept as above
                if (curr->right != nullptr)
                    curr = curr->right;

                else
                {
                    curr->right = new Node(key_copy);
                    curr->left->values.push_back(value_copy);
                    return;
                }
            }
        }
    }

    Iterator find(const KeyType& key) const
    {
        Node* curr = m_root;
        while (curr != nullptr)
        {
            if (key == curr->node_Key)
                return Iterator(&(curr->values));
            else if (key < curr->node_Key)
                curr = curr->left;
            else
                curr = curr->right;
        }

        return Iterator();  // Replace this line with correct code.
    }

  private:
      struct Node
      {
          Node(const KeyType& Key)
          {
              node_Key = Key;
              left = nullptr;
              right = nullptr;
          }
          KeyType node_Key;
          std::vector<ValueType> values;
          Node *left, *right;
      };

      Node *m_root;

      void delete_tree_multimap(Node* curr)
      {
          // Post-order deletion so we delete all leaves first

          if (curr == nullptr)
              return;
          delete_tree_multimap(curr->left);
          delete_tree_multimap(curr->right);
          delete curr;
      }
};

#endif // TREEMULTIMAP_INCLUDED