diff options
Diffstat (limited to 'labb5/lib')
21 files changed, 5199 insertions, 0 deletions
diff --git a/labb5/lib/StanfordCPPLib/error.cpp b/labb5/lib/StanfordCPPLib/error.cpp new file mode 100755 index 0000000..c0e0a36 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/error.cpp @@ -0,0 +1,42 @@ +/* + * File: error.cpp + * --------------- + * Implementation of the error function. + */ + +#include <exception> +#include <string> +#include <iostream> +#include "error.h" +using namespace std; + +/* Definitions for the ErrorException class */ + +ErrorException::ErrorException(string msg) { + this->msg = msg; +} + +ErrorException::~ErrorException() throw () { + /* Empty */ +} + +string ErrorException::getMessage() const { + return msg; +} + +const char *ErrorException::what() const throw () { + return ("Error: " + msg).c_str(); +} + +/* + * Implementation notes: error + * --------------------------- + * Earlier implementations of error made it possible, at least on the + * Macintosh, to help the debugger generate a backtrace at the point + * of the error. Unfortunately, doing so is no longer possible if + * the errors are catchable. + */ + +void error(string msg) { + throw ErrorException(msg); +} diff --git a/labb5/lib/StanfordCPPLib/error.h b/labb5/lib/StanfordCPPLib/error.h new file mode 100755 index 0000000..359ea99 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/error.h @@ -0,0 +1,56 @@ +/* + * File: error.h + * ------------- + * This file defines the <code>ErrorException</code> class and the + * <code>error</code> function. + */ + +#ifndef _error_h +#define _error_h + +#include <string> +#include <exception> + +/* + * Class: ErrorException + * --------------------- + * This exception is thrown by calls to the <code>error</code> + * function. Typical code for catching errors looks like this: + * + *<pre> + * try { + * ... code in which an error might occur ... + * } catch (ErrorException & ex) { + * ... code to handle the error condition ... + * } + *</pre> + * + * If an <code>ErrorException</code> is thrown at any point in the + * range of the <code>try</code> (including in functions called from + * that code), control will jump immediately to the error handler. + */ + +class ErrorException : public std::exception { +public: + ErrorException(std::string msg); + virtual ~ErrorException() throw (); + virtual std::string getMessage() const; + virtual const char *what() const throw (); + +private: + std::string msg; +}; + +/* + * Function: error + * Usage: error(msg); + * ------------------ + * Signals an error condition in a program by throwing an + * <code>ErrorException</code> with the specified message. + */ + +void error(std::string msg); + +#include "private/main.h" + +#endif diff --git a/labb5/lib/StanfordCPPLib/foreach.h b/labb5/lib/StanfordCPPLib/foreach.h new file mode 100755 index 0000000..15a758b --- /dev/null +++ b/labb5/lib/StanfordCPPLib/foreach.h @@ -0,0 +1,217 @@ +/* + * File: foreach.h + * --------------- + * This file defines the <code>foreach</code> keyword, which implements + * a substitute for the range-based <code>for</code> loop from C++11. + * All iterable classes in the Stanford libraries import this file, so + * clients don't ordinarily need to do so explicitly. This version of + * <code>foreach</code> also supports C++ strings and arrays. + */ + +#ifndef _foreach_h +#define _foreach_h + +/* + * Statement: foreach + * Usage: foreach (type var in collection) { ... } + * ----------------------------------------------- + * The <code>foreach</code> statement steps through the elements in + * a collection. It works correctly with the collection classes in + * both the Standard Template Library and the Stanford C++ libraries, + * but can also be used with C++ strings and statically initialized + * arrays. + * + * <p>The following code, for example, prints every element in the + * string vector <code>lines</code>: + * + *<pre> + * foreach (string str in lines) { + * cout << str << endl; + * } + *</pre> + * + * Similarly, the following function calculates the sum of the character + * codes in a string: + * + *<pre> + * int sumCharacterCodes(string str) { + * int sum = 0; + * foreach (char ch in str) sum += ch; + * return sum; + * } + *</pre> + * + * As a simplification when iterating over maps, the <code>foreach</code> + * macro iterates through the keys rather than the key/value pairs. + */ + +/* Private section */ + +/**********************************************************************/ +/* Note: Everything below this point in the file is logically part */ +/* of the implementation and should not be of interest to clients. */ +/**********************************************************************/ + +#include <iterator> +#include <map> +#include <cstddef> +#include <cstring> + +/* These #includes are for files that contain "in" as a token */ + +#include <ios> +#include <fstream> +#include <sstream> +using namespace std; + +/* Redefine the ios constants (one of which is "in") */ + +static const ios::openmode IOS_APP = ios::app; +static const ios::openmode IOS_ATE = ios::ate; +static const ios::openmode IOS_BINARY = ios::binary; +static const ios::openmode IOS_IN = ios::in; +static const ios::openmode IOS_OUT = ios::out; +static const ios::openmode IOS_TRUNC = ios::trunc; + +/* Private implementation namespace */ + +namespace _fe { + struct Range { + virtual ~Range() { }; + }; + + template <typename T> + struct ArrayRange : Range { + ArrayRange(const T *begin, const T *end) : iter(begin), end(end) { } + const T *iter; + const T *end; + }; + + template <typename CType> + struct CRange : Range { + CRange(const CType& c) : + cont(c), iter(cont.begin()), end(cont.end()) { } + CType cont; + typename CType::iterator iter, end; + }; + + template <typename KT, typename VT, typename CT, typename AT> + struct MapRange : Range { + MapRange(const map<KT,VT,CT,AT> & c) : + cont(c), iter(cont.begin()), end(cont.end()) { } + map<KT,VT,CT,AT> cont; + typename map<KT,VT,CT,AT>::iterator iter, end; + }; + +/* + * The State struct glues together all of these pieces and + * stores all of the information throughout the loops. + */ + + struct State { + State() : state(0), itr(NULL) { } + ~State() { delete itr; } + int state; + Range *itr; + }; + +/* General hook function */ + + template <typename DowncastType, typename ValueType> + ValueType HookImpl(State& fe) { + DowncastType *ip = (DowncastType *) fe.itr; + if (ip->iter == ip->end) { + fe.state = 2; + return ValueType(); + } + fe.state = 1; + ValueType vp = *ip->iter; /* Subtle implementation note: */ + ++ip->iter; /* Using *ip->iter++ here would */ + return vp; /* require copying the iterator. */ + } + +/* Foreach implementation for containers */ + + template <typename CType> + CRange<CType> *Init(State & fe, const CType & collection) { + fe.itr = new CRange<CType>(collection); + return (CRange<CType>*) fe.itr; + } + + template <typename CType> + typename iterator_traits<typename CType::iterator>::value_type + Hook(State & fe, CRange<CType> *) { + return HookImpl<CRange<CType>, + typename iterator_traits<typename CType::iterator>::value_type>(fe); + } + +/* For maps */ + + template <typename K, typename V, typename C, typename A> + MapRange<K,V,C,A> *Init(State & fe, const map<K,V,C,A> & collection) { + fe.itr = new MapRange<K,V,C,A>(collection); + return (MapRange<K,V,C,A>*) fe.itr; + } + + template <typename DowncastType, typename ValueType> + ValueType MapHookImpl(State & fe) { + DowncastType *ip = (DowncastType *) fe.itr; + if (ip->iter == ip->end) { + fe.state = 2; + return ValueType(); + } + fe.state = 1; + ValueType key = ip->iter->first; + ++ip->iter; + return key; + } + + template <typename K, typename V, typename C, typename A> + K Hook(State & fe, MapRange<K,V,C,A> *) { + return MapHookImpl<MapRange<K,V,C,A>,K>(fe); + } + +/* For C strings */ + + template <size_t n> + ArrayRange<char> *Init(State & fe, char (&str)[n]) { + fe.itr = new ArrayRange<char>(str, str + strlen(str)); + return (ArrayRange<char>*) fe.itr; + } + + template <size_t n> + ArrayRange<char> *Init(State & fe, const char (&str)[n]) { + fe.itr = new ArrayRange<char>(str, str + strlen(str)); + return (ArrayRange<char>*) fe.itr; + } + +/* For arrays */ + + template <typename T, size_t n> + ArrayRange<T> *Init(State & fe, T (&arr)[n]) { + fe.itr = new ArrayRange<T>(arr, arr + n); + return (ArrayRange<T>*) fe.itr; + } + + template <typename T, size_t n> + ArrayRange<T> *Init(State & fe, const T (&arr)[n]) { + fe.itr = new ArrayRange<T>(arr, arr + n); + return (ArrayRange<T>*) fe.itr; + } + + template <typename T> + T Hook(State& fe, ArrayRange<T>*) { + return HookImpl<ArrayRange<T>, T>(fe); + } + +} + +/* The actual foreach and in macros */ + +#define foreach(arg) \ + for (_fe::State _fe; _fe.state < 2; ) \ + for (arg)); _fe.state++ == 1; _fe.state = 0) + +#define in = _fe::Hook(_fe, _fe.state != 0 ? NULL : _fe::Init(_fe, + +#endif diff --git a/labb5/lib/StanfordCPPLib/grid.h b/labb5/lib/StanfordCPPLib/grid.h new file mode 100755 index 0000000..7f4c71f --- /dev/null +++ b/labb5/lib/StanfordCPPLib/grid.h @@ -0,0 +1,548 @@ +/* + * File: grid.h + * ------------ + * This file exports the <code>Grid</code> class, which offers a + * convenient abstraction for representing a two-dimensional array. + */ + +#ifndef _grid_h +#define _grid_h + +#include <string> +#include <sstream> +#include <vector> +#include <stdexcept> +#include "strlib.h" + +/* + * Class: Grid<ValueType> + * ---------------------- + * This class stores an indexed, two-dimensional array. The following code, + * for example, creates an identity matrix of size <code>n</code>, in which + * the elements are 1.0 along the main diagonal and 0.0 everywhere else: + * + *<pre> + * Grid<double> createIdentityMatrix(int n) { + * Grid<double> matrix(n, n); + * for (int i = 0; i < n; i++) { + * matrix[i][i] = 1.0; + * } + * return matrix; + * } + *</pre> + */ + +template <typename ValueType> +class Grid { + +public: + + /* Forward reference */ + class GridRow; + class ConstGridRow; + + /* + * Constructor: Grid + * Usage: Grid<ValueType> grid; + * Grid<ValueType> grid(nRows, nCols); + * ------------------------------------------ + * Initializes a new grid. The second form of the constructor is + * more common and creates a grid with the specified number of rows + * and columns. Each element of the grid is initialized to the + * default value for the type. The default constructor creates an + * empty grid for which the client must call <code>resize</code> to + * set the dimensions. + */ + + Grid(); + Grid(int nRows, int nCols); + + /* + * Destructor: ~Grid + * ----------------- + * Frees any heap storage associated with this grid. + */ + + virtual ~Grid(); + + /* + * Method: numRows + * Usage: int nRows = grid.numRows(); + * ---------------------------------- + * Returns the number of rows in the grid. + */ + + int numRows() const; + + /* + * Method: numCols + * Usage: int nCols = grid.numCols(); + * ---------------------------------- + * Returns the number of columns in the grid. + */ + + int numCols() const; + + /* + * Method: resize + * Usage: grid.resize(nRows, nCols); + * --------------------------------- + * Reinitializes the grid to have the specified number of rows + * and columns. Any previous grid contents are discarded. + */ + + void resize(int nRows, int nCols); + + /* + * Method: inBounds + * Usage: if (grid.inBounds(row, col)) ... + * --------------------------------------- + * Returns <code>true</code> if the specified row and column position + * is inside the bounds of the grid. + */ + + bool inBounds(int row, int col) const; + + /* + * Method: get + * Usage: ValueType value = grid.get(row, col); + * -------------------------------------------- + * Returns the element at the specified <code>row</code>/<code>col</code> + * position in this grid. This method signals an error if the + * <code>row</code> and <code>col</code> arguments are outside + * the grid boundaries. + */ + + ValueType get(int row, int col); + const ValueType & get(int row, int col) const; + + /* + * Method: set + * Usage: grid.set(row, col, value); + * --------------------------------- + * Replaces the element at the specified <code>row</code>/<code>col</code> + * location in this grid with a new value. This method signals an error + * if the <code>row</code> and <code>col</code> arguments are outside + * the grid boundaries. + */ + + void set(int row, int col, ValueType value); + + /* + * Operator: [] + * Usage: grid[row][col] + * ---------------------- + * Overloads <code>[]</code> to select elements from this grid. + * This extension enables the use of traditional array notation to + * get or set individual elements. This method signals an error if + * the <code>row</code> and <code>col</code> arguments are outside + * the grid boundaries. + */ + + GridRow operator[](int row); + const ConstGridRow operator[](int row) const; + + /* + * Method: toString + * Usage: string str = grid.toString(); + * ------------------------------------ + * Converts the grid to a printable string representation. + */ + + std::string toString(); + + /* + * Method: mapAll + * Usage: grid.mapAll(fn); + * ----------------------- + * Calls the specified function on each element of the grid. The + * elements are processed in <b><i>row-major order,</i></b> in which + * all the elements of row 0 are processed, followed by the elements + * in row 1, and so on. + */ + + void mapAll(void (*fn)(ValueType value)) const; + void mapAll(void (*fn)(const ValueType & value)) const; + + template <typename FunctorType> + void mapAll(FunctorType fn) const; + +/* + * Additional Grid operations + * -------------------------- + * In addition to the methods listed in this interface, the Grid + * class supports the following operations: + * + * - Stream I/O using the << and >> operators + * - Deep copying for the copy constructor and assignment operator + * - Iteration using the range-based for statement and STL iterators + * + * The iteration forms process the grid in row-major order. + */ + + /* 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: Grid data structure + * ----------------------------------------- + * The Grid is internally managed as a dynamic array of elements. + * The array itself is one-dimensional, the logical separation into + * rows and columns is done by arithmetic computation. The layout + * is in row-major order, which is to say that the entire first row + * is laid out contiguously, followed by the entire second row, + * and so on. + */ + + /* Instance variables */ + + ValueType *elements; /* A dynamic array of the elements */ + int nRows; /* The number of rows in the grid */ + int nCols; /* The number of columns in the grid */ + + /* Private method prototypes */ + + void checkRange(int row, int col); + +/* + * Hidden features + * --------------- + * The remainder of this file consists of the code required to + * support deep copying and iteration. Including these methods + * in the public interface would make that interface more + * difficult to understand for the average client. + */ + +/* + * Deep copying support + * -------------------- + * This copy constructor and operator= are defined to make a + * deep copy, making it possible to pass/return grids by value + * and assign from one grid to another. The entire contents of + * the grid, including all elements, are copied. Each grid + * element is copied from the original grid to the copy using + * assignment (operator=). Making copies is generally avoided + * because of the expense and thus, grids are typically passed + * by reference, however, when a copy is needed, these operations + * are supported. + */ + + void deepCopy(const Grid & grid) { + int n = grid.nRows * grid.nCols; + elements = new ValueType[n]; + for (int i = 0; i < n; i++) { + elements[i] = grid.elements[i]; + } + nRows = grid.nRows; + nCols = grid.nCols; + } + +public: + + Grid & operator=(const Grid & src) { + if (this != &src) { + delete[] elements; + deepCopy(src); + } + return *this; + } + + Grid(const Grid & src) { + deepCopy(src); + } + +/* + * Iterator support + * ---------------- + * The classes in the StanfordCPPLib collection implement input + * iterators so that they work symmetrically with respect to the + * corresponding STL classes. + */ + + class iterator : public std::iterator<std::input_iterator_tag, ValueType> { + + public: + + iterator(const Grid *gp, int index) { + this->gp = gp; + this->index = index; + } + + iterator(const iterator & it) { + this->gp = it.gp; + this->index = it.index; + } + + iterator & operator++() { + index++; + return *this; + } + + iterator operator++(int) { + iterator copy(*this); + operator++(); + return copy; + } + + bool operator==(const iterator & rhs) { + return gp == rhs.gp && index == rhs.index; + } + + bool operator!=(const iterator & rhs) { + return !(*this == rhs); + } + + ValueType & operator*() { + return gp->elements[index]; + } + + ValueType *operator->() { + return &gp->elements[index]; + } + + private: + const Grid *gp; + int index; + }; + + iterator begin() const { + return iterator(this, 0); + } + + iterator end() const { + return iterator(this, nRows * nCols); + } + +/* + * Private class: Grid<ValType>::GridRow + * ------------------------------------- + * This section of the code defines a nested class within the Grid template + * that makes it possible to use traditional subscripting on Grid values. + */ + + class GridRow { + public: + GridRow() { + /* Empty */ + } + + ValueType & operator[](int col) { + if (!gp->inBounds(row, col)) { + throw std::out_of_range("Grid index values out of range"); + } + return gp->elements[(row * gp->nCols) + col]; + } + + ValueType operator[](int col) const { + if (!gp->inBounds(row, col)) { + throw std::out_of_range("Grid index values out of range"); + } + return gp->elements[(row * gp->nCols) + col]; + } + + private: + GridRow(Grid *gridRef, int index) { + gp = gridRef; + row = index; + } + + Grid *gp; + int row; + friend class Grid; + }; + friend class ConstGridRow; + +/* + * Private class: Grid<ValType>::ConstGridRow + * ------------------------------------- + * This section of the code defines a nested class within the Grid template + * that makes it possible to use traditional subscripting on Grid values for + * const versions of the Grid. + */ + + class ConstGridRow { + public: + ConstGridRow() { + /* Empty */ + } + + ValueType operator[](int col) const { + if (!gp->inBounds(row, col)) { + throw std::out_of_range("Grid index values out of range"); + } + return gp->elements[(row * gp->nCols) + col]; + } + + private: + ConstGridRow(const Grid *gridRef, int index) { + gp = gridRef; + row = index; + } + + const Grid *gp; + int row; + friend class Grid; + }; + friend class GridRow; + +}; + +template <typename ValueType> +Grid<ValueType>::Grid() { + elements = NULL; + nRows = 0; + nCols = 0; +} + +template <typename ValueType> +Grid<ValueType>::Grid(int nRows, int nCols) { + elements = NULL; + resize(nRows, nCols); +} + +template <typename ValueType> +Grid<ValueType>::~Grid() { + if (elements != NULL) delete[] elements; +} + +template <typename ValueType> +int Grid<ValueType>::numRows() const { + return nRows; +} + +template <typename ValueType> +int Grid<ValueType>::numCols() const { + return nCols; +} + +template <typename ValueType> +void Grid<ValueType>::resize(int nRows, int nCols) { + if (nRows < 0 || nCols < 0) { + throw std::invalid_argument("Attempt to resize grid to invalid size (" + + std::to_string(nRows) + ", " + + std::to_string(nCols) + ")"); + } + if (elements != NULL) delete[] elements; + this->nRows = nRows; + this->nCols = nCols; + elements = new ValueType[nRows * nCols]; + ValueType value = ValueType(); + for (int i = 0; i < nRows * nCols; i++) { + elements[i] = value; + } +} + +template <typename ValueType> +bool Grid<ValueType>::inBounds(int row, int col) const { + return row >= 0 && col >= 0 && row < nRows && col < nCols; +} + +template <typename ValueType> +ValueType Grid<ValueType>::get(int row, int col) { + if (!inBounds(row, col)) throw std::out_of_range("get: Grid indices out of bounds"); + return elements[(row * nCols) + col]; +} + +template <typename ValueType> +const ValueType & Grid<ValueType>::get(int row, int col) const { + if (!inBounds(row, col)) throw std::out_of_range("get: Grid indices out of bounds"); + return elements[(row * nCols) + col]; +} + +template <typename ValueType> +void Grid<ValueType>::set(int row, int col, ValueType value) { + if (!inBounds(row, col)) throw std::out_of_range("set: Grid indices out of bounds"); + elements[(row * nCols) + col] = value; +} + +template <typename ValueType> +typename Grid<ValueType>::GridRow Grid<ValueType>::operator[](int row) { + return GridRow(this, row); +} + +template <typename ValueType> +const typename Grid<ValueType>::ConstGridRow +Grid<ValueType>::operator[](int row) const { + return ConstGridRow(this, row); +} + +template <typename ValueType> +void Grid<ValueType>::mapAll(void (*fn)(ValueType value)) const { + for (int i = 0; i < nRows; i++) { + for (int j = 0; j < nCols; j++) { + fn(get(i, j)); + } + } +} + +template <typename ValueType> +void Grid<ValueType>::mapAll(void (*fn)(const ValueType & value)) const { + for (int i = 0; i < nRows; i++) { + for (int j = 0; j < nCols; j++) { + fn(get(i, j)); + } + } +} + +template <typename ValueType> +template <typename FunctorType> +void Grid<ValueType>::mapAll(FunctorType fn) const { + for (int i = 0; i < nRows; i++) { + for (int j = 0; j < nCols; j++) { + fn(get(i, j)); + } + } +} + +template <typename ValueType> +std::string Grid<ValueType>::toString() { + std::ostringstream os; + os << *this; + return os.str(); +} + +/* + * Implementation notes: << and >> + * ------------------------------- + * The insertion and extraction operators use the template facilities in + * strlib.h to read and write generic values in a way that treats strings + * specially. + */ + +template <typename ValueType> +std::ostream & operator<<(std::ostream & os, const Grid<ValueType> & grid) { + os << "{"; + int nRows = grid.numRows(); + int nCols = grid.numCols(); + for (int i = 0; i < nRows; i++) { + if (i > 0) os << ", "; + os << "{"; + for (int j = 0; j < nCols; j++) { + if (j > 0) os << ", "; + writeGenericValue(os, grid.get(i, j), true); + } + os << "}"; + } + return os << "}"; +} + +template <typename ValueType> +std::istream & operator>>(std::istream & is, Grid<ValueType> & grid) { + std::vector<std::vector<ValueType>> vec2d; + is >> vec2d; + int nRows = vec2d.size(); + int nCols = (nRows == 0) ? 0 : vec2d[0].size(); + grid.resize(nRows, nCols); + for (int i = 0; i < nRows; i++) { + for (int j = 0; j < nCols; j++) { + grid[i][j] = vec2d[i][j]; + } + } + return is; +} + +#endif diff --git a/labb5/lib/StanfordCPPLib/lexicon.cpp b/labb5/lib/StanfordCPPLib/lexicon.cpp new file mode 100755 index 0000000..242542f --- /dev/null +++ b/labb5/lib/StanfordCPPLib/lexicon.cpp @@ -0,0 +1,315 @@ +/* + * File: lexicon.cpp + * ----------------- + * A lexicon is a word list. This lexicon is backed by two separate data + * structures for storing the words in the list: + * + * 1) a DAWG (directed acyclic word graph) + * 2) a Set<string> of other words. + * + * Typically the DAWG is used for a large list read from a file in binary + * format. The STL set is for words added piecemeal at runtime. + * + * The DAWG idea comes from an article by Appel & Jacobson, CACM May 1988. + * This lexicon implementation only has the code to load/search the DAWG. + * The DAWG builder code is quite a bit more intricate. + */ + +#include <fstream> +#include <string> +#include <cstring> +#include <algorithm> +#include <cstdlib> +#include <iostream> +#include <stdint.h> +#include "error.h" +#include "lexicon.h" +#include "strlib.h" +using namespace std; + +static void toLowerCaseInPlace(string & str); + +/* + * The DAWG is stored as an array of edges. Each edge is represented by + * one 32-bit struct. The 5 "letter" bits indicate the character on this + * transition (expressed as integer from 1 to 26), the "accept" bit indicates + * if you accept after appending that char (current path forms word), and the + * "lastEdge" bit marks this as the last edge in a sequence of childeren. + * The bulk of the bits (24) are used for the index within the edge array for + * the children of this node. The children are laid out contiguously in + * alphabetical order. Since we read edges as binary bits from a file in + * a big-endian format, we have to swap the struct order for little-endian + * machines. + */ + +Lexicon::Lexicon() { + edges = start = NULL; + numEdges = numDawgWords = 0; +} + +Lexicon::Lexicon(string filename) { + edges = start = NULL; + numEdges = numDawgWords = 0; + addWordsFromFile(filename); +} + +Lexicon::~Lexicon() { + if (edges) delete[] edges; +} + +/* + * Swaps a 4-byte long from big to little endian byte order + */ + +static uint32_t my_ntohl(uint32_t arg) { + uint32_t result = ((arg & 0xff000000) >> 24) | + ((arg & 0x00ff0000) >> 8) | + ((arg & 0x0000ff00) << 8) | + ((arg & 0x000000ff) << 24); + return result; +} + +/* + * Implementation notes: readBinaryFile + * ------------------------------------ + * The binary lexicon file format must follow this pattern: + * DAWG:<startnode index>:<num bytes>:<num bytes block of edge data> + */ + +void Lexicon::readBinaryFile(string filename) { + long startIndex, numBytes; + char firstFour[4], expected[] = "DAWG"; + ifstream istr(filename.c_str(), IOS_IN | IOS_BINARY); + if (false) my_ntohl(0); + if (istr.fail()) { + error("Couldn't open lexicon file " + filename); + } + istr.read(firstFour, 4); + istr.get(); + istr >> startIndex; + istr.get(); + istr >> numBytes; + istr.get(); + if (istr.fail() || strncmp(firstFour, expected, 4) != 0 + || startIndex < 0 || numBytes < 0) { + error("Improperly formed lexicon file " + filename); + } + numEdges = numBytes/sizeof(Edge); + edges = new Edge[numEdges]; + start = &edges[startIndex]; + istr.read((char *)edges, numBytes); + if (istr.fail() && !istr.eof()) { + error("Improperly formed lexicon file " + filename); + } + +#if defined(BYTE_ORDER) && BYTE_ORDER == LITTLE_ENDIAN + uint32_t *cur = (uint32_t *) edges; + for (int i = 0; i < numEdges; i++, cur++) { + *cur = my_ntohl(*cur); + } +#endif + + istr.close(); + numDawgWords = countDawgWords(start); +} + +int Lexicon::countDawgWords(Edge *ep) const { + int count = 0; + while (true) { + if (ep->accept) count++; + if (ep->children != 0) { + count += countDawgWords(&edges[ep->children]); + } + if (ep->lastEdge) break; + ep++; + } + return count; +} + +/* + * Check for DAWG in first 4 to identify as special binary format, + * otherwise assume ASCII, one word per line + */ + +void Lexicon::addWordsFromFile(string filename) { + char firstFour[4], expected[] = "DAWG"; + ifstream istr(filename.c_str()); + if (istr.fail()) { + error("Couldn't open lexicon file " + filename); + } + istr.read(firstFour, 4); + if (strncmp(firstFour, expected, 4) == 0) { + if (otherWords.size() != 0) { + error("Binary files require an empty lexicon"); + } + readBinaryFile(filename); + return; + } + istr.seekg(0); + string line; + while (getline(istr, line)) { + add(line); + } + istr.close(); +} + +int Lexicon::size() const { + return numDawgWords + otherWords.size(); +} + +bool Lexicon::isEmpty() const { + return size() == 0; +} + +void Lexicon::clear() { + if (edges) delete[] edges; + edges = start = NULL; + numEdges = numDawgWords = 0; + otherWords.clear(); +} + +/* + * Implementation notes: findEdgeForChar + * ------------------------------------- + * Iterate over sequence of children to find one that + * matches the given char. Returns NULL if we get to + * last child without finding a match (thus no such + * child edge exists). + */ + +Lexicon::Edge *Lexicon::findEdgeForChar(Edge *children, char ch) const { + Edge *curEdge = children; + while (true) { + if (curEdge->letter == charToOrd(ch)) return curEdge; + if (curEdge->lastEdge) return NULL; + curEdge++; + } +} + +/* + * Implementation notes: traceToLastEdge + * ------------------------------------- + * Given a string, trace out path through the DAWG edge-by-edge. + * If a path exists, return last edge; otherwise return NULL. + */ + +Lexicon::Edge *Lexicon::traceToLastEdge(const string & s) const { + if (!start) return NULL; + Edge *curEdge = findEdgeForChar(start, s[0]); + int len = (int) s.length(); + for (int i = 1; i < len; i++) { + if (!curEdge || !curEdge->children) return NULL; + curEdge = findEdgeForChar(&edges[curEdge->children], s[i]); + } + return curEdge; +} + +bool Lexicon::containsPrefix(string prefix) const { + if (prefix.empty()) return true; + toLowerCaseInPlace(prefix); + if (traceToLastEdge(prefix)) return true; + foreach (string word in otherWords) { + if (startsWith(word, prefix)) return true; + if (prefix < word) return false; + } + return false; +} + +bool Lexicon::contains(string word) const { + toLowerCaseInPlace(word); + Edge *lastEdge = traceToLastEdge(word); + if (lastEdge && lastEdge->accept) return true; + return otherWords.contains(word); +} + +void Lexicon::add(string word) { + toLowerCaseInPlace(word); + if (!contains(word)) { + otherWords.add(word); + } +} + +Lexicon::Lexicon(const Lexicon & src) { + deepCopy(src); +} + +Lexicon & Lexicon::operator=(const Lexicon & src) { + if (this != &src) { + if (edges != NULL) delete[] edges; + deepCopy(src); + } + return *this; +} + +void Lexicon::deepCopy(const Lexicon & src) { + if (src.edges == NULL) { + edges = NULL; + start = NULL; + } else { + numEdges = src.numEdges; + edges = new Edge[src.numEdges]; + memcpy(edges, src.edges, sizeof(Edge)*src.numEdges); + start = edges + (src.start - src.edges); + } + numDawgWords = src.numDawgWords; + otherWords = src.otherWords; +} + +void Lexicon::mapAll(void (*fn)(string)) const { + foreach (string word in *this) { + fn(word); + } +} + +void Lexicon::mapAll(void (*fn)(const string &)) const { + foreach (string word in *this) { + fn(word); + } +} + +void Lexicon::iterator::advanceToNextWordInSet() { + if (setIterator == setEnd) { + currentSetWord = ""; + } else { + currentSetWord = *setIterator; + ++setIterator; + } +} + +void Lexicon::iterator::advanceToNextWordInDawg() { + if (edgePtr == NULL) { + edgePtr = lp->start; + } else { + advanceToNextEdge(); + } + while (edgePtr != NULL && !edgePtr->accept) { + advanceToNextEdge(); + } +} + +void Lexicon::iterator::advanceToNextEdge() { + Edge *ep = edgePtr; + if (ep->children == 0) { + while (ep != NULL && ep->lastEdge) { + if (stack.isEmpty()) { + edgePtr = NULL; + return; + } else { + ep = stack.pop(); + currentDawgPrefix.resize(currentDawgPrefix.length() - 1); + } + } + edgePtr = ep + 1; + } else { + stack.push(ep); + currentDawgPrefix.push_back(lp->ordToChar(ep->letter)); + edgePtr = &lp->edges[ep->children]; + } +}; + +static void toLowerCaseInPlace(string & str) { + int nChars = str.length(); + for (int i = 0; i < nChars; i++) { + str[i] = tolower(str[i]); + } +} diff --git a/labb5/lib/StanfordCPPLib/lexicon.h b/labb5/lib/StanfordCPPLib/lexicon.h new file mode 100755 index 0000000..fea4726 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/lexicon.h @@ -0,0 +1,366 @@ +/* + * File: lexicon.h + * --------------- + * This file exports the <code>Lexicon</code> class, which is a + * compact structure for storing a list of words. + */ + +#ifndef _lexicon_h +#define _lexicon_h + +#include <string> +#include "foreach.h" +#include "set.h" +#include "stack.h" + +/* + * Class: Lexicon + * -------------- + * This class is used to represent a <b><i>lexicon,</i></b> or word list. + * The main difference between a lexicon and a dictionary is that + * a lexicon does not provide any mechanism for storing definitions; + * the lexicon contains only words, with no associated information. + * It is therefore similar to a set of strings, but with a more + * space-efficient internal representation. The <code>Lexicon</code> + * class supports efficient lookup operations for words and prefixes. + * + * <p>As an example of the use of the <code>Lexicon</code> class, the + * following program lists all the two-letter words in the lexicon + * stored in <code>EnglishWords.dat</code>: + * + *<pre> + * int main() { + * Lexicon english("EnglishWords.dat"); + * foreach (string word in english) { + * if (word.length() == 2) { + * cout << word << endl; + * } + * } + * return 0; + * } + *</pre> + */ + +#include <cctype> + +class Lexicon { + +public: + +/* + * Constructor: Lexicon + * Usage: Lexicon lex; + * Lexicon lex(filename); + * ----------------------------- + * Initializes a new lexicon. The default constructor creates an empty + * lexicon. The second form reads in the contents of the lexicon from + * the specified data file. The data file must be in one of two formats: + * (1) a space-efficient precompiled binary format or (2) a text file + * containing one word per line. The Stanford library distribution + * includes a binary lexicon file named <code>English.dat</code> + * containing a list of words in English. The standard code pattern + * to initialize that lexicon looks like this: + * + *<pre> + * Lexicon english("English.dat"); + *</pre> + */ + + Lexicon(); + Lexicon(std::string filename); + +/* + * Destructor: ~Lexicon + * -------------------- + * The destructor deallocates any storage associated with the lexicon. + */ + + virtual ~Lexicon(); + +/* + * Method: size + * Usage: int n = lex.size(); + * -------------------------- + * Returns the number of words contained in the lexicon. + */ + + int size() const; + +/* + * Method: isEmpty + * Usage: if (lex.isEmpty()) ... + * ----------------------------- + * Returns <code>true</code> if the lexicon contains no words. + */ + + bool isEmpty() const; + +/* + * Method: clear + * Usage: lex.clear(); + * ------------------- + * Removes all words from the lexicon. + */ + + void clear(); + +/* + * Method: add + * Usage: lex.add(word); + * --------------------- + * Adds the specified word to the lexicon. + */ + + void add(std::string word); + +/* + * Method: addWordsFromFile + * Usage: lex.addWordsFromFile(filename); + * -------------------------------------- + * Reads the file and adds all of its words to the lexicon. + */ + + void addWordsFromFile(std::string filename); + +/* + * Method: contains + * Usage: if (lex.contains(word)) ... + * ---------------------------------- + * Returns <code>true</code> if <code>word</code> is contained in the + * lexicon. In the <code>Lexicon</code> class, the case of letters is + * ignored, so "Zoo" is the same as "ZOO" or "zoo". + */ + + bool contains(std::string word) const; + +/* + * Method: containsPrefix + * Usage: if (lex.containsPrefix(prefix)) ... + * ------------------------------------------ + * Returns true if any words in the lexicon begin with <code>prefix</code>. + * Like <code>containsWord</code>, this method ignores the case of letters + * so that "MO" is a prefix of "monkey" or "Monday". + */ + + bool containsPrefix(std::string prefix) const; + +/* + * Method: mapAll + * Usage: lexicon.mapAll(fn); + * -------------------------- + * Calls the specified function on each word in the lexicon. + */ + + void mapAll(void (*fn)(std::string)) const; + void mapAll(void (*fn)(const std::string &)) const; + + template <typename FunctorType> + void mapAll(FunctorType fn) const; + +/* + * Additional Lexicon operations + * ----------------------------- + * In addition to the methods listed in this interface, the Lexicon + * class supports the following operations: + * + * - Deep copying for the copy constructor and assignment operator + * - Iteration using the range-based for statement and STL iterators + * + * All iteration is guaranteed to proceed in alphabetical order. All + * words in the lexicon are stored in lowercase. + */ + +/* Private section */ + +/**********************************************************************/ +/* Note: Everything below this point in the file is logically part */ +/* of the implementation and should not be of interest to clients. */ +/**********************************************************************/ + +private: + +#ifdef _WIN32 +#define LITTLE_ENDIAN 1 +#define BYTE_ORDER LITTLE_ENDIAN +#endif + +#pragma pack(1) + struct Edge { +#if defined(BYTE_ORDER) && BYTE_ORDER == LITTLE_ENDIAN + unsigned long letter:5; + unsigned long lastEdge:1; + unsigned long accept:1; + unsigned long unused:1; + unsigned long children:24; +#else + unsigned long children:24; + unsigned long unused:1; + unsigned long accept:1; + unsigned long lastEdge:1; + unsigned long letter:5; +#endif + }; +#pragma pack() + + Edge *edges, *start; + int numEdges, numDawgWords; + Set<std::string> otherWords; + +public: + +/* + * Deep copying support + * -------------------- + * This copy constructor and operator= are defined to make a + * deep copy, making it possible to pass/return lexicons by value + * and assign from one lexicon to another. The entire contents of + * the lexicon, including all words, are copied. Making copies is + * generally avoided because of the expense and thus, lexicons are + * typically passed by reference. When a copy is needed, these + * operations are supported. + */ + + Lexicon(const Lexicon & src); + Lexicon & operator=(const Lexicon & src); + +/* + * Iterator support + * ---------------- + * The classes in the StanfordCPPLib collection implement input + * iterators so that they work symmetrically with respect to the + * corresponding STL classes. + */ + + class iterator : public std::iterator<std::input_iterator_tag,std::string> { + private: + const Lexicon *lp; + int index; + std::string currentDawgPrefix; + std::string currentSetWord; + std::string tmpWord; + Edge *edgePtr; + Stack<Edge *> stack; + Set<std::string>::iterator setIterator; + Set<std::string>::iterator setEnd; + + void advanceToNextWordInDawg(); + void advanceToNextWordInSet(); + void advanceToNextEdge(); + + public: + iterator() { + this->lp = NULL; + } + + iterator(const Lexicon *lp, bool endFlag) { + this->lp = lp; + if (endFlag) { + index = lp->size(); + } else { + index = 0; + edgePtr = NULL; + setIterator = lp->otherWords.begin(); + setEnd = lp->otherWords.end(); + currentDawgPrefix = ""; + currentSetWord = ""; + advanceToNextWordInDawg(); + advanceToNextWordInSet(); + } + } + + iterator(const iterator & it) { + lp = it.lp; + index = it.index; + currentDawgPrefix = it.currentDawgPrefix; + currentSetWord = it.currentSetWord; + edgePtr = it.edgePtr; + stack = it.stack; + setIterator = it.setIterator; + } + + iterator & operator++() { + if (edgePtr == NULL) { + advanceToNextWordInSet(); + } else { + if (currentSetWord == "" || currentDawgPrefix < currentSetWord) { + advanceToNextWordInDawg(); + } else { + advanceToNextWordInSet(); + } + } + index++; + return *this; + } + + iterator operator++(int) { + iterator copy(*this); + operator++(); + return copy; + } + + bool operator==(const iterator & rhs) { + return lp == rhs.lp && index == rhs.index; + } + + bool operator!=(const iterator & rhs) { + return !(*this == rhs); + } + + std::string operator*() { + if (edgePtr == NULL) return currentSetWord; + if (currentSetWord == "" || currentDawgPrefix < currentSetWord) { + return currentDawgPrefix + lp->ordToChar(edgePtr->letter); + } else { + return currentSetWord; + } + } + + std::string *operator->() { + if (edgePtr == NULL) return ¤tSetWord; + if (currentSetWord == "" || currentDawgPrefix < currentSetWord) { + tmpWord = currentDawgPrefix + lp->ordToChar(edgePtr->letter); + return &tmpWord; + } else { + return ¤tSetWord; + } + } + + }; + + iterator begin() const { + return iterator(this, false); + } + + iterator end() const { + return iterator(this, true); + } + +private: + + Edge *findEdgeForChar(Edge *children, char ch) const; + Edge *traceToLastEdge(const std::string & s) const; + void readBinaryFile(std::string filename); + void deepCopy(const Lexicon & src); + int countDawgWords(Edge *start) const; + + unsigned int charToOrd(char ch) const { + return ((unsigned int)(tolower(ch) - 'a' + 1)); + } + + char ordToChar(unsigned int ord) const { + return ((char)(ord - 1 + 'a')); + } + +}; + +template <typename FunctorType> +void Lexicon::mapAll(FunctorType fn) const { + foreach (std::string word in *this) { + fn(word); + } +} + +// hashing functions for lexicons; defined in hashmap.cpp +int hashCode(const Lexicon& l); + +#endif diff --git a/labb5/lib/StanfordCPPLib/map.h b/labb5/lib/StanfordCPPLib/map.h new file mode 100755 index 0000000..663de03 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/map.h @@ -0,0 +1,910 @@ +/* + * File: map.h + * ----------- + * This file exports the template class <code>Map</code>, which + * maintains a collection of <i>key</i>-<i>value</i> pairs. + */ + +#ifndef _map_h +#define _map_h + +#include <cstdlib> +#include "foreach.h" +#include "stack.h" +#include "vector.h" + +/* + * Class: Map<KeyType,ValueType> + * ----------------------------- + * This class maintains an association between <b><i>keys</i></b> and + * <b><i>values</i></b>. The types used for keys and values are + * specified using templates, which makes it possible to use + * this structure with any data type. + */ + +template <typename KeyType, typename ValueType> +class Map { + +public: + +/* + * Constructor: Map + * Usage: Map<KeyType,ValueType> map; + * ---------------------------------- + * Initializes a new empty map that associates keys and values of the + * specified types. + */ + + Map(); + +/* + * Destructor: ~Map + * ---------------- + * Frees any heap storage associated with this map. + */ + + virtual ~Map(); + +/* + * Method: size + * Usage: int nEntries = map.size(); + * --------------------------------- + * Returns the number of entries in this map. + */ + + int size() const; + +/* + * Method: isEmpty + * Usage: if (map.isEmpty()) ... + * ----------------------------- + * Returns <code>true</code> if this map contains no entries. + */ + + bool isEmpty() const; + +/* + * Method: put + * Usage: map.put(key, value); + * --------------------------- + * Associates <code>key</code> with <code>value</code> in this map. + * Any previous value associated with <code>key</code> is replaced + * by the new value. + */ + + void put(const KeyType & key, const ValueType & value); + +/* + * Method: get + * Usage: ValueType value = map.get(key); + * -------------------------------------- + * Returns the value associated with <code>key</code> in this map. + * If <code>key</code> is not found, <code>get</code> returns the + * default value for <code>ValueType</code>. + */ + + ValueType get(const KeyType & key) const; + +/* + * Method: containsKey + * Usage: if (map.containsKey(key)) ... + * ------------------------------------ + * Returns <code>true</code> if there is an entry for <code>key</code> + * in this map. + */ + + bool containsKey(const KeyType & key) const; + +/* + * Method: remove + * Usage: map.remove(key); + * ----------------------- + * Removes any entry for <code>key</code> from this map. + */ + + void remove(const KeyType & key); + +/* + * Method: clear + * Usage: map.clear(); + * ------------------- + * Removes all entries from this map. + */ + + void clear(); + +/* + * Method: keys + * Usage: Vector<KeyType> keys = map.keys(); + * ------------------------------------------- + * Returns a collection containing all keys in this map. + */ + + Vector<KeyType> keys() const; + +/* + * Method: values + * Usage: Vector<ValueType> values = map.values(); + * ------------------------------------------- + * Returns a collection containing all values in this map. + */ + + Vector<ValueType> values() const; + +/* + * Operator: [] + * Usage: map[key] + * --------------- + * Selects the value associated with <code>key</code>. This syntax + * makes it easy to think of a map as an "associative array" + * indexed by the key type. If <code>key</code> is already present + * in the map, this function returns a reference to its associated + * value. If key is not present in the map, a new entry is created + * whose value is set to the default for the value type. + */ + + ValueType & operator[](const KeyType & key); + ValueType operator[](const KeyType & key) const; + +/* + * Method: toString + * Usage: string str = map.toString(); + * ----------------------------------- + * Converts the map to a printable string representation. + */ + + std::string toString(); + +/* + * Method: mapAll + * Usage: map.mapAll(fn); + * ---------------------- + * Iterates through the map entries and calls <code>fn(key, value)</code> + * for each one. The keys are processed in ascending order, as defined + * by the comparison function. + */ + + void mapAll(void (*fn)(KeyType, ValueType)) const; + void mapAll(void (*fn)(const KeyType &, const ValueType &)) const; + template <typename FunctorType> + void mapAll(FunctorType fn) const; + +/* + * Additional Map operations + * ------------------------- + * In addition to the methods listed in this interface, the Map + * class supports the following operations: + * + * - Stream I/O using the << and >> operators + * - Deep copying for the copy constructor and assignment operator + * - Iteration using the range-based for statement and STL iterators + * + * All iteration is guaranteed to proceed in the order established by + * the comparison function passed to the constructor, which ordinarily + * matches the order of the key type. + */ + +/* 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: + * --------------------- + * The map class is represented using a binary search tree. The + * specific implementation used here is the classic AVL algorithm + * developed by Georgii Adel'son-Vel'skii and Evgenii Landis in 1962. + */ + +private: + +/* Constant definitions */ + + static const int BST_LEFT_HEAVY = -1; + static const int BST_IN_BALANCE = 0; + static const int BST_RIGHT_HEAVY = +1; + +/* Type definition for nodes in the binary search tree */ + + struct BSTNode { + KeyType key; /* The key stored in this node */ + ValueType value; /* The corresponding value */ + BSTNode *left; /* Subtree containing all smaller keys */ + BSTNode *right; /* Subtree containing all larger keys */ + int bf; /* AVL balance factor */ + }; + +/* + * Implementation notes: Comparator + * -------------------------------- + * The Comparator class encapsulates a functor that compares two values + * of KeyType. In contrast to the classes in the STL, all of which embed + * the comparator in the type, the Map class and its derivatives pass an + * optional Comparator value. While this strategy results in a more + * complex implementation, it has the advantage of allowing maps and sets + * to carry their own comparators without forcing the client to include + * the comparator in the template declaration. This simplification is + * particularly important for the Graph class. + * + * The allocation is required in the TemplateComparator class because + * the type std::binary_function has subclasses but does not define a + * virtual destructor. + */ + + class Comparator { + public: + virtual ~Comparator() { } + virtual bool lessThan(const KeyType & k1, const KeyType & k2) = 0; + virtual Comparator *clone() = 0; + }; + + template <typename CompareType> + class TemplateComparator : public Comparator { + public: + TemplateComparator(CompareType cmp) { + this->cmp = new CompareType(cmp); + } + + virtual bool lessThan(const KeyType & k1, const KeyType & k2) { + return (*cmp)(k1, k2); + } + + virtual Comparator *clone() { + return new TemplateComparator<CompareType>(*cmp); + } + + private: + CompareType *cmp; + }; + + Comparator & getComparator() const { + return *cmpp; + } + +/* Instance variables */ + + BSTNode *root; /* Pointer to the root of the tree */ + int nodeCount; /* Number of entries in the map */ + Comparator *cmpp; /* Pointer to the comparator */ + + int (*cmpFn)(const KeyType &, const KeyType &); + +/* Private methods */ + +/* + * Implementation notes: findNode(t, key) + * -------------------------------------- + * Searches the tree rooted at t to find the specified key, searching + * in the left or right subtree, as approriate. If a matching node + * is found, findNode returns a pointer to the value cell in that node. + * If no matching node exists in the tree, findNode returns NULL. + */ + + ValueType *findNode(BSTNode *t, const KeyType & key) const { + if (t == NULL) return NULL; + int sign = compareKeys(key, t->key); + if (sign == 0) return &t->value; + if (sign < 0) { + return findNode(t->left, key); + } else { + return findNode(t->right, key); + } + } + +/* + * Implementation notes: addNode(t, key, heightFlag) + * ------------------------------------------------- + * Searches the tree rooted at t to find the specified key, searching + * in the left or right subtree, as approriate. If a matching node + * is found, addNode returns a pointer to the value cell in that node, + * just like findNode. If no matching node exists in the tree, addNode + * creates a new node with a default value. The heightFlag reference + * parameter returns a bool indicating whether the height of the tree + * was changed by this operation. + */ + + ValueType *addNode(BSTNode * & t, const KeyType & key, bool & heightFlag) { + heightFlag = false; + if (t == NULL) { + t = new BSTNode(); + t->key = key; + t->value = ValueType(); + t->bf = BST_IN_BALANCE; + t->left = t->right = NULL; + heightFlag = true; + nodeCount++; + return &t->value; + } + int sign = compareKeys(key, t->key); + if (sign == 0) return &t->value; + ValueType *vp = NULL; + int bfDelta = BST_IN_BALANCE; + if (sign < 0) { + vp = addNode(t->left, key, heightFlag); + if (heightFlag) bfDelta = BST_LEFT_HEAVY; + } else { + vp = addNode(t->right, key, heightFlag); + if (heightFlag) bfDelta = BST_RIGHT_HEAVY; + } + updateBF(t, bfDelta); + heightFlag = (bfDelta != 0 && t->bf != BST_IN_BALANCE); + return vp; + } + +/* + * Implementation notes: removeNode(t, key) + * ---------------------------------------- + * Removes the node containing the specified key from the tree rooted + * at t. The return value is true if the height of this subtree + * changes. The removeTargetNode method does the actual deletion. + */ + + bool removeNode(BSTNode * & t, const KeyType & key) { + if (t == NULL) return false; + int sign = compareKeys(key, t->key); + if (sign == 0) return removeTargetNode(t); + int bfDelta = BST_IN_BALANCE; + if (sign < 0) { + if (removeNode(t->left, key)) bfDelta = BST_RIGHT_HEAVY; + } else { + if (removeNode(t->right, key)) bfDelta = BST_LEFT_HEAVY; + } + updateBF(t, bfDelta); + return bfDelta != 0 && t->bf == BST_IN_BALANCE; + } + +/* + * Implementation notes: removeTargetNode(t) + * ----------------------------------------- + * Removes the node which is passed by reference as t. The easy case + * occurs when either (or both) of the children is NULL; all you need + * to do is replace the node with its non-NULL child, if any. If both + * children are non-NULL, this code finds the rightmost descendent of + * the left child; this node may not be a leaf, but will have no right + * child. Its left child replaces it in the tree, after which the + * replacement data is moved to the position occupied by the target node. + */ + + bool removeTargetNode(BSTNode * & t) { + BSTNode *toDelete = t; + if (t->left == NULL) { + t = t->right; + delete toDelete; + nodeCount--; + return true; + } else if (t->right == NULL) { + t = t->left; + delete toDelete; + nodeCount--; + return true; + } else { + BSTNode *successor = t->left; + while (successor->right != NULL) { + successor = successor->right; + } + t->key = successor->key; + t->value = successor->value; + if (removeNode(t->left, successor->key)) { + updateBF(t, BST_RIGHT_HEAVY); + return (t->bf == BST_IN_BALANCE); + } + return false; + } + } + +/* + * Implementation notes: updateBF(t, bfDelta) + * ------------------------------------------ + * Updates the balance factor in the node and rebalances the tree + * if necessary. + */ + + void updateBF(BSTNode * & t, int bfDelta) { + t->bf += bfDelta; + if (t->bf < BST_LEFT_HEAVY) { + fixLeftImbalance(t); + } else if (t->bf > BST_RIGHT_HEAVY) { + fixRightImbalance(t); + } + } + +/* + * Implementation notes: fixLeftImbalance(t) + * ----------------------------------------- + * This function is called when a node has been found that is out + * of balance with the longer subtree on the left. Depending on + * the balance factor of the left child, the code performs a + * single or double rotation. + */ + + void fixLeftImbalance(BSTNode * & t) { + BSTNode *child = t->left; + if (child->bf == BST_RIGHT_HEAVY) { + int oldBF = child->right->bf; + rotateLeft(t->left); + rotateRight(t); + t->bf = BST_IN_BALANCE; + switch (oldBF) { + case BST_LEFT_HEAVY: + t->left->bf = BST_IN_BALANCE; + t->right->bf = BST_RIGHT_HEAVY; + break; + case BST_IN_BALANCE: + t->left->bf = t->right->bf = BST_IN_BALANCE; + break; + case BST_RIGHT_HEAVY: + t->left->bf = BST_LEFT_HEAVY; + t->right->bf = BST_IN_BALANCE; + break; + } + } else if (child->bf == BST_IN_BALANCE) { + rotateRight(t); + t->bf = BST_RIGHT_HEAVY; + t->right->bf = BST_LEFT_HEAVY; + } else { + rotateRight(t); + t->right->bf = t->bf = BST_IN_BALANCE; + } + } + +/* + * Implementation notes: rotateLeft(t) + * ----------------------------------- + * This function performs a single left rotation of the tree + * that is passed by reference. The balance factors + * are unchanged by this function and must be corrected at a + * higher level of the algorithm. + */ + + void rotateLeft(BSTNode * & t) { + BSTNode *child = t->right; + t->right = child->left; + child->left = t; + t = child; + } + +/* + * Implementation notes: fixRightImbalance(t) + * ------------------------------------------ + * This function is called when a node has been found that + * is out of balance with the longer subtree on the right. + * Depending on the balance factor of the right child, the + * code performs a single or double rotation. + */ + + void fixRightImbalance(BSTNode * & t) { + BSTNode *child = t->right; + if (child->bf == BST_LEFT_HEAVY) { + int oldBF = child->left->bf; + rotateRight(t->right); + rotateLeft(t); + t->bf = BST_IN_BALANCE; + switch (oldBF) { + case BST_LEFT_HEAVY: + t->left->bf = BST_IN_BALANCE; + t->right->bf = BST_RIGHT_HEAVY; + break; + case BST_IN_BALANCE: + t->left->bf = t->right->bf = BST_IN_BALANCE; + break; + case BST_RIGHT_HEAVY: + t->left->bf = BST_LEFT_HEAVY; + t->right->bf = BST_IN_BALANCE; + break; + } + } else if (child->bf == BST_IN_BALANCE) { + rotateLeft(t); + t->bf = BST_LEFT_HEAVY; + t->left->bf = BST_RIGHT_HEAVY; + } else { + rotateLeft(t); + t->left->bf = t->bf = BST_IN_BALANCE; + } + } + +/* + * Implementation notes: rotateRight(t) + * ------------------------------------ + * This function performs a single right rotation of the tree + * that is passed by reference. The balance factors + * are unchanged by this function and must be corrected at a + * higher level of the algorithm. + */ + + void rotateRight(BSTNode * & t) { + + BSTNode *child = t->left; + t->left = child->right; + child->right = t; + t = child; + } + +/* + * Implementation notes: deleteTree(t) + * ----------------------------------- + * Deletes all the nodes in the tree. + */ + + void deleteTree(BSTNode *t) { + if (t != NULL) { + deleteTree(t->left); + deleteTree(t->right); + delete t; + } + } + +/* + * Implementation notes: mapAll + * ---------------------------- + * Calls fn(key, value) for every key-value pair in the tree. + */ + + void mapAll(BSTNode *t, void (*fn)(KeyType, ValueType)) const { + if (t != NULL) { + mapAll(t->left, fn); + fn(t->key, t->value); + mapAll(t->right, fn); + } + } + + void mapAll(BSTNode *t, + void (*fn)(const KeyType &, const ValueType &)) const { + if (t != NULL) { + mapAll(t->left, fn); + fn(t->key, t->value); + mapAll(t->right, fn); + } + } + + template <typename FunctorType> + void mapAll(BSTNode *t, FunctorType fn) const { + if (t != NULL) { + mapAll(t->left, fn); + fn(t->key, t->value); + mapAll(t->right, fn); + } + } + + void deepCopy(const Map & other) { + root = copyTree(other.root); + nodeCount = other.nodeCount; + cmpp = (other.cmpp == NULL) ? NULL : other.cmpp->clone(); + } + + BSTNode *copyTree(BSTNode * const t) { + if (t == NULL) return NULL; + BSTNode *np = new BSTNode(); + np->key = t->key; + np->value = t->value; + np->bf = t->bf; + np->left = copyTree(t->left); + np->right = copyTree(t->right); + return np; + } + +public: + +/* + * Hidden features + * --------------- + * The remainder of this file consists of the code required to + * support deep copying and iteration. Including these methods in + * the public portion of the interface would make that interface more + * difficult to understand for the average client. + */ + +/* Extended constructors */ + + template <typename CompareType> + explicit Map(CompareType cmp) { + root = NULL; + nodeCount = 0; + cmpp = new TemplateComparator<CompareType>(cmp); + } + +/* + * Implementation notes: compareKeys(k1, k2) + * ----------------------------------------- + * Compares the keys k1 and k2 and returns an integer (-1, 0, or +1) + * depending on whether k1 < k2, k1 == k2, or k1 > k2, respectively. + */ + + int compareKeys(const KeyType & k1, const KeyType & k2) const { + if (cmpp->lessThan(k1, k2)) return -1; + if (cmpp->lessThan(k2, k1)) return +1; + return 0; + } + +/* + * Deep copying support + * -------------------- + * This copy constructor and operator= are defined to make a + * deep copy, making it possible to pass/return maps by value + * and assign from one map to another. + */ + + Map & operator=(const Map & src) { + if (this != &src) { + clear(); + deepCopy(src); + } + return *this; + } + + Map(const Map & src) { + deepCopy(src); + } + +/* + * Iterator support + * ---------------- + * The classes in the StanfordCPPLib collection implement input + * iterators so that they work symmetrically with respect to the + * corresponding STL classes. + */ + + class iterator : public std::iterator<std::input_iterator_tag,KeyType> { + + private: + + struct NodeMarker { + BSTNode *np; + bool processed; + }; + + const Map *mp; /* Pointer to the map */ + int index; /* Index of current element */ + Stack<NodeMarker> stack; /* Stack of unprocessed nodes */ + + void findLeftmostChild() { + BSTNode *np = stack.peek().np; + if (np == NULL) return; + while (np->left != NULL) { + NodeMarker marker = { np->left, false }; + stack.push(marker); + np = np->left; + } + } + + public: + + iterator() { + /* Empty */ + } + + iterator(const Map *mp, bool end) { + this->mp = mp; + if (end || mp->nodeCount == 0) { + index = mp->nodeCount; + } else { + index = 0; + NodeMarker marker = { mp->root, false }; + stack.push(marker); + findLeftmostChild(); + } + } + + iterator(const iterator & it) { + mp = it.mp; + index = it.index; + stack = it.stack; + } + + iterator & operator++() { + NodeMarker marker = stack.pop(); + BSTNode *np = marker.np; + if (np->right == NULL) { + while (!stack.isEmpty() && stack.peek().processed) { + stack.pop(); + } + } else { + marker.processed = true; + stack.push(marker); + marker.np = np->right; + marker.processed = false; + stack.push(marker); + findLeftmostChild(); + } + index++; + return *this; + } + + iterator operator++(int) { + iterator copy(*this); + operator++(); + return copy; + } + + bool operator==(const iterator & rhs) { + return mp == rhs.mp && index == rhs.index; + } + + bool operator!=(const iterator & rhs) { + return !(*this == rhs); + } + + KeyType operator*() { + return stack.peek().np->key; + } + + KeyType *operator->() { + return &stack.peek().np->key; + } + + friend class Map; + + }; + + iterator begin() const { + return iterator(this, false); + } + + iterator end() const { + return iterator(this, true); + } + +}; + +template <typename KeyType, typename ValueType> +Map<KeyType,ValueType>::Map() { + root = NULL; + nodeCount = 0; + cmpp = new TemplateComparator< less<KeyType> >(less<KeyType>()); +} + +template <typename KeyType, typename ValueType> +Map<KeyType,ValueType>::~Map() { + if (cmpp != NULL) delete cmpp; + deleteTree(root); +} + +template <typename KeyType, typename ValueType> +int Map<KeyType,ValueType>::size() const { + return nodeCount; +} + +template <typename KeyType, typename ValueType> +bool Map<KeyType,ValueType>::isEmpty() const { + return nodeCount == 0; +} + +template <typename KeyType, typename ValueType> +void Map<KeyType,ValueType>::put(const KeyType & key, + const ValueType & value) { + bool dummy; + *addNode(root, key, dummy) = value; +} + +template <typename KeyType, typename ValueType> +ValueType Map<KeyType,ValueType>::get(const KeyType & key) const { + ValueType *vp = findNode(root, key); + if (vp == NULL) return ValueType(); + return *vp; +} + +template <typename KeyType, typename ValueType> +void Map<KeyType,ValueType>::remove(const KeyType & key) { + removeNode(root, key); +} + +template <typename KeyType, typename ValueType> +void Map<KeyType,ValueType>::clear() { + deleteTree(root); + root = NULL; + nodeCount = 0; +} + +template <typename KeyType, typename ValueType> +bool Map<KeyType,ValueType>::containsKey(const KeyType & key) const { + return findNode(root, key) != NULL; +} + +template <typename KeyType, typename ValueType> +ValueType & Map<KeyType,ValueType>::operator[](const KeyType & key) { + bool dummy; + return *addNode(root, key, dummy); +} + +template <typename KeyType, typename ValueType> +ValueType Map<KeyType,ValueType>::operator[](const KeyType & key) const { + return get(key); +} + +template <typename KeyType, typename ValueType> +void Map<KeyType,ValueType>::mapAll(void (*fn)(KeyType, ValueType)) const { + mapAll(root, fn); +} + +template <typename KeyType, typename ValueType> +void Map<KeyType,ValueType>::mapAll(void (*fn)(const KeyType &, + const ValueType &)) const { + mapAll(root, fn); +} + +template <typename KeyType, typename ValueType> +template <typename FunctorType> +void Map<KeyType,ValueType>::mapAll(FunctorType fn) const { + mapAll(root, fn); +} + +template <typename KeyType, typename ValueType> +std::string Map<KeyType,ValueType>::toString() { + ostringstream os; + os << *this; + return os.str(); +} + +template <typename KeyType,typename ValueType> +Vector<KeyType> Map<KeyType,ValueType>::keys() const { + Vector<KeyType> keyset; + foreach (KeyType key in *this) { + keyset.add(key); + } + return keyset; +} + +template <typename KeyType,typename ValueType> +Vector<ValueType> Map<KeyType,ValueType>::values() const { + Vector<ValueType> values; + foreach (KeyType key in *this) { + values.add(this->get(key)); + } + return values; +} + +/* + * Implementation notes: << and >> + * ------------------------------- + * The insertion and extraction operators use the template facilities in + * strlib.h to read and write generic values in a way that treats strings + * specially. + */ + +template <typename KeyType, typename ValueType> +std::ostream & operator<<(std::ostream & os, + const Map<KeyType,ValueType> & map) { + os << "{"; + typename Map<KeyType,ValueType>::iterator begin = map.begin(); + typename Map<KeyType,ValueType>::iterator end = map.end(); + typename Map<KeyType,ValueType>::iterator it = begin; + while (it != end) { + if (it != begin) os << ", "; + writeGenericValue(os, *it, false); + os << ":"; + writeGenericValue(os, map[*it], false); + ++it; + } + return os << "}"; +} + +template <typename KeyType, typename ValueType> +std::istream & operator>>(std::istream & is, Map<KeyType,ValueType> & map) { + char ch; + is >> ch; + if (ch != '{') error("operator >>: Missing {"); + map.clear(); + is >> ch; + if (ch != '}') { + is.unget(); + while (true) { + KeyType key; + readGenericValue(is, key); + is >> ch; + if (ch != ':') error("operator >>: Missing colon after key"); + ValueType value; + readGenericValue(is, value); + map[key] = value; + is >> ch; + if (ch == '}') break; + if (ch != ',') { + error(std::string("operator >>: Unexpected character ") + ch); + } + } + } + return is; +} + +#endif diff --git a/labb5/lib/StanfordCPPLib/private/_main.h_ b/labb5/lib/StanfordCPPLib/private/_main.h_ new file mode 100755 index 0000000..5392d18 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/private/_main.h_ @@ -0,0 +1,218 @@ +/* + * File: main.h + * ------------ + * This file renames the <code>main</code> method in the client's + * program to <code>Main</code>, thereby allowing a custom + * <code>main</code> method in the libraries to take control + * before passing control back to the client program. The main macro + * also defines a function getMainFlags that returns an int whose bits + * indicate which of the various interfaces have been loaded by this + * definition of main. + * + * Note: This file can be loaded more than once and must therefore + * check to see what has already been defined. + */ + +#ifdef main +# undef main +# undef CONSOLE_FLAG +# undef GRAPHICS_FLAG +#else +# define MAIN_USES_CONSOLE (1<<0) +# define MAIN_USES_GRAPHICS (1<<1) +#endif + +#ifdef _console_h +# define CONSOLE_FLAG MAIN_USES_CONSOLE +#else +# define CONSOLE_FLAG 0 +#endif + +#ifdef _gwindow_h +# define GRAPHICS_FLAG MAIN_USES_GRAPHICS +#else +# define GRAPHICS_FLAG 0 +#endif + +#if CONSOLE_FLAG | GRAPHICS_FLAG + +#define main main(int argc, char **argv) { \ + extern int _mainFlags; \ + _mainFlags = GRAPHICS_FLAG + CONSOLE_FLAG; \ + try { \ + return startupMain(argc, argv); \ + } catch (const std::exception& ex) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** An exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += ex.what(); \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw ex; \ + } catch (std::string str) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A string exception occurred during program execution: \n"; \ + msg += " *** \""; \ + msg += str; \ + msg += "\"\n ***\n"; \ + std::cerr << msg; \ + throw str; \ + } catch (char const* str) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A string exception occurred during program execution: \n"; \ + msg += " *** \""; \ + msg += str; \ + msg += "\"\n ***\n"; \ + std::cerr << msg; \ + throw str; \ + } catch (int n) { \ + char buf[128]; \ + snprintf(buf, 128, "%d", n); \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** An int exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += buf; \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw n; \ + } catch (long l) { \ + char buf[128]; \ + snprintf(buf, 128, "%ld", l); \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A long exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += buf; \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw l; \ + } catch (char c) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A char exception occurred during program execution: \n"; \ + msg += " *** '"; \ + msg += c; \ + msg += "'\n ***\n"; \ + std::cerr << msg; \ + throw c; \ + } catch (bool b) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A bool exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += (b ? "true" : "false"); \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw b; \ + } catch (double d) { \ + char buf[128]; \ + snprintf(buf, 128, "%lf", d); \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A double exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += buf; \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw d; \ + } \ + } \ + int Main + +extern int startupMain(int argc, char **argv); + +#else + +#define main main(int argc, char **argv) { \ + extern int _mainFlags; \ + _mainFlags = GRAPHICS_FLAG + CONSOLE_FLAG; \ + try { \ + return mainWrapper(argc, argv); } \ + } catch (const std::exception& ex) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** An exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += ex.what(); \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw ex; \ + } catch (std::string str) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A string exception occurred during program execution: \n"; \ + msg += " *** \""; \ + msg += str; \ + msg += "\"\n ***\n"; \ + std::cerr << msg; \ + throw str; \ + } catch (char const* str) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A string exception occurred during program execution: \n"; \ + msg += " *** \""; \ + msg += str; \ + msg += "\"\n ***\n"; \ + std::cerr << msg; \ + throw str; \ + } catch (int n) { \ + char buf[128]; \ + snprintf(buf, 128, "%d", n); \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** An int exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += buf; \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw n; \ + } catch (long l) { \ + char buf[128]; \ + snprintf(buf, 128, "%ld", l); \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A long exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += buf; \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw l; \ + } catch (char c) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A char exception occurred during program execution: \n"; \ + msg += " *** '"; \ + msg += c; \ + msg += "'\n ***\n"; \ + std::cerr << msg; \ + throw c; \ + } catch (bool b) { \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A bool exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += (b ? "true" : "false"); \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw b; \ + } catch (double d) { \ + char buf[128]; \ + snprintf(buf, 128, "%lf", d); \ + string msg = "\n ***\n"; \ + msg += " *** STANFORD C++ LIBRARY \n"; \ + msg += " *** A double exception occurred during program execution: \n"; \ + msg += " *** "; \ + msg += buf; \ + msg += "\n ***\n\n"; \ + std::cerr << msg; \ + throw d; \ + } \ + int Main + +extern int mainWrapper(int argc, char **argv); + +#endif diff --git a/labb5/lib/StanfordCPPLib/private/main.h b/labb5/lib/StanfordCPPLib/private/main.h new file mode 100755 index 0000000..4339915 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/private/main.h @@ -0,0 +1,62 @@ +/* + * File: main.h + * ------------ + * This file renames the <code>main</code> method in the client's + * program to <code>Main</code>, thereby allowing a custom + * <code>main</code> method in the libraries to take control + * before passing control back to the client program. The main macro + * also defines a function getMainFlags that returns an int whose bits + * indicate which of the various interfaces have been loaded by this + * definition of main. + * + * Note: This file can be loaded more than once and must therefore + * check to see what has already been defined. + */ + +#ifdef main +# undef main +# undef CONSOLE_FLAG +# undef GRAPHICS_FLAG +#else +# define MAIN_USES_CONSOLE (1<<0) +# define MAIN_USES_GRAPHICS (1<<1) +#endif + +#ifdef _console_h +# define CONSOLE_FLAG MAIN_USES_CONSOLE +#else +# define CONSOLE_FLAG 0 +#endif + +#ifdef _gwindow_h +# define GRAPHICS_FLAG MAIN_USES_GRAPHICS +#else +# define GRAPHICS_FLAG 0 +#endif + +void __StanfordCPPLib_terminate_handler(); +void __StanfordCPPLib_set_terminate(); + +#if CONSOLE_FLAG | GRAPHICS_FLAG + +#define main main(int argc, char **argv) { \ + extern int _mainFlags; \ + _mainFlags = GRAPHICS_FLAG + CONSOLE_FLAG; \ + return startupMain(argc, argv); \ + } \ + int Main + +extern int startupMain(int argc, char **argv); + +#else + +#define main main(int argc, char **argv) { \ + extern int _mainFlags; \ + _mainFlags = GRAPHICS_FLAG + CONSOLE_FLAG; \ + return mainWrapper(argc, argv); } \ + } \ + int Main + +extern int mainWrapper(int argc, char **argv); + +#endif diff --git a/labb5/lib/StanfordCPPLib/private/randompatch.h b/labb5/lib/StanfordCPPLib/private/randompatch.h new file mode 100755 index 0000000..c7a4b86 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/private/randompatch.h @@ -0,0 +1,63 @@ +/* + * File: private/randompatch.h + * --------------------------- + * This file patches the implementation of the random number library + * to avoid some serious bugs in standard implementations of rand, + * particularly on Mac OS X. It also includes a hack to set the + * seed from the RANDOM_SEED environment variable, which makes it + * possible to produce repeatable figures. + */ + +/* + * Implementation notes: rand, srand + * --------------------------------- + * To ensure that this package works the same way on all platforms, + * this file completely reimplements the rand and srand methods. The + * algorithm is a conventional linear congruential generator with the + * parameters used in GNU's gclib. RAND_MAX for this implementation + * is 2147483647 (2^31 - 1). + */ + +#define MULTIPLIER 1103515245 +#define OFFSET 12345 + +static int _seed = 1; + +#undef rand +#define rand() ((_seed = MULTIPLIER * _seed + OFFSET) & 0x7FFFFFFF) + +#undef srand +#define srand(seed) (_seed = int(seed), _seed = (_seed <= 0) ? 1 : _seed) + +#undef RAND_MAX +#define RAND_MAX 2147483647 + +/* + * Implementation notes: Windows patch + * ----------------------------------- + * On some versions of Windows, the time function is too coarse to use + * as a random seed. On those versions, this definition substitutes the + * GetTickCount function. + */ + +#if defined (_MSC_VER) && (_MSC_VER >= 1200) +# include <windows.h> +# define time(dummy) (GetTickCount()) +#endif + +#ifdef __APPLE__ + +# include <cstdlib> + + static time_t patchedTime(time_t *) { + char *str = getenv("RANDOM_SEED"); + if (str == NULL) { + return time(NULL); + } else { + return atoi(str); + } + } + +# define time(dummy) patchedTime(dummy) + +#endif diff --git a/labb5/lib/StanfordCPPLib/private/tokenpatch.h b/labb5/lib/StanfordCPPLib/private/tokenpatch.h new file mode 100755 index 0000000..d4930e5 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/private/tokenpatch.h @@ -0,0 +1,11 @@ +/* + * File: tokenpatch.h + * ------------------ + * This file renames TokenType and WORD to avoid conflict with the + * <windows.h> header. + */ + +#ifdef _MSC_VER +# define TokenType TokenTypeT +# define WORD WORD_TC +#endif diff --git a/labb5/lib/StanfordCPPLib/private/tplatform.h b/labb5/lib/StanfordCPPLib/private/tplatform.h new file mode 100755 index 0000000..6cf4bae --- /dev/null +++ b/labb5/lib/StanfordCPPLib/private/tplatform.h @@ -0,0 +1,25 @@ +/* + * File: tplatform.h + * ----------------- + * This interface defines the platform-specific methods on threads + * and locks. + */ + +/* Methods for threads */ + +int forkForPlatform(void (*fn)(void *), void *arg); +void incThreadRefCountForPlatform(int id); +void decThreadRefCountForPlatform(int id); +void joinForPlatform(int id); +int getCurrentThreadForPlatform(); +void yieldForPlatform(); + +/* Methods for locks */ + +int initLockForPlatform(); +void incLockRefCountForPlatform(int id); +void decLockRefCountForPlatform(int id); +void lockForPlatform(int id); +void unlockForPlatform(int id); +void waitForPlatform(int id); +void signalForPlatform(int id); diff --git a/labb5/lib/StanfordCPPLib/random.cpp b/labb5/lib/StanfordCPPLib/random.cpp new file mode 100755 index 0000000..b7ea860 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/random.cpp @@ -0,0 +1,99 @@ +/* + * File: random.cpp + * ---------------- + * This file implements the random.h interface. + */ + +#include <cstdlib> +#include <cmath> +#include <ctime> +#include "random.h" +#include "private/randompatch.h" +using namespace std; + +/* Private function prototype */ + +static void initRandomSeed(); + +/* + * Implementation notes: randomInteger + * ----------------------------------- + * The code for randomInteger produces the number in four steps: + * + * 1. Generate a random real number d in the range [0 .. 1). + * 2. Scale the number to the range [0 .. N) where N is the number of values. + * 3. Translate the number so that the range starts at the appropriate value. + * 4. Convert the result to the next lower integer. + * + * The implementation is complicated by the fact that both the expression + * + * RAND_MAX + 1 + * + * and the expression for the number of values + * + * high - low + 1 + * + * can overflow the integer range. These calculations must therefore be + * performed using doubles instead of ints. + */ + +int randomInteger(int low, int high) { + initRandomSeed(); + double d = rand() / (double(RAND_MAX) + 1); + double s = d * (double(high) - low + 1); + return int(floor(low + s)); +} + +/* + * Implementation notes: randomReal + * -------------------------------- + * The code for randomReal is similar to that for randomInteger, + * without the final conversion step. + */ + +double randomReal(double low, double high) { + initRandomSeed(); + double d = rand() / (double(RAND_MAX) + 1); + double s = d * (high - low); + return low + s; +} + +/* + * Implementation notes: randomChance + * ---------------------------------- + * The code for randomChance calls randomReal(0, 1) and then checks + * whether the result is less than the requested probability. + */ + +bool randomChance(double p) { + initRandomSeed(); + return randomReal(0, 1) < p; +} + +/* + * Implementation notes: setRandomSeed + * ----------------------------------- + * The setRandomSeed function simply forwards its argument to srand. + * The call to initRandomSeed is required to set the initialized flag. + */ + +void setRandomSeed(int seed) { + initRandomSeed(); + srand(seed); +} + +/* + * Implementation notes: initRandomSeed + * ------------------------------------ + * The initRandomSeed function declares a static variable that keeps track + * of whether the seed has been initialized. The first time initRandomSeed + * is called, initialized is false, so the seed is set to the current time. + */ + +static void initRandomSeed() { + static bool initialized = false; + if (!initialized) { + srand(int(time(NULL))); + initialized = true; + } +} diff --git a/labb5/lib/StanfordCPPLib/random.h b/labb5/lib/StanfordCPPLib/random.h new file mode 100755 index 0000000..3286f8f --- /dev/null +++ b/labb5/lib/StanfordCPPLib/random.h @@ -0,0 +1,58 @@ +/* + * File: random.h + * -------------- + * This file exports functions for generating pseudorandom numbers. + */ + +#ifndef _random_h +#define _random_h + +/* + * Function: randomInteger + * Usage: int n = randomInteger(low, high); + * ---------------------------------------- + * Returns a random integer in the range <code>low</code> to + * <code>high</code>, inclusive. + */ + +int randomInteger(int low, int high); + +/* + * Function: randomReal + * Usage: double d = randomReal(low, high); + * ---------------------------------------- + * Returns a random real number in the half-open interval + * [<code>low</code> .. <code>high</code>). A half-open + * interval includes the first endpoint but not the second, which + * means that the result is always greater than or equal to + * <code>low</code> but strictly less than <code>high</code>. + */ + +double randomReal(double low, double high); + +/* + * Function: randomChance + * Usage: if (randomChance(p)) ... + * ------------------------------- + * Returns <code>true</code> with the probability indicated by <code>p</code>. + * The argument <code>p</code> must be a floating-point number between + * 0 (never) and 1 (always). For example, calling + * <code>randomChance(.30)</code> returns <code>true</code> 30 percent + * of the time. + */ + +bool randomChance(double p); + +/* + * Function: setRandomSeed + * Usage: setRandomSeed(seed); + * --------------------------- + * Sets the internal random number seed to the specified value. You + * can use this function to set a specific starting point for the + * pseudorandom sequence or to ensure that program behavior is + * repeatable during the debugging phase. + */ + +void setRandomSeed(int seed); + +#endif diff --git a/labb5/lib/StanfordCPPLib/set.h b/labb5/lib/StanfordCPPLib/set.h new file mode 100755 index 0000000..4395fa5 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/set.h @@ -0,0 +1,621 @@ +/* + * File: set.h + * ----------- + * This file exports the <code>Set</code> class, which implements a + * collection for storing a set of distinct elements. + */ + +#ifndef _set_h +#define _set_h + +#include <iostream> +#include "foreach.h" +#include "map.h" +#include "vector.h" + +/* + * Class: Set<ValueType> + * --------------------- + * This class stores a collection of distinct elements. + */ + +template <typename ValueType> +class Set { + +public: + +/* + * Constructor: Set + * Usage: Set<ValueType> set; + * -------------------------- + * Creates an empty set of the specified element type. + */ + + Set(); + +/* + * Destructor: ~Set + * ---------------- + * Frees any heap storage associated with this set. + */ + + virtual ~Set(); + +/* + * Method: size + * Usage: count = set.size(); + * -------------------------- + * Returns the number of elements in this set. + */ + + int size() const; + +/* + * Method: isEmpty + * Usage: if (set.isEmpty()) ... + * ----------------------------- + * Returns <code>true</code> if this set contains no elements. + */ + + bool isEmpty() const; + +/* + * Method: add + * Usage: set.add(value); + * ---------------------- + * Adds an element to this set, if it was not already there. For + * compatibility with the STL <code>set</code> class, this method + * is also exported as <code>insert</code>. + */ + + void add(const ValueType & value); + void insert(const ValueType & value); + +/* + * Method: remove + * Usage: set.remove(value); + * ------------------------- + * Removes an element from this set. If the value was not + * contained in the set, no error is generated and the set + * remains unchanged. + */ + + void remove(const ValueType & value); + +/* + * Method: contains + * Usage: if (set.contains(value)) ... + * ----------------------------------- + * Returns <code>true</code> if the specified value is in this set. + */ + + bool contains(const ValueType & value) const; + +/* + * Method: isSubsetOf + * Usage: if (set.isSubsetOf(set2)) ... + * ------------------------------------ + * Implements the subset relation on sets. It returns + * <code>true</code> if every element of this set is + * contained in <code>set2</code>. + */ + + bool isSubsetOf(const Set & set2) const; + +/* + * Method: clear + * Usage: set.clear(); + * ------------------- + * Removes all elements from this set. + */ + + void clear(); + +/* + * Operator: == + * Usage: set1 == set2 + * ------------------- + * Returns <code>true</code> if <code>set1</code> and <code>set2</code> + * contain the same elements. + */ + + bool operator==(const Set & set2) const; + +/* + * Operator: != + * Usage: set1 != set2 + * ------------------- + * Returns <code>true</code> if <code>set1</code> and <code>set2</code> + * are different. + */ + + bool operator!=(const Set & set2) const; + +/* + * Operator: + + * Usage: set1 + set2 + * set1 + element + * --------------------- + * Returns the union of sets <code>set1</code> and <code>set2</code>, which + * is the set of elements that appear in at least one of the two sets. The + * right hand set can be replaced by an element of the value type, in which + * case the operator returns a new set formed by adding that element. + */ + + Set operator+(const Set & set2) const; + Set operator+(const ValueType & element) const; + +/* + * Operator: * + * Usage: set1 * set2 + * ------------------ + * Returns the intersection of sets <code>set1</code> and <code>set2</code>, + * which is the set of all elements that appear in both. + */ + + Set operator*(const Set & set2) const; + +/* + * Operator: - + * Usage: set1 - set2 + * set1 - element + * --------------------- + * Returns the difference of sets <code>set1</code> and <code>set2</code>, + * which is all of the elements that appear in <code>set1</code> but + * not <code>set2</code>. The right hand set can be replaced by an + * element of the value type, in which case the operator returns a new + * set formed by removing that element. + */ + + Set operator-(const Set & set2) const; + Set operator-(const ValueType & element) const; + +/* + * Operator: += + * Usage: set1 += set2; + * set1 += value; + * --------------------- + * Adds all of the elements from <code>set2</code> (or the single + * specified value) to <code>set1</code>. As a convenience, the + * <code>Set</code> package also overloads the comma operator so + * that it is possible to initialize a set like this: + * + *<pre> + * Set<int> digits; + * digits += 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; + *</pre> + */ + + Set & operator+=(const Set & set2); + Set & operator+=(const ValueType & value); + +/* + * Operator: *= + * Usage: set1 *= set2; + * -------------------- + * Removes any elements from <code>set1</code> that are not present in + * <code>set2</code>. + */ + + Set & operator*=(const Set & set2); + +/* + * Operator: -= + * Usage: set1 -= set2; + * set1 -= value; + * --------------------- + * Removes the elements from <code>set2</code> (or the single + * specified value) from <code>set1</code>. As a convenience, the + * <code>Set</code> package also overloads the comma operator so + * that it is possible to remove multiple elements from a set + * like this: + * + *<pre> + * digits -= 0, 2, 4, 6, 8; + *</pre> + * + * which removes the values 0, 2, 4, 6, and 8 from the set + * <code>digits</code>. + */ + + Set & operator-=(const Set & set2); + Set & operator-=(const ValueType & value); + +/* + * Method: first + * Usage: ValueType value = set.first(); + * ------------------------------------- + * Returns the first value in the set in the order established by the + * <code>foreach</code> macro. If the set is empty, <code>first</code> + * generates an error. + */ + + ValueType first() const; + +/* + * Method: toString + * Usage: string str = set.toString(); + * ----------------------------------- + * Converts the set to a printable string representation. + */ + + std::string toString(); + +/* + * Method: mapAll + * Usage: set.mapAll(fn); + * ---------------------- + * Iterates through the elements of the set and calls <code>fn(value)</code> + * for each one. The values are processed in ascending order, as defined + * by the comparison function. + */ + + void mapAll(void (*fn)(ValueType)) const; + void mapAll(void (*fn)(const ValueType &)) const; + + template <typename FunctorType> + void mapAll(FunctorType fn) const; + +/* + * Additional Set operations + * ------------------------- + * In addition to the methods listed in this interface, the Set class + * supports the following operations: + * + * - Stream I/O using the << and >> operators + * - Deep copying for the copy constructor and assignment operator + * - Iteration using the range-based for statement and STL iterators + * + * The iteration forms process the Set in ascending order. + */ + +/* Private section */ + +/**********************************************************************/ +/* Note: Everything below this point in the file is logically part */ +/* of the implementation and should not be of interest to clients. */ +/**********************************************************************/ + +private: + + Map<ValueType,bool> map; /* Map used to store the element */ + bool removeFlag; /* Flag to differentiate += and -= */ + +public: + +/* + * Hidden features + * --------------- + * The remainder of this file consists of the code required to + * support the comma operator, deep copying, and iteration. + * Including these methods in the public interface would make + * that interface more difficult to understand for the average client. + */ + +/* Extended constructors */ + + template <typename CompareType> + explicit Set(CompareType cmp) : map(Map<ValueType,bool>(cmp)) { + /* Empty */ + } + + Set & operator,(const ValueType & value) { + if (this->removeFlag) { + this->remove(value); + } else { + this->add(value); + } + return *this; + } + +/* + * Iterator support + * ---------------- + * The classes in the StanfordCPPLib collection implement input + * iterators so that they work symmetrically with respect to the + * corresponding STL classes. + */ + + class iterator : public std::iterator<std::input_iterator_tag,ValueType> { + + private: + + typename Map<ValueType,bool>::iterator mapit; /* Iterator for the map */ + + public: + + iterator() { + /* Empty */ + } + + iterator(typename Map<ValueType,bool>::iterator it) : mapit(it) { + /* Empty */ + } + + iterator(const iterator & it) { + mapit = it.mapit; + } + + iterator & operator++() { + ++mapit; + return *this; + } + + iterator operator++(int) { + iterator copy(*this); + operator++(); + return copy; + } + + bool operator==(const iterator & rhs) { + return mapit == rhs.mapit; + } + + bool operator!=(const iterator & rhs) { + return !(*this == rhs); + } + + ValueType operator*() { + return *mapit; + } + + ValueType *operator->() { + return mapit; + } + }; + + iterator begin() const { + return iterator(map.begin()); + } + + iterator end() const { + return iterator(map.end()); + } + +}; + +extern void error(std::string msg); + +template <typename ValueType> +Set<ValueType>::Set() { + /* Empty */ +} + +template <typename ValueType> +Set<ValueType>::~Set() { + /* Empty */ +} + +template <typename ValueType> +int Set<ValueType>::size() const { + return map.size(); +} + +template <typename ValueType> +bool Set<ValueType>::isEmpty() const { + return map.isEmpty(); +} + +template <typename ValueType> +void Set<ValueType>::add(const ValueType & value) { + map.put(value, true); +} + +template <typename ValueType> +void Set<ValueType>::insert(const ValueType & value) { + map.put(value, true); +} + +template <typename ValueType> +void Set<ValueType>::remove(const ValueType & value) { + map.remove(value); +} + +template <typename ValueType> +bool Set<ValueType>::contains(const ValueType & value) const { + return map.containsKey(value); +} + +template <typename ValueType> +void Set<ValueType>::clear() { + map.clear(); +} + +template <typename ValueType> +bool Set<ValueType>::isSubsetOf(const Set & set2) const { + iterator it = begin(); + iterator end = this->end(); + while (it != end) { + if (!set2.map.containsKey(*it)) return false; + ++it; + } + return true; +} + +/* + * Implementation notes: set operators + * ----------------------------------- + * The implementations for the set operators use iteration to walk + * over the elements in one or both sets. + */ + +template <typename ValueType> +bool Set<ValueType>::operator==(const Set & set2) const { + if (size() != set2.map.size()) return false; + iterator it1 = begin(); + iterator it2 = set2.map.begin(); + iterator end = this->end(); + while (it1 != end) { + if (map.compareKeys(*it1, *it2) != 0) return false; + ++it1; + ++it2; + } + return true; +} + +template <typename ValueType> +bool Set<ValueType>::operator!=(const Set & set2) const { + return !(*this == set2); +} + +template <typename ValueType> +Set<ValueType> Set<ValueType>::operator+(const Set & set2) const { + Set<ValueType> set = *this; + foreach (ValueType value in set2) { + set.add(value); + } + return set; +} + +template <typename ValueType> +Set<ValueType> Set<ValueType>::operator+(const ValueType & element) const { + Set<ValueType> set = *this; + set.add(element); + return set; +} + +template <typename ValueType> +Set<ValueType> Set<ValueType>::operator*(const Set & set2) const { + Set<ValueType> set = *this; + set.clear(); + foreach (ValueType value in *this) { + if (set2.contains(value)) set.add(value); + } + return set; +} + +template <typename ValueType> +Set<ValueType> Set<ValueType>::operator-(const Set & set2) const { + Set<ValueType> set = *this; + foreach (ValueType value in set2) { + set.remove(value); + } + return set; +} + +template <typename ValueType> +Set<ValueType> Set<ValueType>::operator-(const ValueType & element) const { + Set<ValueType> set = *this; + set.remove(element); + return set; +} + +template <typename ValueType> +Set<ValueType> & Set<ValueType>::operator+=(const Set & set2) { + foreach (ValueType value in set2) { + this->add(value); + } + return *this; +} + +template <typename ValueType> +Set<ValueType> & Set<ValueType>::operator+=(const ValueType & value) { + this->add(value); + this->removeFlag = false; + return *this; +} + +template <typename ValueType> +Set<ValueType> & Set<ValueType>::operator*=(const Set & set2) { + Vector<ValueType> toRemove; + foreach (ValueType value in *this) { + if (!set2.map.containsKey(value)) toRemove.add(value); + } + foreach (ValueType value in toRemove) { + this->remove(value); + } + return *this; +} + +template <typename ValueType> +Set<ValueType> & Set<ValueType>::operator-=(const Set & set2) { + Vector<ValueType> toRemove; + foreach (ValueType value in *this) { + if (set2.map.containsKey(value)) toRemove.add(value); + } + foreach (ValueType value in toRemove) { + this->remove(value); + } + return *this; +} + +template <typename ValueType> +Set<ValueType> & Set<ValueType>::operator-=(const ValueType & value) { + this->remove(value); + this->removeFlag = true; + return *this; +} + +template <typename ValueType> +ValueType Set<ValueType>::first() const { + if (isEmpty()) error("first: set is empty"); + return *begin(); +} + +template <typename ValueType> +std::string Set<ValueType>::toString() { + ostringstream os; + os << *this; + return os.str(); +} + +template <typename ValueType> +void Set<ValueType>::mapAll(void (*fn)(ValueType)) const { + map.mapAll(fn); +} + +template <typename ValueType> +void Set<ValueType>::mapAll(void (*fn)(const ValueType &)) const { + map.mapAll(fn); +} + +template <typename ValueType> +template <typename FunctorType> +void Set<ValueType>::mapAll(FunctorType fn) const { + map.mapAll(fn); +} + +template <typename ValueType> +std::ostream & operator<<(std::ostream & os, const Set<ValueType> & set) { + os << "{"; + bool started = false; + foreach (ValueType value in set) { + if (started) os << ", "; + writeGenericValue(os, value, true); + started = true; + } + os << "}"; + return os; +} + +template <typename ValueType> +std::istream & operator>>(std::istream & is, Set<ValueType> & set) { + char ch; + is >> ch; + if (ch != '{') error("operator >>: Missing {"); + set.clear(); + is >> ch; + if (ch != '}') { + is.unget(); + while (true) { + ValueType value; + readGenericValue(is, value); + set += value; + is >> ch; + if (ch == '}') break; + if (ch != ',') { + error(std::string("operator >>: Unexpected character ") + ch); + } + } + } + return is; +} + +// hashing functions for sets; defined in hashmap.cpp +int hashCode(const Set<std::string>& s); +int hashCode(const Set<int>& s); +int hashCode(const Set<char>& s); +int hashCode(const Set<long>& s); +int hashCode(const Set<double>& s); + +#endif diff --git a/labb5/lib/StanfordCPPLib/simpio.cpp b/labb5/lib/StanfordCPPLib/simpio.cpp new file mode 100755 index 0000000..4f91551 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/simpio.cpp @@ -0,0 +1,67 @@ +/* + * File: simpio.cpp + * ---------------- + * This file implements the simpio.h interface. + */ + +#include <fstream> +#include <iostream> +#include <sstream> +#include <string> +#include "simpio.h" +using namespace std; + +/* + * Implementation notes: getInteger, getReal + * ----------------------------------------- + * Each of these functions reads a complete input line and then uses the + * <sstream> library to parse that line into a value of the desired type. + * If that fails, the implementation asks the user for a new value. + */ + +int getInteger(string prompt) { + int value; + string line; + while (true) { + cout << prompt; + getline(cin, line); + istringstream stream(line); + stream >> value >> ws; + if (!stream.fail() && stream.eof()) break; + cout << "Illegal integer format. Try again." << endl; + if (prompt == "") prompt = "Enter an integer: "; + } + return value; +} + +double getReal(string prompt) { + double value; + string line; + while (true) { + cout << prompt; + getline(cin, line); + istringstream stream(line); + stream >> value >> ws; + if (!stream.fail() && stream.eof()) break; + cout << "Illegal numeric format. Try again." << endl; + if (prompt == "") prompt = "Enter a number: "; + } + return value; +} + +/* + * Implementation notes: getLine + * ----------------------------- + * The getLine function simply combines the process of displaying a + * prompt and reading an input line into a single call. The primary + * reason for including this function in the library is to ensure + * that the process of reading integers, floating-point numbers, and + * strings remains as consistent as possible. + */ + +string getLine(string prompt) { + string line; + cout << prompt; + getline(cin, line); + return line; +} diff --git a/labb5/lib/StanfordCPPLib/simpio.h b/labb5/lib/StanfordCPPLib/simpio.h new file mode 100755 index 0000000..25c32c1 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/simpio.h @@ -0,0 +1,53 @@ +/* + * File: simpio.h + * -------------- + * This file exports a set of functions that simplify input/output + * operations in C++ and provide some error-checking on console input. + */ + +#ifndef _simpio_h +#define _simpio_h + +#include <string> + +/* + * Function: getInteger + * Usage: int n = getInteger(prompt); + * ---------------------------------- + * Reads a complete line from <code>cin</code> and scans it as an + * integer. If the scan succeeds, the integer value is returned. If + * the argument is not a legal integer or if extraneous characters + * (other than whitespace) appear in the string, the user is given + * a chance to reenter the value. If supplied, the optional + * <code>prompt</code> string is printed before reading the value. + */ + +int getInteger(std::string prompt = ""); + +/* + * Function: getReal + * Usage: double x = getReal(prompt); + * ---------------------------------- + * Reads a complete line from <code>cin</code> and scans it as a + * floating-point number. If the scan succeeds, the floating-point + * value is returned. If the input is not a legal number or if + * extraneous characters (other than whitespace) appear in the string, + * the user is given a chance to reenter the value. If supplied, the + * optional <code>prompt</code> string is printed before reading the value. + */ + +double getReal(std::string prompt = ""); + +/* + * Function: getLine + * Usage: string line = getLine(prompt); + * ------------------------------------- + * Reads a line of text from <code>cin</code> and returns that line + * as a string. The newline character that terminates the input is + * not stored as part of the return value. If supplied, the optional + * <code>prompt</code> string is printed before reading the value. + */ + +std::string getLine(std::string prompt = ""); + +#endif 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 <code>Stack</code> 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<ValueType> + * ----------------------- + * This class models a linear structure called a <b><i>stack</i></b> + * 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 <code>push</code> (add to top) and <code>pop</code> + * (remove from top). + */ + +template <typename ValueType> +class Stack { + +public: + +/* + * Constructor: Stack + * Usage: Stack<ValueType> 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 <code>true</code> 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 <code>top</code>, 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 <code>true</code> if <code>stack1</code> and <code>stack2</code> + * contain the same elements. + */ + + bool operator==(const Stack & stack2) const; + +/* + * Operator: != + * Usage: stack1 != stack2 + * ------------------- + * Returns <code>true</code> if <code>stack1</code> and <code>stack2</code> + * 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<ValueType> 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 <typename ValueType> +Stack<ValueType>::Stack() { + /* Empty */ +} + +template <typename ValueType> +Stack<ValueType>::~Stack() { + /* Empty */ +} + +template <typename ValueType> +int Stack<ValueType>::size() const { + return elements.size(); +} + +template <typename ValueType> +bool Stack<ValueType>::isEmpty() const { + return size() == 0; +} + +template <typename ValueType> +void Stack<ValueType>::push(ValueType value) { + elements.add(value); +} + +template <typename ValueType> +ValueType Stack<ValueType>::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 <typename ValueType> +ValueType Stack<ValueType>::peek() const { + if (isEmpty()) error("peek: Attempting to peek at an empty stack"); + return elements.get(elements.size() - 1); +} + +template <typename ValueType> +ValueType & Stack<ValueType>::top() { + if (isEmpty()) error("top: Attempting to read top of an empty stack"); + return elements[elements.size() - 1]; +} + +template <typename ValueType> +void Stack<ValueType>::clear() { + elements.clear(); +} + +template <typename ValueType> +std::string Stack<ValueType>::toString() { + ostringstream os; + os << *this; + return os.str(); +} + +template <typename ValueType> +bool Stack<ValueType>::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 <typename ValueType> +bool Stack<ValueType>::operator!=(const Stack & stack2) const { + return !(*this == stack2); +} + +template <typename ValueType> +std::ostream & operator<<(std::ostream & os, const Stack<ValueType> & stack) { + os << "{"; + Stack<ValueType> copy = stack; + Stack<ValueType> 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 <typename ValueType> +std::istream & operator>>(std::istream & is, Stack<ValueType> & 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<std::string>& s); +int hashCode(const Stack<int>& s); +int hashCode(const Stack<char>& s); +int hashCode(const Stack<long>& s); +int hashCode(const Stack<double>& s); + +#endif diff --git a/labb5/lib/StanfordCPPLib/strlib.cpp b/labb5/lib/StanfordCPPLib/strlib.cpp new file mode 100755 index 0000000..7e53235 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/strlib.cpp @@ -0,0 +1,252 @@ +/* + * File: strlib.cpp + * ---------------- + * This file implements the strlib.h interface. + */ + +#include <cctype> +#include <iomanip> +#include <iostream> +#include <sstream> +#include "error.h" +#include "strlib.h" +using namespace std; + +/* Function prototypes */ + +/* + * Implementation notes: numeric conversion + * ---------------------------------------- + * These functions use the <sstream> library to perform the conversion. + */ + +string integerToString(int n) { + ostringstream stream; + stream << n; + return stream.str(); +} + +int stringToInteger(string str) { + istringstream stream(str); + int value; + stream >> value >> ws; + if (stream.fail() || !stream.eof()) { + error("stringToInteger: Illegal integer format (" + str + ")"); + } + return value; +} + +string realToString(double d) { + ostringstream stream; + stream << uppercase << d; + return stream.str(); +} + +double stringToReal(string str) { + istringstream stream(str); + double value; + stream >> value >> ws; + if (stream.fail() || !stream.eof()) { + error("stringToReal: Illegal floating-point format (" + str + ")"); + } + return value; +} + +/* + * Implementation notes: case conversion + * ------------------------------------- + * The functions toUpperCase and toLowerCase return a new string whose + * characters appear in the desired case. These implementations rely on + * the fact that the characters in the string are copied when the + * argument is passed to the function, which makes it possible to change + * the case of the copy without affecting the original. + */ + +string toUpperCase(string str) { + int nChars = str.length(); + for (int i = 0; i < nChars; i++) { + str[i] = toupper(str[i]); + } + return str; +} + +string toLowerCase(string str) { + int nChars = str.length(); + for (int i = 0; i < nChars; i++) { + str[i] = tolower(str[i]); + } + return str; +} + +/* + * Implementation notes: equalsIgnoreCase + * -------------------------------------- + * This implementation uses a for loop to cycle through the characters in + * each string. Converting each string to uppercase and then comparing + * the results makes for a shorter but less efficient implementation. + */ + +bool equalsIgnoreCase(string s1, string s2) { + if (s1.length() != s2.length()) return false; + int nChars = s1.length(); + for (int i = 0; i < nChars; i++) { + if (tolower(s1[i]) != tolower(s2[i])) return false; + } + return true; +} + +/* + * Implementation notes: startsWith, endsWith + * ------------------------------------------ + * These implementations are overloaded to allow the second argument to + * be either a string or a character. + */ + +bool startsWith(string str, string prefix) { + if (str.length() < prefix.length()) return false; + int nChars = prefix.length(); + for (int i = 0; i < nChars; i++) { + if (str[i] != prefix[i]) return false; + } + return true; +} + +bool startsWith(string str, char prefix) { + return str.length() > 0 && str[0] == prefix; +} + +bool endsWith(string str, string suffix) { + int nChars = suffix.length(); + int start = str.length() - nChars; + if (start < 0) return false; + for (int i = 0; i < nChars; i++) { + if (str[start + i] != suffix[i]) return false; + } + return true; +} + +bool endsWith(string str, char suffix) { + return str.length() > 0 && str[str.length() - 1] == suffix; +} + +string trim(string str) { + int finish = str.length() - 1; + while (finish >= 0 && isspace(str[finish])) { + finish--; + } + int start = 0; + while (start <= finish && isspace(str[start])) { + start++; + } + return str.substr(start, finish - start + 1); +} + +/* + * Implementation notes: readQuotedString and writeQuotedString + * ------------------------------------------------------------ + * Most of the work in these functions has to do with escape sequences. + */ + +static const string STRING_DELIMITERS = ",:)}]\n"; + +bool stringNeedsQuoting(const string & str) { + int n = str.length(); + for (int i = 0; i < n; i++) { + char ch = str[i]; + if (isspace(ch)) return false; + if (STRING_DELIMITERS.find(ch) != string::npos) return true; + } + return false; +} + +void readQuotedString(istream & is, string & str) { + str = ""; + char ch; + while (is.get(ch) && isspace(ch)) { + /* Empty */ + } + if (is.fail()) return; + if (ch == '\'' || ch == '"') { + char delim = ch; + while (is.get(ch) && ch != delim) { + if (is.fail()) error("Unterminated string"); + if (ch == '\\') { + if (!is.get(ch)) error("Unterminated string"); + if (isdigit(ch) || ch == 'x') { + int maxDigits = 3; + int base = 8; + if (ch == 'x') { + base = 16; + maxDigits = 2; + } + int result = 0; + int digit = 0; + for (int i = 0; i < maxDigits && ch != delim; i++) { + if (isdigit(ch)) { + digit = ch - '0'; + } else if (base == 16 && isxdigit(ch)) { + digit = toupper(ch) - 'A' + 10; + } else { + break; + } + result = base * result + digit; + if (!is.get(ch)) error("Unterminated string"); + } + ch = char(result); + is.unget(); + } else { + switch (ch) { + case 'a': ch = '\a'; break; + case 'b': ch = '\b'; break; + case 'f': ch = '\f'; break; + case 'n': ch = '\n'; break; + case 'r': ch = '\r'; break; + case 't': ch = '\t'; break; + case 'v': ch = '\v'; break; + case '"': ch = '"'; break; + case '\'': ch = '\''; break; + case '\\': ch = '\\'; break; + } + } + } + str += ch; + } + } else { + str += ch; + int endTrim = 0; + while (is.get(ch) && STRING_DELIMITERS.find(ch) == string::npos) { + str += ch; + if (!isspace(ch)) endTrim = str.length(); + } + if (is) is.unget(); + str = str.substr(0, endTrim); + } +} + +void writeQuotedString(ostream & os, const string & str, bool forceQuotes) { + if (!forceQuotes && stringNeedsQuoting(str)) forceQuotes = true; + if (forceQuotes) os << '"'; + int len = str.length(); + for (int i = 0; i < len; i++) { + char ch = str.at(i); + switch (ch) { + case '\a': os << "\\a"; break; + case '\b': os << "\\b"; break; + case '\f': os << "\\f"; break; + case '\n': os << "\\n"; break; + case '\r': os << "\\r"; break; + case '\t': os << "\\t"; break; + case '\v': os << "\\v"; break; + case '\\': os << "\\\\"; break; + default: + if (isprint(ch) && ch != '"') { + os << ch; + } else { + ostringstream oss; + oss << oct << setw(3) << setfill('0') << (int(ch) & 0xFF); + os << "\\" << oss.str(); + } + } + } + if (forceQuotes) os << '"'; +} diff --git a/labb5/lib/StanfordCPPLib/strlib.h b/labb5/lib/StanfordCPPLib/strlib.h new file mode 100755 index 0000000..d3be3d2 --- /dev/null +++ b/labb5/lib/StanfordCPPLib/strlib.h @@ -0,0 +1,204 @@ +/* + * File: strlib.h + * -------------- + * This file exports several useful string functions that are not + * included in the C++ string library. + */ + +#ifndef _strlib_h +#define _strlib_h + +#include <iostream> +#include <string> + +/* + * Function: integerToString + * Usage: string s = integerToString(n); + * ------------------------------------- + * Converts an integer into the corresponding string of digits. + * For example, calling <code>integerToString(123)</code> returns + * the string <code>"123"</code>. + */ + +std::string integerToString(int n); + +/* + * Function: stringToInteger + * Usage: int n = stringToInteger(str); + * ------------------------------------ + * Converts a string of digits into an integer. If the string is not a + * legal integer or contains extraneous characters other than whitespace, + * <code>stringToInteger</code> calls <code>error</code> with an + * appropriate message. + */ + +int stringToInteger(std::string str); + +/* + * Function: realToString + * Usage: string s = realToString(d); + * ---------------------------------- + * Converts a floating-point number into the corresponding string form. + * For example, calling <code>realToString(23.45)</code> returns + * the string <code>"23.45"</code>. + */ + +std::string realToString(double d); + +/* + * Function: stringToReal + * Usage: double d = stringToReal(str); + * ------------------------------------ + * Converts a string representing a real number into its corresponding + * value. If the string is not a legal floating-point number or contains + * extraneous characters other than whitespace, <code>stringToReal</code> + * calls <code>error</code> with an appropriate message. + */ + +double stringToReal(std::string str); + +/* + * Function: toUpperCase + * Usage: string s = toUpperCase(str); + * ----------------------------------- + * Returns a new string in which all lowercase characters have been converted + * into their uppercase equivalents. + */ + +std::string toUpperCase(std::string str); + +/* + * Function: toLowerCase + * Usage: string s = toLowerCase(str); + * ----------------------------------- + * Returns a new string in which all uppercase characters have been converted + * into their lowercase equivalents. + */ + +std::string toLowerCase(std::string str); + +/* + * Function: equalsIgnoreCase + * Usage: if (equalsIgnoreCase(s1, s2)) ... + * ---------------------------------------- + * Returns <code>true</code> if <code>s1</code> and <code>s2</code> are + * equal discounting differences in case. + */ + +bool equalsIgnoreCase(std::string s1, std::string s2); + +/* + * Function: startsWith + * Usage: if (startsWith(str, prefix)) ... + * --------------------------------------- + * Returns <code>true</code> if the string <code>str</code> starts with + * the specified prefix, which may be either a string or a character. + */ + +bool startsWith(std::string str, std::string prefix); +bool startsWith(std::string str, char prefix); + +/* + * Function: endsWith + * Usage: if (endsWith(str, suffix)) ... + * ------------------------------------- + * Returns <code>true</code> if the string <code>str</code> ends with + * the specified suffix, which may be either a string or a character. + */ + +bool endsWith(std::string str, std::string suffix); +bool endsWith(std::string str, char suffix); + +/* + * Function: trim + * Usage: string trimmed = trim(str); + * ---------------------------------- + * Returns a new string after removing any whitespace characters + * from the beginning and end of the argument. + */ + +std::string trim(std::string str); + +/* Private section */ + +/**********************************************************************/ +/* Note: Everything below this point in the file is logically part */ +/* of the implementation and should not be of interest to clients. */ +/**********************************************************************/ + +/* + * Friend function: writeQuotedString + * Usage: writeQuotedString(outfile, str, forceQuotes); + * ---------------------------------------------------- + * Writes the string str to outfile surrounded by double quotes, converting + * special characters to escape sequences, as necessary. If the optional + * parameter forceQuotes is explicitly set to false, quotes are included + * in the output only if necessary. + */ + +void writeQuotedString(std::ostream & os, const std::string & str, + bool forceQuotes = true); + +/* + * Friend function: readQuotedString + * Usage: readQuotedString(infile, str); + * ------------------------------------- + * Reads the next string from infile into the reference parameter str. + * If the first character (other than whitespace) is either a single + * or a double quote, this function reads characters up to the + * matching quote, processing standard escape sequences as it goes. + * If not, readString reads characters up to any of the characters + * in the string STRING_DELIMITERS in the implementation file. + */ + +void readQuotedString(std::istream & is, std::string & str); + +/* + * Friend function: stringNeedsQuoting + * Usage: if (stringNeedsQuoting(str)) ... + * --------------------------------------- + * Checks whether the string needs quoting in order to be read correctly. + */ + +bool stringNeedsQuoting(const std::string & str); + +/* + * Friend function: writeGenericValue + * Usage: writeGenericValue(os, value, forceQuotes); + * ------------------------------------------------- + * Writes a generic value to the output stream. If that value is a string, + * this function uses writeQuotedString to write the value. + */ + +template <typename ValueType> +void writeGenericValue(std::ostream & os, const ValueType & value, + bool) { + os << value; +} + +template <> +inline void writeGenericValue(std::ostream & os, const std::string & value, + bool forceQuotes) { + writeQuotedString(os, value, forceQuotes); +} + +/* + * Friend function: readGenericValue + * Usage: readGenericValue(is, value); + * ----------------------------------- + * Reads a generic value from the input stream. If that value is a string, + * this function uses readQuotedString to read the value. + */ + +template <typename ValueType> +void readGenericValue(std::istream & is, ValueType & value) { + is >> value; +} + +template <> +inline void readGenericValue(std::istream & is, std::string & value) { + readQuotedString(is, value); +} + + +#endif diff --git a/labb5/lib/StanfordCPPLib/vector.h b/labb5/lib/StanfordCPPLib/vector.h new file mode 100755 index 0000000..9781daa --- /dev/null +++ b/labb5/lib/StanfordCPPLib/vector.h @@ -0,0 +1,727 @@ +/* + * File: vector.h + * -------------- + * This file exports the <code>Vector</code> class, which provides an + * efficient, safe, convenient replacement for the array type in C++. + */ + +#ifndef _vector_h +#define _vector_h + +#include <iterator> +#include <iostream> +#include <sstream> +#include <string> +#include "foreach.h" +#include "strlib.h" + +/* + * Class: Vector<ValueType> + * ------------------------ + * This class stores an ordered list of values similar to an array. + * It supports traditional array selection using square brackets, but + * also supports inserting and deleting elements. It is similar in + * function to the STL <code>vector</code> type, but is simpler both + * to use and to implement. + */ + +template <typename ValueType> +class Vector { + +public: + +/* + * Constructor: Vector + * Usage: Vector<ValueType> vec; + * Vector<ValueType> vec(n, value); + * --------------------------------------- + * Initializes a new vector. The default constructor creates an + * empty vector. The second form creates an array with <code>n</code> + * elements, each of which is initialized to <code>value</code>; + * if <code>value</code> is missing, the elements are initialized + * to the default value for the type. + */ + + Vector(); + explicit Vector(int n, ValueType value = ValueType()); + +/* + * Destructor: ~Vector + * ------------------- + * Frees any heap storage allocated by this vector. + */ + + virtual ~Vector(); + +/* + * Method: size + * Usage: int nElems = vec.size(); + * ------------------------------- + * Returns the number of elements in this vector. + */ + + int size() const; + +/* + * Method: isEmpty + * Usage: if (vec.isEmpty()) ... + * ----------------------------- + * Returns <code>true</code> if this vector contains no elements. + */ + + bool isEmpty() const; + +/* + * Method: clear + * Usage: vec.clear(); + * ------------------- + * Removes all elements from this vector. + */ + + void clear(); + +/* + * Method: get + * Usage: ValueType val = vec.get(index); + * -------------------------------------- + * Returns the element at the specified index in this vector. This + * method signals an error if the index is not in the array range. + */ + + const ValueType & get(int index) const; + +/* + * Method: set + * Usage: vec.set(index, value); + * ----------------------------- + * Replaces the element at the specified index in this vector with + * a new value. The previous value at that index is overwritten. + * This method signals an error if the index is not in the array range. + */ + + void set(int index, const ValueType & value); + +/* + * Method: insert + * Usage: vec.insert(0, value); + * ---------------------------- + * Inserts the element into this vector before the specified index. + * All subsequent elements are shifted one position to the right. This + * method signals an error if the index is outside the range from 0 + * up to and including the length of the vector. + */ + + void insert(int index, ValueType value); + +/* + * Method: remove + * Usage: vec.remove(index); + * ------------------------- + * Removes the element at the specified index from this vector. + * All subsequent elements are shifted one position to the left. This + * method signals an error if the index is outside the array range. + */ + + void remove(int index); + +/* + * Method: add + * Usage: vec.add(value); + * ---------------------- + * Adds a new value to the end of this vector. To ensure compatibility + * with the <code>vector</code> class in the Standard Template Library, + * this method is also called <code>push_back</code>. + */ + + void add(ValueType value); + void push_back(ValueType value); + +/* + * Operator: [] + * Usage: vec[index] + * ----------------- + * Overloads <code>[]</code> to select elements from this vector. + * This extension enables the use of traditional array notation to + * get or set individual elements. This method signals an error if + * the index is outside the array range. The file supports two + * versions of this operator, one for <code>const</code> vectors and + * one for mutable vectors. + */ + + ValueType & operator[](int index); + const ValueType & operator[](int index) const; + +/* + * Operator: + + * Usage: v1 + v2 + * -------------- + * Concatenates two vectors. + */ + + Vector operator+(const Vector & v2) const; + +/* + * Operator: += + * Usage: v1 += v2; + * v1 += value; + * ------------------- + * Adds all of the elements from <code>v2</code> (or the single + * specified value) to <code>v1</code>. As a convenience, the + * <code>Vector</code> package also overloads the comma operator so + * that it is possible to initialize a vector like this: + * + *<pre> + * Vector<int> digits; + * digits += 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; + *</pre> + */ + + Vector & operator+=(const Vector & v2); + Vector & operator+=(const ValueType & value); + + bool operator==(const Vector & v2); + bool operator!=(const Vector & v2); + +/* + * Method: toString + * Usage: string str = vec.toString(); + * ----------------------------------- + * Converts the vector to a printable string representation. + */ + + std::string toString(); + +/* + * Method: mapAll + * Usage: vec.mapAll(fn); + * ---------------------- + * Calls the specified function on each element of the vector in + * ascending index order. + */ + + void mapAll(void (*fn)(ValueType)) const; + void mapAll(void (*fn)(const ValueType &)) const; + + template <typename FunctorType> + void mapAll(FunctorType fn) const; + +/* + * Additional Vector operations + * ---------------------------- + * In addition to the methods listed in this interface, the Vector + * class supports the following operations: + * + * - Stream I/O using the << and >> operators + * - Deep copying for the copy constructor and assignment operator + * - Iteration using the range-based for statement or STL iterators + * + * The iteration forms process the Vector in index order. + */ + +/* Private section */ + +/**********************************************************************/ +/* Note: Everything below this point in the file is logically part */ +/* of the implementation and should not be of interest to clients. */ +/**********************************************************************/ + +private: + +/* + * Implementation notes: Vector data structure + * ------------------------------------------- + * The elements of the Vector are stored in a dynamic array of + * the specified element type. If the space in the array is ever + * exhausted, the implementation doubles the array capacity. + */ + +/* Instance variables */ + + ValueType *elements; /* A dynamic array of the elements */ + int capacity; /* The allocated size of the array */ + int count; /* The number of elements in use */ + +/* Private methods */ + + void expandCapacity(); + void deepCopy(const Vector & src); + +/* + * Hidden features + * --------------- + * The remainder of this file consists of the code required to + * support deep copying and iteration. Including these methods + * in the public interface would make that interface more + * difficult to understand for the average client. + */ + +public: + +/* + * Deep copying support + * -------------------- + * This copy constructor and operator= are defined to make a deep copy, + * making it possible to pass or return vectors by value and assign + * from one vector to another. + */ + + Vector(const Vector & src); + Vector & operator=(const Vector & src); + +/* + * Operator: , + * ----------- + * Adds an element to the vector passed as the left-hand operatand. + * This form makes it easier to initialize vectors in old versions of C++. + */ + + Vector & operator,(const ValueType & value); + +/* + * Iterator support + * ---------------- + * The classes in the StanfordCPPLib collection implement input + * iterators so that they work symmetrically with respect to the + * corresponding STL classes. + */ + + class iterator : + public std::iterator<std::random_access_iterator_tag, ValueType> { + + private: + const Vector *vp; + int index; + + public: + + iterator() { + this->vp = NULL; + } + + iterator(const iterator & it) { + this->vp = it.vp; + this->index = it.index; + } + + iterator(const Vector *vp, int index) { + this->vp = vp; + this->index = index; + } + + iterator & operator++() { + index++; + return *this; + } + + iterator operator++(int) { + iterator copy(*this); + operator++(); + return copy; + } + + iterator & operator--() { + index--; + return *this; + } + + iterator operator--(int) { + iterator copy(*this); + operator--(); + return copy; + } + + bool operator==(const iterator & rhs) { + return vp == rhs.vp && index == rhs.index; + } + + bool operator!=(const iterator & rhs) { + return !(*this == rhs); + } + + bool operator<(const iterator & rhs) { + extern void error(std::string msg); + if (vp != rhs.vp) error("Iterators are in different vectors"); + return index < rhs.index; + } + + bool operator<=(const iterator & rhs) { + extern void error(std::string msg); + if (vp != rhs.vp) error("Iterators are in different vectors"); + return index <= rhs.index; + } + + bool operator>(const iterator & rhs) { + extern void error(std::string msg); + if (vp != rhs.vp) error("Iterators are in different vectors"); + return index > rhs.index; + } + + bool operator>=(const iterator & rhs) { + extern void error(std::string msg); + if (vp != rhs.vp) error("Iterators are in different vectors"); + return index >= rhs.index; + } + + iterator operator+(const int & rhs) { + return iterator(vp, index + rhs); + } + + iterator operator+=(const int & rhs) { + index += rhs; + return *this; + } + + iterator operator-(const int & rhs) { + return iterator(vp, index - rhs); + } + + iterator operator-=(const int & rhs) { + index -= rhs; + return *this; + } + + int operator-(const iterator & rhs) { + extern void error(std::string msg); + if (vp != rhs.vp) error("Iterators are in different vectors"); + return index - rhs.index; + } + + ValueType & operator*() { + return vp->elements[index]; + } + + ValueType *operator->() { + return &vp->elements[index]; + } + + ValueType & operator[](int k) { + return vp->elements[index + k]; + } + + }; + + iterator begin() const { + return iterator(this, 0); + } + + iterator end() const { + return iterator(this, count); + } + +}; + +/* Implementation section */ + +extern void error(std::string msg); + +/* + * Implementation notes: Vector constructor and destructor + * ------------------------------------------------------- + * The constructor allocates storage for the dynamic array + * and initializes the other fields of the object. The + * destructor frees the memory used for the array. + */ + +template <typename ValueType> +Vector<ValueType>::Vector() { + count = capacity = 0; + elements = NULL; +} + +template <typename ValueType> +Vector<ValueType>::Vector(int n, ValueType value) { + count = capacity = n; + elements = (n == 0) ? NULL : new ValueType[n]; + for (int i = 0; i < n; i++) { + elements[i] = value; + } +} + +template <typename ValueType> +Vector<ValueType>::~Vector() { + if (elements != NULL) delete[] elements; +} + +/* + * Implementation notes: Vector methods + * ------------------------------------ + * The basic Vector methods are straightforward and should require + * no detailed documentation. + */ + +template <typename ValueType> +int Vector<ValueType>::size() const { + return count; +} + +template <typename ValueType> +bool Vector<ValueType>::isEmpty() const { + return count == 0; +} + +template <typename ValueType> +void Vector<ValueType>::clear() { + if (elements != NULL) delete[] elements; + count = capacity = 0; + elements = NULL; +} + +template <typename ValueType> +const ValueType & Vector<ValueType>::get(int index) const { + if (index < 0 || index >= count) error("get: index out of range"); + return elements[index]; +} + +template <typename ValueType> +void Vector<ValueType>::set(int index, const ValueType & value) { + if (index < 0 || index >= count) error("set: index out of range"); + elements[index] = value; +} + +/* + * Implementation notes: insert, remove, add + * ----------------------------------------- + * These methods must shift the existing elements in the array to + * make room for a new element or to close up the space left by a + * deleted one. + */ + +template <typename ValueType> +void Vector<ValueType>::insert(int index, ValueType value) { + if (count == capacity) expandCapacity(); + if (index < 0 || index > count) { + error("insert: index out of range"); + } + for (int i = count; i > index; i--) { + elements[i] = elements[i - 1]; + } + elements[index] = value; + count++; +} + +template <typename ValueType> +void Vector<ValueType>::remove(int index) { + if (index < 0 || index >= count) error("remove: index out of range"); + for (int i = index; i < count - 1; i++) { + elements[i] = elements[i + 1]; + } + count--; +} + +template <typename ValueType> +void Vector<ValueType>::add(ValueType value) { + insert(count, value); +} + +template <typename ValueType> +void Vector<ValueType>::push_back(ValueType value) { + insert(count, value); +} + +/* + * Implementation notes: Vector selection + * -------------------------------------- + * The following code implements traditional array selection using + * square brackets for the index. + */ + +template <typename ValueType> +ValueType & Vector<ValueType>::operator[](int index) { + if (index < 0 || index >= count) error("Selection index out of range"); + return elements[index]; +} +template <typename ValueType> +const ValueType & Vector<ValueType>::operator[](int index) const { + if (index < 0 || index >= count) error("Selection index out of range"); + return elements[index]; +} + +template <typename ValueType> +Vector<ValueType> Vector<ValueType>::operator+(const Vector & v2) const { + Vector<ValueType> vec = *this; + foreach (ValueType value in v2) { + vec.add(value); + } + return vec; +} + +template <typename ValueType> +Vector<ValueType> & Vector<ValueType>::operator+=(const Vector & v2) { + foreach (ValueType value in v2) { + *this += value; + } + return *this; +} + +template <typename ValueType> +Vector<ValueType> & Vector<ValueType>::operator+=(const ValueType & value) { + this->add(value); + return *this; +} + +template <typename ValueType> +bool Vector<ValueType>::operator==(const Vector & v2) { + if (this->size() != v2.size()) { + return false; + } + for (int i = 0, size = this->size(); i < size; i++) { + if (this->get(i) != v2.get(i)) { + return false; + } + } + return true; +} + +template <typename ValueType> +bool Vector<ValueType>::operator!=(const Vector & v2) { + return !(*this == v2); +} + +template <typename ValueType> +std::string Vector<ValueType>::toString() { + ostringstream os; + os << *this; + return os.str(); +} + +/* + * Implementation notes: copy constructor and assignment operator + * -------------------------------------------------------------- + * The constructor and assignment operators follow a standard paradigm, + * as described in the associated textbook. + */ + +template <typename ValueType> +Vector<ValueType>::Vector(const Vector & src) { + deepCopy(src); +} + +template <typename ValueType> +Vector<ValueType> & Vector<ValueType>::operator=(const Vector & src) { + if (this != &src) { + if (elements != NULL) delete[] elements; + deepCopy(src); + } + return *this; +} + +template <typename ValueType> +void Vector<ValueType>::deepCopy(const Vector & src) { + count = capacity = src.count; + elements = (capacity == 0) ? NULL : new ValueType[capacity]; + for (int i = 0; i < count; i++) { + elements[i] = src.elements[i]; + } +} + +/* + * Implementation notes: The , operator + * ------------------------------------ + * The comma operator works adding the right operand to the vector and + * then returning the vector by reference so that it is set for the next + * value in the chain. + */ + +template <typename ValueType> +Vector<ValueType> & Vector<ValueType>::operator,(const ValueType & value) { + this->add(value); + return *this; +} + +/* + * Implementation notes: mapAll + * ---------------------------- + * The various versions of the mapAll function apply the function or + * function object to each element in ascending index order. + */ + +template <typename ValueType> +void Vector<ValueType>::mapAll(void (*fn)(ValueType)) const { + for (int i = 0; i < count; i++) { + fn(elements[i]); + } +} + +template <typename ValueType> +void Vector<ValueType>::mapAll(void (*fn)(const ValueType &)) const { + for (int i = 0; i < count; i++) { + fn(elements[i]); + } +} + +template <typename ValueType> +template <typename FunctorType> +void Vector<ValueType>::mapAll(FunctorType fn) const { + for (int i = 0; i < count; i++) { + fn(elements[i]); + } +} + +/* + * Implementation notes: expandCapacity + * ------------------------------------ + * This function doubles the array capacity, copies the old elements + * into the new array, and then frees the old one. + */ + +template <typename ValueType> +void Vector<ValueType>::expandCapacity() { + capacity = max(1, capacity * 2); + ValueType *array = new ValueType[capacity]; + for (int i = 0; i < count; i++) { + array[i] = elements[i]; + } + if (elements != NULL) delete[] elements; + elements = array; +} + +/* + * Implementation notes: << and >> + * ------------------------------- + * The insertion and extraction operators use the template facilities in + * strlib.h to read and write generic values in a way that treats strings + * specially. + */ + +template <typename ValueType> +std::ostream & operator<<(std::ostream & os, const Vector<ValueType> & vec) { + os << "{"; + int len = vec.size(); + for (int i = 0; i < len; i++) { + if (i > 0) os << ", "; + writeGenericValue(os, vec[i], true); + } + return os << "}"; +} + +template <typename ValueType> +std::istream & operator>>(std::istream & is, Vector<ValueType> & vec) { + char ch; + is >> ch; + if (ch != '{') error("operator >>: Missing {"); + vec.clear(); + is >> ch; + if (ch != '}') { + is.unget(); + while (true) { + ValueType value; + readGenericValue(is, value); + vec += value; + is >> ch; + if (ch == '}') break; + if (ch != ',') { + error(std::string("operator >>: Unexpected character ") + ch); + } + } + } + return is; +} + +// hashing functions for vectors; defined in hashmap.cpp +int hashCode(const Vector<std::string>& v); +int hashCode(const Vector<int>& v); +int hashCode(const Vector<char>& v); +int hashCode(const Vector<long>& v); +int hashCode(const Vector<double>& v); + +#endif |