Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement