C++ Program to Implement Dictionaries and Order Assignment Solution

Instructions

Objective

Write a C++ assignment program to manipulate dictionaries and order.

Requirements and Specifications

Source Code

// Nelson Pham, nppham // CSE101 PA#7 // Dictionary.cpp // Dictionary.cpp file to implement the required functions in Dictionary.h header file #include "Dictionary.h" Dictionary::Node::Node(keyType k, valType v) { key = k; val = v; parent = nullptr; left = nullptr; right = nullptr; } Dictionary::Dictionary() { current = nullptr; root = nullptr; nil = nullptr; num_pairs = 0; } Dictionary::Dictionary(const Dictionary& D) { if (D.root != nullptr) { root = new Node(D.root->key, D.root->val); preOrderCopy(D.root, root); } num_pairs = D.num_pairs; } Dictionary::~Dictionary() { clear(); } // Helper functions -------------------------------------------------------- void Dictionary::inOrderString(std::string& s, Node* R) const { if (R == nullptr) { return; } std::string pair = R->key + " : " + std::to_string(R->val) + "\n"; inOrderString(s, R->left); s += pair; inOrderString(s, R->right); } void Dictionary::preOrderString(std::string& s, Node* R) const { if (R == nullptr) { return; } std::string pair = R->key + "\n"; s += pair; preOrderString(s, R->left); preOrderString(s, R->right); } void Dictionary::preOrderCopy(Node* R, Node* N) { Node* left = nullptr; Node* right = nullptr; if (R->left != nullptr) { left = new Node(R->left->key, R->left->val); left->parent = N; N->left = left; preOrderCopy(R->left, N->left); } if (R->right != nullptr) { right = new Node(R->right->key, R->right->val); right->parent = N; N->right = right; preOrderCopy(R->right, N->right); } } void Dictionary::postOrderDelete(Node* R) { if (R->left != nullptr) { postOrderDelete(R->left); } if (R->right != nullptr) { postOrderDelete(R->right); } delete R; } Dictionary::Node* Dictionary::search(Node* R, keyType k) const { if (R == nullptr) { return nullptr; } std::string key = R->key; if (key > k) { return search(R->left, k); } else if (key < k) { return search(R->right, k); } return R; } Dictionary::Node* Dictionary::findMin(Node* R) { Node* curr = R; while (curr->left != nullptr) { curr = curr->left; } return curr; } Dictionary::Node* Dictionary::findMax(Node* R) { Node* curr = R; while (curr->right != nullptr) { curr = curr->right; } return curr; } Dictionary::Node* Dictionary::findNext(Node* N) { if (N->right == nullptr) { Node* curr = N; while (curr != nullptr) { if (curr->parent != nullptr && curr->parent->left == curr) { curr = curr->parent; break; } curr = curr->parent; } return curr; } else { return findMin(N->right); } } Dictionary::Node* Dictionary::findPrev(Node* N) { if (N->left == nullptr) { Node* curr = N; while (curr != nullptr) { if (curr->parent != nullptr && curr->parent->right == curr) { curr = curr->parent; break; } curr = curr->parent; } return curr; } else { return findMax(N->left); } } // Access functions -------------------------------------------------------- // size() // Returns the size of this Dictionary. int Dictionary::size() const { return num_pairs; } // contains() // Returns true if there exists a pair such that key==k, and returns false // otherwise. bool Dictionary::contains(keyType k) const { return search(root, k) != nullptr; } // getValue() // Returns a reference to the value corresponding to key k. // Pre: contains(k) valType& Dictionary::getValue(keyType k) const { Node* node = search(root, k); if (node == nullptr) { throw std::logic_error("Dictionary: getValue(): key \"" + k + "\" does not exist"); } return node->val; } // hasCurrent() // Returns true if the current iterator is defined, and returns false // otherwise. bool Dictionary::hasCurrent() const { return current != nullptr; } // currentKey() // Returns the current key. // Pre: hasCurrent() keyType Dictionary::currentKey() const { if (current == nullptr) { throw std::logic_error("Dictionary: currentKey(): current undefined"); } return current->key; } // currentVal() // Returns a reference to the current value. // Pre: hasCurrent() valType& Dictionary::currentVal() const { if (current == nullptr) { throw std::logic_error("Dictionary: currentVal(): current undefined"); } return current->val; } // clear() // Resets this Dictionary to the empty state, containing no pairs. void Dictionary::clear() { if (root != nullptr) { postOrderDelete(root); } root = nullptr; current = nullptr; num_pairs = 0; } // setValue() // If a pair with key==k exists, overwrites the corresponding value with v, // otherwise inserts the new pair (k, v). void Dictionary::setValue(keyType k, valType v) { Node* node = search(root, k); if (node != nullptr) { node->val = v; } else { Node* newNode = new Node(k, v); if (root == nullptr) { root = newNode; num_pairs = 1; } else { Node* curr = root; while(true) { keyType key = curr->key; if (k < key) { if (curr->left == nullptr) { curr->left = newNode; newNode->parent = curr; num_pairs++; break; } curr = curr->left; } else if (k > key) { if (curr->right == nullptr) { curr->right = newNode; newNode->parent = curr; num_pairs++; break; } curr = curr->right; } } } } } // remove() // Deletes the pair for which key==k. If that pair is current, then current // becomes undefined. // Pre: contains(k). void Dictionary::remove(keyType k) { Node* node = search(root, k); if (node == nullptr) { throw std::logic_error("Dictionary: remove(): key \"" + k + "\" does not exist"); } if (current == node) {\ current = nullptr; return; } Node* parent = node->parent; if (node->left == nullptr) { Node* curr = node->right; if (parent == nullptr) { root = curr; } else if (parent->left == node) { parent->left = curr; } else { parent->right = curr; } if (curr != nullptr) { curr->parent = parent; } } else if (node->right == nullptr) { Node* curr = node->left; if (parent == nullptr) { root = curr; } else if (parent->left == node) { parent->left = curr; } else { parent->right = curr; } if (curr != nullptr) { curr->parent = parent; } } else { Node* leftMost; if (node->right->left == nullptr) { leftMost = node->right; } else { leftMost = findMin(node->right); Node* parent = leftMost->parent; parent->left = leftMost->right; if (leftMost->right != nullptr) { leftMost->right->parent = parent; } } leftMost->left = node->left; leftMost->right = node->right; node->right->parent = leftMost; node->left->parent = leftMost; leftMost->parent = node->parent; if (parent == nullptr) { root = leftMost; } else if (parent->left == node) { parent->left = leftMost; } else { parent->right = leftMost; } } num_pairs--; delete node; } // begin() // If non-empty, places current iterator at the first (key, value) pair // (as defined by the order operator < on keys), otherwise does nothing. void Dictionary::begin() { current = findMin(root); } // end() // If non-empty, places current iterator at the last (key, value) pair // (as defined by the order operator < on keys), otherwise does nothing. void Dictionary::end() { current = findMax(root); } // next() // If the current iterator is not at the last pair, advances current // to the next pair (as defined by the order operator < on keys). If // the current iterator is at the last pair, makes current undefined. // Pre: hasCurrent() void Dictionary::next() { if (current == nullptr) { throw std::logic_error("Dictionary: next(): current not defined"); } current = findNext(current); } // prev() // If the current iterator is not at the first pair, moves current to // the previous pair (as defined by the order operator < on keys). If // the current iterator is at the first pair, makes current undefined. // Pre: hasCurrent() void Dictionary::prev() { if (current == nullptr) { throw std::logic_error("Dictionary: prev(): current not defined"); } current = findPrev(current); } // Other Functions --------------------------------------------------------- // to_string() // Returns a string representation of this Dictionary. Consecutive (key, value) // pairs are separated by a newline "\n" character, and the items key and value // are separated by the sequence space-colon-space " : ". The pairs are arranged // in order, as defined by the order operator <. std::string Dictionary::to_string() const { std::string s = ""; inOrderString(s, root); return s; } // pre_string() // Returns a string consisting of all keys in this Dictionary. Consecutive // keys are separated by newline "\n" characters. The key order is given // by a pre-order tree walk. std::string Dictionary::pre_string() const { std::string s = ""; preOrderString(s, root); return s; } // equals() // Returns true if and only if this Dictionary contains the same (key, value) // pairs as Dictionary D. bool Dictionary::equals(const Dictionary& D) const { std::string s1 = to_string(); std::string s2 = D.to_string(); return s1 == s2; } // Overloaded Operators ---------------------------------------------------- // operator<<() // Inserts string representation of Dictionary D into stream, as defined by // member function to_string(). std::ostream& operator<<( std::ostream& stream, Dictionary& D ) { stream << D.to_string(); return stream; } // operator==() // Returns true if and only if Dictionary A equals Dictionary B, as defined // by member function equals(). bool operator==( const Dictionary& A, const Dictionary& B ) { return A.equals(B); } // operator=() // Overwrites the state of this Dictionary with state of D, and returns a // reference to this Dictionary. Dictionary& Dictionary::operator=( const Dictionary& D ) { clear(); if (D.root != nullptr) { root = new Node(D.root->key, D.root->val); preOrderCopy(D.root, root); } num_pairs = D.num_pairs; return *this; }