From fb80ac50825c7ca1fa063d3493175b7b27adbdb1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Tue, 17 Nov 2020 15:42:27 +0100 Subject: add given code --- labb5/lib/StanfordCPPLib/stack.h | 285 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 285 insertions(+) create mode 100755 labb5/lib/StanfordCPPLib/stack.h (limited to 'labb5/lib/StanfordCPPLib/stack.h') diff --git a/labb5/lib/StanfordCPPLib/stack.h b/labb5/lib/StanfordCPPLib/stack.h new file mode 100755 index 0000000..21d5058 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/stack.h @@ -0,0 +1,285 @@ +/* + * File: stack.h + * ------------- + * This file exports the Stack class, which implements + * a collection that processes values in a last-in/first-out (LIFO) order. + */ + +#ifndef _stack_h +#define _stack_h + +#include "vector.h" + +/* + * Class: Stack + * ----------------------- + * This class models a linear structure called a stack + * in which values are added and removed only from one end. + * This discipline gives rise to a last-in/first-out behavior (LIFO) + * that is the defining feature of stacks. The fundamental stack + * operations are push (add to top) and pop + * (remove from top). + */ + +template +class Stack { + +public: + +/* + * Constructor: Stack + * Usage: Stack stack; + * ------------------------------ + * Initializes a new empty stack. + */ + + Stack(); + +/* + * Destructor: ~Stack + * ------------------ + * Frees any heap storage associated with this stack. + */ + + virtual ~Stack(); + +/* + * Method: size + * Usage: int n = stack.size(); + * ---------------------------- + * Returns the number of values in this stack. + */ + + int size() const; + +/* + * Method: isEmpty + * Usage: if (stack.isEmpty()) ... + * ------------------------------- + * Returns true if this stack contains no elements. + */ + + bool isEmpty() const; + +/* + * Method: clear + * Usage: stack.clear(); + * --------------------- + * Removes all elements from this stack. + */ + + void clear(); + +/* + * Method: push + * Usage: stack.push(value); + * ------------------------- + * Pushes the specified value onto this stack. + */ + + void push(ValueType value); + +/* + * Method: pop + * Usage: ValueType top = stack.pop(); + * ----------------------------------- + * Removes the top element from this stack and returns it. This + * method signals an error if called on an empty stack. + */ + + ValueType pop(); + +/* + * Method: peek + * Usage: ValueType top = stack.peek(); + * ------------------------------------ + * Returns the value of top element from this stack, without removing + * it. This method signals an error if called on an empty stack. For + * compatibility with the STL classes, this method is also exported + * under the name top, in which case it returns the value + * by reference. + */ + + ValueType peek() const; + ValueType & top(); + +/* + * Method: toString + * Usage: string str = stack.toString(); + * ------------------------------------- + * Converts the stack to a printable string representation. + */ + + std::string toString(); + +/* + * Operator: == + * Usage: stack1 == stack2 + * ------------------- + * Returns true if stack1 and stack2 + * contain the same elements. + */ + + bool operator==(const Stack & stack2) const; + +/* + * Operator: != + * Usage: stack1 != stack2 + * ------------------- + * Returns true if stack1 and stack2 + * do not contain the same elements. + */ + + bool operator!=(const Stack & stack2) const; + +/* Private section */ + +/**********************************************************************/ +/* Note: Everything below this point in the file is logically part */ +/* of the implementation and should not be of interest to clients. */ +/**********************************************************************/ + +/* + * Implementation notes: Stack data structure + * ------------------------------------------ + * The easiest way to implement a stack is to store the elements in a + * Vector. Doing so means that the problems of dynamic memory allocation + * and copy assignment are already solved by the implementation of the + * underlying Vector class. + */ + +private: + Vector elements; + +}; + +extern void error(std::string msg); + +/* + * Stack class implementation + * -------------------------- + * The Stack is internally managed using a Vector. This layered design + * makes the implementation extremely simple, to the point that most + * methods can be implemented in as single line. + */ + +template +Stack::Stack() { + /* Empty */ +} + +template +Stack::~Stack() { + /* Empty */ +} + +template +int Stack::size() const { + return elements.size(); +} + +template +bool Stack::isEmpty() const { + return size() == 0; +} + +template +void Stack::push(ValueType value) { + elements.add(value); +} + +template +ValueType Stack::pop() { + if (isEmpty()) error("pop: Attempting to pop an empty stack"); + ValueType top = elements[elements.size() - 1]; + elements.remove(elements.size() - 1); + return top; +} + +template +ValueType Stack::peek() const { + if (isEmpty()) error("peek: Attempting to peek at an empty stack"); + return elements.get(elements.size() - 1); +} + +template +ValueType & Stack::top() { + if (isEmpty()) error("top: Attempting to read top of an empty stack"); + return elements[elements.size() - 1]; +} + +template +void Stack::clear() { + elements.clear(); +} + +template +std::string Stack::toString() { + ostringstream os; + os << *this; + return os.str(); +} + +template +bool Stack::operator==(const Stack & stack2) const { + if (size() != stack2.size()) return false; + for (int i = 0; i < size(); i++) { + if (this->elements[i] != stack2.elements[i]) { + return false; + } + } + return true; +} + +template +bool Stack::operator!=(const Stack & stack2) const { + return !(*this == stack2); +} + +template +std::ostream & operator<<(std::ostream & os, const Stack & stack) { + os << "{"; + Stack copy = stack; + Stack reversed; + while (!copy.isEmpty()) { + reversed.push(copy.pop()); + } + int len = stack.size(); + for (int i = 0; i < len; i++) { + if (i > 0) os << ", "; + writeGenericValue(os, reversed.pop(), true); + } + return os << "}"; +} + +template +std::istream & operator>>(std::istream & is, Stack & stack) { + char ch; + is >> ch; + if (ch != '{') error("operator >>: Missing {"); + stack.clear(); + is >> ch; + if (ch != '}') { + is.unget(); + while (true) { + ValueType value; + readGenericValue(is, value); + stack.push(value); + is >> ch; + if (ch == '}') break; + if (ch != ',') { + error(std::string("operator >>: Unexpected character ") + ch); + } + } + } + return is; +} + +// hashing functions for stacks; defined in hashmap.cpp +int hashCode(const Stack& s); +int hashCode(const Stack& s); +int hashCode(const Stack& s); +int hashCode(const Stack& s); +int hashCode(const Stack& s); + +#endif -- cgit v1.2.1