Instructions
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;
}