#include #include #include #include #include #include using namespace std; int main() { AbtTester tester = AbtTester(); tester.readInput(); } class AbtTester { public: AbtTester(); ~AbtTester(); void readInput(); private: stack forest; bool readNextLine(ifstream& fin, ofstream& fout); void addTree(int); void copyTree(); void removeTree(); void push(int); void push(int *, int); string pop(); int size(); int height(); void printBFS(ofstream& fout); void printDFS(ofstream& fout); bool isEmpty(); string find(int val); int count(int val); }; AbtTester::AbtTester() : forest() { } AbtTester::~AbtTester() { forest = stack(); } void AbtTester::readInput() { ifstream fin; fin.open("input.txt"); ofstream fout; fout.open("output.txt"); while (readNextLine(fin, fout)); fin.close(); fout.close(); } bool AbtTester::readNextLine(ifstream& fin, ofstream& fout) { string inputLine; if (getline(fin, inputLine)) { stringstream ss(inputLine); string command = ""; if (ss.good()) { ss >> command; if (command == "") return true; else if (command == "new") { int param = 0; if (ss.good()) ss >> param; addTree(param); } else if (command == "exit") return false; else if (command == "copy") copyTree(); else if (command == "end") { removeTree(); if (forest.empty()) return false; } else if (command == "size") fout << size() << endl; else if (command == "height") fout << height() << endl; else if (command == "printDFS") printDFS(fout); else if (command == "printBFS") printBFS(fout); else if (command == "empty") fout << std::boolalpha << isEmpty() << endl; else if (command == "pop") fout << pop() << endl; else { int param; if (ss.good()) ss >> param; else throw IllegalArgument(); if (command == "push") push(param); else if (command == "find") fout << find(param) << endl; else if (command == "count") fout << count(param) << endl; else if (command == "pushB") { if (param <= 0) throw IllegalArgument(); int* params = new int[param]; for (int i = 0; i < param; i++) ss >> params[i]; push(params, param); } } return true; } else { return true; } } else { return false; } } void AbtTester::addTree(int degree) { AbstractTree newTree = AbstractTree(degree); forest.push(newTree); } void AbtTester::copyTree() { AbstractTree newTree(forest.top()); forest.push(newTree); } void AbtTester::removeTree() { forest.pop(); } void AbtTester::push(int val) { forest.top().push(val); } void AbtTester::push(int * vals, int len) { forest.top().push(vals, len); } string AbtTester::pop() { try { int val = forest.top().pop(); return to_string(val); } catch (Underflow ex) { return "empty"; } catch (Exception ex) { return "error"; } return "none"; } int AbtTester::size() { return forest.top().size(); } int AbtTester::height() { return forest.top().height(); } void AbtTester::printBFS(ofstream& fout) { forest.top().printBFS(fout); } void AbtTester::printDFS(ofstream& fout) { forest.top().printDFS(fout); } bool AbtTester::isEmpty() { return forest.top().empty(); } string AbtTester::find(int val) { if (forest.top().find(val)) return "found"; return "not-found"; } int AbtTester::count(int val) { return forest.top().count(val); } class AbstractTree { public: class TreeNode { public: explicit TreeNode(int const &, TreeNode * = nullptr); int value() const; int degree() const; TreeNode *getParent() const; TreeNode *child(int const &) const; private: int nodeValue; TreeNode *parent; // Functions DoubleLinkedList children; int subtreeSize() const; int subtreeHeight() const; bool findInChildren(const int &) const; int count(const int &) const; void push(const int &, int); bool isFull(const int &) const; void clear(); void copy(const AbstractTree &, TreeNode *); friend AbstractTree; }; explicit AbstractTree(int const &); AbstractTree(AbstractTree const &); ~AbstractTree(); // Accessors int size() const; int height() const; bool empty() const; bool find(int const &); int count(int const &); // Mutators void push(int const &); void push(int *&, int const &); int pop(); // Printers void printBFS(std::ostream &); void printDFS(std::ostream &); private: TreeNode *root; int maxDegree; }; ///////////////////////////////////////////////////////////////////////// // Public member functions // ///////////////////////////////////////////////////////////////////////// AbstractTree::AbstractTree(int const &maxDegree) : maxDegree(maxDegree), root(nullptr) { } AbstractTree::AbstractTree(AbstractTree const &tree) : maxDegree(tree.maxDegree), root(nullptr){ if (!tree.empty()) { root = new TreeNode(tree.root->nodeValue); root->copy(tree, tree.root); } } AbstractTree::~AbstractTree() { if (!empty()) root->clear(); } int AbstractTree::size() const { if (empty()) { return 0; } return root->subtreeSize(); } int AbstractTree::height() const { if (empty()) return -1; return root->subtreeHeight(); } bool AbstractTree::empty() const { return root == nullptr; } bool AbstractTree::find(const int &val) { if (empty()) return false; if (val == root->nodeValue) { return true; } return root->findInChildren(val); } int AbstractTree::count(const int &val) { int number = 0; if (!empty()) { if (root->value() == val) { number++; } number += root->count(val); } return number; } void AbstractTree::push(const int &val) { if (empty()) { root = new TreeNode(val); } else { root->push(val, maxDegree); } } void AbstractTree::push(int *&ints, const int &number) { for (int i = 0; i < number; ++i) { push(ints[i]); } } int AbstractTree::pop() { Stack stack; TreeNode *lastNode = nullptr; if (!empty()) { stack.push(root); while (!stack.empty()) { TreeNode *node = stack.pop(); lastNode = node; for (int i = node->degree() - 1; i >= 0; --i) { stack.push(node->child(i)); } } } int lastNodeValue = lastNode->nodeValue; lastNode->getParent()->children.erase(lastNode); delete lastNode; return lastNodeValue; } void AbstractTree::printBFS(ostream &out) { out << "START->"; ResizableDeque queue; if (!empty()) { queue.pushBack(root); while (!queue.empty()) { TreeNode *currentNode = queue.front(); queue.popFront(); out << currentNode->nodeValue << "->"; for (int i = 0; i < currentNode->degree(); ++i) { queue.pushBack(currentNode->child(i)); } } } out << "END"; out << endl; } void AbstractTree::printDFS(ostream &out) { out << "START->"; Stack stack; if (!empty()) { stack.push(root); while (!stack.empty()) { TreeNode *node = stack.pop(); out << node->nodeValue << "->"; for (int i = node->degree() - 1; i >= 0; --i) { stack.push(node->child(i)); } } } out << "END"; out << endl; } // Enter your implementation here ////////////////////////////////////////////////////////////////////// // treeNode Functions // ////////////////////////////////////////////////////////////////////// AbstractTree::TreeNode::TreeNode( int const &nv, TreeNode *parent) : nodeValue(nv), parent(parent) { // Updated the initialization list here // Enter your implementation here } int AbstractTree::TreeNode::value() const { return nodeValue; } int AbstractTree::TreeNode::degree() const { return children.size(); } AbstractTree::TreeNode *AbstractTree::TreeNode::child(const int &n) const { if (n < 0 || n >= degree()) { return nullptr; } auto child = children.begin(); for (int i = 0; i < n; ++i) { child = child->next(); } return child->value(); } int AbstractTree::TreeNode::subtreeSize() const { int subtreeSize = 1; for (int i = 0; i < degree(); ++i) { subtreeSize += child(i)->subtreeSize(); } return subtreeSize; } int AbstractTree::TreeNode::subtreeHeight() const { int subtreeHeight = 0; for (int i = 0; i < degree(); ++i) { subtreeHeight = max(subtreeHeight, child(i)->subtreeHeight() + 1); } return subtreeHeight; } bool AbstractTree::TreeNode::findInChildren(const int &val) const { for (int i = 0; i < degree(); ++i) { if (val == child(i)->nodeValue) { return true; } if (child(i)->findInChildren(val)) { return true; } } return false; } int AbstractTree::TreeNode::count(const int &val) const { int n = 0; for (int i = 0; i < degree(); ++i) { if (val == child(i)->nodeValue) { n++; } n += child(i)->count(val); } return n; } AbstractTree::TreeNode *AbstractTree::TreeNode::getParent() const { return parent; } void AbstractTree::TreeNode::push(const int &val, int max) { if (isFull(max)) { for (int i = 0; i < degree(); ++i) { if (!child(i)->isFull(max)) { child(i)->push(val, max); return; } } } else { children.pushBack(new AbstractTree::TreeNode(val, this)); return; } } bool AbstractTree::TreeNode::isFull(const int &max) const { return max == degree(); } void AbstractTree::TreeNode::clear() { for (int i = 0; i < degree(); ++i) { child(i)->clear(); } delete this; } void AbstractTree::TreeNode::copy(const AbstractTree &tree, TreeNode *treeParent) { for (int i = 0; i < treeParent->degree(); ++i) { children.pushBack(new TreeNode(treeParent->child(i)->nodeValue, this)); child(i)->copy(tree, treeParent->child(i)); } } template < typename Type> class Stack { private: // List as linked list DoubleLinkedList linkedList; public: // Check if list is empty or not bool empty() const; // Push in back of list void push(Type const &); // Pop of back of list Type pop(); }; template < typename Type> bool Stack::empty() const { return linkedList.empty(); }; template < typename Type> void Stack::push(Type const &value) { linkedList.pushBack(value); }; template < typename Type> Type Stack::pop() { Type back = linkedList.back(); linkedList.popBack(); return back; }; template class ResizableDeque { public: /* * Constructor, receives list capacity as optional input parameter, * If a value is not set in the parameter, the value 16 is considered. * If it is less than 16, capacity 16 is considered. */ ResizableDeque(int = 16); /* * Copier Constructor, receives a list as input parameter, * Copies all it's elements in itself. */ ResizableDeque(ResizableDeque const &); /* * Destructor, deletes the array. */ ~ResizableDeque(); /* * Returns the value in the front of the list. * If the list is empty, throws an underFlow error. */ Type front() const; /* * returns the value in the back of the list. * If the list is empty, throws an underFlow error. */ Type back() const; /* * Returns the number of elements in the list. */ int size() const; /* * Returns True if the list is empty. */ bool empty() const; /* * Returns the capacity of the list. */ int capacity() const; /* * Moves the input ResizableDeque to itself. */ void swap(ResizableDeque &); /* * Adds the input into the array in the front. * If the array is full, creates a new array with double size. */ void pushFront(Type const &); /* * Adds the input into the array in the back. * If the array is full, creates a new array with double size. */ void pushBack(Type const &); /* * Removes the initial value. * If the list is empty, throws an underFlow error. * If, after removing the value, only a quarter of the array capacity * is full (or less than a quarter) and the current array capacity is * greater than the initial capacity, creates a new array with half size. */ void popFront(); /* * Removes the final value * If the list is empty, throws an underFlow error. * If, after removing the value, only a quarter of the array capacity * is full (or less than a quarter) and the current array capacity is * greater than the initial capacity, creates a new array with half size. */ void popBack(); /* * Removes all element in array and returns capacity to the initial value. */ void clear(); private: // Holds list elements. Type *array; // Index of the front entry int iFront; // Index of the back entry int iBack; // The number of elements in the list int dequeSize; // Initial list capacity int initialCapacity; // Current list capacity int currCapacity; /* * Creates a new array with size of input * Moves all elements in old array to new array. */ void resize(int); }; ///////////////////////////////////////////////////////////////////////// // Constructors and Destructors // ///////////////////////////////////////////////////////////////////////// // Constructor template ResizableDeque::ResizableDeque(int n) : iBack(-1), iFront(-1), dequeSize(0), initialCapacity(std::max(n, 16)) { currCapacity = initialCapacity; array = new Type[currCapacity]; } // Copy Constructor template ResizableDeque::ResizableDeque(ResizableDeque const &deque) : iBack(deque.iBack), iFront(deque.iFront), dequeSize(deque.dequeSize), currCapacity(deque.currCapacity), initialCapacity(deque.initialCapacity) { array = new Type[currCapacity]; for (int i = 0; i < capacity(); ++i) { array[i] = deque.array[i]; } } // Destructor template ResizableDeque::~ResizableDeque() { delete[] array; } ///////////////////////////////////////////////////////////////////////// // Public Member Functions // ///////////////////////////////////////////////////////////////////////// template int ResizableDeque::size() const { return dequeSize; } template int ResizableDeque::capacity() const { return currCapacity; } template bool ResizableDeque::empty() const { return dequeSize == 0; } template Type ResizableDeque::front() const { return array[iFront]; } template Type ResizableDeque::back() const { return array[iBack]; } template void ResizableDeque::swap(ResizableDeque &deque) { std::swap(iBack, deque.iBack); std::swap(iFront, deque.iFront); std::swap(dequeSize, deque.dequeSize); std::swap(currCapacity, deque.currCapacity); std::swap(initialCapacity, deque.initialCapacity); std::swap(array, deque.array); } template void ResizableDeque::pushFront(Type const &val) { if (size() == capacity()) { resize(2 * capacity()); } if (empty()) { iBack = capacity() - 1; iFront++; } if (iFront == 0) { iFront = capacity() - 1; } else iFront--; array[iFront] = val; dequeSize++; } template void ResizableDeque::pushBack(Type const &val) { if (size() == capacity()) { resize(2 * capacity()); } if (empty()) { iFront++; } if (iBack != capacity() - 1) { iBack++; } else { iBack = 0; } array[iBack] = val; dequeSize++; } template void ResizableDeque::popFront() { if (empty()) { throw Underflow(); } if (size() == 1) { iFront = -1; iBack = -1; } else if (iFront == capacity() - 1) iFront = 0; else iFront++; dequeSize--; if (size() <= (capacity() / 4) && currCapacity > initialCapacity) { resize(capacity() / 2); } } template void ResizableDeque::popBack() { if (empty()) { throw Underflow(); } if (size() == 1) { iFront = -1; iBack = -1; } else if (iBack == 0) iBack = capacity() - 1; else iBack--; dequeSize--; if (size() <= (capacity() / 4) && currCapacity > initialCapacity) { resize(capacity() / 2); } } template void ResizableDeque::clear() { iFront = -1; iBack = -1; dequeSize = 0; currCapacity = initialCapacity; } ///////////////////////////////////////////////////////////////////////// // Private member functions // ///////////////////////////////////////////////////////////////////////// template void ResizableDeque::resize(int newSize) { int oldCapacity = currCapacity; currCapacity = newSize; Type *oldArr = array; array = new Type[currCapacity]; if (iFront > iBack) { int j = 0; for (int i = iFront; i < oldCapacity; ++i, ++j) { array[j] = oldArr[i]; } for (int i = 0; i <= iBack; ++i, ++j) { array[j] = oldArr[i]; } } else { for (int i = iFront, j = 0; i <= iBack; ++i, ++j) { array[j] = oldArr[i]; } } delete[] oldArr; iFront = 0; iBack = size() - 1; } template class DoubleLinkedList { public: class DoubleNode { public: /* * Constructor * Set volume of the node, the previous node & the next node pointer */ DoubleNode(Type const & = Type(), DoubleNode * = nullptr, DoubleNode * = nullptr); /* * Return volume of the node */ Type value() const; /* * Return the pointer of the previous node */ DoubleNode *previous() const; /* * Return the pointer of the next node */ DoubleNode *next() const; /* * Store volume of the node */ Type nodeValue; /* * Store the pointer of the previous node */ DoubleNode *previousNode; /* * Store the pointer of the next node */ DoubleNode *nextNode; }; /* * Constructor without input parameter * Set the list head & the list tail & the list size to the default volume */ DoubleLinkedList(); /* * Constructor with input parameter: Double linked list * Set the list head & the list tail & the list size to the default volume * Copy elements of the list to this list */ DoubleLinkedList(DoubleLinkedList const &); /* * Destructor * While the list is not empty destroys any element. */ ~DoubleLinkedList(); // Accessors /* * Return size of the list */ int size() const; // Check if the list size is zero or not bool empty() const; /* * Return the volume at the top of the list. If the list is empty * throws an Underflow error. */ Type front() const; /* * Return the volume at the end of the list. If the list is empty * throws an Underflow error. */ Type back() const; /* * Return the reference of the head of the list */ DoubleNode *begin() const; /* * Return the reference of the tail of the list */ DoubleNode *end() const; /* * Return the address of the first node whose value is equal to the value of the input parameter. * If the corresponding volume is not found, nullptr is returned. */ DoubleNode *find(Type const &) const; /* * Return the number of elements whose volume is equal to the value of the input parameter. */ int count(Type const &) const; // Mutators /* * Move the input link list to this linked list. * Swap the head, tail & size of the lists */ void swap(DoubleLinkedList &); /* * Create a new node with the volume given in the input, * Insert it at the beginning of the list. * Move the list head to new node */ void pushFront(Type const &); /* * Create a new node with the volume given in the input, * Insert it at the end of the list. * Move the list tail to new node. * Increase the list size. */ void pushBack(Type const &); /* * Delete the starting node of the list. If the list is empty * throw an Underflow error. * Move the list head to next node. * Reduce the list size. */ void popFront(); /* * Delete the last node of the list. If the list is empty * throw an Underflow error. * Move the list tail to previous node. * Reduce the list size */ void popBack(); /* * Delete all nodes whose value is equal to the volume of the input parameter, * Return the number of deleted nodes. * Navigate the list, delete corresponding node * Link the previous & the next node */ int erase(Type const &); private: /* *Pointer to the beginning of the list */ DoubleNode *listHead; /* * Pointer to the end of the list */ DoubleNode *listTail; /* * Store the size of the list */ int listSize; // Friends // friend std::ostream &operator<<(std::ostream &, DoubleLinkedList const &); }; ///////////////////////////////////////////////////////////////////////// // Public member functions // ///////////////////////////////////////////////////////////////////////// template DoubleLinkedList::DoubleLinkedList() : listHead(nullptr), listTail(nullptr), listSize(0) { } template DoubleLinkedList::DoubleLinkedList(DoubleLinkedList const &list) : listHead(nullptr), listTail(nullptr), listSize(0) { DoubleNode *ptr = list.begin(); while (ptr != nullptr) { pushBack(ptr->value()); ptr = ptr->next(); } } template DoubleLinkedList::~DoubleLinkedList() { while (!empty()) { popFront(); } } template int DoubleLinkedList::size() const { return listSize; } template bool DoubleLinkedList::empty() const { return listSize == 0; } template Type DoubleLinkedList::front() const { if (empty()) { throw Underflow(); } return begin()->value(); } template Type DoubleLinkedList::back() const { if (empty()) { throw Underflow(); } return end()->value(); } template typename DoubleLinkedList::DoubleNode *DoubleLinkedList::begin() const { return listHead; } template typename DoubleLinkedList::DoubleNode *DoubleLinkedList::end() const { return listTail; } template typename DoubleLinkedList::DoubleNode *DoubleLinkedList::find(Type const &value) const { DoubleNode *node = listHead; while (node != nullptr) { if (node->value() == value) return node; node = node->next(); } return nullptr; } template int DoubleLinkedList::count(Type const &value) const { int listCount = 0; DoubleNode *node = listHead; while (node != nullptr) { if (node->value() == value) listCount++; node = node->next(); } return listCount; } template void DoubleLinkedList::swap(DoubleLinkedList &list) { std::swap(this->listHead, list.listHead); std::swap(this->listTail, list.listTail); std::swap(this->listSize, list.listSize); } template void DoubleLinkedList::pushFront(Type const &value) { // Next node is old head auto *newNode = new DoubleNode(value, nullptr, begin()); if (empty()) { // If list is empty the tail & the head are equal listTail = newNode; } else { listHead->previousNode = newNode; } listHead = newNode; listSize++; } template void DoubleLinkedList::pushBack(Type const &value) { // Previous node is old tail auto *newNode = new DoubleNode(value, end(), nullptr); if (empty()) { // If list is empty the tail & the head are equal listHead = newNode; } else { listTail->nextNode = newNode; } listTail = newNode; listSize++; } template void DoubleLinkedList::popFront() { if (!empty()) { listSize--; DoubleNode *temp = begin(); listHead = begin()->next(); // If the list is empty the listHead will be NULL so it has not previous node then the listTail is NULL too if (!empty()) { listHead->previousNode = nullptr; } else listTail = nullptr; delete temp; } else throw Underflow(); } template void DoubleLinkedList::popBack() { if (!empty()) { listSize--; DoubleNode *temp = end(); listTail = end()->previous(); // If the list is empty the listTail will be NULL so it has not next node then the listHead is NULL too if (!empty()) listTail->nextNode = nullptr; else listHead = nullptr; delete temp; } else throw Underflow(); } template int DoubleLinkedList::erase(Type const &value) { int number = 0; DoubleNode *node = listHead; while (node != nullptr) { if (node->value() == value) { DoubleNode *temp = node; // If node is the head, It must move to next node if (node != begin()) node->previous()->nextNode = node->next(); else listHead = node->next(); // If node is the tail, It must move to previous node if (node != end()) node->next()->previousNode = node->previous(); else listTail = node->previous(); delete temp; listSize--; number++; } node = node->next(); } return number; } template DoubleLinkedList::DoubleNode::DoubleNode( Type const &nv, DoubleLinkedList::DoubleNode *pn, DoubleLinkedList::DoubleNode *nn) : nodeValue(nv), previousNode(pn), nextNode(nn) { } template Type DoubleLinkedList::DoubleNode::value() const { return nodeValue; } template typename DoubleLinkedList::DoubleNode *DoubleLinkedList::DoubleNode::previous() const { return previousNode; } template typename DoubleLinkedList::DoubleNode *DoubleLinkedList::DoubleNode::next() const { return nextNode; } /* * All exceptions are derived from the 'exception' class * - consequently, catch( excpetion ) { ... } will catch only these exceptions * * exception <----- Underflow * |-- Underflow * |-- Overflow * |-- DivisionByZero * |-- IllegalArgument * -- OutOfRange */ class Exception { // empty class }; class Underflow : public Exception { // empty class }; class Overflow : public Exception { // empty class }; class DivisionByZero : public Exception { // emtpy class }; class IllegalArgument : public Exception { // emtpy class }; class OutOfRange : public Exception { // emtpy class };

abstract tree