spl.cpp

// Stanford C++ library (extracted)
// @author Marty Stepp
// @version Sat Oct 12 18:21:52 PDT 2019
//
// This library has been merged into a single .h and .cpp file by an automatic script
// to make it easier to include and use with the CodeStepByStep tool.
// DO NOT EDIT THIS FILE DIRECTLY!
// If you want to make changes or additions to the Stanford C++ library,
// make them to the library's original source as separate .cpp / .h files,
// then re-run the script to extract the library into these single large merged files.

#include "spl.h"

/////////////////////// BEGIN code extracted from StanfordCPPLib/private/init.cpp ///////////////////////
/*
 * File: init.cpp
 * --------------
 *
 * TODO
 *
 * @author Marty Stepp
 * @version 2018/11/22
 * - added headless mode support
 * @version 2018/08/28
 * - refactor to use stanfordcpplib namespace
 * @version 2018/08/27
 * - initial version
 */

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

#ifdef _WIN32
#  include <direct.h>   // for chdir
#else // _WIN32
#  include <unistd.h>   // for chdir
#endif // _WIN32


namespace stanfordcpplib {

namespace qtgui {
extern void initializeQtGraphicalConsole();
extern void shutdownConsole();
}

static void parseArgsQt(int argc, char** argv);

STATIC_VARIABLE_DECLARE(bool, isExitEnabled, true)

bool exitEnabled() {
    return STATIC_VARIABLE(isExitEnabled);
}

// called automatically by real main() function;
// call to this is inserted by library init.h
// to be run in Qt GUI main thread
void initializeLibrary(int argc, char** argv) {
    // ensure that library is initialized only once
    static bool _initialized = false;
    if (_initialized) {
        return;
    }
    _initialized = true;

#ifndef SPL_HEADLESS_MODE
    GThread::setMainThread();
#endif // SPL_HEADLESS_MODE

    parseArgsQt(argc, argv);

#ifndef SPL_HEADLESS_MODE
    // initialize the main Qt graphics subsystem
    QtGui::instance()->setArgs(argc, argv);
    QtGui::instance()->initializeQt();

    // initialize Qt graphical console (if student #included it)
    initializeQtGraphicalConsole();
#endif // SPL_HEADLESS_MODE
}

void initializeLibraryStudentThread() {
#if defined(SPL_CONSOLE_PRINT_EXCEPTIONS)
    setConsolePrintExceptions(true, /* force */ true);
#endif
}

// this should be roughly the same code as platform.cpp's parseArgs function
static void parseArgsQt(int argc, char** argv) {
    if (argc <= 0) {
        return;
    }
    std::string arg0 = argv[0];
    exceptions::setProgramNameForStackTrace(argv[0]);
    // programName() = getRoot(getTail(arg0));

#ifndef _WIN32
    // on Mac only, may need to change folder because of app's nested dir structure
    size_t ax = arg0.find(".app/Contents/");
    if (ax != std::string::npos) {
        while (ax > 0 && arg0[ax] != '/') {
            ax--;
        }
        if (ax > 0) {
            std::string cwd = arg0.substr(0, ax);
            chdir(cwd.c_str());
        }
    }
#endif // _WIN32

    char* noConsoleFlag = getenv("NOCONSOLE");
    if (noConsoleFlag && startsWith(std::string(noConsoleFlag), "t")) {
        return;
    }
}

// called automatically by real main() function;
// call to this is inserted by library init.h
// to be run in Qt main thread
#ifdef SPL_HEADLESS_MODE
void runMainInThread(int (* mainFunc)(void)) {
    mainFunc();
}

void runMainInThread(std::function<int()> mainFunc) {
    mainFunc();
}

void runMainInThreadVoid(void (* mainFuncVoid)(void)) {
    mainFuncVoid();
}

void runMainInThreadVoid(std::function<void()> mainFuncVoid) {
    mainFuncVoid();
}
#else // SPL_HEADLESS_MODE
void runMainInThread(int (* mainFunc)(void)) {
    QtGui::instance()->startBackgroundEventLoop(mainFunc);
}

void runMainInThread(std::function<int()> mainFunc) {
    QtGui::instance()->startBackgroundEventLoop(mainFunc);
}

void runMainInThreadVoid(void (* mainFuncVoid)(void)) {
    QtGui::instance()->startBackgroundEventLoopVoid(mainFuncVoid);
}

void runMainInThreadVoid(std::function<void()> mainFuncVoid) {
    QtGui::instance()->startBackgroundEventLoopVoid(mainFuncVoid);
}
#endif // SPL_HEADLESS_MODE

void setExitEnabled(bool enabled) {
    STATIC_VARIABLE(isExitEnabled) = enabled;
    // TODO: notify GConsoleWindow?
}

// shut down the Qt graphical console window;
// to be run in Qt main thread
void shutdownLibrary() {
#ifdef SPL_HEADLESS_MODE
    // empty
#else
    shutdownConsole();
#endif // SPL_HEADLESS_MODE
}

void staticInitializeLibrary() {
    // empty
}

} // namespace stanfordcpplib

namespace std {
void __stanfordcpplib__exitLibrary(int status) {
    if (stanfordcpplib::exitEnabled()) {
        // call std::exit (has been renamed)

#ifdef exit
#undef exit
        std::exit(status);
#define exit __stanfordcpplib__exitLibrary
#endif // exit

    } else {
        // not allowed to call exit(); produce error message
        std::ostringstream out;
        out << "Program tried to call exit(" << status << ") to quit. " << std::endl;
        out << "*** This function has been disabled; main should end through " << std::endl;
        out << "*** normal program control flow." << std::endl;
        error(out.str());
    }
}

} // namespace std

/////////////////////// END code extracted from StanfordCPPLib/private/init.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/collections/collections.cpp ///////////////////////
/*
 * File: collections.cpp
 * ---------------------
 * This file implements the collections.h interface.
 * 
 * @version 2019/04/11
 * - added functions to read/write quoted char values
 * @version 2018/10/20
 * - initial version
 */

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE
#include <iomanip>
#include <iostream>

/*
 * Implementation notes: readQuotedString and writeQuotedString
 * ------------------------------------------------------------
 * Most of the work in these functions has to do with escape sequences.
 */

STATIC_CONST_VARIABLE_DECLARE(std::string, STRING_DELIMITERS, ",:)}]\n")

bool stringNeedsQuoting(const std::string& str) {
    int n = str.length();
    for (int i = 0; i < n; i++) {
        char ch = str[i];
        if (isspace(ch)) return false;
        if (STATIC_VARIABLE(STRING_DELIMITERS).find(ch) != std::string::npos) return true;
    }
    return false;
}

bool readQuotedChar(std::istream& is, char& ch, bool throwOnError) {
    // skip whitespace
    char temp;
    while (is.get(temp) && isspace(temp)) {
        // empty
    }
    if (is.fail()) {
        return true;
    }

    // now we are either at a character, like X, or at the start of a quoted
    // character such as 'X' or '\n'
    if (temp == '\'' || temp == '"') {
        // quoted character; defer to string-reading code
        is.unget();
        std::string s;
        bool result = readQuotedString(is, s, throwOnError);
        if (result && !s.empty()) {
            ch = s[0];
        }
        return result;
    } else {
        // unquoted character; read it ourselves
        // special case: \ (e.g. \n, \t)
        if (temp == '\\') {
            // TODO
            char temp2;
            if (is.get(temp2)) {
                switch (temp2) {
                    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 '0':  ch = '\0'; break;
                    case '\\': ch = '\\'; break;
                    case '\'': ch = '\''; break;
                    case '"':  ch = '"'; break;
                    default:   ch = '\0'; break;
                }
            }
        } else {
            ch = temp;
        }
        return true;
    }
}

bool readQuotedString(std::istream& is, std::string& str, bool throwOnError) {
    str = "";
    char ch;
    while (is.get(ch) && isspace(ch)) {
        /* Empty */
    }
    if (is.fail()) {
        return true;   // empty string?
    }
    if (ch == '\'' || ch == '"') {
        char delim = ch;
        while (is.get(ch) && ch != delim) {
            if (is.fail()) {
                if (throwOnError) {
                    error("Unterminated string");
                }
                return false;
            }
            if (ch == '\\') {
                if (!is.get(ch)) {
                    if (throwOnError) {
                        error("Unterminated string");
                    }
                    is.setstate(std::ios_base::failbit);
                    return false;
                }
                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)) {
                            if (throwOnError) {
                                error("Unterminated string");
                            }
                            is.setstate(std::ios_base::failbit);
                            return false;
                        }
                    }
                    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) && STATIC_VARIABLE(STRING_DELIMITERS).find(ch) == std::string::npos) {
            str += ch;
            if (!isspace(ch)) {
                endTrim = str.length();
            }
        }
        if (is) is.unget();
        str = str.substr(0, endTrim);
    }
    return true;   // read successfully
}

std::ostream& writeQuotedChar(std::ostream& os, char ch, bool forceQuotes) {
    if (forceQuotes) {
        os << '\'';
    }
    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 {
            std::ostringstream oss;
            oss << std::oct << std::setw(3) << std::setfill('0') << (int(ch) & 0xFF);
            os << "\\" << oss.str();
        }
    }
    if (forceQuotes) {
        os << '\'';
    }
    return os;
}

std::ostream& writeQuotedString(std::ostream& os, const std::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 {
                std::ostringstream oss;
                oss << std::oct << std::setw(3) << std::setfill('0') << (int(ch) & 0xFF);
                os << "\\" << oss.str();
            }
        }
    }
    if (forceQuotes) {
        os << '"';
    }
    return os;
}

/////////////////////// END code extracted from StanfordCPPLib/collections/collections.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/collections/basicgraph.cpp ///////////////////////
/*
 * File: basicgraph.cpp
 * --------------------
 * This file implements any non-template functionality used by
 * the BasicGraph class.
 *
 * @version 2016/12/01
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

int hashCode(const BasicGraph& graph) {
    int code = hashSeed();
    for (Vertex* v : graph) {
        code = hashMultiplier() * code + hashCode(v->name);
    }
    for (Edge* e : graph.getEdgeSet()) {
        code = hashMultiplier() * code + hashCode(e->start->name);
        code = hashMultiplier() * code + hashCode(e->finish->name);
    }
    return (code & hashMask());
}

/////////////////////// END code extracted from StanfordCPPLib/collections/basicgraph.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/collections/dawglexicon.cpp ///////////////////////
/*
 * File: dawglexicon.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, see Julie Zelenski
 * if you need it.
 * 
 * @version 2018/03/10
 * - added method front
 * @version 2017/11/14
 * - added iterator version checking support
 * @version 2016/08/10
 * - added constructor support for std initializer_list usage, such as {"a", "b", "c"}
 * @version 2016/08/04
 * - added operator >>
 * @version 2015/07/05
 * - using global hashing functions rather than global variables
 * @version 2014/11/13
 * - added comparison operators <, >=, etc.
 * - added hashCode function
 * @version 2014/10/10
 * - removed 'using namespace' statement
 * - added equals method, ==, != operators
 * - fixed inclusion of foreach macro to avoid errors
 * - BUGFIX: operator << now shows "" marks around words to match Lexicon
 */

#define INTERNAL_INCLUDE 1

#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
#include <stdint.h>
#include <string>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

static uint32_t my_ntohl(uint32_t arg);

/*
 * 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.
 */

DawgLexicon::DawgLexicon() :
        _edges(nullptr),
        _start(nullptr),
        _edgeCount(0),
        _dawgWordsCount(0) {
    // empty
}

DawgLexicon::DawgLexicon(std::istream& input) :
        _edges(nullptr),
        _start(nullptr),
        _edgeCount(0),
        _dawgWordsCount(0) {
    addWordsFromFile(input);
}

DawgLexicon::DawgLexicon(const std::string& filename) :
        _edges(nullptr),
        _start(nullptr),
        _edgeCount(0),
        _dawgWordsCount(0) {
    addWordsFromFile(filename);
}

DawgLexicon::DawgLexicon(const DawgLexicon& src) :
        _edges(nullptr),
        _start(nullptr),
        _edgeCount(0),
        _dawgWordsCount(0) {
    deepCopy(src);
}

DawgLexicon::DawgLexicon(std::initializer_list<std::string> list) :
        _edges(nullptr),
        _start(nullptr),
        _edgeCount(0),
        _dawgWordsCount(0) {
    addAll(list);
}

DawgLexicon::~DawgLexicon() {
    if (_edges) {
        delete[] _edges;
    }
}

void DawgLexicon::add(const std::string& word) {
    std::string copy = word;
    toLowerCaseInPlace(copy);
    if (!contains(copy)) {
        _otherWords.add(copy);
    }
}

DawgLexicon& DawgLexicon::addAll(const DawgLexicon& lex) {
    for (const std::string& word : lex) {
        add(word);
    }
    return *this;
}

DawgLexicon& DawgLexicon::addAll(std::initializer_list<std::string> list) {
    for (const std::string& word : list) {
        add(word);
    }
    return *this;
}

/*
 * Check for DAWG in first 4 to identify as special binary format,
 * otherwise assume ASCII, one word per line
 */
void DawgLexicon::addWordsFromFile(std::istream& input) {
    char firstFour[4], expected[] = "DAWG";
    if (input.fail()) {
        error("DawgLexicon::addWordsFromFile: Couldn't read input");
    }
    input.read(firstFour, 4);
    if (strncmp(firstFour, expected, 4) == 0) {
        if (_otherWords.size() != 0) {
            error("DawgLexicon::addWordsFromFile: Binary files require an empty lexicon");
        }
        readBinaryFile(input);
    } else {
        // plain text file
        input.seekg(0);
        std::string line;
        while (getline(input, line)) {
            add(line);
        }
    }
}

/*
 * Check for DAWG in first 4 to identify as special binary format,
 * otherwise assume ASCII, one word per line
 */
void DawgLexicon::addWordsFromFile(const std::string& filename) {
    std::ifstream input(filename.c_str());
    if (input.fail()) {
        error("DawgLexicon::addWordsFromFile: Couldn't open lexicon file " + filename);
    }
    addWordsFromFile(input);
    input.close();
}

void DawgLexicon::clear() {
    if (_edges) {
        delete[] _edges;
    }
    _edges = _start = nullptr;
    _edgeCount = _dawgWordsCount = 0;
    _otherWords.clear();
}

bool DawgLexicon::contains(const std::string& word) const {
    std::string copy = word;
    toLowerCaseInPlace(copy);
    Edge* lastEdge = traceToLastEdge(copy);
    if (lastEdge && lastEdge->accept) {
        return true;
    }
    return _otherWords.contains(copy);
}

bool DawgLexicon::containsAll(const DawgLexicon& lex2) const {
    for (const std::string& word : lex2) {
        if (!contains(word)) {
            return false;
        }
    }
    return true;
}

bool DawgLexicon::containsAll(std::initializer_list<std::string> list) const {
    for (const std::string& word : list) {
        if (!contains(word)) {
            return false;
        }
    }
    return true;
}

bool DawgLexicon::containsPrefix(const std::string& prefix) const {
    if (prefix.empty()) {
        return true;
    }
    std::string copy = prefix;
    toLowerCaseInPlace(copy);
    if (traceToLastEdge(copy)) {
        return true;
    }
    for (std::string word : _otherWords) {
        if (startsWith(word, copy)) {
            return true;
        }
        if (copy < word) {
            return false;
        }
    }
    return false;
}

bool DawgLexicon::equals(const DawgLexicon& lex2) const {
    return stanfordcpplib::collections::equals(*this, lex2);
}

std::string DawgLexicon::front() const {
    if (isEmpty()) {
        error("DawgLexicon::front: lexicon is empty");
    }
    auto it = begin();
    return *it;
}

void DawgLexicon::insert(const std::string& word) {
    add(word);
}

bool DawgLexicon::isEmpty() const {
    return size() == 0;
}

bool DawgLexicon::isSubsetOf(const DawgLexicon& lex2) const {
    auto it = begin();
    auto end = this->end();
    while (it != end) {
        if (!lex2.contains(*it)) {
            return false;
        }
        ++it;
    }
    return true;
}

bool DawgLexicon::isSubsetOf(std::initializer_list<std::string> list) const {
    DawgLexicon lex2(list);
    return isSubsetOf(lex2);
}

bool DawgLexicon::isSupersetOf(const DawgLexicon& lex2) const {
    return containsAll(lex2);
}

bool DawgLexicon::isSupersetOf(std::initializer_list<std::string> list) const {
    return containsAll(list);
}

void DawgLexicon::mapAll(void (*fn)(std::string)) const {
    for (std::string word : *this) {
        fn(word);
    }
}

void DawgLexicon::mapAll(void (*fn)(const std::string &)) const {
    for (std::string word : *this) {
        fn(word);
    }
}

int DawgLexicon::size() const {
    return _dawgWordsCount + _otherWords.size();
}

std::string DawgLexicon::toString() const {
    std::ostringstream out;
    out << *this;
    return out.str();
}

/*
 * Operators
 */
bool DawgLexicon::operator ==(const DawgLexicon& lex2) const {
    return equals(lex2);
}

bool DawgLexicon::operator !=(const DawgLexicon& lex2) const {
    return !equals(lex2);
}

bool DawgLexicon::operator <(const DawgLexicon& lex2) const {
    return stanfordcpplib::collections::compare(*this, lex2) < 0;
}

bool DawgLexicon::operator <=(const DawgLexicon& lex2) const {
    return stanfordcpplib::collections::compare(*this, lex2) <= 0;
}

bool DawgLexicon::operator >(const DawgLexicon& lex2) const {
    return stanfordcpplib::collections::compare(*this, lex2) > 0;
}

bool DawgLexicon::operator >=(const DawgLexicon& lex2) const {
    return stanfordcpplib::collections::compare(*this, lex2) >= 0;
}

DawgLexicon DawgLexicon::operator +(const DawgLexicon& lex2) const {
    DawgLexicon lex = *this;
    lex.addAll(lex2);
    return lex;
}

DawgLexicon DawgLexicon::operator +(std::initializer_list<std::string> list) const {
    DawgLexicon lex = *this;
    lex.addAll(list);
    return lex;
}

DawgLexicon DawgLexicon::operator +(const std::string& word) const {
    DawgLexicon lex = *this;
    lex.add(word);
    return lex;
}

DawgLexicon& DawgLexicon::operator +=(const DawgLexicon& lex2) {
    return addAll(lex2);
}

DawgLexicon& DawgLexicon::operator +=(std::initializer_list<std::string> list) {
    return addAll(list);
}

DawgLexicon& DawgLexicon::operator +=(const std::string& word) {
    add(word);
    return *this;
}

/*
 * Private methods and helpers
 */

DawgLexicon& DawgLexicon::operator ,(const std::string& word) {
    add(word);
    return *this;
}

int DawgLexicon::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;
}

void DawgLexicon::deepCopy(const DawgLexicon& src) {
    if (!src._edges) {
        _edges = nullptr;
        _start = nullptr;
    } else {
        _edgeCount = src._edgeCount;
        _edges = new Edge[src._edgeCount];
        memcpy(_edges, src._edges, sizeof(Edge)*src._edgeCount);
        _start = _edges + (src._start - src._edges);
    }
    _dawgWordsCount = src._dawgWordsCount;
    _otherWords = src._otherWords;
}

/*
 * Implementation notes: findEdgeForChar
 * -------------------------------------
 * Iterate over sequence of children to find one that
 * matches the given char.  Returns nullptr if we get to
 * last child without finding a match (thus no such
 * child edge exists).
 */
DawgLexicon::Edge* DawgLexicon::findEdgeForChar(Edge* children, char ch) const {
    Edge* curEdge = children;
    while (true) {
        if (curEdge->letter == charToOrd(ch)) {
            return curEdge;
        }
        if (curEdge->lastEdge) {
            return nullptr;
        }
        curEdge++;
    }
}

/*
 * Implementation notes: readBinaryFile
 * ------------------------------------
 * The binary lexicon file format must follow this pattern:
 * DAWG:<startnode index>:<num bytes>:<num bytes block of edge data>
 */
void DawgLexicon::readBinaryFile(std::istream& input) {
    input.clear();
    input.seekg(0, std::ios::beg);
    long startIndex, numBytes;
    char firstFour[4], expected[] = "DAWG";
    if (input.fail()) {
        error("DawgLexicon::addWordsFromFile: Couldn't read input");
    }
    input.read(firstFour, 4);
    input.get();
    input >> startIndex;
    input.get();
    input >> numBytes;
    input.get();
    if (input.fail() || strncmp(firstFour, expected, 4) != 0
            || startIndex < 0 || numBytes < 0) {
        error("DawgLexicon::addWordsFromFile: Improperly formed lexicon file");
    }
    _edgeCount = numBytes / sizeof(Edge);
    _edges = new Edge[_edgeCount];
    _start = &_edges[startIndex];
    input.read((char*) _edges, numBytes);
    if (input.fail() && !input.eof()) {
        error("DawgLexicon::addWordsFromFile: Improperly formed lexicon file");
    }

#if defined(BYTE_ORDER) && BYTE_ORDER == LITTLE_ENDIAN
    // uint32_t* cur = (uint32_t*) edges;
    uint32_t* cur = reinterpret_cast<uint32_t*>(_edges);
    for (int i = 0; i < _edgeCount; i++, cur++) {
        *cur = my_ntohl(*cur);
    }
#endif

    _dawgWordsCount = countDawgWords(_start);
}

/*
 * Implementation notes: readBinaryFile
 * ------------------------------------
 * The binary lexicon file format must follow this pattern:
 * DAWG:<startnode index>:<num bytes>:<num bytes block of edge data>
 */
void DawgLexicon::readBinaryFile(const std::string& filename) {
#ifdef _foreachpatch_h
    std::ifstream input(filename.c_str(), __IOS_IN__ | __IOS_BINARY__);
#else
    std::ifstream input(filename.c_str(), std::ios::in | std::ios::binary);
#endif // _foreachpatch_h
    if (input.fail()) {
        error("DawgLexicon::addWordsFromFile: Couldn't open lexicon file " + filename);
    }
    readBinaryFile(input);
    input.close();
}

/*
 * Implementation notes: traceToLastEdge
 * -------------------------------------
 * Given a string, trace out path through the DAWG edge-by-edge.
 * If a path exists, return last edge; otherwise return nullptr.
 */

DawgLexicon::Edge* DawgLexicon::traceToLastEdge(const std::string& s) const {
    if (!_start) {
        return nullptr;
    }
    Edge* curEdge = findEdgeForChar(_start, s[0]);
    int len = (int) s.length();
    for (int i = 1; i < len; i++) {
        if (!curEdge || !curEdge->children) {
            return nullptr;
        }
        curEdge = findEdgeForChar(&_edges[curEdge->children], s[i]);
    }
    return curEdge;
}

DawgLexicon& DawgLexicon::operator =(const DawgLexicon& src) {
    if (this != &src) {
        if (_edges) {
            delete[] _edges;
        }
        deepCopy(src);
    }
    return *this;
}

void DawgLexicon::iterator::advanceToNextWordInSet() {
    if (setIterator == setEnd) {
        currentSetWord = "";
    } else {
        currentSetWord = *setIterator;
        ++setIterator;
    }
}

void DawgLexicon::iterator::advanceToNextEdge() {
    Edge *ep = edgePtr;
    if (ep->children == 0) {
        while (ep && ep->lastEdge) {
            if (stack.isEmpty()) {
                edgePtr = nullptr;
                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];
    }
}

void DawgLexicon::iterator::advanceToNextWordInDawg() {
    if (!edgePtr) {
        edgePtr = lp->_start;
    } else {
        advanceToNextEdge();
    }
    while (edgePtr && !edgePtr->accept) {
        advanceToNextEdge();
    }
}

std::ostream& operator <<(std::ostream& os, const DawgLexicon& lex) {
    return stanfordcpplib::collections::writeCollection(os, lex);
}

std::istream& operator >>(std::istream& is, DawgLexicon& lex) {
    std::string element;
    return stanfordcpplib::collections::readCollection(is, lex, element, /* descriptor */ "DawgLexicon::operator >>");
}

int hashCode(const DawgLexicon& lex) {
    return stanfordcpplib::collections::hashCodeCollection(lex);
}

/*
 * 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;
}

/////////////////////// END code extracted from StanfordCPPLib/collections/dawglexicon.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/collections/hashcode.cpp ///////////////////////
/*
 * File: hashcode.cpp
 * ------------------
 * This file implements the interface declared in hashcode.h.
 *
 * @version 2019/04/16
 * - bugfix for win64 involving hashCode for void* pointers
 * @version 2018/08/10
 * - bugfixes involving negative hash codes, unified string hashing
 * @version 2017/10/21
 * - added hash codes for short, unsigned integers
 * @version 2015/07/05
 * - using global hashing functions rather than global variables
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE
#include <cstddef>       // For size_t
#include <cstdint>       // For uintptr_t
#include <cstring>       // For strlen

static const int HASH_SEED = 5381;               // Starting point for first cycle
static const int HASH_MULTIPLIER = 33;           // Multiplier for each cycle
static const int HASH_MASK = unsigned(-1) >> 1;  // All 1 bits except the sign

int hashSeed() {
    return HASH_SEED;
}

int hashMultiplier() {
    return HASH_MULTIPLIER;
}

int hashMask() {
    return HASH_MASK;
}

/* 
 * Implementation notes: hashCode(int)
 * -----------------------------------
 * Hash code for integers masks off the sign bit, guaranteeing a nonnegative value.
 */
int hashCode(int key) {
    return key & HASH_MASK;
}

/* 
 * Implementation notes: hashCode(other primitive types)
 * -----------------------------------------------------
 * Hash codes for all other primitive types forward to the hash code for integers.
 * This ensures that all hash codes get the proper masking treatment.
 *
 * Thanks to Jeremy Barenholtz for identifying that the original versions of these
 * functions, which just cast their arguments to integers, could lead to negative
 * results.
 */
int hashCode(bool key) {
    return hashCode(static_cast<int>(key));
}

int hashCode(char key) {
    return hashCode(static_cast<int>(key));
}

int hashCode(unsigned int key) {
    return hashCode(static_cast<int>(key));
}

int hashCode(long key) {
    return hashCode(static_cast<int>(key));
}

int hashCode(unsigned long key) {
    return hashCode(static_cast<int>(key));
}

int hashCode(short key) {
    return hashCode(static_cast<int>(key));
}

int hashCode(unsigned short key) {
    return hashCode(static_cast<int>(key));
}

#ifdef _WIN64
int hashCode(uintptr_t key) {
    return hashCode(static_cast<unsigned long>(key));
}
#endif // _WIN64

/* 
 * Implementation notes: hashCode(void*)
 * -----------------------------------------------------
 * Catch-all handler for pointers not matched by other
 * overloads just treats the pointer value numerically.
 */
int hashCode(void* key) {
    return hashCode(reinterpret_cast<uintptr_t>(key));
}

/*
 * Implementation notes: hashCode(string), hashCode(double)
 * --------------------------------------------------------
 * This function takes a string key and uses it to derive a hash code,
 * which is a nonnegative integer related to the key by a deterministic
 * function that distributes keys well across the space of integers.
 * The general method is called linear congruence, which is also used
 * in random-number generators.  The specific algorithm used here is
 * called djb2 after the initials of its inventor, Daniel J. Bernstein,
 * Professor of Mathematics at the University of Illinois at Chicago.
 */
int hashCode(const char* base, size_t numBytes) {
    unsigned hash = HASH_SEED;
    for (size_t i = 0; i < numBytes; i++) {
        hash = HASH_MULTIPLIER * hash + base[i];
    }
    return hashCode(hash);
} 

int hashCode(const char* str) {
    return hashCode(str, strlen(str));
}

int hashCode(const std::string& str) {
    return hashCode(str.data(), str.length());
}

int hashCode(double key) {
    return hashCode(reinterpret_cast<const char *>(&key), sizeof(double));
}

int hashCode(float key) {
    return hashCode(reinterpret_cast<const char *>(&key), sizeof(float));
}

int hashCode(long double key) {
    return hashCode(reinterpret_cast<const char *>(&key), sizeof(long double));
}

/////////////////////// END code extracted from StanfordCPPLib/collections/hashcode.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/collections/lexicon.cpp ///////////////////////
/*
 * File: lexicon.cpp
 * -----------------
 * A Lexicon is a word list. This Lexicon is backed by a data
 * structure called a prefix tree or trie ("try").
 *
 * This is a re-implementation of Lexicon.  Its previous implementation used
 * a pair of structures: a directed acyclic word graph (DAWG) and an STL set.
 * That implementation was discarded because of several reasons:
 *
 * - It relied on binary file formats that were not readable by students.
 * - It did not provide for expected class members like remove.
 * - It had a clunky pair of data structures that had to be searched separately.
 * - It was optimized for space usage over ease of use and maintenance.
 *
 * The original DAWG implementation is retained as dawglexicon.h/cpp.
 * 
 * @version 2018/03/10
 * - added method front
 * @version 2016/09/24
 * - refactored to use collections.h utility functions
 * @version 2016/08/11
 * - added operators +, +=, -, -=, *, *= to better match Set/HashSet
 * @version 2016/08/10
 * - added constructor support for std initializer_list usage, such as {"a", "b", "c"}
 * @version 2016/08/04
 * - fixed operator >> to not throw errors
 * @version 2015/07/05
 * - using global hashing functions rather than global variables
 * @version 2014/11/13
 * - added comparison operators <, >=, etc.
 * - added hashCode function
 * @version 2014/10/10
 * - added comparison operators ==, !=
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

static bool scrub(std::string& str);

Lexicon::Lexicon() :
        _root(nullptr),
        _size(0),
        _removeFlag(false) {
    // empty
}

Lexicon::Lexicon(std::istream& input) :
        _root(nullptr),
        _size(0),
        _removeFlag(false) {
    addWordsFromFile(input);
}

Lexicon::Lexicon(const std::string& filename) :
        _root(nullptr),
        _size(0),
        _removeFlag(false) {
    addWordsFromFile(filename);
}

Lexicon::Lexicon(std::initializer_list<std::string> list) :
        _root(nullptr),
        _size(0),
        _removeFlag(false) {
    addAll(list);
}

Lexicon::Lexicon(const Lexicon& src) :
        _root(nullptr),
        _size(0),
        _removeFlag(false) {
    deepCopy(src);
}

Lexicon::~Lexicon() {
    clear();
}

bool Lexicon::add(const std::string& word) {
    if (word.empty()) {
        return false;
    }
    std::string scrubbed = word;
    if (!scrub(scrubbed)) {
        return false;
    }
    return addHelper(_root, scrubbed, /* originalWord */ scrubbed);
}

Lexicon& Lexicon::addAll(const Lexicon& lex) {
    for (const std::string& word : lex) {
        add(word);
    }
    return *this;
}

Lexicon& Lexicon::addAll(std::initializer_list<std::string> list) {
    for (const std::string& word : list) {
        add(word);
    }
    return *this;
}

void Lexicon::addWordsFromFile(std::istream& input) {
    bool isDAWG = isDAWGFile(input);
    rewindStream(input);
    if (isDAWG) {
        readBinaryFile(input);
    } else {
        if (input.fail()) {
            error("Lexicon::addWordsFromFile: Couldn't read from input");
        }
        std::string line;
        while (getline(input, line)) {
            add(trim(line));
        }
    }
}

void Lexicon::addWordsFromFile(const std::string& filename) {
    std::ifstream input(filename.c_str());
    if (input.fail()) {
        error("Lexicon::addWordsFromFile: Couldn't read from input file " + filename);
    }
    addWordsFromFile(input);
    input.close();
}

std::string Lexicon::back() const {
    if (isEmpty()) {
        error("Lexicon::back: lexicon is empty");
    }
    return _allWords.back();
}

void Lexicon::clear() {
    _size = 0;
    _allWords.clear();
    deleteTree(_root);
    _root = nullptr;
}

bool Lexicon::contains(const std::string& word) const {
    if (word.empty()) {
        return false;
    }
    std::string scrubbed = word;
    if (!scrub(scrubbed)) {
        return false;
    }
    return containsHelper(_root, scrubbed, /* isPrefix */ false);
}

bool Lexicon::containsAll(const Lexicon& lex2) const {
    for (const std::string& word : lex2) {
        if (!contains(word)) {
            return false;
        }
    }
    return true;
}

bool Lexicon::containsAll(std::initializer_list<std::string> list) const {
    for (const std::string& word : list) {
        if (!contains(word)) {
            return false;
        }
    }
    return true;
}

bool Lexicon::containsPrefix(const std::string& prefix) const {
    if (prefix.empty()) {
        return true;
    }
    std::string scrubbed = prefix;
    if (!scrub(scrubbed)) {
        return false;
    }
    return containsHelper(_root, scrubbed, /* isPrefix */ true);
}

bool Lexicon::equals(const Lexicon& lex2) const {
    return stanfordcpplib::collections::equals(*this, lex2);
}

std::string Lexicon::first() const {
    if (isEmpty()) {
        error("Lexicon::first: lexicon is empty");
    }
    return _allWords.front();
}

std::string Lexicon::front() const {
    if (isEmpty()) {
        error("Lexicon::front: lexicon is empty");
    }
    return _allWords.front();
}

void Lexicon::insert(const std::string& word) {
    add(word);
}

bool Lexicon::isEmpty() const {
    return size() == 0;
}

bool Lexicon::isSubsetOf(const Lexicon& lex2) const {
    auto it = begin();
    auto end = this->end();
    while (it != end) {
        if (!lex2.contains(*it)) {
            return false;
        }
        ++it;
    }
    return true;
}

bool Lexicon::isSubsetOf(std::initializer_list<std::string> list) const {
    Lexicon lex2(list);
    return isSubsetOf(lex2);
}

bool Lexicon::isSupersetOf(const Lexicon& lex2) const {
    return containsAll(lex2);
}

bool Lexicon::isSupersetOf(std::initializer_list<std::string> list) const {
    return containsAll(list);
}

void Lexicon::mapAll(void (*fn)(std::string)) const {
    for (std::string word : _allWords) {
        fn(word);
    }
}

void Lexicon::mapAll(void (*fn)(const std::string&)) const {
    for (std::string word : _allWords) {
        fn(word);
    }
}

bool Lexicon::remove(const std::string& word) {
    if (word.empty()) {
        return false;
    }
    std::string scrubbed = word;
    if (!scrub(scrubbed)) {
        return false;
    }
    return removeHelper(_root, scrubbed, /* originalWord */ scrubbed, /* isPrefix */ false);
}

Lexicon& Lexicon::removeAll(const Lexicon& lex2) {
    Vector<std::string> toRemove;
    for (const std::string& word : *this) {
        if (lex2.contains(word)) {
            toRemove.add(word);
        }
    }
    for (const std::string& word : toRemove) {
        remove(word);
    }
    return *this;
}

Lexicon& Lexicon::removeAll(std::initializer_list<std::string> list) {
    for (const std::string& word : list) {
        remove(word);
    }
    return *this;
}

bool Lexicon::removePrefix(const std::string& prefix) {
    if (prefix.empty()) {
        bool result = !isEmpty();
        clear();
        return result;
    }
    std::string scrubbed = prefix;
    if (!scrub(scrubbed)) {
        return false;
    }
    
    return removeHelper(_root, scrubbed, /* originalWord */ scrubbed, /* isPrefix */ true);
}

Lexicon& Lexicon::retainAll(const Lexicon& lex2) {
    Vector<std::string> toRemove;
    for (const std::string& word : *this) {
        if (!lex2.contains(word)) {
            toRemove.add(word);
        }
    }
    for (const std::string& word : toRemove) {
        remove(word);
    }
    return *this;
}

Lexicon& Lexicon::retainAll(std::initializer_list<std::string> list) {
    Lexicon lex2(list);
    return retainAll(lex2);
}

int Lexicon::size() const {
    return _size;
}

std::string Lexicon::toString() const {
    std::ostringstream out;
    out << *this;
    return out.str();
}

/*
 * Operators
 */
bool Lexicon::operator ==(const Lexicon& lex2) const {
    return equals(lex2);
}

bool Lexicon::operator !=(const Lexicon& lex2) const {
    return !equals(lex2);
}

bool Lexicon::operator <(const Lexicon& lex2) const {
    return stanfordcpplib::collections::compare(*this, lex2) < 0;
}

bool Lexicon::operator <=(const Lexicon& lex2) const {
    return stanfordcpplib::collections::compare(*this, lex2) <= 0;
}

bool Lexicon::operator >(const Lexicon& lex2) const {
    return stanfordcpplib::collections::compare(*this, lex2) > 0;
}

bool Lexicon::operator >=(const Lexicon& lex2) const {
    return stanfordcpplib::collections::compare(*this, lex2) >= 0;
}

Lexicon Lexicon::operator +(const Lexicon& lex2) const {
    Lexicon lex = *this;
    lex.addAll(lex2);
    return lex;
}

Lexicon Lexicon::operator +(std::initializer_list<std::string> list) const {
    Lexicon lex = *this;
    lex.addAll(list);
    return lex;
}

Lexicon Lexicon::operator +(const std::string& word) const {
    Lexicon lex = *this;
    lex.add(word);
    return lex;
}

Lexicon Lexicon::operator *(const Lexicon& lex2) const {
    Lexicon lex = *this;
    return lex.retainAll(lex2);
}

Lexicon Lexicon::operator *(std::initializer_list<std::string> list) const {
    Lexicon lex = *this;
    return lex.retainAll(list);
}

Lexicon Lexicon::operator -(const Lexicon& lex2) const {
    Lexicon lex = *this;
    return lex.removeAll(lex2);
}

Lexicon Lexicon::operator -(std::initializer_list<std::string> list) const {
    Lexicon lex = *this;
    return lex.removeAll(list);
}

Lexicon Lexicon::operator -(const std::string& word) const {
    Lexicon lex = *this;
    lex.remove(word);
    return lex;
}

Lexicon& Lexicon::operator +=(const Lexicon& lex2) {
    return addAll(lex2);
}

Lexicon& Lexicon::operator +=(std::initializer_list<std::string> list) {
    return addAll(list);
}

Lexicon& Lexicon::operator +=(const std::string& word) {
    add(word);
    _removeFlag = false;
    return *this;
}

Lexicon& Lexicon::operator *=(const Lexicon& lex2) {
    return retainAll(lex2);
}

Lexicon& Lexicon::operator *=(std::initializer_list<std::string> list) {
    return retainAll(list);
}

Lexicon& Lexicon::operator -=(const Lexicon& lex2) {
    return removeAll(lex2);
}

Lexicon& Lexicon::operator -=(std::initializer_list<std::string> list) {
    return removeAll(list);
}

Lexicon& Lexicon::operator -=(const std::string& word) {
    remove(word);
    _removeFlag = true;
    return *this;
}

/* private helpers implementation */

Lexicon& Lexicon::operator ,(const std::string& word) {
    if (_removeFlag) {
        remove(word);
    } else {
        add(word);
    }
    return *this;
}

// pre: word is scrubbed to contain only lowercase a-z letters
bool Lexicon::addHelper(TrieNode*& node, const std::string& word, const std::string& originalWord) {
    if (!node) {
        // create nodes all the way down, one for each letter of the word
        node = new TrieNode();
    }

    if (word.empty()) {
        // base case: we have added all of the letters of this word
        if (node->isWord()) {
            return false;   // duplicate word; already present
        } else {
            // new word; add it
            node->setWord(true);
            _size++;
            _allWords.add(originalWord);
            return true;
        }
    } else {
        // recursive case: chop off first letter, traverse the rest
        return addHelper(node->child(word[0]), word.substr(1), originalWord);
    }
}

// pre: word is scrubbed to contain only lowercase a-z letters
bool Lexicon::containsHelper(TrieNode* node, const std::string& word, bool isPrefix) const {
    if (!node) {
        // base case: no pointer down to here, so prefix must not exist
        return false;
    } else if (word.length() == 0) {
        // base case: Found nodes all the way down.
        // If we are looking for a prefix, this means this path IS a prefix,
        // so we should return true.
        // If we are looking for an exact word match rather than a prefix,
        // we must check the isWord flag to see that this word was added
        return (isPrefix ? true : node->isWord());
    } else {
        // recursive case: follow appropriate child pointer for one letter
        return containsHelper(node->child(word[0]), word.substr(1), isPrefix);
    }
}

// pre: word is scrubbed to contain only lowercase a-z letters
bool Lexicon::removeHelper(TrieNode*& node, const std::string& word, const std::string& originalWord, bool isPrefix) {
    if (!node) {
        // base case: dead end; this word/prefix must not be contained
        return false;
    } else if (word.empty()) {
        // base case: we have walked all of the letters of this word/prefix
        // and now we must do the removal
        if (isPrefix) {
            // remove this node and all of its descendents
            removeSubtreeHelper(node, originalWord);   // removes from m_allWords, sets m_size
            node = nullptr;
        } else {
            // found this word in the lexicon;
            if (node->isLeaf()) {
                // remove this leaf node only
                delete node;
                node = nullptr;
            } else {
                // de-word-ify this node, but leave it because it may
                // still have children that are valid words
                if (node->isWord()) {
                    node->setWord(false);
                }
            }
            _allWords.remove(originalWord);
            _size--;
        }
        return true;
    } else {
        // recursive case: chop off first letter, traverse the rest
        bool wasLeaf = node->isLeaf();
        bool result = removeHelper(node->child(word[0]), word.substr(1), originalWord, isPrefix);

        // memory cleanup: if I wasn't a leaf but now am, and am not a word,
        // then I am now unneeded, so remove me too
        if (result && !wasLeaf && node
                && node->isLeaf() && !node->isWord()) {
            delete node;
            node = nullptr;
        }
        return result;
    }
}

// remove/free this node and all descendents
void Lexicon::removeSubtreeHelper(TrieNode*& node, const std::string& originalWord) {
    if (node) {
        for (char letter = 'a'; letter <= 'z'; letter++) {
            removeSubtreeHelper(node->child(letter), originalWord + letter);
        }
        if (node->isWord()) {
            _allWords.remove(originalWord);
            _size--;
        }
        delete node;
        node = nullptr;
    }
}

void Lexicon::deepCopy(const Lexicon& src) {
    for (std::string word : src._allWords) {
        add(word);
    }
}

void Lexicon::deleteTree(TrieNode* node) {
    if (node) {
        for (char letter = 'a'; letter <= 'z'; letter++) {
            deleteTree(node->child(letter));
        }
        delete node;
    }
}

/*
 * Returns true if the given file (probably) represents a
 * binary DAWG lexicon data file.
 */
bool Lexicon::isDAWGFile(std::istream& input) const {
    char firstFour[4], expected[] = "DAWG";
    if (input.fail()) {
        error(std::string("Lexicon::addWordsFromFile: Couldn't read input"));
    }
    input.read(firstFour, 4);
    bool result = strncmp(firstFour, expected, 4) == 0;
    return result;
}

/*
 * Returns true if the given file (probably) represents a
 * binary DAWG lexicon data file.
 */
bool Lexicon::isDAWGFile(const std::string& filename) const {
    std::ifstream input(filename.c_str());
    if (input.fail()) {
        error(std::string("Lexicon::addWordsFromFile: Couldn't open lexicon file ") + filename);
    }
    bool result = isDAWGFile(input);
    input.close();
    return result;
}

/*
 * We just delegate to DawgLexicon, the old implementation, to read a binary
 * lexicon data file, and then we extract its yummy data into our trie.
 */
void Lexicon::readBinaryFile(std::istream& input) {
    DawgLexicon ldawg(input);
    for (std::string word : ldawg) {
        add(word);
    }
}

/*
 * We just delegate to DawgLexicon, the old implementation, to read a binary
 * lexicon data file, and then we extract its yummy data into our trie.
 */
void Lexicon::readBinaryFile(const std::string& filename) {
    DawgLexicon ldawg(filename);
    for (std::string word : ldawg) {
        add(word);
    }
}

Lexicon& Lexicon::operator =(const Lexicon& src) {
    if (this != &src) {
        clear();
        deepCopy(src);
    }
    return *this;
}

std::ostream& operator <<(std::ostream& out, const Lexicon& lex) {
    out << lex._allWords;
    return out;
}

std::istream& operator >>(std::istream& is, Lexicon& lex) {
    std::string element;
    return stanfordcpplib::collections::readCollection(is, lex, element, /* descriptor */ "Lexicon::operator >>");
}

/*
 * Hash function for lexicons.
 */
int hashCode(const Lexicon& lex) {
    return stanfordcpplib::collections::hashCodeCollection(lex);
}

static bool scrub(std::string& str) {
    size_t nChars = str.length();
    size_t outIndex = 0;
    for (size_t i = 0; i < nChars; i++) {
        std::string::value_type ch = tolower(str[i]);
        if (ch < 'a' || ch > 'z') {
            return false;   // illegal string
        } else {
            str[outIndex] = ch;
            outIndex++;
        }
    }
    if (outIndex != nChars) {
        str.erase(outIndex, nChars - outIndex);
    }
    return true;
}

/////////////////////// END code extracted from StanfordCPPLib/collections/lexicon.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/collections/shuffle.cpp ///////////////////////
/*
 * File: shuffle.cpp
 * -----------------
 * Implementation of the functions in shuffle.h.
 * See shuffle.h for documentation of each function.
 *
 * @author Marty Stepp
 * @version 2014/10/08
 * - removed 'using namespace' statement
 * @since 2014/02/01
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

/*
 * Randomly rearranges the characters of the given string and returns the
 * rearranged version.
 */
std::string shuffle(std::string s) {
    for (int i = 0, length = s.length(); i < length; i++) {
        int j = randomInteger(i, length - 1);
        if (i != j) {
            std::string::value_type temp = s[i];
            s[i] = s[j];
            s[j] = temp;
        }
    }
    return s;
}

/////////////////////// END code extracted from StanfordCPPLib/collections/shuffle.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/collections/gridlocation.cpp ///////////////////////
/*
 * File: gridlocation.cpp
 * ----------------------
 * This file implements the members of the <code>GridLocation</code> structure
 * and the <code>GridLocationRange</code> class.
 * See gridlocation.h for the declarations of each member.
 *
 * @version 2018/03/12
 * - initial version
 */

#define INTERNAL_INCLUDE 1

#include <sstream>
#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

GridLocation::GridLocation(int row, int col) {
    this->row = row;
    this->col = col;
}

GridLocationRange GridLocation::neighbors(int range, bool rowMajor) const {
    return GridLocationRange(row - range, col - range, row + range, col + range, rowMajor);
}

std::string GridLocation::toString() const {
    std::ostringstream out;
    out << *this;
    return out.str();
}

int hashCode(const GridLocation& loc) {
    return hashCode(loc.row, loc.col);
}

bool operator <(const GridLocation& loc1, const GridLocation& loc2) {
    return loc1.row < loc2.row ||
            (loc1.row == loc2.row && loc1.col < loc2.col);
}

bool operator <=(const GridLocation& loc1, const GridLocation& loc2) {
    return loc1 < loc2 || loc1 == loc2;
}

bool operator ==(const GridLocation& loc1, const GridLocation& loc2) {
    return loc1.row == loc2.row && loc1.col == loc2.col;
}

bool operator !=(const GridLocation& loc1, const GridLocation& loc2) {
    return !(loc1 == loc2);
}

bool operator >(const GridLocation& loc1, const GridLocation& loc2) {
    return loc2 < loc1;
}

bool operator >=(const GridLocation& loc1, const GridLocation& loc2) {
    return !(loc1 < loc2);
}

std::ostream& operator <<(std::ostream& out, const GridLocation& loc) {
    return out << "r" << loc.row << "c" << loc.col;
}

std::istream& operator >>(std::istream& input, GridLocation& loc) {
    // read 'r'
    input.get();
    if (!input) {
        input.setstate(std::ios_base::failbit);
        return input;
    }

    // read row
    int row;
    if (!(input >> row)) {
        input.setstate(std::ios_base::failbit);
        return input;
    }

    // read 'c'
    input.get();
    if (!input) {
        input.setstate(std::ios_base::failbit);
        return input;
    }

    // read row
    int col;
    if (!(input >> col)) {
        input.setstate(std::ios_base::failbit);
        return input;
    }

    // success!
    loc.row = row;
    loc.col = col;
    return input;
}

GridLocationRange::GridLocationRange(int startRow, int startCol, int endRow, int endCol, bool isRowMajor)
        : _start(startRow, startCol),
          _end(endRow, endCol),
          _isRowMajor(isRowMajor) {
    // empty
}

GridLocationRange::GridLocationRange(const GridLocation& startLoc, const GridLocation& endLoc, bool isRowMajor)
        : _start(startLoc),
          _end(endLoc),
          _isRowMajor(isRowMajor) {
    // empty
}

GridLocationRange::GridLocationRangeIterator GridLocationRange::begin() const {
    return GridLocationRangeIterator(this, /* end */ false);
}

bool GridLocationRange::contains(const GridLocation& loc) const {
    return _start <= loc && loc <= _end;
}

GridLocationRange::GridLocationRangeIterator GridLocationRange::end() const {
    return GridLocationRangeIterator(this, /* end */ true);
}

int GridLocationRange::endCol() const {
    return _end.col;
}

const GridLocation& GridLocationRange::endLocation() const {
    return _end;
}

int GridLocationRange::endRow() const {
    return _end.row;
}

bool GridLocationRange::isEmpty() const {
    return _start > _end;
}

bool GridLocationRange::isRowMajor() const {
    return _isRowMajor;
}

int GridLocationRange::startCol() const {
    return _start.col;
}

const GridLocation& GridLocationRange::startLocation() const {
    return _start;
}

int GridLocationRange::startRow() const {
    return _start.row;
}

std::string GridLocationRange::toString() const {
    std::ostringstream out;
    out << *this;
    return out.str();
}

std::ostream& operator <<(std::ostream& out, const GridLocationRange& range) {
    return out << range.startLocation() << " .. " << range.endLocation();
}

/////////////////////// END code extracted from StanfordCPPLib/collections/gridlocation.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/io/base64.cpp ///////////////////////
/*
 * File: base64.cpp
 * ----------------
 * This file defines a set of functions for encoding and decoding binary data
 * in the base64 format, as declared in base64.h.  See:
 * http://en.wikipedia.org/wiki/Base64
 *
 * @author Marty Stepp, based upon open-source Apache Base64 en/decoder
 * @version 2017/10/18
 * - fixed compiler warnings
 * @version 2014/10/08
 * - removed 'using namespace' statement
 * 2014/08/14
 * - Fixed bug with variables declared with deprecated 'register' keyword.
 * @since 2014/08/03
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE
#include <cstring>
#include <sstream>

/* aaaack but it's fast and const should make it shared text page. */
static const unsigned char pr2six[256] = {
    /* ASCII table */
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 62, 64, 64, 64, 63,
    52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 64, 64, 64, 64, 64, 64,
    64,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
    15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 64, 64, 64, 64, 64,
    64, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
    41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64
};

int Base64decode_len(const char *bufcoded) {
    int nbytesdecoded;
    const unsigned char *bufin;
    int nprbytes;

    bufin = (const unsigned char *) bufcoded;
    while (pr2six[*(bufin++)] <= 63);

    nprbytes = (bufin - (const unsigned char *) bufcoded) - 1;
    nbytesdecoded = ((nprbytes + 3) / 4) * 3;

    return nbytesdecoded + 1;
}

int Base64decode(char *bufplain, const char *bufcoded) {
    int nbytesdecoded;
    const unsigned char *bufin;
    unsigned char *bufout;
    int nprbytes;

    bufin = (const unsigned char *) bufcoded;
    while (pr2six[*(bufin++)] <= 63);
    nprbytes = (bufin - (const unsigned char *) bufcoded) - 1;
    nbytesdecoded = ((nprbytes + 3) / 4) * 3;

    bufout = (unsigned char *) bufplain;
    bufin = (const unsigned char *) bufcoded;

    while (nprbytes > 4) {
        *(bufout++) =
                (unsigned char) (pr2six[*bufin] << 2 | pr2six[bufin[1]] >> 4);
        *(bufout++) =
                (unsigned char) (pr2six[bufin[1]] << 4 | pr2six[bufin[2]] >> 2);
        *(bufout++) =
                (unsigned char) (pr2six[bufin[2]] << 6 | pr2six[bufin[3]]);
        bufin += 4;
        nprbytes -= 4;
    }

    /* Note: (nprbytes == 1) would be an error, so just ingore that case */
    if (nprbytes > 1) {
        *(bufout++) =
                (unsigned char) (pr2six[*bufin] << 2 | pr2six[bufin[1]] >> 4);
    }
    if (nprbytes > 2) {
        *(bufout++) =
                (unsigned char) (pr2six[bufin[1]] << 4 | pr2six[bufin[2]] >> 2);
    }
    if (nprbytes > 3) {
        *(bufout++) =
                (unsigned char) (pr2six[bufin[2]] << 6 | pr2six[bufin[3]]);
    }

    *(bufout++) = '\0';
    nbytesdecoded -= (4 - nprbytes) & 3;
    return nbytesdecoded;
}

static const char basis_64[] =
        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

int Base64encode_len(int len) {
    return ((len + 2) / 3 * 4) + 1;
}

int Base64encode(char *encoded, const char *string, int len) {
    int i;
    char *p;

    p = encoded;
    for (i = 0; i < len - 2; i += 3) {
        *p++ = basis_64[(string[i] >> 2) & 0x3F];
        *p++ = basis_64[((string[i] & 0x3) << 4) | ((string[i + 1] & 0xF0) >> 4)];
        *p++ = basis_64[((string[i + 1] & 0xF) << 2) | ((string[i + 2] & 0xC0) >> 6)];
        *p++ = basis_64[string[i + 2] & 0x3F];
    }
    if (i < len) {
        *p++ = basis_64[(string[i] >> 2) & 0x3F];
        if (i == (len - 1)) {
            *p++ = basis_64[((string[i] & 0x3) << 4)];
            *p++ = '=';
        }
        else {
            *p++ = basis_64[((string[i] & 0x3) << 4) | ((string[i + 1] & 0xF0) >> 4)];
            *p++ = basis_64[((string[i + 1] & 0xF) << 2)];
        }
        *p++ = '=';
    }

    *p++ = '\0';
    return p - encoded;
}

namespace Base64 {
std::string encode(const std::string& s) {
    // make C char* buffer to store the encoded output (for compatibility)
    int len = Base64encode_len(s.length());
    char* buf = (char*) malloc(len);
    memset(buf, 0, len);
    Base64encode(buf, s.c_str(), s.length());
    
    // convert back into a C++ string, and return it
    // (unlike below in decode(), I can just directly construct the C++
    // string from the C one, because the Base64-encoded C string will
    // not contain any intermediate null bytes by definition)
    std::string result(buf);
    free(buf);
    return result;
}

std::string decode(const std::string& s) {
    // convert into C string and decode into that char* buffer
    const char* cstr = s.c_str();
    int len = Base64decode_len(cstr);
    char* buf = (char*) malloc(len);
    memset(buf, 0, len);
    Base64decode(buf, cstr);
    
    // read bytes from that buffer into a C++ string
    // (cannot just construct/assign C++ string from C char* buffer,
    // because that will terminate the string at the first null \0 byte)
    std::ostringstream out;
    for (int i = 0; i < len; i++) {
        out << buf[i];
    }
    std::string result = out.str();
    
    free(buf);
    return result;
}

} // namespace Base64

/////////////////////// END code extracted from StanfordCPPLib/io/base64.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/io/bitstream.cpp ///////////////////////
/*
 * File: bitstream.cpp
 * -------------------
 * This file contains the implementation of ibitstream and obitstream classes.
 * These classes are patterned after (and, in fact, inherit from) the standard
 * ifstream and ofstream classes.  Please see bitstream.h for information about
 * how a client properly uses these classes.
 *
 * @author Keith Schwarz, Eric Roberts, Marty Stepp
 * @version 2019/04/20
 * - added toPrintable(string)
 * @version 2016/11/12
 * - made toPrintable non-static and visible
 * @version 2014/10/08
 * - removed 'using namespace' statement
 * 2014/01/23
 * - added slightly more descriptive error messages e.g. in writeBit
 * - whitespace reformatting
 * Previously last modified on Mon May 21 19:50:00 PST 2012 by Keith Schwarz
 */

#define INTERNAL_INCLUDE 1

#include <iostream>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

static const int NUM_BITS_IN_BYTE = 8;

inline int GetNthBit(int n, int fromByte) {
    return ((fromByte & (1 << n)) != 0);
}

inline void SetNthBit(int n, int & inByte) {
    inByte |= (1 << n);
}

std::string toPrintable(int ch) {
    if (ch == '\n') {
        return "'\\n'";
    } else if (ch == '\t') {
        return "'\\t'";
    } else if (ch == '\r') {
        return "'\\r'";
    } else if (ch == '\f') {
        return "'\\f'";
    } else if (ch == '\b') {
        return "'\\b'";
    } else if (ch == '\0') {
        return "'\\0'";
    } else if (ch == ' ') {
        return "' '";
    } else if (ch == (int) PSEUDO_EOF) {
        return "EOF";
    } else if (ch == (int) NOT_A_CHAR) {
        return "NONE";
    } else if (!isgraph(ch)) {
        return "???";
    } else {
        return std::string("'") + (char) ch + std::string("'");
    }
}

std::string toPrintable(const std::string& s) {
    std::ostringstream out;
    for (char ch : s) {
        if (ch == '\n') {
            out << "\\n";
        } else if (ch == '\t') {
            out << "\\t";
        } else if (ch == '\r') {
            out << "\\r";
        } else if (ch == '\f') {
            out << "\\f";
        } else if (ch == '\b') {
            out << "\\b";
        } else if (ch == '\0') {
            out << "\\0";
        } else if (ch == ' ') {
            out << ' ';
        } else if (isgraph(ch)) {
            out << ch;
        } else {
            out << '\\';
            out << (static_cast<int>(ch & 0xff));
        }
    }
    return out.str();
}

/* Constructor ibitstream::ibitstream
 * ----------------------------------
 * Each ibitstream tracks 3 integers as private data.
 * "lastTell" is streampos of the last byte that was read (this is used
 * to detect when other non-readBit activity has changed the tell)
 * "curByte" contains contents of byte currently being read
 * "pos" is the bit position within curByte that is next to read
 * We set initial state for lastTell and curByte to 0, then pos is
 * set at 8 so that next readBit will trigger a fresh read.
 */
ibitstream::ibitstream() : std::istream(nullptr), lastTell(0), curByte(0), pos(NUM_BITS_IN_BYTE) {
    this->fake = false;
}

/* Member function ibitstream::readBit
 * -----------------------------------
 * If bits remain in curByte, retrieve next and increment pos
 * Else if end of curByte (or some other read happened), then read next byte
 * and start reading from bit position 0 of that byte.
 * If read byte from file at EOF, return EOF.
 */
int ibitstream::readBit() {
    if (!is_open()) {
        error("ibitstream::readBit: Cannot read a bit from a stream that is not open.");
    }

    if (this->fake) {
        int bit = get();
        if (bit == 0 || bit == '0') {
            return 0;
        } else {
            return 1;
        }
    } else {
        // if just finished bits from curByte or if data read from stream after last readBit()
        if (lastTell != tellg() || pos == NUM_BITS_IN_BYTE) {
            if ((curByte = get()) == EOF) {
                // read next single byte from file
                return EOF;
            }
            pos = 0; // start reading from first bit of new byte
            lastTell = tellg();
        }
        int result = GetNthBit(pos, curByte);
        pos++;   // advance bit position for next call to readBit
        return result;
    }
}

/* Member function ibitstream::rewind
 * ----------------------------------
 * Simply seeks back to beginning of file, so reading begins again
 * from start.
 */
void ibitstream::rewind() {
    if (!is_open()) {
        error("ibitstream::rewind: Cannot rewind stream that is not open.");
    }
    clear();
    seekg(0, std::ios::beg);
}

void ibitstream::setFake(bool fake) {
    this->fake = fake;
}

/* Member function ibitstream::size
 * --------------------------------
 * Seek to file end and use tell to retrieve position.
 * In order to not disrupt reading, we also record cur streampos and
 * re-seek to there before returning.
 */
long ibitstream::size() {
    if (!is_open()) {
        error("ibitstream::size: Cannot get size of stream which is not open.");
    }
    clear();                    // clear any error state
    streampos cur = tellg();    // save current streampos
    seekg(0, std::ios::end);    // seek to end
    streampos end = tellg();    // get offset
    seekg(cur);                 // seek back to original pos
    return long(end);
}

/* Member function ibitstream::is_open
 * -----------------------------------
 * Default implementation of is_open has the stream always
 * open.  Subclasses can customize this if they'd like.
 */
bool ibitstream::is_open() {
    return true;
}

/* Constructor obitstream::obitstream
 * ----------------------------------
 * Each obitstream tracks 3 integers as private data.
 * "lastTell" is streampos of the last byte that was written (this is used
 * to detect when other non-writeBit activity has changed the tell)
 * "curByte" contains contents of byte currently being written
 * "pos" is the bit position within curByte that is next to write
 * We set initial state for lastTell and curByte to 0, then pos is
 * set at 8 so that next writeBit will start a new byte.
 */
obitstream::obitstream() : std::ostream(nullptr), lastTell(0), curByte(0), pos(NUM_BITS_IN_BYTE) {
    this->fake = false;
}

/* Member function obitstream::writeBit
 * ------------------------------------
 * If bits remain to be written in curByte, add bit into byte and increment pos
 * Else if end of curByte (or some other write happened), then start a fresh
 * byte at position 0.
 * We write the byte out for each bit (backing up to overwrite as needed), rather
 * than waiting for 8 bits.  This is because the client might make
 * 3 writeBit calls and then start using << so we can't wait til full-byte
 * boundary to flush any partial-byte bits.
 */
void obitstream::writeBit(int bit) {
    if (bit != 0 && bit != 1) {
        error(std::string("obitstream::writeBit: must pass an integer argument of 0 or 1. You passed the integer ")
              + toPrintable(bit) + " (" + std::to_string(bit) + ").");
    }
    if (!is_open()) {
        error("obitstream::writeBit: stream is not open");
    }

    if (this->fake) {
        put(bit == 1 ? '1' : '0');
    } else {
        // if just filled curByte or if data written to stream after last writeBit()
        if (lastTell != tellp() || pos == NUM_BITS_IN_BYTE) {
            curByte = 0;   // zero out byte for next writes
            pos = 0;       // start writing to first bit of new byte
        }

        if (bit) {
            // only need to change if bit needs to be 1 (byte starts already zeroed)
            SetNthBit(pos, curByte);
        }

        if (pos == 0 || bit) {   // only write if first bit in byte or changing 0 to 1
            if (pos != 0) {
                seekp(-1, std::ios::cur);   // back up to overwite if pos > 0
            }
            put(curByte);
        }

        pos++; // advance to next bit position for next write
        lastTell = tellp();
    }
}

void obitstream::setFake(bool fake) {
    this->fake = fake;
}

/* Member function obitstream::size
 * --------------------------------
 * Seek to file end and use tell to retrieve position.
 * In order to not disrupt writing, we also record cur streampos and
 * re-seek to there before returning.
 */
long obitstream::size() {
    if (!is_open()) {
        error("obitstream::size: stream is not open");
    }
    clear();                    // clear any error state
    streampos cur = tellp();    // save current streampos
    seekp(0, std::ios::end);    // seek to end
    streampos end = tellp();    // get offset
    seekp(cur);                 // seek back to original pos
    return long(end);
}

/* Member function obitstream::is_open
 * -----------------------------------
 * Default implementation of is_open has the stream always
 * open.  Subclasses can customize this if they'd like.
 */
bool obitstream::is_open() {
    return true;
}

/* Constructor ifbitstream::ifbitstream
 * ------------------------------------
 * Wires up the stream class so that it knows to read data
 * from disk.
 */
ifbitstream::ifbitstream() {
    init(&fb);
}

/* Constructor ifbitstream::ifbitstream
 * ------------------------------------
 * Wires up the stream class so that it knows to read data
 * from disk, then opens the given file.
 */
ifbitstream::ifbitstream(const char* filename) {
    init(&fb);
    open(filename);
}
ifbitstream::ifbitstream(const std::string& filename) {
    init(&fb);
    open(filename);
}

/* Member function ifbitstream::open
 * ---------------------------------
 * Attempts to open the specified file, failing if unable
 * to do so.
 */
void ifbitstream::open(const char* filename) {
    if (!fb.open(filename, std::ios::in | std::ios::binary)) {
        setstate(std::ios::failbit);
    }
}

void ifbitstream::open(const std::string& filename) {
    open(filename.c_str());
}

/* Member function ifbitstream::is_open
 * ------------------------------------
 * Determines whether the file stream is open.
 */
bool ifbitstream::is_open() {
    return fb.is_open();
}

/* Member function ifbitstream::close
 * ----------------------------------
 * Closes the file stream, if one is open.
 */
void ifbitstream::close() {
    if (!fb.close()) {
        setstate(std::ios::failbit);
    }
}

/* Constructor ofbitstream::ofbitstream
 * ------------------------------------
 * Wires up the stream class so that it knows to write data
 * to disk.
 */
ofbitstream::ofbitstream() {
    init(&fb);
}

/* Constructor ofbitstream::ofbitstream
 * ------------------------------------
 * Wires up the stream class so that it knows to write data
 * to disk, then opens the given file.
 */
ofbitstream::ofbitstream(const char* filename) {
    init(&fb);
    open(filename);
}

ofbitstream::ofbitstream(const std::string& filename) {
    init(&fb);
    open(filename);
}

/* Member function ofbitstream::open
 * ---------------------------------
 * Attempts to open the specified file, failing if unable
 * to do so.
 */
void ofbitstream::open(const char* filename) {
    // Confirm we aren't about to do something that could potentially be a
    // Very Bad Idea.
    if (endsWith(filename, ".cpp") || endsWith(filename, ".h") ||
            endsWith(filename, ".hh") || endsWith(filename, ".cc")) {
        setstate(std::ios::failbit);
        error(std::string("ofbitstream::open: It is potentially dangerous to write to file ")
              + filename + ", because that might be your own source code.  "
              + "We are explicitly disallowing this operation.  Please choose a "
              + "different filename.");
    } else {
        if (!fb.open(filename, std::ios::out | std::ios::binary)) {
            setstate(std::ios::failbit);
        }
    }
}
void ofbitstream::open(const std::string& filename) {
    open(filename.c_str());
}

/* Member function ofbitstream::is_open
 * ------------------------------------
 * Determines whether the file stream is open.
 */
bool ofbitstream::is_open() {
    return fb.is_open();
}

/* Member function ofbitstream::close
 * ----------------------------------
 * Closes the given file.
 */
void ofbitstream::close() {
    if (!fb.close()) {
        setstate(std::ios::failbit);
    }
}

/* Constructor istringbitstream::istringbitstream
 * ----------------------------------------------
 * Sets the stream to use the string buffer, then sets
 * the initial string to the specified value.
 */
istringbitstream::istringbitstream(const std::string& s) {
    init(&sb);
    sb.str(s);
}

/* Member function istringbitstream::str
 * -------------------------------------
 * Sets the underlying string in the buffer to the
 * specified string.
 */
void istringbitstream::str(const std::string& s) {
    sb.str(s);
}

/* Member function ostringbitstream::ostringbitstream
 * --------------------------------------------------
 * Sets the stream to use the string buffer.
 */
ostringbitstream::ostringbitstream() {
    init(&sb);
}

/* Member function ostringbitstream::str
 * -------------------------------------
 * Retrives the underlying string data.
 */
std::string ostringbitstream::str() {
    return sb.str();
}

/////////////////////// END code extracted from StanfordCPPLib/io/bitstream.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/io/filelib.cpp ///////////////////////
/*
 * File: filelib.cpp
 * -----------------
 * This file implements the filelib.h interface.
 * Platform-dependent functions are handled through filelib_* functions
 * defined in filelibunix.cpp and filelibwindows.cpp.
 * 
 * @version 2016/11/20
 * - small bug fix in readEntireStream method (failed for non-text files)
 * @version 2016/11/12
 * - added fileSize, readEntireStream
 * @version 2016/08/12
 * - added second overload of openFileDialog that accepts path parameter
 * @version 2015/07/05
 * - removed static global Platform variable, replaced by getPlatform as needed
 * - moved appendSpace function to simpio
 * @version 2015/04/12
 * - added promptUserForFile overload without stream parameter
 * @version 2014/10/19
 * - alphabetized function declarations
 * - converted many funcs to take const string& rather than string for efficiency
 * - added listDirectory overload that returns a Vector
 * @version 2014/10/08
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#include <algorithm>
#include <cctype>
#include <cstdio>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

/* Prototypes */

static void splitPath(const std::string& path, Vector<std::string> list);
static bool recursiveMatch(const std::string& str, int sx, const std::string& pattern, int px);

/* Implementations */

void createDirectory(const std::string& path) {
    return platform::filelib_createDirectory(expandPathname(path));
}

void createDirectoryPath(const std::string& path) {
    size_t cp = 0;
    if (path == "") return;
    std::string expandedPath = expandPathname(path);
    char sep = getDirectoryPathSeparator()[0];
    if (expandedPath.substr(1, 2) == ":\\") { // Windows drive letter followed by ':\'
        cp = 2;
    }
    while ((cp = expandedPath.find(sep, cp + 1)) != std::string::npos) {
       createDirectory(expandedPath.substr(0, cp));
    }
    createDirectory(expandedPath);
}

std::string defaultExtension(const std::string& filename, const std::string& ext) {
    std::string extCopy = ext;
    bool force = (extCopy[0] == '*');
    if (force) extCopy = extCopy.substr(1);
    int dot = -1;
    int len = filename.length();
    for (int i = 0; i < len; i++) {
        char ch = filename[i];
        if (ch == '.') dot = i;
        if (ch == '/' || ch == '\\') dot = -1;
    }
    if (dot == -1) {
        force = true;
        dot = len;
    }
    if (force) {
        return filename.substr(0, dot) + extCopy;
    } else {
        return filename;
    }
}

void deleteFile(const std::string& filename) {
    platform::filelib_deleteFile(expandPathname(filename));
}

std::string expandPathname(const std::string& filename) {
    return platform::filelib_expandPathname(filename);
}

bool fileExists(const std::string& filename) {
    return platform::filelib_fileExists(filename);
}

int fileSize(const std::string& filename) {
    std::ifstream input;
    input.open(filename.c_str(), std::ifstream::binary);
    if (input.fail()) {
        return -1;
    } else {
        input.seekg(0, std::ifstream::end);
        return (int) input.tellg();
    }
}

std::string findOnPath(const std::string& path, const std::string& filename) {
    std::ifstream stream;
    std::string result = openOnPath(stream, path, filename);
    if (result != "") stream.close();
    return result;
}

std::string getAbsolutePath(const std::string& path) {
    return platform::filelib_getAbsolutePath(path);
}

std::string getCurrentDirectory() {
    return platform::filelib_getCurrentDirectory();
}

std::string getDirectoryPathSeparator() {
    return platform::filelib_getDirectoryPathSeparator();
}

std::string getExtension(const std::string& filename) {
    int dot = -1;
    int len = filename.length();
    for (int i = 0; i < len; i++) {
        char ch = filename[i];
        if (ch == '.') dot = i;
        if (ch == '/' || ch == '\\') dot = -1;
    }
    if (dot == -1) {
        return "";
    } else {
        return filename.substr(dot);
    }
}

std::string getHead(const std::string& filename) {
    size_t slash = std::string::npos;
    size_t len = filename.length();
    for (size_t i = 0; i < len; i++) {
        char ch = filename[i];
        if (ch == '/' || ch == '\\') slash = i;
    }
    if (slash == std::string::npos) {
        return "";
    } else if (slash == 0) {
        return "/";
    } else {
        return filename.substr(0, slash);
    }
}

std::string getRoot(const std::string& filename) {
    int dot = -1;
    int len = filename.length();
    for (int i = 0; i < len; i++) {
        char ch = filename[i];
        if (ch == '.') dot = i;
        if (ch == '/' || ch == '\\') dot = -1;
    }
    if (dot == -1) {
        return filename;
    } else {
        return filename.substr(0, dot);
    }
}

std::string getSearchPathSeparator() {
    return platform::filelib_getSearchPathSeparator();
}

std::string getTail(const std::string& filename) {
    size_t slash = std::string::npos;
    size_t len = filename.length();
    for (size_t i = 0; i < len; i++) {
        char ch = filename[i];
        if (ch == '/' || ch == '\\') slash = i;
    }
    if (slash == std::string::npos) {
        return filename;
    } else {
        return filename.substr(slash + 1);
    }
}

std::string getTempDirectory() {
    return platform::filelib_getTempDirectory();
}

bool isDirectory(const std::string& filename) {
    return platform::filelib_isDirectory(expandPathname(filename));
}

bool isFile(const std::string& filename) {
    return platform::filelib_isFile(expandPathname(filename));
}

bool isSymbolicLink(const std::string& filename) {
    return platform::filelib_isSymbolicLink(filename);
}

void listDirectory(const std::string& path, Vector<std::string>& list) {
    list.clear();
    return platform::filelib_listDirectory(expandPathname(path), list);
}

Vector<std::string> listDirectory(const std::string& path) {
    Vector<std::string> vec;
    listDirectory(path, vec);
    return vec;
}

bool matchFilenamePattern(const std::string& filename, const std::string& pattern) {
    return recursiveMatch(filename, 0, pattern, 0);
}

bool openFile(std::ifstream& stream, const std::string& filename) {
    stream.clear();
    stream.open(expandPathname(filename).c_str());
    return !stream.fail();
}

bool openFile(std::ofstream& stream, const std::string& filename) {
    stream.clear();
    stream.open(expandPathname(filename).c_str());
    return !stream.fail();
}

std::string openFileDialog(std::ifstream& stream) {
    return openFileDialog(stream, "Open File", "");
}

std::string openFileDialog(std::ifstream& stream,
                           const std::string& title) {
    return openFileDialog(stream, title, "");
}

std::string openFileDialog(std::ifstream& stream,
                           const std::string& title,
                           const std::string& path) {
    std::string filename = platform::file_openFileDialog(title, "load", path);
    if (filename == "") return "";
    stream.open(filename.c_str());
    return (stream.fail()) ? "" : filename;
}

std::string openFileDialog(const std::string& title,
                           const std::string& path) {
    std::string filename = platform::file_openFileDialog(title, "load", path);
    if (filename == "") return "";
    return (fileExists(filename)) ? filename : "";
}

std::string openFileDialog(std::ofstream& stream) {
    return openFileDialog(stream, "Open File", "");
}

std::string openFileDialog(std::ofstream& stream,
                           const std::string& title) {
    return openFileDialog(stream, title, "");
}

std::string openFileDialog(std::ofstream& stream,
                           const std::string& title,
                           const std::string& path) {
    std::string filename = platform::file_openFileDialog(title, "save", path);
    if (filename == "") return "";
    stream.open(filename.c_str());
    return (stream.fail()) ? "" : filename;
}

std::string openOnPath(std::ifstream& stream,
                       const std::string& path,
                       const std::string& filename) {
    Vector<std::string> paths;
    splitPath(path, paths);
    for (std::string dir : paths) {
        std::string pathname = dir + "/" + filename;
        if (openFile(stream, pathname)) return pathname;
    }
    return "";
}

std::string openOnPath(std::ofstream& stream,
                       const std::string& path,
                       const std::string& filename) {
    Vector<std::string> paths;
    splitPath(path, paths);
    for (std::string dir : paths) {
        std::string pathname = dir + "/" + filename;
        if (openFile(stream, pathname)) return pathname;
    }
    return "";
}

std::string promptUserForFile(std::ifstream& stream,
                              const std::string& prompt,
                              const std::string& reprompt) {
    std::string promptCopy = prompt;
    std::string repromptCopy = reprompt;
    if (reprompt == "") {
        repromptCopy = "Unable to open that file.  Try again.";
    }
    appendSpace(promptCopy);
    while (true) {
        std::cout << promptCopy;
        std::string filename;
        getline(std::cin, filename);
        if (!filename.empty()) {
            openFile(stream, filename);
            if (!stream.fail()) return filename;
            stream.clear();
        }
        std::cout << repromptCopy << std::endl;
        if (promptCopy == "") promptCopy = "Input file: ";
    }
}

std::string promptUserForFile(std::ofstream& stream,
                              const std::string& prompt,
                              const std::string& reprompt) {
    std::string promptCopy = prompt;
    std::string repromptCopy = reprompt;
    if (reprompt == "") {
        repromptCopy = "Unable to open that file.  Try again.";
    }
    appendSpace(promptCopy);
    while (true) {
        std::cout << promptCopy;
        std::string filename;
        getline(std::cin, filename);
        if (!filename.empty()) {
            openFile(stream, filename);
            if (!stream.fail()) return filename;
            stream.clear();
        }
        std::cout << repromptCopy << std::endl;
        if (promptCopy == "") promptCopy = "Output file: ";
    }
}

std::string promptUserForFile(const std::string& prompt,
                              const std::string& reprompt) {
    std::string promptCopy = prompt;
    std::string repromptCopy = reprompt;
    if (reprompt == "") {
        repromptCopy = "Unable to open that file.  Try again.";
    }
    appendSpace(promptCopy);
    while (true) {
        std::cout << promptCopy;
        std::string filename;
        getline(std::cin, filename);
        if (!filename.empty()) {
            std::ifstream stream;
            openFile(stream, filename);
            if (!stream.fail()) {
                stream.close();
                return filename;
            }
        }
        std::cout << repromptCopy << std::endl;
        if (promptCopy == "") promptCopy = "Input file: ";
    }
}

void readEntireFile(std::istream& is, Vector<std::string>& lines) {
    lines.clear();
    while (true) {
        std::string line;
        getline(is, line);
        if (is.fail()) break;
        lines.add(line);
    }
}

std::string readEntireFile(const std::string& filename) {
    std::string out;
    if (readEntireFile(filename, out)) {
        return out;
    } else {
        error(std::string("input file not found or cannot be opened: ") + filename);
        return "";
    }
}

bool readEntireFile(const std::string& filename, std::string& out) {
    std::ifstream input;
    input.open(filename.c_str());
    if (input.fail()) {
        return false;
    }
    readEntireStream(input, out);
    input.close();
    return true;
}

std::string readEntireStream(std::istream& input) {
    std::string out;
    readEntireStream(input, out);
    return out;
}

void readEntireStream(std::istream& input, std::string& out) {
    std::ostringstream output;
    while (true) {
        int ch = input.get();
        if (input.fail()) {
            break;
        }
        output.put(ch);
    }
    out = output.str();
}

void renameFile(const std::string& oldname, const std::string& newname) {
    std::string oldExpand = expandPathname(oldname);
    std::string newExpand = expandPathname(newname);
    rename(oldExpand.c_str(), newExpand.c_str());
}

void rewindStream(std::istream& input) {
    input.clear();                  // removes any current eof/failure flags
    input.seekg(0, std::ios::beg);  // tells the stream to seek back to the beginning
}

void setCurrentDirectory(const std::string& path) {
    return platform::filelib_setCurrentDirectory(path);
}

bool writeEntireFile(const std::string& filename,
                     const std::string& text,
                     bool append) {
    std::ofstream output;
    if (append) {
        output.open(filename.c_str(), std::ios_base::out | std::ios_base::app);
    } else {
        output.open(filename.c_str());
    }
    if (output.fail()) {
        return false;
    }
    output << text;
    output.close();
    return !output.fail();
}

/* Private functions */

static void splitPath(const std::string& path, Vector<std::string> list) {
    char sep = (path.find(';') == std::string::npos) ? ':' : ';';
    std::string pathCopy = path + sep;
    size_t start = 0;
    while (true) {
        size_t finish = pathCopy.find(sep, start);
        if (finish == std::string::npos) break;
        if (finish > start + 1) {
            list.add(pathCopy.substr(start, finish - start - 1));
        }
        start = finish + 1;
    }
}

static bool recursiveMatch(const std::string& str, int sx, const std::string& pattern, int px) {
    int slen = str.length();
    int plen = pattern.length();
    if (px == plen) return (sx == slen);
    char pch = pattern[px];
    if (pch == '*') {
        for (int i = sx; i <= slen; i++) {
            if (recursiveMatch(str, i, pattern, px + 1)) return true;
        }
        return false;
    }
    if (sx == slen) return false;
    char sch = str[sx];
    if (pch == '[') {
        bool match = false;
        bool invert = false;
        px++;
        if (px == plen) {
            error("matchFilenamePattern: missing ]");
        }
        if (pattern[px] == '^') {
            px++;
            invert = true;
        }
        while (px < plen && pattern[px] != ']') {
            if (px + 2 < plen && pattern[px + 1] == '-') {
                match |= (sch >= pattern[px] && sch <= pattern[px + 2]);
                px += 3;
            } else {
                match |= (sch == pattern[px]);
                px++;
            }
        }
        if (px == plen) {
            error("matchFilenamePattern: missing ]");
        }
        if (match == invert) return false;
    } else if (pch != '?') {
        if (pch != sch) return false;
    }
    return recursiveMatch(str, sx + 1, pattern, px + 1);
}

/////////////////////// END code extracted from StanfordCPPLib/io/filelib.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/private/filelibunix.cpp ///////////////////////
/*
 * File: filelibunix.cpp
 * ---------------------
 * This file contains Unix implementations of filelib.h primitives.
 * This code used to live in platform.cpp before the Java back-end was retired.
 *
 * @version 2018/10/23
 * - added getAbsolutePath
 */

#define INTERNAL_INCLUDE 1


// define all of the following only on non-Windows OS
// (see filelibwindows.cpp for Windows versions)
#ifndef _WIN32
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/resource.h>
#include <dirent.h>
#include <errno.h>
#include <pwd.h>
#include <stdint.h>
#include <unistd.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <ios>
#include <string>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

namespace platform {

void filelib_createDirectory(const std::string& path) {
    std::string pathStr = path;
    if (endsWith(path, "/")) {
        pathStr = path.substr(0, path.length() - 1);
    }
    if (mkdir(pathStr.c_str(), 0777) != 0) {
        if (errno == EEXIST && filelib_isDirectory(pathStr)) {
            return;
        }
        std::string msg = "createDirectory: ";
        std::string err = std::string(strerror(errno));
        error(msg + err);
    }
}

void filelib_deleteFile(const std::string& path) {
    remove(path.c_str());
}

std::string filelib_expandPathname(const std::string& filename) {
    if (filename == "") {
        return "";
    }
    int len = filename.length();
    std::string expanded = filename;
    if (expanded[0] == '~') {
        int spos = 1;
        while (spos < len && expanded[spos] != '\\' && expanded[spos] != '/') {
            spos++;
        }
        char *homedir = nullptr;
        if (spos == 1) {
            homedir = getenv("HOME");
            if (!homedir) {
                homedir = getpwuid(getuid())->pw_dir;
            }
        } else {
            struct passwd *pw = getpwnam(expanded.substr(1, spos - 1).c_str());
            if (!pw) {
                error("expandPathname: No such user");
            } else {
                homedir = pw->pw_dir;
            }
        }
        expanded = std::string(homedir) + expanded.substr(spos);
        len = expanded.length();
    }
    for (int i = 0; i < len; i++) {
        if (expanded[i] == '\\') {
            expanded[i] = '/';
        }
    }
    return expanded;
}

bool filelib_fileExists(const std::string& filename) {
    struct stat fileInfo;
    return stat(filename.c_str(), &fileInfo) == 0;
}

std::string filelib_getAbsolutePath(const std::string& path) {
    char realpathOut[4096];
    realpath(path.c_str(), realpathOut);
    std::string absPath(realpathOut);
    return absPath;
}

std::string filelib_getCurrentDirectory() {
    char currentDirBuf[4096] = {'\0'};
    char* cwd = getcwd(currentDirBuf, 4096 - 1);
    std::string result;
    if (cwd) {
        result = std::string(cwd);
    } else {
        error("getCurrentDirectory: " + std::string(strerror(errno)));
    }
    return result;
}

std::string filelib_getDirectoryPathSeparator() {
    return "/";
}

std::string filelib_getSearchPathSeparator() {
    return ":";
}

// http://stackoverflow.com/questions/8087805/
// how-to-get-system-or-user-temp-folder-in-unix-and-windows
std::string filelib_getTempDirectory() {
    char* dir = getenv("TMPDIR");
    if (!dir) dir = getenv("TMP");
    if (!dir) dir = getenv("TEMP");
    if (!dir) dir = getenv("TEMPDIR");
    if (!dir) return "/tmp";
    return dir;
}

bool filelib_isDirectory(const std::string& filename) {
    struct stat fileInfo;
    if (stat(filename.c_str(), &fileInfo) != 0) {
        return false;
    }
    return S_ISDIR(fileInfo.st_mode) != 0;
}

bool filelib_isFile(const std::string& filename) {
    struct stat fileInfo;
    if (stat(filename.c_str(), &fileInfo) != 0) {
        return false;
    }
    return S_ISREG(fileInfo.st_mode) != 0;
}

bool filelib_isSymbolicLink(const std::string& filename) {
    struct stat fileInfo;
    if (lstat(filename.c_str(), &fileInfo) != 0) {
        return false;
    }
    return S_ISLNK(fileInfo.st_mode) != 0;
}

void filelib_listDirectory(const std::string& path, Vector<std::string>& list) {
    DIR* dir = opendir(path.empty() ? "." : path.c_str());
    if (!dir) {
        error(std::string("listDirectory: Can't open \"") + path + "\"");
    }
    list.clear();
    while (true) {
        struct dirent* ep = readdir(dir);
        if (!ep) {
            break;
        }
        std::string name = std::string(ep->d_name);
        if (name != "." && name != "..") {
            list.push_back(name);
        }
    }
    closedir(dir);
    sort(list.begin(), list.end());
}

std::string file_openFileDialog(const std::string& /*title*/,
                                const std::string& /*mode*/,
                                const std::string& /*path*/) {
    // TODO
    return "";
}

void filelib_setCurrentDirectory(const std::string& path) {
    if (chdir(path.c_str()) != 0) {
        std::string msg = "setCurrentDirectory: ";
        std::string err = std::string(strerror(errno));
        error(msg + err);
    }
}

} // namespace platform

#endif // _WIN32

/////////////////////// END code extracted from StanfordCPPLib/private/filelibunix.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/io/simpio.cpp ///////////////////////
/*
 * File: simpio.cpp
 * ----------------
 * This file implements the simpio.h interface.
 * 
 * @version 2016/09/29
 * - added getDouble method
 * @version 2015/07/05
 * - increased visibility of appendSpace function used by various IO
 *   prompting functions (no longer static)
 * @version 2014/10/19
 * - alphabetized functions
 * - converted many funcs to take const string& rather than string for efficiency
 * @version 2014/10/08
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#include <cctype>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

STATIC_CONST_VARIABLE_DECLARE(std::string, GETCHAR_DEFAULT_PROMPT, "Enter a character: ")
STATIC_CONST_VARIABLE_DECLARE(std::string, GETCHAR_DEFAULT_REPROMPT, "You must type a single character. Try again.")
STATIC_CONST_VARIABLE_DECLARE(std::string, GETINTEGER_DEFAULT_PROMPT, "Enter an integer: ")
STATIC_CONST_VARIABLE_DECLARE(std::string, GETINTEGER_DEFAULT_REPROMPT, "Illegal integer format. Try again.")
STATIC_CONST_VARIABLE_DECLARE(std::string, GETREAL_DEFAULT_PROMPT, "Enter a number: ")
STATIC_CONST_VARIABLE_DECLARE(std::string, GETREAL_DEFAULT_REPROMPT, "Illegal numeric format. Try again.")
STATIC_CONST_VARIABLE_DECLARE(std::string, GETYESORNO_DEFAULT_PROMPT, "Try again: ")
STATIC_CONST_VARIABLE_DECLARE(std::string, GETYESORNO_DEFAULT_REPROMPT, "Please type a word that starts with 'Y' or 'N'.")

/*
 * Implementation notes: getChar, getDouble, 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.
 */

char getChar(const std::string& prompt,
             const std::string& reprompt) {
    std::string promptCopy = prompt;
    appendSpace(promptCopy);
    char value = '\0';
    while (true) {
        std::cout << promptCopy;
        std::string line;
        if (!getline(std::cin, line)) {
            error("getChar: End of input reached while waiting for character value.");
        }
        if (line.length() == 1) {
            value = line[0];
            break;
        }

        std::cout.flush();
        std::cerr << (reprompt.empty() ? STATIC_VARIABLE(GETCHAR_DEFAULT_REPROMPT) : reprompt) << std::endl;
        std::cerr.flush();
        if (promptCopy.empty()) {
            promptCopy = STATIC_VARIABLE(GETCHAR_DEFAULT_PROMPT);
        }
    }
    return value;
}

double getDouble(const std::string& prompt,
                 const std::string& reprompt) {
    return getReal(prompt, reprompt);
}

double getDoubleBetween(const std::string& prompt, double min, double max) {
    return getRealBetween(prompt, min, max);
}

int getInteger(const std::string& prompt,
               const std::string& reprompt) {
    std::string promptCopy = prompt;
    appendSpace(promptCopy);
    int value = 0;
    while (true) {
        std::cout << promptCopy;
        std::string line;
        if (!getline(std::cin, line)) {
            error("getInteger: End of input reached while waiting for integer value.");
        }
        trimInPlace(line);
        std::istringstream stream(line);
        stream >> value;
        if (!stream.fail() && stream.eof()) {
            break;
        }
        std::cout.flush();
        std::cerr << (reprompt.empty() ? STATIC_VARIABLE(GETINTEGER_DEFAULT_REPROMPT) : reprompt) << std::endl;
        std::cerr.flush();
        if (promptCopy.empty()) {
            promptCopy = STATIC_VARIABLE(GETINTEGER_DEFAULT_PROMPT);
        }
    }
    return value;
}

int getIntegerBetween(const std::string& prompt, int min, int max) {
    int value = 0;
    while (true) {
        value = getInteger(prompt);
        if (value < min || value > max) {
            std::cout.flush();
            std::cerr << "Please type a value between " << min
                      << " and " << max << "." << std::endl;
            std::cerr.flush();
        } else {
            break;
        }
    }
    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.
 */
std::string getLine(const std::string& prompt) {
    std::string line;
    getLine(prompt, line);
    return line;
}

void getLine(const std::string& prompt,
             std::string& out) {
    std::string promptCopy = prompt;
    appendSpace(promptCopy);
    std::cout << promptCopy;
    if (!getline(std::cin, out)) {
        error("getLine: End of input reached while waiting for line.");
    }
}

void getLine(std::istream& input,
             std::string& out) {
    if (!getline(input, out)) {
        error("getLine: End of input reached while waiting for line.");
    }
}

double getReal(const std::string& prompt,
               const std::string& reprompt) {
    std::string promptCopy = prompt;
    appendSpace(promptCopy);
    double value = 0.0;
    while (true) {
        std::cout << promptCopy;
        std::string line;
        if (!getline(std::cin, line)) {
            error("getReal: End of input reached while waiting for real value.");
        }
        trimInPlace(line);
        std::istringstream stream(line);
        stream >> value;
        if (!stream.fail() && stream.eof()) {
            break;
        }
        std::cout.flush();
        std::cerr << (reprompt.empty() ? STATIC_VARIABLE(GETREAL_DEFAULT_REPROMPT) : reprompt) << std::endl;
        std::cerr.flush();
        if (promptCopy.empty()) {
            promptCopy = STATIC_VARIABLE(GETREAL_DEFAULT_PROMPT);
        }
    }
    return value;
}

double getRealBetween(const std::string& prompt, double min, double max) {
    double value = 0;
    while (true) {
        value = getReal(prompt);
        if (value < min || value > max) {
            std::cout.flush();
            std::cerr << "Please type a value between " << min
                      << " and " << max << "." << std::endl;
            std::cerr.flush();
        } else {
            break;
        }
    }
    return value;
}

bool getYesOrNo(const std::string& prompt,
                const std::string& reprompt,
                const std::string& defaultValue) {
    std::string promptCopy = prompt;
    appendSpace(promptCopy);
    bool value = false;
    while (true) {
        std::cout << promptCopy;
        std::string line;
        if (!getline(std::cin, line)) {
            error("getYesOrNo: End of input reached while waiting for yes/no value.");
        }
        if (line.empty()) {
            line = defaultValue;
        }
        if ((int) line.length() > 0) {
            char first = tolower(line[0]);
            if (first == 'y') {
                value = true;
                break;
            } else if (first == 'n') {
                value = false;
                break;
            }
        }
        std::cout.flush();
        std::cerr << (reprompt.empty() ? STATIC_VARIABLE(GETYESORNO_DEFAULT_REPROMPT) : reprompt) << std::endl;
        std::cerr.flush();
        if (promptCopy.empty()) {
            promptCopy = STATIC_VARIABLE(GETYESORNO_DEFAULT_PROMPT);
        }
    }
    return value;
}

void appendSpace(std::string& prompt) {
    if (!prompt.empty() && !isspace(prompt[prompt.length() - 1])) {
        prompt += ' ';
    }
}

/////////////////////// END code extracted from StanfordCPPLib/io/simpio.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/io/tokenscanner.cpp ///////////////////////
/*
 * File: tokenscanner.cpp
 * ----------------------
 * Implementation for the TokenScanner class.
 * 
 * @version 2016/11/26
 * - added getInput method
 * - replaced occurrences of string with const string& for efficiency
 * - alphabetized method ordering
 * - added operator << for printing a scanner
 * @version 2014/10/08
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#include <cctype>
#include <iostream>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

TokenScanner::TokenScanner() {
    initScanner();
    setInput("");
}

TokenScanner::TokenScanner(std::istream& infile) {
    initScanner();
    setInput(infile);
}

TokenScanner::TokenScanner(const std::string& str) {
    initScanner();
    setInput(str);
}

TokenScanner::~TokenScanner() {
    if (stringInputFlag) {
        delete isp;
    }
}

void TokenScanner::addOperator(const std::string& op) {
    StringCell* cp = new StringCell;
    cp->str = op;
    cp->link = operators;
    operators = cp;
}

void TokenScanner::addWordCharacters(const std::string& str) {
    wordChars += str;
}

int TokenScanner::getChar() {
    return isp->get();
}

std::string TokenScanner::getInput() const {
    return buffer;
}

int TokenScanner::getPosition() const {
    if (!savedTokens) {
        return int(isp->tellg());
    } else {
        return int(isp->tellg()) - savedTokens->str.length();
    }
}

std::string TokenScanner::getStringValue(const std::string& token) const {
    std::string str = "";
    int start = 0;
    int finish = token.length();
    if (finish > 1 && (token[0] == '"' || token[0] == '\'')) {
        start = 1;
        finish--;
    }
    for (int i = start; i < finish; i++) {
        char ch = token[i];
        if (ch == '\\') {
            ch = token[++i];
            if (isdigit(ch) || ch == 'x') {
                int base = 8;
                if (ch == 'x') {
                    base = 16;
                    i++;
                }
                int result = 0;
                int digit = 0;
                while (i < finish) {
                    ch = token[i];
                    if (isdigit(ch)) {
                        digit = ch - '0';
                    } else if (isalpha(ch)) {
                        digit = toupper(ch) - 'A' + 10;
                    } else {
                        digit = base;
                    }
                    if (digit >= base) {
                        break;
                    }
                    result = base * result + digit;
                    i++;
                }
                ch = char(result);
                i--;
            } 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;
    }
    return str;
}

TokenScanner::TokenType TokenScanner::getTokenType(const std::string& token) const {
    if (token.empty()) {
        return TokenType(EOF);
    }

    char ch = token[0];
    if (isspace(ch)) {
        return SEPARATOR;
    } else if (ch == '"' || (ch == '\'' && token.length() > 1)) {
        return STRING;
    } else if (isdigit(ch)) {
        return NUMBER;
    } else if (isWordCharacter(ch)) {
        return WORD;
    } else {
        return OPERATOR;
    }
}

bool TokenScanner::hasMoreTokens() {
    std::string token = nextToken();
    saveToken(token);
    return !token.empty();
}

void TokenScanner::ignoreComments() {
    ignoreCommentsFlag = true;
}

void TokenScanner::ignoreWhitespace() {
    ignoreWhitespaceFlag = true;
}

bool TokenScanner::isWordCharacter(char ch) const {
    return isalnum(ch) || wordChars.find(ch) != std::string::npos;
}

std::string TokenScanner::nextToken() {
    if (savedTokens) {
        StringCell* cp = savedTokens;
        std::string token = cp->str;
        savedTokens = cp->link;
        delete cp;
        return token;
    }

    while (true) {
        if (ignoreWhitespaceFlag) {
            skipSpaces();
        }
        int ch = isp->get();
        if (ch == '/' && ignoreCommentsFlag) {
            ch = isp->get();
            if (ch == '/') {
                while (true) {
                    ch = isp->get();
                    if (ch == '\n' || ch == '\r' || ch == EOF) {
                        break;
                    }
                }
                continue;
            } else if (ch == '*') {
                int prev = EOF;
                while (true) {
                    ch = isp->get();
                    if (ch == EOF || (prev == '*' && ch == '/')) {
                        break;
                    }
                    prev = ch;
                }
                continue;
            }
            if (ch != EOF) {
                isp->unget();
            }
            ch = '/';
        }
        if (ch == EOF) {
            return "";
        }
        if ((ch == '"' || ch == '\'') && scanStringsFlag) {
            isp->unget();
            return scanString();
        }
        if (isdigit(ch) && scanNumbersFlag) {
            isp->unget();
            return scanNumber();
        }
        if (isWordCharacter(ch)) {
            isp->unget();
            return scanWord();
        }
        std::string op = std::string(1, ch);
        while (isOperatorPrefix(op)) {
            ch = isp->get();
            if (ch == EOF) {
                break;
            }
            op += ch;
        }
        while (op.length() > 1 && !isOperator(op)) {
            isp->unget();
            op.erase(op.length() - 1, 1);
        }
        return op;
    }
}

void TokenScanner::saveToken(const std::string& token) {
    StringCell* cp = new StringCell;
    cp->str = token;
    cp->link = savedTokens;
    savedTokens = cp;
}

void TokenScanner::scanNumbers() {
    scanNumbersFlag = true;
}

void TokenScanner::scanStrings() {
    scanStringsFlag = true;
}

void TokenScanner::setInput(std::istream& infile) {
    stringInputFlag = false;
    isp = &infile;
    savedTokens = nullptr;
}

void TokenScanner::setInput(const std::string& str) {
    stringInputFlag = true;
    buffer = str;
    isp = new std::istringstream(buffer);
    savedTokens = nullptr;
}

void TokenScanner::ungetChar(int) {
    isp->unget();
}

void TokenScanner::verifyToken(const std::string& expected) {
    std::string token = nextToken();
    if (token != expected) {
        std::string msg = "TokenScanner::verifyToken: Found \"" + token + "\""
                + " when expecting \"" + expected + "\"";
        if (!buffer.empty()) {
            msg += "\ninput = \"" + buffer + "\"";
        }
        error(msg);
    }
}

/* Private methods */

void TokenScanner::initScanner() {
    ignoreWhitespaceFlag = false;
    ignoreCommentsFlag = false;
    scanNumbersFlag = false;
    scanStringsFlag = false;
    operators = nullptr;
}

/*
 * Implementation notes: isOperator, isOperatorPrefix
 * --------------------------------------------------
 * These methods search the list of operators and return true if the
 * specified operator is either in the list or a prefix of an operator
 * in the list, respectively.  This code could be made considerably more
 * efficient by implementing operators as a trie.
 */
bool TokenScanner::isOperator(const std::string& op) {
    for (StringCell *cp = operators; cp != nullptr; cp = cp->link) {
        if (op == cp->str) {
            return true;
        }
    }
    return false;
}

bool TokenScanner::isOperatorPrefix(const std::string& op) {
    for (StringCell* cp = operators; cp != nullptr; cp = cp->link) {
        if (startsWith(cp->str, op)) {
            return true;
        }
    }
    return false;
}

/*
 * Implementation notes: scanNumber
 * --------------------------------
 * Reads characters until the scanner reaches the end of a legal number.
 * The function operates by simulating what computer scientists
 * call a finite-state machine.  The program uses the variable
 * <code>state</code> to record the history of the process and
 * determine what characters would be legal at this point in time.
 */
std::string TokenScanner::scanNumber() {
    std::string token = "";
    NumberScannerState state = INITIAL_STATE;
    while (state != FINAL_STATE) {
        int ch = isp->get();
        switch (state) {
        case INITIAL_STATE:
            if (!isdigit(ch)) {
                error("TokenScanner::scanNumber: internal error: illegal call");
            }
            state = BEFORE_DECIMAL_POINT;
            break;
        case BEFORE_DECIMAL_POINT:
            if (ch == '.') {
                state = AFTER_DECIMAL_POINT;
            } else if (ch == 'E' || ch == 'e') {
                state = STARTING_EXPONENT;
            } else if (!isdigit(ch)) {
                if (ch != EOF) {
                    isp->unget();
                }
                state = FINAL_STATE;
            }
            break;
        case AFTER_DECIMAL_POINT:
            if (ch == 'E' || ch == 'e') {
                state = STARTING_EXPONENT;
            } else if (!isdigit(ch)) {
                if (ch != EOF) {
                    isp->unget();
                }
                state = FINAL_STATE;
            }
            break;
        case STARTING_EXPONENT:
            if (ch == '+' || ch == '-') {
                state = FOUND_EXPONENT_SIGN;
            } else if (isdigit(ch)) {
                state = SCANNING_EXPONENT;
            } else {
                if (ch != EOF) {
                    isp->unget();
                }
                isp->unget();
                state = FINAL_STATE;
            }
            break;
        case FOUND_EXPONENT_SIGN:
            if (isdigit(ch)) {
                state = SCANNING_EXPONENT;
            } else {
                if (ch != EOF) {
                    isp->unget();
                }
                isp->unget();
                isp->unget();
                state = FINAL_STATE;
            }
            break;
        case SCANNING_EXPONENT:
            if (!isdigit(ch)) {
                if (ch != EOF) {
                    isp->unget();
                }
                state = FINAL_STATE;
            }
            break;
        default:
            state = FINAL_STATE;
            break;
        }
        if (state != FINAL_STATE) {
            token += char(ch);
        }
    }
    return token;
}

/*
 * Implementation notes: scanString
 * --------------------------------
 * Reads and returns a quoted string from the scanner, continuing until
 * it scans the matching delimiter.  The scanner generates an error if
 * there is no closing quotation mark before the end of the input.
 */
std::string TokenScanner::scanString() {
    std::string token = "";
    char delim = isp->get();
    token += delim;
    bool escape = false;
    while (true) {
        int ch = isp->get();
        if (ch == EOF) {
            error("TokenScanner::scanString: found unterminated string");
        }
        if (ch == delim && !escape) {
            break;
        }
        escape = (ch == '\\') && !escape;
        token += ch;
    }
    return token + delim;
}

/*
 * Implementation notes: scanWord
 * ------------------------------
 * Reads characters until the scanner reaches the end of a sequence
 * of word characters.
 */
std::string TokenScanner::scanWord() {
    std::string token = "";
    while (true) {
        int ch = isp->get();
        if (ch == EOF) {
            break;
        }
        if (!isWordCharacter(ch)) {
            isp->unget();
            break;
        }
        token += char(ch);
    }
    return token;
}

/*
 * Implementation notes: skipSpaces
 * --------------------------------
 * Advances the position of the scanner until the current character is
 * not a whitespace character.
 */
void TokenScanner::skipSpaces() {
    while (true) {
        int ch = isp->get();
        if (ch == EOF) {
            return;
        }
        if (!isspace(ch)) {
            isp->unget();
            return;
        }
    }
}

std::ostream& operator <<(std::ostream& out, const TokenScanner& scanner) {
    out << "TokenScanner{";
    bool first = true;
    if (!scanner.buffer.empty()) {
        out << "input=\"" << scanner.buffer << "\"";
        first = false;
    }
    out << (first ? "" : ",") << "position=" << scanner.getPosition();
    first = false;

    if (scanner.scanNumbersFlag) {
        out << (first ? "" : ",") << "scanNumbers";
        first = false;
    }
    if (scanner.scanStringsFlag) {
        out << (first ? "" : ",") << "scanStrings";
        first = false;
    }
    if (!scanner.wordChars.empty()) {
        out << (first ? "" : ",") << "wordChars=[" << scanner.wordChars << "]";
        first = false;
    }
    if (scanner.ignoreWhitespaceFlag) {
        out << (first ? "" : ",") << "ignoreWhitespace";
        first = false;
    }
    if (scanner.ignoreCommentsFlag) {
        out << (first ? "" : ",") << "ignoreComments";
        // first = false;
    }
    out << "}";
    return out;
}

/////////////////////// END code extracted from StanfordCPPLib/io/tokenscanner.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/private/version.cpp ///////////////////////
/*
 * File: version.cpp
 * -----------------
 * This file implements functions for checking the version number of the
 * Stanford C++ library, its Java back-end, and the project properties
 * file (.pro).
 *
 * @author Marty Stepp 
 * @version 2016/09/24
 * - bug fix for std::quick_exit function
 * @version 2015/07/05
 * - removed static global Platform variable, replaced by getPlatform as needed
 * @version 2014/11/13
 * - ifdef'd out macroIntegerToDate function to remove unused function warning on some platforms
 * @since 2014/10/31
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>

namespace version {
#ifdef SPL_PROJECT_VERSION
/*
 * converts an 8-digit integer into a YYYY/MM/DD date string,
 * e.g. 20140907 -> "2014/09/07"
 * needed because I can't have a string as a -D command-line defined flag
 */
static std::string macroIntegerToDate(int macroInteger) {
    int year = (macroInteger / 10000);          // 2014
    int month = (macroInteger % 10000 / 100);   // 09
    int day = (macroInteger % 100);             // 07
    std::ostringstream out;
    out << std::setw(4) << std::setfill('0') << year
        << "/" << std::setw(2) << std::setfill('0') << month
        << "/" << std::setw(2) << std::setfill('0') << day;
    return out.str();
}
#endif // SPL_PROJECT_VERSION

static void ensureProjectVersionHelper(std::string minVersion) {
#ifdef SPL_PROJECT_VERSION
    std::string projectVersion = macroIntegerToDate(SPL_PROJECT_VERSION);
#else
    std::string projectVersion = "";
#endif

    if (projectVersion < minVersion) {
        fputs("\n", stderr);
        fputs("***\n", stderr);
        fputs("*** STANFORD C++ LIBRARY ERROR:\n", stderr);
        fputs("*** Your project's properties (from your .pro file) are too old\n", stderr);
        fputs("*** and are not compatible with this version of the C++ library.\n", stderr);
        fputs("*** Exiting immediately to avoid compatibility errors.\n", stderr);
        fputs("*** Please update your .pro to a newer compatible version.\n", stderr);
        fprintf(stderr, "*** Your .pro version found : %s\n", projectVersion.c_str());
        fprintf(stderr, "*** Minimum version accepted: %s\n", minVersion.c_str());
        fputs("***\n", stderr);
        fputs("\n", stderr);
        fflush(stderr);
        
        std::exit(1);
    }
}

void ensureJavaBackEndVersion(std::string /*minVersion*/) {
    // empty
}

void ensureProjectVersion(std::string minVersion) {
    if (minVersion.empty()) {
#ifdef SPL_MINIMUM_PROJECT_VERSION
        minVersion = SPL_MINIMUM_PROJECT_VERSION;
#else
        minVersion = STANFORD_CPP_PROJECT_MINIMUM_VERSION;
#endif
    }
    ensureProjectVersionHelper(minVersion);
}

std::string getCppLibraryDocsUrl() {
    return STANFORD_CPP_LIB_DOCS_URL;
}

std::string getCppLibraryVersion() {
    return STANFORD_CPP_LIB_VERSION;
}

std::string getJavaBackEndVersion() {
    return "?";
}

/*
 * Returns version of project properties as defined in .pro file.
 */
std::string getProjectVersion() {
#ifdef SPL_PROJECT_VERSION
    // 20141031 -> "2014/10/31"
    std::ostringstream out;
    out << (SPL_PROJECT_VERSION / 10000);         // 2014
    out << "/";
    out << (SPL_PROJECT_VERSION % 10000 / 100);   // 10
    out << "/";
    out << (SPL_PROJECT_VERSION % 100);           // 31
    return out.str();
#endif
    return "";
}

} // namespace version

/////////////////////// END code extracted from StanfordCPPLib/private/version.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/system/call_stack_gcc.cpp ///////////////////////
/*
 * File: call_stack_gcc.cpp
 * ------------------------
 * Linux/gcc implementation of the call_stack class.
 *
 * @author Marty Stepp, based on code from Fredrik Orderud
 * @version 2019/04/16
 * - bug fix for stack trace line numbers on some Mac systems (thanks to Julie Zelenski)
 * @version 2018/10/22
 * - bug fix for STL vector vs Stanford Vector
 * @version 2018/10/18
 * - added addr2line_functionName to resolve some function names not in backtrace
 * - improved calculation of function offsets for better stack trace resolving
 * @version 2017/10/18
 * - small bug fix for pointer comparison
 * @version 2017/09/02
 * - small bug fix for new clang warning about ordered comparison between pointer and zero
 * @version 2016/12/01
 * - bug fixes for call stack line number retrieval
 * @version 2016/10/14
 * - modified floating-point equality tests to use floatingPointEqual function
 * @version 2016/10/04
 * - removed all static variables (replaced with STATIC_VARIABLE macros)
 * @version 2015/05/28
 */

/* Copyright (c) 2009, Fredrik Orderud
   License: BSD licence (http://www.opensource.org/licenses/bsd-license.php)
   Based on: http://stupefydeveloper.blogspot.com/2008/10/cc-call-stack.html */

#define INTERNAL_INCLUDE 1
#ifdef __GNUC__
#include <stdio.h>
#include <cxxabi.h>
#ifdef _WIN32
#include <windows.h>
#include <tchar.h>
#include <stdio.h>
#include <strsafe.h>
#undef MOUSE_EVENT
#undef KEY_EVENT
#undef MOUSE_MOVED
#undef HELP_KEY
#else // _WIN32
#include <execinfo.h>
#include <dlfcn.h>
#include <cstring>
#endif // _WIN32
#endif // __GNUC__
#if defined(__APPLE__)
#include <mach-o/dyld.h>   // for _dyld_get_image_header
#endif // __APPLE__
#include <iomanip>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

namespace platform {
std::string os_getLastError() {
#ifdef _WIN32
    // Windows error-reporting code
    DWORD lastErrorCode = ::GetLastError();
    char* errorMsg = nullptr;
    // Ask Windows to prepare a standard message for a GetLastError() code:
    ::FormatMessageA(
                   /* dwFlags */ FORMAT_MESSAGE_ALLOCATE_BUFFER | FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS,
                   /* lpSource */ nullptr,
                   /* dwMessageId */ lastErrorCode,
                   /* dwLanguageId */ LANG_NEUTRAL,
                   /* lpBuffer */ reinterpret_cast<LPSTR>(&errorMsg),
                   /* dwSize */ 0,
                   /* arguments */ nullptr);
    if (errorMsg) {
        return std::string(errorMsg);
    } else {
        return "";
    }
#else
    // Linux/Mac error-reporting code
    return std::string(strerror(errno));
#endif // _WIN32
}
} // namespace platform

namespace stacktrace {

/*
 * Run a sub-process and capture its output.
 */
int execAndCapture(std::string cmd, std::string& output) {
#ifdef _WIN32
    // Windows code for external process (ugly)
    HANDLE g_hChildStd_IN_Rd = nullptr;
    HANDLE g_hChildStd_IN_Wr = nullptr;
    HANDLE g_hChildStd_OUT_Rd = nullptr;
    HANDLE g_hChildStd_OUT_Wr = nullptr;
    SECURITY_ATTRIBUTES saAttr;
    saAttr.nLength = sizeof(SECURITY_ATTRIBUTES);
    saAttr.bInheritHandle = TRUE;
    saAttr.lpSecurityDescriptor = nullptr;
    if (!CreatePipe(&g_hChildStd_OUT_Rd, &g_hChildStd_OUT_Wr, &saAttr, 0)) {
        return 1;   // fail
    }
    if (!SetHandleInformation(g_hChildStd_OUT_Rd, HANDLE_FLAG_INHERIT, 0)) {
        return 1;   // fail
    }
    if (!CreatePipe(&g_hChildStd_IN_Rd, &g_hChildStd_IN_Wr, &saAttr, 0)) {
        return 1;   // fail
    }
    if (!SetHandleInformation(g_hChildStd_IN_Wr, HANDLE_FLAG_INHERIT, 0) ) {
        return 1;   // fail
    }

    // CreateChildProcess();
    PROCESS_INFORMATION piProcInfo;
    STARTUPINFOA siStartInfo;
    ZeroMemory(&piProcInfo, sizeof(PROCESS_INFORMATION));
    ZeroMemory( &siStartInfo, sizeof(STARTUPINFOA) );
    siStartInfo.cb = sizeof(STARTUPINFO);
    siStartInfo.hStdError = g_hChildStd_OUT_Wr;
    siStartInfo.hStdOutput = g_hChildStd_OUT_Wr;
    siStartInfo.hStdInput = g_hChildStd_IN_Rd;
    siStartInfo.dwFlags |= STARTF_USESTDHANDLES;

    if (!CreateProcessA(
            nullptr,
            const_cast<char*>(cmd.c_str()),    // command line
            nullptr,                           // process security attributes
            nullptr,                           // primary thread security attributes
            TRUE,                              // handles are inherited
            CREATE_NO_WINDOW,                  // creation flags
            nullptr,                           // use parent's environment
            nullptr,                           // use parent's current directory
            &siStartInfo,                      // STARTUPINFO pointer
            &piProcInfo)) {                    // receives PROCESS_INFORMATION
        std::cerr << "CREATE PROCESS FAIL: " << platform::os_getLastError() << std::endl;
        std::cerr << cmd << std::endl;
        return 1;   // fail
    }

    // close the subprocess's handles (waits for it to finish)
    WaitForSingleObject(piProcInfo.hProcess, INFINITE);
    CloseHandle(piProcInfo.hProcess);
    CloseHandle(piProcInfo.hThread);

    // ReadFromPipe();
    DWORD dwRead;
    const int BUFSIZE = 65536;
    CHAR chBuf[BUFSIZE] = {0};
    if (!ReadFile(g_hChildStd_OUT_Rd, chBuf, BUFSIZE, &dwRead, nullptr) || dwRead == 0) {
        return 1;
    }
    std::ostringstream out;
    for (int i = 0; i < static_cast<int>(dwRead); i++) {
        out.put(chBuf[i]);
    }

    output = out.str();
    return 0;
#else
    // Linux / Mac code for external process
    cmd += " 2>&1";
    FILE* pipe = popen(cmd.c_str(), "r");
    if (!pipe) {
        return -1;
    }
    char buffer[65536] = {0};
    output = "";
    while (!feof(pipe)) {
        if (fgets(buffer, 65536, pipe) != nullptr) {
            output += buffer;
        }
    }
    return pclose(pipe);
#endif // _WIN32
}

std::string addr2line_clean(std::string line) {
#if defined(_WIN32)
    // TODO: implement on Windows
    // "ZN10stacktrace25print_stack_trace_windowsEv at C:\Users\stepp\Documents\StanfordCPPLib\build\stanfordcpplib-windows-Desktop_Qt_5_3_MinGW_32bit-Debug/../../StanfordCPPLib/stacktrace/call_stack_windows.cpp:126"
#elif defined(__APPLE__)
    // Mac OS X version (atos)
    // "Vector<int>::checkIndex(int) const (in Autograder_QtCreatorProject) (vector.h:764)"
    if (line.find(" (") != std::string::npos) {
        line = line.substr(line.rfind(" (") + 2);
    }
    if (line.find(')') != std::string::npos) {
        line = line.substr(0, line.rfind(')'));
    }
    line = trim(line);
#elif defined(__GNUC__)
    // Linux version (addr2line)
    // "_Z4Mainv at /home/stepp/.../FooProject/src/mainfunc.cpp:131"
    if (line.find(" at ") != std::string::npos) {
        line = line.substr(line.rfind(" at ") + 4);
    }
    if (line.find('/') != std::string::npos) {
        line = line.substr(line.rfind('/') + 1);
    }

    // strip extra parenthesized info from the end
    if (line.find(" (") != std::string::npos) {
        line = line.substr(0, line.rfind(" ("));
    }
    line = trim(line);
#endif
    return line;
}

std::string addr2line_functionName(std::string line) {
#if defined(_WIN32)
    // TODO: implement on Windows
    // "ZN10stacktrace25print_stack_trace_windowsEv at C:\Users\stepp\Documents\StanfordCPPLib\build\stanfordcpplib-windows-Desktop_Qt_5_3_MinGW_32bit-Debug/../../StanfordCPPLib/stacktrace/call_stack_windows.cpp:126"
#elif defined(__APPLE__)
    // Mac OS X version (atos)
    // "Vector<int>::checkIndex(int) const (in Autograder_QtCreatorProject) (vector.h:764)"
    if (line.find(" (") != std::string::npos) {
        line = line.substr(0, line.rfind(" (") - 1);
    }
    if (line.find("(in ") != std::string::npos) {
        line = line.substr(0, line.rfind("(in "));
    }
    line = trim(line);
#elif defined(__GNUC__)
    // Linux version (addr2line)
    // "_Z4Mainv at /home/stepp/.../FooProject/src/mainfunc.cpp:131"
    // "std::_Function_handler<void (), stanfordcpplib::autograder::GuiAutograder::runTest(stanfordcpplib::autograder::AutograderTest*)::{lambda()#1}>::_M_invoke(std::_Any_data const&) at std_function.h:318"
    if (line.find(" at ") != std::string::npos) {
        line = line.substr(0, line.rfind(" at "));
    }
    line = trim(line);
#endif
    return line;
}

int addr2line_all(Vector<void*> addrsVector, std::string& output) {
    int length = static_cast<int>(addrsVector.size());
    void* addrs[length];
    for (int i = 0; i < length; i++) {
        addrs[i] = addrsVector[i];
    }
    return addr2line_all(addrs, length, output);
}

int addr2line_all(void** addrs, int length, std::string& output) {
    // turn the addresses into a space-separated string
    std::ostringstream out;
    for (int i = 0; i < length; i++) {
        out << " " << std::hex << std::setfill('0') << addrs[i];
    }
    std::string addrsStr = out.str();
    out.str("");

    // have addr2line map the address to the relevant line in the code
#if defined(__APPLE__)
    // Mac OS X
    // JL : change "atos" to "xcrun atos"?
    void *base = (void *) _dyld_get_image_header(0);
    if (base) {
        out << "atos -l " << base << " -o " << exceptions::getProgramNameForStackTrace() << addrsStr;
    } else {
        out << "atos -o " << exceptions::getProgramNameForStackTrace() << addrsStr;
    }
#elif defined(_WIN64)
    // Windows
    if (fileExists("addr2line64.exe")) {
        out << "addr2line64.exe -f -i -C -s -p -e \"" << exceptions::getProgramNameForStackTrace() << "\"" << addrsStr;
    } else {
        out << "(addr2line64.exe unavailable; no stack trace produced)";
    }
#elif defined(_WIN32)
    // Windows
    if (fileExists("addr2line.exe")) {
        out << "addr2line.exe -f -i -C -s -p -e \"" << exceptions::getProgramNameForStackTrace() << "\"" << addrsStr;
    } else {
        out << "(addr2line.exe unavailable; no stack trace produced)";
    }
#else
    // Linux
    out << "addr2line -f -i -C -s -p -e " << exceptions::getProgramNameForStackTrace() << addrsStr;
#endif
    std::string command = out.str();
    int result = execAndCapture(command, output);
    return result;
}

/*
 * Resolve symbol name and source location given the path to the executable
 * and an address
 */
int addr2line(void* addr, std::string& line) {
    void* addrs[1] = {addr};
    return addr2line_all(addrs, 1, line);
}

void*& fakeCallStackPointer() {
    static void* fakeCallStackPointer = nullptr;
    return fakeCallStackPointer;
}
} // namespace stacktrace


/*
 * Below is the Linux/Mac-specific stack trace code.
 */
#ifndef _WIN32

namespace stacktrace {
STATIC_CONST_VARIABLE_DECLARE(int, STACK_FRAMES_TO_SKIP, 0)
STATIC_CONST_VARIABLE_DECLARE(int, STACK_FRAMES_MAX, 50)

std::ostream& operator <<(std::ostream& out, const entry& ent) {
    return out << ent.toString();
}

call_stack::call_stack(const size_t /*num_discard = 0*/) {
    // retrieve call-stack as an array of void* pointers to each function on stack
    void* trace[STATIC_VARIABLE(STACK_FRAMES_MAX)];
    for (int i = 0; i < STATIC_VARIABLE(STACK_FRAMES_MAX); i++) {
        trace[i] = nullptr;
    }

    int stack_depth = backtrace(trace, STATIC_VARIABLE(STACK_FRAMES_MAX));

    // First pass: read linker symbol info and get address offsets.
    for (int i = STATIC_VARIABLE(STACK_FRAMES_TO_SKIP); i < stack_depth; i++) {
        // DL* = programmer API to dynamic linking loader

        // https://linux.die.net/man/3/dladdr
        // const char *dli_fname;   // pathname of shared object (file) that contains address
        // void       *dli_fbase;   // address at which shared object is loaded in system memory
        // const char *dli_sname;   // name of nearest symbol with address lower than addr
        // void       *dli_saddr;   // exact address of symbol named in dli_sname

        Dl_info dlinfo;
        if (!dladdr(trace[i], &dlinfo)) {
            continue;
        }

        const char* symname = dlinfo.dli_sname;

        int   status;
        char* demangled = abi::__cxa_demangle(symname, /* buffer */ nullptr,
                                              /* length pointer */ nullptr, &status);
        if (status == 0 && demangled) {
            symname = demangled;
        }

        // debug code left in because we occasionally need to debug stack traces
//        std::cout << "call_stack: I am thread " << GThread::getCurrentThread()->objectName().toStdString() << std::endl;
//        std::cout << "info for " << trace[i] << ":" << std::endl;
//        std::cout << "dlinfo " << i << ":"
//                  << " fbase=" << dlinfo.dli_fbase
//                  << " fname=" << (dlinfo.dli_fname ? dlinfo.dli_fname : "NULL")
//                  << " sname=" << (dlinfo.dli_sname ? dlinfo.dli_sname : "NULL")
//                  << " saddr=" << dlinfo.dli_saddr
//                  << std::endl;
//        if (demangled) {
//            std::cout << "demangled name " << i << ": " << std::string(demangled) << " (status " << status << ")" << std::endl;
//        } else {
//            std::cout << "demangled name " << i << ": NULL" << " (status " << status << ")" << std::endl;
//        }
//        std::cout << std::endl;
        
        // store entry to stack
        if (dlinfo.dli_fname) {
            entry e;
            e.file     = dlinfo.dli_fname;
            e.line     = 0;   // unsupported; use lineStr instead (later)
            e.function = symname ? symname : "(unknown)";
            e.address  = trace[i];

            // The dli_fbase gives an overall offset into the file itself;
            // the dli_saddr is the offset of that symbol/function/line.
            // by subtracting them we get the offset of the function within the file
            // which addr2line can use to look up function line numbers.

            if (dlinfo.dli_fbase) {
                // subtract smaller address from larger one to get offset
                if (trace[i] >= dlinfo.dli_fbase) {
                    e.address2 = (void*) ((long) trace[i] - (long) dlinfo.dli_fbase);
                } else {
                    e.address2 = (void*) ((long) dlinfo.dli_fbase - (long) trace[i]);
                }
            } else {
                e.address2 = dlinfo.dli_saddr;
            }
            stack.push_back(e);
        }

        if (demangled) {
            free(demangled);
        }
    }

    if (stack_depth == 0 || stack.isEmpty()) {
        return;
    }

    // Second pass: try to look up line numbers.
    //
    // let's also try to get the line numbers via an 'addr2line' external process
    // (for max compatibility with GCC and Clang, we look up the addresses 2 ways:
    // 1) by the raw void* given to us from backtrace(), and
    // 2) by the offsetted pointer where we subtract the addr of the exe file.
    // Option 1 used to work for all compilers, but sometime around summer 2016
    // GCC started failing unless we use option 2.
    // Clang and other compilers still need option 1 and fail with option 2,
    // and to avoid running external addr2line process twice, we just look it up
    // both ways and then figure out which one is best by string length.
    // The failing one will emit a lot of short "??:?? 0" lines.

    Vector<void*> addrsToLookup;
    for (const entry& e : stack) {
        addrsToLookup.add(e.address);
        addrsToLookup.add(e.address2);
    }

    std::string addr2lineOutput;
    addr2line_all(addrsToLookup, addr2lineOutput);

    Vector<std::string> addr2lineLines = stringSplit(addr2lineOutput, "\n");
    int numAddrLines = (int) addr2lineLines.size();
    for (int i = 0, size = (int) stack.size(); i < size; i++) {
        std::string opt1 = (2 * i < numAddrLines ? addr2lineLines[2 * i] : std::string());
        std::string opt2 = (2 * i + 1 < numAddrLines ? addr2lineLines[2 * i + 1] : std::string());
        std::string best = opt1.length() > opt2.length() ? opt1 : opt2;
        stack[i].lineStr = addr2line_clean(best);
        if (stack[i].function.empty() || stack[i].function == "(unknown)") {
            stack[i].function = addr2line_functionName(best);
        }
    }
}

call_stack::~call_stack() throw() {
    // automatic cleanup
}

} // namespace stacktrace

#endif // _WIN32

/////////////////////// END code extracted from StanfordCPPLib/system/call_stack_gcc.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/system/error.cpp ///////////////////////
/*
 * File: error.cpp
 * ---------------
 * Implementation of the error function.
 * 
 * @version 2016/11/23
 * - added operator << to print ErrorExceptions
 * @version 2014/10/08
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#include <sstream>
#undef INTERNAL_INCLUDE

/* Definitions for the ErrorException class */

ErrorException::ErrorException(std::string msg)
        : _kind("error") {
    _msg = msg;

#if defined(SPL_CONSOLE_PRINT_EXCEPTIONS)
    std::ostringstream out;
    exceptions::printStackTrace(out);
    _stackTrace = out.str();
#endif // SPL_CONSOLE_PRINT_EXCEPTIONS
}

void ErrorException::dump() const {
    dump(std::cerr);
}

void ErrorException::dump(std::ostream& out) const {
    out << std::endl;
    out << "***" << std::endl;
    out << "*** STANFORD C++ LIBRARY" << std::endl;
    out << "*** An ErrorException occurred during program execution:" << std::endl;
    if (!_msg.empty()) {
        out << ("*** " + _msg) << std::endl;
    }
    out << "***" << std::endl;
    out << insertStarsBeforeEachLine(getStackTrace()) << std::endl;
    // out << "***" << std::endl;
    // out << "*** To learn more about the crash, we strongly" << std::endl;
    // out << "*** suggest running your program under the debugger." << std::endl;
    // out << "***" << std::endl;
    out.flush();
}

std::string ErrorException::getKind() const {
    return _kind;
}

std::string ErrorException::getMessage() const {
    return _msg;
}

bool ErrorException::hasStackTrace() const {
    return !_stackTrace.empty();
}

std::string ErrorException::getStackTrace() const {
    return _stackTrace;
}

std::string ErrorException::insertStarsBeforeEachLine(const std::string& s) {
    std::string result;
    for (std::string line : stringSplit(s, "\n")) {
        if (!result.empty()) {
            if (!startsWith(line, "***")) {
                line = "*** " + line;
            }
            result += "\n";
        }
        result += line;
    }
    return result;
}

void ErrorException::setKind(const std::string& kind) {
    _kind = kind;
}

void ErrorException::setStackTrace(const std::string& stackTrace) {
    _stackTrace = stackTrace;
}

const char* ErrorException::what() const noexcept {
    // stepp : The original "Error: " prefix is commented out here,
    // because in many error cases, the attempt to do the string concatenation
    // ends up garbling the string and leading to garbage exception text
    // return ("Error: " + msg).c_str();
    return _msg.c_str();
}

std::ostream& operator <<(std::ostream& out, const ErrorException& ex) {
    out << "ErrorException: " << ex.what();
    std::string stack = ex.getStackTrace();
    if (!stack.empty()) {
        out << "Stack trace:" << std::endl;
        out << stack;
        out.flush();
    }
    return out;
}

/*
 * 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.
 */

/* [[noreturn]] */ void error(const std::string& msg) {
    throw ErrorException(msg);
}

/////////////////////// END code extracted from StanfordCPPLib/system/error.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/io/plainconsole.cpp ///////////////////////
/*
 * File: plainconsole.cpp
 * ----------------------
 * This file defines the implementation of functions to add utility to the
 * C++ plain text console streams, cin/cout/cerr.
 * See plainconsole.h for documentation of each function.
 *
 * @author Marty Stepp
 * @version 2017/11/12
 * - changed limited stream to throw error rather than raise SIGABRT for better displaying
 * @version 2017/10/20
 * - fixed compiler warning about 0 vs nullptr
 * @version 2015/10/21
 * @since 2015/10/21
 */

#define INTERNAL_INCLUDE 1

#include <csignal>
#include <iostream>
#include <string>
#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

namespace plainconsole {
/*
 * A stream buffer that just forwards everything to a delegate,
 * but echoes any user input read from it.
 * Used to (sometimes) echo console input when redirected in from a file.
 * http://www.cplusplus.com/reference/streambuf/streambuf/
 */
class EchoingStreambuf : public std::streambuf {
private:
    /* Constants */
    static const int BUFFER_SIZE = 4096;

    /* Instance variables */
    char inBuffer[BUFFER_SIZE];
    char outBuffer[BUFFER_SIZE];
    std::istream instream;
    std::ostream& outstream;
    int outputLimit;
    int outputPrinted;

public:
    EchoingStreambuf(std::streambuf& buf, std::ostream& out)
            : instream(&buf),
              outstream(out),
              outputLimit(0),
              outputPrinted(0) {
        // outstream.rdbuf(&buf);
        setg(inBuffer, inBuffer, inBuffer);
        setp(outBuffer, outBuffer + BUFFER_SIZE);
    }

    ~EchoingStreambuf() {
        /* Empty */
    }
    
    virtual void setOutputLimit(int limit) {
        outputLimit = limit;
    }

    virtual int underflow() {
        // 'return 0' handles end-of-input from stdin redirect
        std::string line;
        if (!getline(instream, line)) {
            return 0;
        }
        
        int n = line.length();
        if (n + 1 >= BUFFER_SIZE) {
            error("EchoingStreambuf::underflow: String too long");
        }
        for (int i = 0; i < n; i++) {
            inBuffer[i] = line[i];
        }
        inBuffer[n++] = '\n';
        inBuffer[n] = '\0';
        setg(inBuffer, inBuffer, inBuffer + n);
        
        // this is the place to echo the input
        // fprintf(stdout, "inBuffer: \"%s\"\n", inBuffer);
        // fflush(stdout);
        outstream << inBuffer;
        outstream.flush();
        
        return inBuffer[0];
    }

    virtual int overflow(int ch = EOF) {
        std::string line = "";
        for (char *cp = pbase(); cp < pptr(); cp++) {
            if (*cp == '\n') {
                // puts(line.c_str());
                outputPrinted += line.length();
                if (outputLimit > 0 && outputPrinted > outputLimit) {
                    error("excessive output printed");
                }
                line = "";
            } else {
                line += *cp;
            }
        }
        if (line != "") {
            // puts(line.c_str());
            outputPrinted += line.length();
            if (outputLimit > 0 && outputPrinted > outputLimit) {
                error("excessive output printed");
            }
        }
        setp(outBuffer, outBuffer + BUFFER_SIZE);
        if (ch != EOF) {
            outBuffer[0] = ch;
            pbump(1);
        }
        return ch != EOF;
    }
    
    virtual int sync() {
        return overflow();
    }
};

/*
 * A stream buffer that limits how many characters you can print to it.
 * If you exceed that many, it throws an ErrorException.
 */
class LimitedStreambuf : public std::streambuf {
private:
    std::ostream outstream;
    int outputLimit;
    int outputPrinted;

public:
    LimitedStreambuf(std::streambuf& buf, int limit)
            : outstream(&buf),
              outputLimit(limit),
              outputPrinted(0) {
        setp(nullptr, nullptr);   // // no buffering, overflow on every char
    }

    virtual void setOutputLimit(int limit) {
        outputLimit = limit;
    }

    virtual int overflow(int ch = EOF) {
        outputPrinted++;
        if (outputLimit > 0 && outputPrinted > outputLimit) {
            // error("excessive output printed");
            // outstream.setstate(std::ios::failbit | std::ios::badbit | std::ios::eofbit);
            // kill the program
            // (use a signal rather than error/exception
            // so student won't try to catch it)
            // error("Excessive output printed; you may have an infinite loop in your code.");
            raise(SIGUSR1);
        } else {
            outstream.put(ch);
        }
        return ch;
    }
};

void setOutputLimit(int limit) {
    if (limit <= 0) {
        error("Platform::setConsoleOutputLimit: limit must be a positive integer");
    }
    LimitedStreambuf* limitedbufOut = new LimitedStreambuf(*std::cout.rdbuf(), limit);
    LimitedStreambuf* limitedbufErr = new LimitedStreambuf(*std::cerr.rdbuf(), limit);
    std::cout.rdbuf(limitedbufOut);
    std::cerr.rdbuf(limitedbufErr);
}

void setEcho(bool value) {
    static EchoingStreambuf* echobufIn = nullptr;
    static std::streambuf* oldBuf = nullptr;
    
    if (!echobufIn && value) {
        // start to echo user input pulled from cin
        oldBuf = std::cin.rdbuf();
        echobufIn = new EchoingStreambuf(*std::cin.rdbuf(), std::cout);
        std::cin.rdbuf(echobufIn);
    } else if (echobufIn && !value) {
        // stop echo
        std::cin.rdbuf(oldBuf);
        oldBuf = nullptr;
        echobufIn = nullptr;
    }
}

} // namespace plainconsole

/////////////////////// END code extracted from StanfordCPPLib/io/plainconsole.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/system/exceptions.cpp ///////////////////////
/*
 * File: exceptions.cpp
 * --------------------
 * This file contains a top-level exception handler to print exceptions thrown
 * by student code on the console.
 * 
 * @author Marty Stepp
 * @version 2019/05/16
 * - added more function names to filter from stack trace
 * @version 2019/04/16
 * - filter Qt/std thread methods from stack trace
 * @version 2019/04/02
 * - small fix for warning about -Wreturn-std-move on string exception
 * @version 2018/10/18
 * - added set_unexpected handler (used by autograders when errors are thrown)
 * - added some new function names to filter from stack traces
 * @version 2018/09/27
 * - bug fixes to print better stack traces when used with threads
 * @version 2018/09/25
 * - modify setTopLevelExceptionHandlerEnabled to work better with threads
 * @version 2016/12/23
 * - added more function names for stack trace filtering (mainly thread stuff)
 * @version 2016/12/09
 * - added insertStarsBeforeEachLine
 * @version 2016/11/07
 * - added cleanupFunctionNameForStackTrace
 * - slight refactor of shouldFilterOutFromStackTrace
 * @version 2016/10/30
 * - moved recursion functions to recursion.h/cpp
 * @version 2016/10/04
 * - removed all static variables (replaced with STATIC_VARIABLE macros)
 * @version 2016/08/02
 * - added some new cxx11 filters to stack traces
 * - fixed spacing on *** messages from exception handlers
 * @version 2015/10/13
 * - bug fix in terminate handler to turn off signal handler at end
 * @version 2015/05/28
 * - tiny bug fix to exception stack trace printing format on Windows
 * @version 2014/11/19
 * - disabled SetThreadErrorMode to avoid compiler errors on Windows systems
 * @version 2014/11/18
 * - fixed minor bug with filtering out nested <> template args from stack traces
 * @version 2014/11/14
 * - fixed bug with SIGABRT handling in autograder mode (was muffling unit test failures)
 * @version 2014/11/12
 * - made printStackTrace function publicly available
 * - added top-level signal handler (for null-pointer derefs etc.)
 * @since 2014/11/05
 */

#define INTERNAL_INCLUDE 1

#include <csignal>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <string>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#ifdef _WIN32
#include <windows.h>
#  undef MOUSE_EVENT
#  undef KEY_EVENT
#  undef MOUSE_MOVED
#  undef HELP_KEY
#endif
#undef INTERNAL_INCLUDE

// uncomment the definition below to use an alternative 'signal stack'
// which helps in handling stack overflow errors
// (disabled because it currently breaks stack traces for other errors)
// #define SHOULD_USE_SIGNAL_STACK

namespace exceptions {
// just some value that is not any existing signal
#define SIGSTACK (static_cast<int>(0xdeadbeef))
#define SIGUNKNOWN (static_cast<int>(0xcafebabe))
#define SIGTIMEOUT (static_cast<int>(0xf00df00d))

// static 'variables' (as functions to avoid initialization ordering bugs)
STATIC_CONST_VARIABLE_DECLARE(bool, STACK_TRACE_SHOULD_FILTER, true)
STATIC_CONST_VARIABLE_DECLARE(bool, STACK_TRACE_SHOW_TOP_BOTTOM_BARS, false)

STATIC_VARIABLE_DECLARE(std::string, programNameForStackTrace, "")
STATIC_VARIABLE_DECLARE(bool, topLevelExceptionHandlerEnabled, false)

// handle SIGABRT in normal mode, but not autograder mode
// (Google Test uses SIGABRT internally so we can't catch it)
#ifdef SPL_AUTOGRADER_MODE
STATIC_CONST_VARIABLE_DECLARE_COLLECTION(Vector<int>, SIGNALS_HANDLED, SIGSEGV, SIGILL, SIGFPE, SIGINT)
#else
STATIC_CONST_VARIABLE_DECLARE_COLLECTION(Vector<int>, SIGNALS_HANDLED, SIGSEGV, SIGILL, SIGFPE, SIGABRT)
#endif // SPL_AUTOGRADER_MODE

static void signalHandlerDisable();
static void signalHandlerEnable();
static void stanfordCppLibSignalHandler(int sig);
[[noreturn]] static void stanfordCppLibTerminateHandler();
static void stanfordCppLibUnexpectedHandler();

std::string cleanupFunctionNameForStackTrace(std::string function) {
    // remove references to std:: namespace
    stringReplaceInPlace(function, "std::", "");
    stringReplaceInPlace(function, "__cxx11::", "");
    stringReplaceInPlace(function, "__cxxabi::", "");
    stringReplaceInPlace(function, "__cxxabiv1::", "");
    stringReplaceInPlace(function, "[abi:cxx11]", "");
    stringReplaceInPlace(function, "__1::", "");   // on Mac

    // a few substitutions related to predefined types for simplicity
    stringReplaceInPlace(function, "basic_ostream", "ostream");
    stringReplaceInPlace(function, "basic_istream", "istream");
    stringReplaceInPlace(function, "basic_ofstream", "ofstream");
    stringReplaceInPlace(function, "basic_ifstream", "ifstream");
    stringReplaceInPlace(function, "basic_string", "string");
    stringReplaceInPlace(function, "stanfordcpplib::collections::GenericSet", "Set");

    // remove empty/unknown function names
    stringReplaceInPlace(function, "?? ??:0", "");

    // cleanup autograder test case names
    stringReplaceInPlace(function, "_Test::TestRealBody", "");
    stringReplaceInPlace(function, "_Test::TestBody", "");

    // remove template arguments
    // TODO: does not work well for nested templates
    int lessThan = stringIndexOf(function, "<");
    while (lessThan >= 0) {
        // see if there is a matching > for this <
        int greaterThan = lessThan + 1;
        int count = 1;
        while (greaterThan < (int) function.length()) {
            if (function[greaterThan] == '<') {
                count++;
            } else if (function[greaterThan] == '>') {
                count--;
                if (count == 0) {
                    break;
                }
            }
            greaterThan++;
        }
        if (count == 0 && lessThan >= 0 && greaterThan > lessThan) {
            function.erase(lessThan, greaterThan - lessThan + 1);
        } else {
            // look for the next < in the string, if any, to see if it has a matching >
            lessThan = stringIndexOf(function, "<", lessThan + 1);
        }
    }

    // addr2line oddly writes "const Foo&" as "Foo const&"
    stringReplaceInPlace(function, "string const&", "const string&");

    // small patch for renamed main function
    if (function == "_main_") {
        function = "main";
    }

    return function;
}

std::string& getProgramNameForStackTrace() {
    return STATIC_VARIABLE(programNameForStackTrace);
}

bool getTopLevelExceptionHandlerEnabled() {
    return STATIC_VARIABLE(topLevelExceptionHandlerEnabled);
}

void setProgramNameForStackTrace(char* programName) {
    STATIC_VARIABLE(programNameForStackTrace) = programName;
}

#ifdef _WIN32
void myInvalidParameterHandler(const wchar_t* expression,
        const wchar_t* function,
        const wchar_t* file,
        unsigned int line,
        uintptr_t /*pReserved*/) {
    wprintf(L"Invalid parameter detected in function %s."
            L" File: %s Line: %d\n", function, file, line);
    wprintf(L"Expression: %s\n", expression);
}

LONG WINAPI UnhandledException(LPEXCEPTION_POINTERS exceptionInfo) {
    // dear student: if you get a compiler error about 'Eip' not being found here,
    // it means you're using a 64-bit compiler like the MS Visual C++ compiler,
    // and not the 32-bit MinGW compiler we instructed you to install.
    // Please re-install Qt Creator with the proper compiler (MinGW 32-bit) enabled.
#if _WIN64
    if (exceptionInfo && exceptionInfo->ContextRecord && exceptionInfo->ContextRecord->Rip) {
        stacktrace::fakeCallStackPointer() = (void*) exceptionInfo;
    }
#else
    if (exceptionInfo && exceptionInfo->ContextRecord && exceptionInfo->ContextRecord->Eip) {
        stacktrace::fakeCallStackPointer() = (void*) exceptionInfo;
    }
#endif // _WIN64
    DWORD code = exceptionInfo->ExceptionRecord->ExceptionCode;
    if (code == EXCEPTION_STACK_OVERFLOW || code == EXCEPTION_FLT_STACK_CHECK) {
        stanfordCppLibSignalHandler(SIGSTACK);
    } else if (code == EXCEPTION_IN_PAGE_ERROR || code == EXCEPTION_ACCESS_VIOLATION) {
        stanfordCppLibSignalHandler(SIGSEGV);
    } else if (code == EXCEPTION_FLT_DENORMAL_OPERAND || code == EXCEPTION_FLT_DIVIDE_BY_ZERO
               || code == EXCEPTION_FLT_INEXACT_RESULT || code == EXCEPTION_FLT_INVALID_OPERATION
               || code == EXCEPTION_FLT_OVERFLOW || code == EXCEPTION_FLT_UNDERFLOW
               || code == EXCEPTION_INT_DIVIDE_BY_ZERO || code == EXCEPTION_INT_OVERFLOW) {
        stanfordCppLibSignalHandler(SIGFPE);
    } else if (code == EXCEPTION_ILLEGAL_INSTRUCTION || code == EXCEPTION_PRIV_INSTRUCTION) {
        stanfordCppLibSignalHandler(SIGILL);
    } else {
        stanfordCppLibSignalHandler(SIGUNKNOWN);
    }
    return EXCEPTION_EXECUTE_HANDLER;
}
#endif // _WIN32

void setTopLevelExceptionHandlerEnabled(bool enabled, bool force) {
    static void (* old_terminate)() = nullptr;
    static void (* old_unexpected)() = nullptr;

    if ((!STATIC_VARIABLE(topLevelExceptionHandlerEnabled) || force) && enabled) {
        if (!old_terminate) {
            old_terminate = std::set_terminate(stanfordCppLibTerminateHandler);
            old_unexpected = std::set_unexpected(stanfordCppLibUnexpectedHandler);
        } else {
            std::set_terminate(stanfordCppLibTerminateHandler);
            std::set_unexpected(stanfordCppLibUnexpectedHandler);
        }
#ifdef _WIN32
        // disabling this code for now because it messes with the
        // newly added uncaught signal handler
        // SetErrorMode(SEM_NOGPFAULTERRORBOX);
        SetErrorMode(SEM_FAILCRITICALERRORS);
        // SetThreadErrorMode(SEM_FAILCRITICALERRORS, nullptr);
        SetUnhandledExceptionFilter(UnhandledException);
        // _invalid_parameter_handler newHandler;
        // newHandler = myInvalidParameterHandler;
        // _set_invalid_parameter_handler(newHandler);
        //_set_error_mode(_OUT_TO_STDERR);
#endif // _WIN32
        
        // also set up a signal handler for things like segfaults / null-pointer-dereferences
        signalHandlerEnable();
    } else if ((STATIC_VARIABLE(topLevelExceptionHandlerEnabled) || force) && !enabled) {
        std::set_terminate(old_terminate);
        std::set_unexpected(old_unexpected);
    }
    STATIC_VARIABLE(topLevelExceptionHandlerEnabled) = enabled;
}

/*
 * Some lines from the stack trace are filtered out because they come from
 * private library code or OS code and would confuse the student.
 */
bool shouldFilterOutFromStackTrace(const std::string& function) {
    // exact names that should be matched and filtered
    static const Vector<std::string> FORBIDDEN_NAMES {
        "",
        "??",
        "call_stack",
        "_clone",
        "clone",
        "error",
        "error(const string&)",
        "error(string)",
        "ErrorException",
        "__libc_start_main",
        "_start",
        "startupMain(int, char**)",
        "(unknown)",
        "_Unwind_Resume"
    };

    // substrings to filter (don't show any func whose name contains these)
    static const Vector<std::string> FORBIDDEN_SUBSTRINGS {
        " error(",
        "__cxa_rethrow",
        "__cxa_call_terminate",
        "__cxa_call_unexpected",
        "__func::",
        "__function::",
        "_endthreadex",
        "_Function_base::_Base_manager::",
        "_Function_handler",
        "_Internal_",
        "__invoke_impl",
        "__invoke_result::type",
        "__invoke_void",
        "__unexpected",
        "thread::_Invoker",
        "thread::_State_impl",
        "_M_invoke",
        "_sigtramp",
        "autograderMain",
        "BaseThreadInitThunk",
        "call_stack_gcc.cpp",
        "call_stack_windows.cpp",
        "CFRunLoopDoSource",
        "CFRunLoopRun",
        "CFRUNLOOP_IS",
        "crtexe.c",
        "decltype(forward",
        "ErrorException::ErrorException",
        "exceptions.cpp",
        "function::operator",
        "GetModuleFileName",
        "GetProfileString",
        // "GStudentThread::run",
        "GThreadQt::run",
        "GThreadQt::start",
        "GThreadStd::run",
        "GThreadStd::start",
        "InitializeExceptionChain",
        "KnownExceptionFilter",
        "M_invoke",
        "multimain.cpp",
        // "operator",
        "pthread_body",
        "pthread_start",
        "printStackTrace",
        // "QAbstractItemModel::",
        // "QAbstractProxyModel::",
        "QApplication::notify",
        "QApplicationPrivate::",
        "QCoreApplication::",
        "QGuiApplicationPrivate::",
        "QMetaMethod::",
        "QMetaObject::",
        "QObjectPrivate::",
        "qt_plugin_instance",
        "QtGui::startBackgroundEventLoop",
        // "QWidget::",
        "QWidgetBackingStore::",
        "QWindowSystemInterface::",
        "require::_errorMessage",
        "RunCurrentEventLoopInMode",
        "shouldFilterOutFromStackTrace",
        "stacktrace::",
        "stanfordCppLibPosixSignalHandler",
        "stanfordCppLibSignalHandler",
        "stanfordCppLibTerminateHandler",
        "stanfordCppLibUnexpectedHandler",
        "testing::",
        "UnhandledException",
        "WinMain@"
    };

    // prefixes to filter (don't show any func whose name starts with these)
    static const Vector<std::string> FORBIDDEN_PREFIXES {
        // "__"
    };

    for (const std::string& name : FORBIDDEN_NAMES) {
        if (function == name) {
            return true;
        }
    }

    for (const std::string& name : FORBIDDEN_SUBSTRINGS) {
        if (function.find(name) != std::string::npos) {
            return true;
        }
    }

    for (const std::string& name : FORBIDDEN_PREFIXES) {
        if (function.find(name) == 0) {
            return true;
        }
    }

    return false;
}

void printStackTrace() {
    printStackTrace(std::cerr);
}

void printStackTrace(std::ostream& out) {
    // constructing the following object jumps into fancy code in call_stack_gcc/windows.cpp
    // to rebuild the stack trace; implementation differs for each operating system
    stacktrace::call_stack trace;
    Vector<stacktrace::entry> entries = trace.stack;
    
    // get longest line string length to line up stack traces
    void* fakeStackPtr = stacktrace::fakeCallStackPointer();
    int entriesToShowCount = 0;
    int funcNameLength = 0;
    int lineStrLength = 0;
    for (int i = 0; i < entries.size(); ++i) {
        entries[i].function = cleanupFunctionNameForStackTrace(entries[i].function);
        if (!STATIC_VARIABLE(STACK_TRACE_SHOULD_FILTER)
                || (!shouldFilterOutFromStackTrace(entries[i].function)
                    && !shouldFilterOutFromStackTrace(entries[i].file)
                    && !shouldFilterOutFromStackTrace(entries[i].lineStr))) {
            lineStrLength = std::max(lineStrLength, (int) entries[i].lineStr.length());
            funcNameLength = std::max(funcNameLength, (int) entries[i].function.length());
            entriesToShowCount++;
        }
    }
    
    if (entries.isEmpty() || entriesToShowCount == 0) {
        return;   // couldn't get a stack trace, or had no useful data  :-(
    }
    
    if (lineStrLength > 0) {
        out << "*** Stack trace (line numbers are approximate):" << std::endl;
        if (STATIC_VARIABLE(STACK_TRACE_SHOW_TOP_BOTTOM_BARS)) {
            std::ostringstream lineout;
            lineout << "*** " << std::setw(lineStrLength) << std::left
                    << "file:line" << "  " << "function" << std::endl
                    << "*** " << std::string(lineStrLength + 2 + funcNameLength, '=') << std::endl;
            out << lineout.str() << std::endl;
        }
    } else {
        out << "*** Stack trace:" << std::endl;
    }
    
    for (int i = 0; i < entries.size(); ++i) {
        stacktrace::entry entry = entries[i];
        entry.file = getTail(entry.file);
        
        // skip certain entries for clarity
        if (STATIC_VARIABLE(STACK_TRACE_SHOULD_FILTER)
                && (shouldFilterOutFromStackTrace(entry.function)
                    || shouldFilterOutFromStackTrace(entry.file)
                    || shouldFilterOutFromStackTrace(entry.lineStr))) {
            continue;
        }
        
        // show Main() as main() to hide hidden case-change by Stanford C++ lib internals
        if (startsWith(entry.function, "Main(")) {
            entry.function.replace(0, 5, "main(");
        }

        // for some reason, some functions don't show () parens after; add them
        if (!entry.function.empty() && !stringContains(entry.function, "(")) {
            entry.function += "()";
        }

        // fix main to hide int/char**
        if (entry.function == "main(int, char**)") {
            entry.function = "main()";
        }

        // fix qMain => main to hide Qt main renaming
        if (entry.function == "qMain()") {
            entry.function = "main()";
        }

        std::string lineStr = "";
        if (!entry.lineStr.empty()) {
            lineStr = trimEnd(entry.lineStr);
            if (lineStr == "?? ??:0") {
                lineStr = "(unknown)";
            }

            if (entry.line == 0 && stringContains(lineStr, ":")) {
                Vector<std::string> tokens = stringSplit(lineStr, ":");
                if (stringIsInteger(tokens[tokens.size() - 1])) {
                    entry.line = stringToInteger(tokens[tokens.size() - 1]);
                }
            }
        }
        if (entry.lineStr.empty() && entry.line > 0) {
            lineStr = "line " + std::to_string(entry.line);
        }
        
        // we use a temporary 'lineout' because cerr aggressively flushes on <<,
        // leading to awkward line breaks in the output pane
        std::ostringstream lineout;
        lineout << "*** " << std::left << std::setw(lineStrLength) << lineStr
                  << "  " << entry.function;
        out << lineout.str() << std::endl;
        
        // don't show entries beneath the student's main() function, for simplicity
        if (entry.function == "main"
                || entry.function == "main()"
                || entry.function == "main(int, char**)"
                || entry.function == "qMain"
                || entry.function == "qMain()") {
            break;
        }
    }
    if (entries.size() == 1 && fakeStackPtr && entries[0].address == fakeStackPtr) {
        out << "*** (partial stack due to crash)" << std::endl;
    }

    if (STATIC_VARIABLE(STACK_TRACE_SHOW_TOP_BOTTOM_BARS) && lineStrLength > 0) {
        std::ostringstream lineout;
        lineout << "*** " << std::string(lineStrLength + 2 + funcNameLength, '=');
        out << lineout.str() << std::endl;
    }
    
    out << "***" << std::endl;
    out << "*** To learn more about the crash, we strongly" << std::endl;
    out << "*** suggest running your program under the debugger." << std::endl;
    out << "***" << std::endl;
}

// macro to avoid lots of redundancy in catch statements below
#ifdef _WIN32
#define THROW_NOT_ON_WINDOWS(ex)
#else
#define THROW_NOT_ON_WINDOWS(ex) throw(ex)
#endif // _WIN32

#define FILL_IN_EXCEPTION_TRACE(ex, kind, desc) \
    {\
    std::string __kind = (kind); \
    std::string __desc = (desc); \
    if ((!__kind.empty())) { stringReplaceInPlace(msg, DEFAULT_EXCEPTION_KIND, __kind); } \
    if ((!__desc.empty())) { stringReplaceInPlace(msg, DEFAULT_EXCEPTION_DETAILS, __desc); } \
    out << msg; \
    out.flush(); \
    printStackTrace(out); \
    THROW_NOT_ON_WINDOWS(ex); \
    }

#define FILL_IN_EXCEPTION_TRACE_AND_THROW_ERROREXCEPTION(ex, kind, desc) \
    {\
    std::string __kind = (kind); \
    std::string __desc = (desc); \
    if ((!__kind.empty())) { stringReplaceInPlace(msg, DEFAULT_EXCEPTION_KIND, __kind); } \
    if ((!__desc.empty())) { stringReplaceInPlace(msg, DEFAULT_EXCEPTION_DETAILS, __desc); } \
    out << msg; \
    printStackTrace(out); \
    ErrorException errorEx(out.str()); \
    errorEx.setKind(kind); \
    THROW_NOT_ON_WINDOWS(errorEx); \
    }

static void signalHandlerDisable() {
    for (int sig : STATIC_VARIABLE(SIGNALS_HANDLED)) {
        signal(sig, SIG_DFL);
    }
}

#ifndef _WIN32
void stanfordCppLibPosixSignalHandler(int sig, siginfo_t* /*siginfo*/, void* /*context*/) {
    stanfordCppLibSignalHandler(sig);
}
#endif

static void signalHandlerEnable() {
    bool handled = false;
#ifdef SHOULD_USE_SIGNAL_STACK
#if !defined(_WIN32)
    // alternate stack on Linux for stack overflows
    static uint8_t alternate_stack[SIGSTKSZ];
    stack_t ss = {};
    ss.ss_sp = (void*) alternate_stack;
    ss.ss_size = SIGSTKSZ;
    ss.ss_flags = 0;
    sigaltstack(&ss, nullptr);
    
    struct sigaction sig_action = {};
    sig_action.sa_sigaction = stanfordCppLibPosixSignalHandler;
    sigemptyset(&sig_action.sa_mask);
#ifdef __APPLE__
    // backtrace() doesn't work on OS X when we use an alternate stack
    sig_action.sa_flags = SA_SIGINFO;
#else
    sig_action.sa_flags = SA_SIGINFO | SA_ONSTACK;
#endif // __APPLE__
    sigaction(SIGSEGV, &sig_action, nullptr);
    sigaction(SIGFPE,  &sig_action, nullptr);
    sigaction(SIGILL,  &sig_action, nullptr);
    sigaction(SIGTERM, &sig_action, nullptr);
    sigaction(SIGUSR1, &sig_action, nullptr);
#ifdef SPL_AUTOGRADER_MODE
    sigaction(SIGINT,  &sig_action, nullptr);
#else // not SPL_AUTOGRADER_MODE
    sigaction(SIGABRT, &sig_action, nullptr);
#endif // SPL_AUTOGRADER_MODE
    handled = true;
#endif
#endif // SHOULD_USE_SIGNAL_STACK

    if (!handled) {
        for (int sig : STATIC_VARIABLE(SIGNALS_HANDLED)) {
            signal(sig, stanfordCppLibSignalHandler);
        }
    }
}

/*
 * A general handler for process signals.
 * Prints details about the signal and then tries to print a stack trace.
 */
static void stanfordCppLibSignalHandler(int sig) {
#ifndef SPL_AUTOGRADER_MODE
    // turn the signal handler off (should run only once; avoid infinite cycle)
    signalHandlerDisable();
#endif // SPL_AUTOGRADER_MODE

    // tailor the error message to the kind of signal that occurred
    std::string SIGNAL_KIND = "A fatal error";
    std::string SIGNAL_DETAILS = "No details were provided about the error.";
    if (sig == SIGSEGV) {
        SIGNAL_KIND = "A segmentation fault (SIGSEGV)";
        SIGNAL_DETAILS = "This typically happens when you try to dereference a pointer\n*** that is null or invalid.";
    } else if (sig == SIGABRT) {
        SIGNAL_KIND = "An abort error (SIGABRT)";
        SIGNAL_DETAILS = "This error is thrown by system functions that detect corrupt state.";
    } else if (sig == SIGILL) {
        SIGNAL_KIND = "An illegal instruction error (SIGILL)";
        SIGNAL_DETAILS = "This typically happens when you have corrupted your program's memory.";
    } else if (sig == SIGFPE) {
        SIGNAL_KIND = "An arithmetic error (SIGFPE)";
        SIGNAL_DETAILS = "This typically happens when you divide by 0 or produce an overflow.";
    } else if (sig == SIGINT) {
        SIGNAL_KIND = "An interrupt error (SIGINT)";
        SIGNAL_DETAILS = "This typically happens when your code timed out because it was stuck in an infinite loop.";
    } else if (sig == SIGSTACK) {
        SIGNAL_KIND = "A stack overflow";
        SIGNAL_DETAILS = "This can happen when you have a function that calls itself infinitely.";
    } else if (sig == SIGUSR1) {
        SIGNAL_KIND = "Custom signal 1";
        SIGNAL_DETAILS = "This can happen when you produce infinite output in your code.";
    }
    
#ifndef SPL_AUTOGRADER_MODE
    std::cerr << std::endl;
    std::cerr << "***" << std::endl;
    std::cerr << "*** STANFORD C++ LIBRARY" << std::endl;
    std::cerr << (std::string("*** ") + SIGNAL_KIND + " occurred during program execution.") << std::endl;
    std::cerr << (std::string("*** ") + SIGNAL_DETAILS) << std::endl;
    std::cerr << "***" << std::endl;
    
//    if (sig != SIGSTACK) {
        exceptions::printStackTrace();
//    } else {
//        std::string line;
//        stacktrace::addr2line(stacktrace::getFakeCallStackPointer(), line);
//        std::cerr << "*** (unable to print stack trace because of stack memory corruption.)" << std::endl;
//        std::cerr << "*** " << line << std::endl;
//    }
    std::cerr.flush();

    // if in autograder mode, swallow the signal;
    // if in student code, let it bubble out to crash the app
    raise(sig == SIGSTACK ? SIGABRT : sig);
#else // SPL_AUTOGRADER_MODE
    // throw an exception
    std::ostringstream out;
    out << SIGNAL_KIND << "." << std::endl;
    out << SIGNAL_DETAILS << std::endl;
    error(out.str());
#endif // SPL_AUTOGRADER_MODE
}

// puts "*** " before each line for multi-line error messages
static std::string insertStarsBeforeEachLine(const std::string& s) {
    std::string result;
    for (std::string line : stringSplit(s, "\n")) {
        if (!result.empty()) {
            if (!startsWith(line, "***")) {
                line = "*** " + line;
            }
            result += "\n";
        }
        result += line;
    }
    return result;
}

/*
 * A general handler for any uncaught exception.
 * Prints details about the exception and then tries to print a stack trace.
 */
[[noreturn]] static void stanfordCppLibTerminateHandler() {
    std::string DEFAULT_EXCEPTION_KIND = "An exception";
    std::string DEFAULT_EXCEPTION_DETAILS = "(unknown exception details)";
    
    std::string msg;
    msg += "\n";
    msg += "***\n";
    msg += "*** STANFORD C++ LIBRARY \n";
    msg += "*** " + DEFAULT_EXCEPTION_KIND + " occurred during program execution: \n";
    msg += "*** " + DEFAULT_EXCEPTION_DETAILS + "\n";
    msg += "***\n";
    
    std::ostream& out = std::cerr;   // used by FILL_IN_EXCEPTION_TRACE macro
    try {
        signalHandlerDisable();   // don't want both a signal AND a terminate() call
        throw;   // re-throws the exception that already occurred
    } catch (const ErrorException& ex) {
        if (ex.hasStackTrace()) {
            ex.dump();
        } else {
            FILL_IN_EXCEPTION_TRACE(ex, "An ErrorException", insertStarsBeforeEachLine(ex.what()));
        }
    } catch (const std::exception& ex) {
        FILL_IN_EXCEPTION_TRACE(ex, "A C++ exception", insertStarsBeforeEachLine(ex.what()));
    } catch (const std::string& str) {
        FILL_IN_EXCEPTION_TRACE(str, "A string exception", insertStarsBeforeEachLine(str));
    } catch (char const* str) {
        FILL_IN_EXCEPTION_TRACE(str, "A string exception", insertStarsBeforeEachLine(str));
    } catch (int n) {
        FILL_IN_EXCEPTION_TRACE(n, "An int exception", std::to_string(n));
    } catch (long l) {
        FILL_IN_EXCEPTION_TRACE(l, "A long exception", std::to_string(l));
    } catch (char c) {
        FILL_IN_EXCEPTION_TRACE(c, "A char exception", charToString(c));
    } catch (bool b) {
        FILL_IN_EXCEPTION_TRACE(b, "A bool exception", boolToString(b));
    } catch (double d) {
        FILL_IN_EXCEPTION_TRACE(d, "A double exception", realToString(d));
    } catch (...) {
        std::string ex = "Unknown";
        FILL_IN_EXCEPTION_TRACE(ex, "An exception", std::string());
    }

    abort();   // terminate the program with a SIGABRT signal
}

/*
 * A general handler for any exception thrown that is missing from the throw()
 * clause of a function header.
 * Prints details about the exception and then tries to print a stack trace.
 */
static void stanfordCppLibUnexpectedHandler() {
    std::string DEFAULT_EXCEPTION_KIND = "An exception";
    std::string DEFAULT_EXCEPTION_DETAILS = "(unknown exception details)";

    std::string msg;
    msg += "\n";
    msg += "***\n";
    msg += "*** STANFORD C++ LIBRARY \n";
    msg += "*** " + DEFAULT_EXCEPTION_KIND + " occurred during program execution: \n";
    msg += "*** " + DEFAULT_EXCEPTION_DETAILS + "\n";
    msg += "***\n";

    std::string kind = "error";
    std::string message = "";
    try {
        throw;   // re-throws the exception that already occurred
    } catch (bool b) {
        kind = "bool";
        message = boolToString(b);
    } catch (char c) {
        kind = "char";
        message = charToString(c);
    } catch (char const* str) {
        kind = "string";
        message = str;
    } catch (double d) {
        kind = "double";
        message = realToString(d);
    } catch (const ErrorException& ex) {
        kind = "error";
        message = ex.what();
    } catch (const std::exception& ex) {
        kind = "exception";
        message = ex.what();
    } catch (int n) {
        kind = "int";
        message = std::to_string(n);
    } catch (long l) {
        kind = "long";
        message = std::to_string(l);
    } catch (std::string str) {
        kind = "string";
        message = str;
    } catch (...) {
        kind = "unknown";
    }

    ErrorException errorEx(message);
    errorEx.setKind(kind);
    throw errorEx;
}

} // namespace exceptions


/////////////////////// END code extracted from StanfordCPPLib/system/exceptions.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/util/recursion.cpp ///////////////////////
/*
 * File: recursion.cpp
 * -------------------
 * This file implements the recursion.h interface.
 */

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

int getRecursionIndentLevel() {
    // constructing the following object jumps into fancy code in call_stack_gcc/windows.cpp
    // to rebuild the stack trace; implementation differs for each operating system
    stacktrace::call_stack trace;
    Vector<stacktrace::entry> entries = trace.stack;

    std::string currentFunction = "";
    int currentFunctionCount = 0;
    for (int i = 0; i < entries.size(); ++i) {
        // remove references to std:: namespace
        if (exceptions::shouldFilterOutFromStackTrace(entries[i].function)
                || entries[i].function.find("recursionIndent(") != std::string::npos
                || entries[i].function.find("getRecursionIndentLevel(") != std::string::npos) {
            continue;
        } else if (currentFunction.empty()) {
            currentFunction = entries[i].function;
            currentFunctionCount = 1;
        } else if (entries[i].function == currentFunction) {
            currentFunctionCount++;
        } else {
            break;
        }
    }
    return currentFunctionCount;
}

std::string recursionIndent(const std::string& indenter) {
    int indent = getRecursionIndentLevel();
    std::string result = "";
    for (int i = 0; i < indent - 1; i++) {
        result += indenter;
    }
    return result;
}

/////////////////////// END code extracted from StanfordCPPLib/util/recursion.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/util/direction.cpp ///////////////////////
/*
 * File: direction.cpp
 * -------------------
 * This file implements the direction.h interface.
 * 
 * @version 2016/08/04
 * - fixed operator >> to not throw errors
 * @version 2014/10/08
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

/*
 * Implementation notes: leftFrom, rightFrom, opposite
 * ---------------------------------------------------
 * These functions use the remainder operator to cycle through the
 * internal values of the enumeration type.  Note that the leftFrom
 * function cannot subtract 1 from the direction because the result
 * might then be negative; adding 3 achieves the same effect but
 * ensures that the values remain positive.
 */

Direction leftFrom(Direction dir) {
    return Direction((dir + 3) % 4);
}

Direction rightFrom(Direction dir) {
    return Direction((dir + 1) % 4);
}

Direction opposite(Direction dir) {
    return Direction((dir + 2) % 4);
}

/*
 * Implementation notes: directionToString
 * ---------------------------------------
 * The C++ compiler requires the default clause to ensure that this
 * function always returns a string, even if the direction is not one
 * of the legal values.
 */

std::string directionToString(Direction dir) {
    switch (dir) {
    case NORTH:
        return "NORTH";
    case EAST:
        return "EAST";
    case SOUTH:
        return "SOUTH";
    default:
    // case WEST:
        return "WEST";   // BUGFIX 2014/07/09: removed unreachable 'default' case
    }
}

/*
 * Implementation notes: <<
 * ------------------------
 * This operator must return the stream by reference after printing
 * the value.  The operator << returns this stream, so the function
 * can be implemented as a single line.
 */

std::ostream& operator <<(std::ostream& os, const Direction& dir) {
    return os << directionToString(dir);
}

/*
 * Implementation notes: >>
 * ------------------------
 * This implementation uses the TokenScanner to read tokens from the
 * stream.
 */

std::istream& operator >>(std::istream& is, Direction& dir) {
    TokenScanner scanner(is);
    scanner.ignoreWhitespace();
    std::string token = toUpperCase(scanner.nextToken());
    if (token == "") {
        dir = Direction(-1);
    } else if (startsWith("NORTH", token)) {
        dir = NORTH;
    } else if (startsWith("EAST", token)) {
        dir = EAST;
    } else if (startsWith("SOUTH", token)) {
        dir = SOUTH;
    } else if (startsWith("WEST", token)) {
        dir = WEST;
    } else {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
        error("Direction::operator >>: Unrecognized direction \"" + token + "\"");
#endif
        is.setstate(std::ios_base::failbit);
        return is;
    }
    return is;
}

/*
 * Implementation notes: ++
 * ------------------------
 * The int parameter in the signature for this operator is a marker used
 * by the C++ compiler to identify the suffix form of the operator.  Note
 * that the value after incrementing a variable containing WEST will be
 * out of the Direction range.  That fact will not cause a problem if
 * this operator is used only in the for loop idiom for which it is defined.
 */

Direction operator ++(Direction& dir, int) {
    Direction old = dir;
    dir = Direction(dir + 1);
    return old;
}

/////////////////////// END code extracted from StanfordCPPLib/util/direction.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/util/gmath.cpp ///////////////////////
/*
 * File: gmath.cpp
 * ---------------
 * This file implements the gmath.h interface.  In all cases, the
 * implementation for each function requires only one line of code,
 * which makes detailed documentation unnecessary.
 *
 * @version 2018/11/22
 * - added headless mode support
 * - alphabetized methods
 * @version 2016/10/14
 * - modified floating-point equality tests to use floatingPointEqual function
 */

#define INTERNAL_INCLUDE 1

#include <cmath>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

extern const double PI = 3.14159265358979323846;
extern const double E  = 2.71828182845904523536;

double cosDegrees(double angle) {
    return cos(toRadians(angle));
}

int countDigits(int n, int base) {
    if (base <= 0) {
        error("countDigits: base must be 1 or greater");
    }
    if (n == 0) {
        return 0;
    } else if (n < 0) {
        n = -n;
    }

    int digits = 0;
    for (int temp = n; temp > 0 && digits < 65; temp /= base) {
        digits++;
    }
    return digits;
}

double sinDegrees(double angle) {
    return sin(toRadians(angle));
}

double tanDegrees(double angle) {
    return tan(toRadians(angle));
}

double toDegrees(double radians) {
    return radians * 180 / PI;
}

double toRadians(double degrees) {
    return degrees * PI / 180;
}

double vectorAngle(double x, double y) {
    return floatingPointEqual(x, 0) && floatingPointEqual(y, 0)
            ? 0 : toDegrees(atan2(-y, x));
}

#ifndef SPL_HEADLESS_MODE
double vectorAngle(const GPoint& pt) {
    return vectorAngle(pt.getX(), pt.getY());
}
#endif // SPL_HEADLESS_MODE

double vectorAngle(const Point& pt) {
    return vectorAngle(pt.getX(), pt.getY());
}

double vectorDistance(double x, double y) {
    return sqrt(x * x + y * y);
}

#ifndef SPL_HEADLESS_MODE
double vectorDistance(const GPoint& pt) {
    return vectorDistance(pt.getX(), pt.getY());
}
#endif // SPL_HEADLESS_MODE

double vectorDistance(const Point& pt) {
    return vectorDistance(pt.getX(), pt.getY());
}

/////////////////////// END code extracted from StanfordCPPLib/util/gmath.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/util/point.cpp ///////////////////////
/*
 * File: point.cpp
 * ---------------
 * This file implements the point.h interface.
 * 
 * @version 2018/11/22
 * - added headless mode support
 * @version 2017/09/29
 * - updated to use composite hashCode function
 * @version 2014/10/08
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#include <string>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

Point::Point() {
    x = 0;
    y = 0;
}

Point::Point(int x, int y) {
    this->x = x;
    this->y = y;
}

#ifndef SPL_HEADLESS_MODE
Point::Point(const GPoint& point) {
    this->x = (int) point.getX();
    this->y = (int) point.getY();
}
#endif // SPL_HEADLESS_MODE

int Point::getX() const {
    return x;
}

int Point::getY() const {
    return y;
}

std::string Point::toString() const {
    return "(" + std::to_string(x) + "," + std::to_string(y) + ")";
}

bool Point::operator ==(const Point& p2) const {
    return (x == p2.x) && (y == p2.y);
}

bool Point::operator !=(const Point& p2) const {
    return (x != p2.x) || (y != p2.y);
}

std::ostream& operator <<(std::ostream& os, const Point& pt) {
    return os << pt.toString();
}

int hashCode(const Point& pt) {
    return hashCode(pt.getX(), pt.getY());
}

/////////////////////// END code extracted from StanfordCPPLib/util/point.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/util/random.cpp ///////////////////////
/*
 * File: random.cpp
 * ----------------
 * This file implements the random.h interface.
 * 
 * @version 2019/05/16
 * - added randomColor that takes min/max RGB
 * @version 2017/10/05
 * - added randomFeedClear
 * @version 2017/09/28
 * - moved random 'feed' functions into autograder namespace
 * - ensure that randomly fed integers are within the specified range
 * @version 2016/10/04
 * - removed all static variables (replaced with STATIC_VARIABLE macros)
 * @version 2016/08/02
 * - added randomColor, randomColorString
 * @version 2014/10/19
 * - alphabetized functions
 * @version 2014/10/08
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <iomanip>
#include <queue>
#include <sstream>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

/* Private function prototype */

static void initRandomSeed();

/* internal buffer of fixed random numbers to return; used by autograders */
STATIC_VARIABLE_DECLARE_COLLECTION_EMPTY(std::queue<bool>, fixedBools)
STATIC_VARIABLE_DECLARE_COLLECTION_EMPTY(std::queue<int>, fixedInts)
STATIC_VARIABLE_DECLARE_COLLECTION_EMPTY(std::queue<double>, fixedReals)

namespace autograder {
void randomFeedBool(bool value) {
    STATIC_VARIABLE(fixedBools).push(value);
}

void randomFeedClear() {
    STATIC_VARIABLE(fixedBools) = std::queue<bool>();
    STATIC_VARIABLE(fixedInts) = std::queue<int>();
    STATIC_VARIABLE(fixedReals) = std::queue<double>();
}

void randomFeedInteger(int value) {
    STATIC_VARIABLE(fixedInts).push(value);
}

void randomFeedReal(double value) {
    STATIC_VARIABLE(fixedReals).push(value);
}
}
/* end 'fixed' internal stuff */

bool randomBool() {
    return randomChance(0.5);
}

/*
 * 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) {
    if (!STATIC_VARIABLE(fixedBools).empty()) {
        bool top = STATIC_VARIABLE(fixedBools).front();
        STATIC_VARIABLE(fixedBools).pop();
        return top;
    }
    initRandomSeed();
    return randomReal(0, 1) < p;
}

int randomColor() {
    if (!STATIC_VARIABLE(fixedInts).empty()) {
        int top = STATIC_VARIABLE(fixedInts).front();
        STATIC_VARIABLE(fixedInts).pop();
        return top & 0x00ffffff;
    }
    initRandomSeed();
    return rand() & 0x00ffffff;
}

int randomColor(int minRGB, int maxRGB) {
    if (!STATIC_VARIABLE(fixedInts).empty()) {
        return randomColor();
    }
    if (minRGB < 0 || minRGB > 255 || maxRGB < 0 || maxRGB > 255
            || minRGB > maxRGB) {
        error("randomColor: min/max values out of range");
    }
    int r = randomInteger(minRGB, maxRGB);
    int g = randomInteger(minRGB, maxRGB);
    int b = randomInteger(minRGB, maxRGB);
    return r << 16 | g << 8 | b;
}

// see convertRGBToColor in gcolor.h (repeated here to avoid Qt dependency)
std::string randomColorString() {
    int rgb = randomColor();
    std::ostringstream os;
    os << std::hex << std::uppercase << "#";
    os << std::setw(2) << std::setfill('0') << (rgb >> 16 & 0xFF);
    os << std::setw(2) << std::setfill('0') << (rgb >> 8 & 0xFF);
    os << std::setw(2) << std::setfill('0') << (rgb & 0xFF);
    return os.str();
}

std::string randomColorString(int minRGB, int maxRGB) {
    int rgb = randomColor(minRGB, maxRGB);
    std::ostringstream os;
    os << std::hex << std::uppercase << "#";
    os << std::setw(2) << std::setfill('0') << (rgb >> 16 & 0xFF);
    os << std::setw(2) << std::setfill('0') << (rgb >> 8 & 0xFF);
    os << std::setw(2) << std::setfill('0') << (rgb & 0xFF);
    return os.str();
}

/*
 * 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) {
    if (!STATIC_VARIABLE(fixedInts).empty()) {
        int top = STATIC_VARIABLE(fixedInts).front();
        STATIC_VARIABLE(fixedInts).pop();
        if (top < low || top > high) {
            // make sure the value is in the given range
            // (assumes that low/high don't overflow int range)
            int range = high - low + 1;
            top = low + std::abs(top) % range;
        }
        return top;
    }
    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) {
    if (!STATIC_VARIABLE(fixedReals).empty()) {
        double top = STATIC_VARIABLE(fixedReals).front();
        STATIC_VARIABLE(fixedReals).pop();
        return top;
    }
    initRandomSeed();
    double d = rand() / (double(RAND_MAX) + 1);
    double s = d * (high - low);
    return low + s;
}

/*
 * 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(nullptr)));
        rand();   // BUGFIX: throwaway call to get randomness going
        _initialized = true;
    }
}

/////////////////////// END code extracted from StanfordCPPLib/util/random.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/util/regexpr.cpp ///////////////////////
/*
 * File: regexpr.cpp
 * -----------------
 * Implementation of the functions in regexpr.h.
 * See regexpr.h for documentation of each function.
 *
 * @author Marty Stepp
 * @version 2018/12/16
 * - added CodeStepByStep disabling of regexes
 * @version 2018/11/22
 * - added headless (non-Qt) mode support
 * @version 2015/07/05
 * - removed static global Platform variable, replaced by getPlatform as needed
 * @version 2014/10/14
 * - removed regexMatchCountWithLines for simplicity
 * 2014/10/08
 * - removed 'using namespace' statement
 * @since 2014/03/01
 */

#define INTERNAL_INCLUDE 1

#ifndef SPL_HEADLESS_MODE
#include <QtGlobal>
#endif // SPL_HEADLESS_MODE
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

#if defined(SPL_CODESTEPBYSTEP) || QT_VERSION < QT_VERSION_CHECK(5, 9, 0)
bool regexMatch(const std::string& /*s*/, const std::string& /*regexp*/) {
    return false;   // not supported
}

int regexMatchCount(const std::string& /*s*/, const std::string& /*regexp*/) {
    return 0;   // not supported
}

void regexMatchCountWithLines(const std::string& /*s*/, const std::string& /*regexp*/,
                             Vector<int>& /*linesOut*/) {
    // empty; not supported
}

std::string regexReplace(const std::string& s, const std::string& /*regexp*/, const std::string& /*replacement*/, int /*limit*/) {
    return s;   // not supported
}

#else // QT_VERSION

// C++ regex support
#include <iterator>
#include <regex>

bool regexMatch(const std::string& s, const std::string& regexp) {
    std::regex reg(regexp);
    std::smatch match;
    return std::regex_search(s, match, reg);
}

int regexMatchCount(const std::string& s, const std::string& regexp) {
    std::regex reg(regexp);
    auto it1 = std::sregex_iterator(s.begin(), s.end(), reg);
    auto it2 = std::sregex_iterator();
    return std::distance(it1, it2);
}

void regexMatchCountWithLines(const std::string& s, const std::string& regexp,
                             Vector<int>& linesOut) {
    linesOut.clear();

    // keep a running index and line#, and each time we find a regex match,
    // "walk" forward to its index.  when we see a \n, increment line number
    int currentIndex = 0;
    int currentLine = 1;

    // get all regex matches by character position/index
    std::regex reg(regexp);
    for (std::sregex_iterator itr = std::sregex_iterator(s.begin(), s.end(), reg),
            end = std::sregex_iterator();
            itr != end;
            ++itr) {
        std::smatch match = *itr;
        int matchIndex = (int) match.position();
        while (currentIndex < (int) s.length() && currentIndex < matchIndex) {
            if (s[currentIndex] == '\n') {
                currentLine++;
            }
            currentIndex++;
        }
        linesOut.add(currentLine);
    }
}

std::string regexReplace(const std::string& s, const std::string& regexp, const std::string& replacement, int limit) {
    std::regex reg(regexp);
    std::string result;
    if (limit == 1) {
        // replace single occurrence
        result = std::regex_replace(s, reg, replacement,
                                    std::regex_constants::format_first_only);
    } else if (limit <= 0) {
        // replace all
        result = std::regex_replace(s, reg, replacement);
    } else {
        error("regexReplace: given limit not supported.");
    }
    return result;
}
#endif // QT_VERSION

// this function can be implemented the same way whether regexes are available or not
int regexMatchCountWithLines(const std::string& s, const std::string& regexp, std::string& linesOut) {
    Vector<int> linesOutVec;
    regexMatchCountWithLines(s, regexp, linesOutVec);

    // concatenate the vector into a string like "1, 4, 7, 7, 19"
    linesOut = "";
    if (!linesOutVec.isEmpty()) {
        linesOut += std::to_string(linesOutVec[0]);
        for (int i = 1; i < linesOutVec.size(); i++) {
            linesOut += ", " + std::to_string(linesOutVec[i]);
        }
    }
    return linesOutVec.size();
}

/////////////////////// END code extracted from StanfordCPPLib/util/regexpr.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/util/strlib.cpp ///////////////////////
/*
 * File: strlib.cpp
 * ----------------
 * This file implements the strlib.h interface.
 * 
 * @version 2018/11/14
 * - added std::to_string for bool, char, pointer, and generic template type T
 * - bug fix for pointerToString (was putting two "0x" prefixes)
 * @version 2018/09/02
 * - added padLeft, padRight
 * @version 2017/10/24
 * - print nullptr instead of null in uppercase
 * @version 2016/11/07
 * - bug fix: urlDecode throws error on invalid encodings (courtesy GitHub @scinart)
 * @version 2016/10/30
 * - alphabetized functions
 * - added overloads that take type char instead of string:
 *   stringContains, stringIndexOf, stringJoin, stringLastIndexOf, stringReplace,
 *   stringSplit, toLowerCase, toUpperCase
 * @version 2016/10/13
 * - modified writeQuotedString to return ostream
 * @version 2016/08/03
 * - modified readQuotedString not to throw error() on parse failures
 *   (needed to support idiomatic silent-failing >> operators)
 * @version 2015/11/07
 * - fixed bugs in urlDecode (wasn't decoding % sequences properly, oops)
 * @version 2015/10/26
 * - added charToInteger/integerToChar functions
 * @version 2015/06/19
 * - slight bug fix to make stringToInteger functions compile with int radix
 * @version 2015/05/22
 * - slight bug fix in stringToBool function
 * @version 2014/10/31
 * - fixed infinite loop bug in stringReplace function
 * @version 2014/10/19
 * - alphabetized functions
 * - added several 'inPlace' variants of existing functions that return strings
 * @version 2014/10/08
 * - removed 'using namespace' statement
 */

#define INTERNAL_INCLUDE 1

#include <cctype>
#include <iomanip>
#include <iostream>
#include <sstream>

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

/* Function prototypes */

std::string boolToString(bool b) {
    return (b ? "true" : "false");
}

std::string boolToString(int b) {
    return (b ? "true" : "false");
}

int charToInteger(char c) {
    if (c < '0' || c > '9') {
        std::ostringstream out;
        out << "charToInteger: character is not numeric: '" << c
            << "' (ASCII value " << (int) c << ")";
        error(out.str());
    }
    return c - '0';
}

std::string charToString(char c) {
    std::string s;
    s += c;
    return s;
}

std::string doubleToString(double d) {
    return realToString(d);
}

bool endsWith(const std::string& str, char suffix) {
    return str.length() > 0 && str[str.length() - 1] == suffix;
}

bool endsWith(const std::string& str, const std::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;
}

/*
 * 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(const std::string& s1, const std::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;
}

std::string htmlDecode(const std::string& s) {
    std::string result = s;
    stringReplaceInPlace(result, "&lt;", "<");
    stringReplaceInPlace(result, "&gt;", ">");
    stringReplaceInPlace(result, "&quot;", "\"");
    stringReplaceInPlace(result, "&amp;", "&");
    return result;
}

std::string htmlEncode(const std::string& s) {
    std::string result = s;
    stringReplaceInPlace(result, "&", "&amp;");
    stringReplaceInPlace(result, "<", "&lt;");
    stringReplaceInPlace(result, ">", "&gt;");
    stringReplaceInPlace(result, "\"", "&quot;");
    return result;
}

char integerToChar(int n) {
    if (n < 0 || n > 9) {
        std::ostringstream out;
        out << "integerToChar: number must be between 0-9: " << n;
        error(out.str());
    }
    return (char) (n + '0');
}

/*
 * Implementation notes: numeric conversion
 * ----------------------------------------
 * These functions use the <sstream> library to perform the conversion.
 */
std::string integerToString(int n, int radix) {
    if (radix <= 0) {
        error("integerToString: Illegal radix: " + std::to_string(radix));
    }
    std::ostringstream stream;
    if (radix != 10) {
        stream << std::setbase(radix);
    }
    stream << n;
    return stream.str();
}

std::string longToString(long n, int radix) {
    if (radix <= 0) {
        error("longToString: Illegal radix: " + std::to_string(radix));
    }
    std::ostringstream stream;
    if (radix != 10) {
        stream << std::setbase(radix);
    }
    stream << n;
    return stream.str();
}

std::string padLeft(const std::string& s, int length, char fill) {
    if ((int) s.length() >= length) {
        return s;
    } else {
        std::ostringstream out;
        for (int i = 0, count = length - (int) s.length(); i < count; i++) {
            out << fill;
        }
        out << s;
        return out.str();
    }
}

std::string padRight(const std::string& s, int length, char fill) {
    if ((int) s.length() >= length) {
        return s;
    } else {
        std::ostringstream out;
        out << s;
        for (int i = 0, count = length - (int) s.length(); i < count; i++) {
            out << fill;
        }
        return out.str();
    }
}

std::string pointerToString(void* p) {
    if (p) {
        std::ostringstream stream;
        stream << std::hex;
        stream << p;
        return stream.str();
    } else {
        return "nullptr";
    }
}

std::string realToString(double d) {
    std::ostringstream stream;
    stream << std::uppercase << d;
    return stream.str();
}

bool startsWith(const std::string& str, char prefix) {
    return str.length() > 0 && str[0] == prefix;
}

bool startsWith(const std::string& str, const std::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 stringIsBool(const std::string& str) {
    return str == "true" || str == "false";
}

bool stringIsDouble(const std::string& str) {
    return stringIsReal(str);
}

bool stringIsInteger(const std::string& str, int radix) {
    if (radix <= 0) {
        error("stringIsInteger: Illegal radix: " + std::to_string(radix));
    }
    std::istringstream stream(trim(str));
    stream >> std::setbase(radix);
    int value;
    stream >> value;
    return !(stream.fail() || !stream.eof());
}

bool stringIsLong(const std::string& str, int radix) {
    if (radix <= 0) {
        error("stringIsLong: Illegal radix: " + std::to_string(radix));
    }
    std::istringstream stream(trim(str));
    stream >> std::setbase(radix);
    long value;
    stream >> value;
    return !(stream.fail() || !stream.eof());
}

bool stringIsReal(const std::string& str) {
    std::istringstream stream(trim(str));
    double value;
    stream >> value;
    return !(stream.fail() || !stream.eof());
}

bool stringContains(const std::string& s, char ch) {
    return s.find(ch) != std::string::npos;
}

bool stringContains(const std::string& s, const std::string& substring) {
    return s.find(substring) != std::string::npos;
}

int stringIndexOf(const std::string& s, char ch, int startIndex) {
    size_t index = s.find(ch, (size_t) startIndex);
    if (index == std::string::npos) {
        return -1;
    } else {
        return index;
    }
}

int stringIndexOf(const std::string& s, const std::string& substring, int startIndex) {
    size_t index = s.find(substring, (size_t) startIndex);
    if (index == std::string::npos) {
        return -1;
    } else {
        return index;
    }
}

std::string stringJoin(const Vector<std::string>& v, char delimiter) {
    std::string delim = charToString(delimiter);
    return stringJoin(v, delim);
}

std::string stringJoin(const Vector<std::string>& v, const std::string& delimiter) {
    if (v.isEmpty()) {
        return "";
    } else {
        std::ostringstream out;
        out << v[0];
        for (int i = 1; i < (int) v.size(); i++) {
            out << delimiter;
            out << v[i];
        }
        return out.str();
    }
}

int stringLastIndexOf(const std::string& s, char ch, int startIndex) {
    size_t index = s.rfind(ch, (size_t) startIndex);
    if (index == std::string::npos) {
        return -1;
    } else {
        return index;
    }
}

int stringLastIndexOf(const std::string& s, const std::string& substring, int startIndex) {
    size_t index = s.rfind(substring, (size_t) startIndex);
    if (index == std::string::npos) {
        return -1;
    } else {
        return index;
    }
}

std::string stringReplace(const std::string& str, char old, char replacement, int limit) {
    std::string str2 = str;
    stringReplaceInPlace(str2, old, replacement, limit);
    return str2;
}

std::string stringReplace(const std::string& str, const std::string& old, const std::string& replacement, int limit) {
    std::string str2 = str;
    stringReplaceInPlace(str2, old, replacement, limit);
    return str2;
}

int stringReplaceInPlace(std::string& str, char old, char replacement, int limit) {
    int count = 0;
    for (size_t i = 0, len = str.length(); i < len; i++) {
        if (str[i] == old) {
            str[i] = replacement;
            count++;
            if (limit > 0 && count >= limit) {
                break;
            }
        }
    }
    return count;
}

int stringReplaceInPlace(std::string& str, const std::string& old, const std::string& replacement, int limit) {
    int count = 0;
    size_t startIndex = 0;
    size_t rlen = replacement.length();
    while (limit <= 0 || count < limit) {
        size_t index = str.find(old, startIndex);
        if (index == std::string::npos) {
            break;
        }
        str.replace(index, old.length(), replacement);
        startIndex = index + rlen;
        count++;
    }
    return count;
}

Vector<std::string> stringSplit(const std::string& str, char delimiter, int limit) {
    std::string delim = charToString(delimiter);
    return stringSplit(str, delim, limit);
}

Vector<std::string> stringSplit(const std::string& str, const std::string& delimiter, int limit) {
    std::string str2 = str;
    Vector<std::string> result;
    int count = 0;
    size_t index = 0;
    while (limit < 0 || count < limit) {
        index = str2.find(delimiter);
        if (index == std::string::npos) {
            break;
        }
        result.add(str2.substr(0, index));
        str2.erase(str2.begin(), str2.begin() + index + delimiter.length());
        count++;
    }
    if ((int) str2.length() > 0) {
        result.add(str2);
    }

    return result;
}

bool stringToBool(const std::string& str) {
    if (str == "true" || str == "1") {
        return true;
    } else if (str == "false" || str == "0") {
        return false;
    }
    std::istringstream stream(trim(str));
    bool value;
    stream >> std::boolalpha >> value;
    if (stream.fail() || !stream.eof()) {
        error("stringToBool: Illegal bool format (" + str + ")");
    }
    return value;
}

char stringToChar(const std::string& str) {
    std::string str2 = trim(str);
    if ((int) str2.length() != 1) {
        error("stringToChar: string must contain exactly 1 non-whitespace character");
    }
    return str2[0];
}

double stringToDouble(const std::string& str) {
    return stringToReal(str);
}

int stringToInteger(const std::string& str, int radix) {
    if (radix <= 0) {
        error("stringToInteger: Illegal radix: " + std::to_string(radix));
    }
    std::istringstream stream(trim(str));
    stream >> std::setbase(radix);
    int value;
    stream >> value;
    if (stream.fail() || !stream.eof()) {
        error("stringToInteger: Illegal integer format: \"" + str + "\"");
    }
    return value;
}

long stringToLong(const std::string& str, int radix) {
    if (radix <= 0) {
        error("stringToLong: Illegal radix: " + std::to_string(radix));
    }
    std::istringstream stream(trim(str));
    stream >> std::setbase(radix);
    long value;
    stream >> value;
    if (stream.fail() || !stream.eof()) {
        error("stringToLong: Illegal long format \"" + str + "\"");
    }
    return value;
}

double stringToReal(const std::string& str) {
    std::istringstream stream(trim(str));
    double value;
    stream >> value;
    if (stream.fail() || !stream.eof()) {
        error("stringToReal: Illegal floating-point format (" + str + ")");
    }
    return value;
}

char toLowerCase(char ch) {
    return (char) tolower(ch);
}

std::string toLowerCase(const std::string& str) {
    std::string str2 = str;
    toLowerCaseInPlace(str2);
    return str2;
}

void toLowerCaseInPlace(std::string& str) {
    int nChars = str.length();
    for (int i = 0; i < nChars; i++) {
        str[i] = tolower(str[i]);
    }
}

char toUpperCase(char ch) {
    return (char) toupper(ch);
}

std::string toUpperCase(const std::string& str) {
    std::string str2 = str;
    toUpperCaseInPlace(str2);
    return str2;
}

void toUpperCaseInPlace(std::string& str) {
    int nChars = str.length();
    for (int i = 0; i < nChars; i++) {
        str[i] = toupper(str[i]);
    }
}

std::string trim(const std::string& str) {
    std::string str2 = str;
    trimInPlace(str2);
    return str2;
}

void trimInPlace(std::string& str) {
    trimEndInPlace(str);
    trimStartInPlace(str);
}

std::string trimEnd(const std::string& str) {
    std::string str2 = str;
    trimEndInPlace(str2);
    return str2;
}

void trimEndInPlace(std::string& str) {
    int end = (int) str.length();
    int finish = end;
    while (finish > 0 && isspace(str[finish - 1])) {
        finish--;
    }
    if (finish < end) {
        str.erase(finish, end - finish);
    }
}

std::string trimStart(const std::string& str) {
    std::string str2 = str;
    trimStartInPlace(str2);
    return str2;
}

void trimStartInPlace(std::string& str) {
    int start = 0;
    int finish = (int) str.length() - 1;
    while (start <= finish && isspace(str[start])) {
        start++;
    }
    if (start > 0) {
        str.erase(0, start);
    }
}

std::string urlDecode(const std::string& str) {
    std::ostringstream unescaped;
    for (std::string::const_iterator i = str.begin(), n = str.end(); i != n; ++i) {
        std::string::value_type c = (*i);
        if (isalnum(c) || c == '-' || c == '_' || c == '.' || c == '~' || c == '*') {
            unescaped << c;
        } else if (c == '+')  {
            unescaped << ' ';
        } else if (c == '%') {
            // throw error if string is invalid and doesn't have 2 char after,
            // or if it has non-hex chars here (courtesy GitHub @scinart)
            if (i + 2 >= n || !isxdigit(*(i + 1)) || !isxdigit(*(i + 2))) {
                error("urlDecode: Invalid percent-encoding");
            }

            // decode a URL-encoded ASCII character, e.g. %40 => &
            char ch1 = *(i + 1);
            char ch2 = *(i + 2);
            int hex1 = (isdigit(ch1) ? (ch1 - '0') : (toupper(ch1) - 'A' + 10));
            int hex2 = (isdigit(ch2) ? (ch2 - '0') : (toupper(ch2) - 'A' + 10));
            int decodedChar = (hex1 << 4) + hex2;
            unescaped << (char) decodedChar;
            i += 2;
        } else {
            std::ostringstream msg;
            msg << "urlDecode: Unexpected character in string: "
                << (int) c << " (" << c << ")";
            error(msg.str());
        }
    }

    return unescaped.str();
}

void urlDecodeInPlace(std::string& str) {
    str = urlDecode(str);   // no real efficiency gain here
}

std::string urlEncode(const std::string& str) {
    std::ostringstream escaped;
    escaped.fill('0');
    escaped << std::hex << std::uppercase;

    for (std::string::const_iterator i = str.begin(), n = str.end(); i != n; ++i) {
        std::string::value_type c = (*i);
        if (isalnum(c) || c == '-' || c == '_' || c == '.' || c == '~' || c == '*') {
            escaped << c;
        } else if (c == ' ')  {
            escaped << '+';
        } else {
            escaped << '%' << std::setw(2) << ((int) c) << std::setw(0);
        }
    }

    return escaped.str();
}

void urlEncodeInPlace(std::string& str) {
    str = urlEncode(str);   // no real efficiency gain here
}

namespace std {
bool stob(const std::string& str) {
    return ::stringToBool(str);
}

char stoc(const std::string& str) {
    return ::stringToChar(str);
}

std::string to_string(bool b) {
    return ::boolToString(b);
}

std::string to_string(char c) {
    return ::charToString(c);
}

std::string to_string(void* p) {
    return ::pointerToString(p);
}
} // namespace std

/////////////////////// END code extracted from StanfordCPPLib/util/strlib.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/util/timer.cpp ///////////////////////
/*
 * File: timer.cpp
 * ---------------
 * Implementation of the Timer class as declared in timer.h.
 */

#define INTERNAL_INCLUDE 1

#include <sys/time.h>
#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

Timer::Timer(bool autostart) {
    _startMS = 0;
    _stopMS = 0;
    _isStarted = false;
    if (autostart) {
        start();
    }
}

long Timer::elapsed() const {
    return _stopMS - _startMS;
}

bool Timer::isStarted() const {
    return _isStarted;
}

void Timer::start() {
    _startMS = currentTimeMS();
    _isStarted = true;
}

long Timer::stop() {
    _stopMS = currentTimeMS();
    if (!_isStarted) {
        // error("Timer is not started");
        _startMS = _stopMS;
    }
    _isStarted = false;
    return elapsed();
}

long Timer::currentTimeMS() {
    timeval time;
    gettimeofday(&time, nullptr);
    return (time.tv_sec * 1000000 + time.tv_usec) / 1000;
}

/////////////////////// END code extracted from StanfordCPPLib/util/timer.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib/graphics/console.cpp ///////////////////////
/*
 * File: console.cpp
 * -----------------
 * This file implements the console .h interface.
 *
 * @author Marty Stepp
 * @version 2019/04/12
 * - added pause() implementation (empty) in headless mode
 * @version 2018/11/22
 * - added headless mode support
 * @version 2018/10/01
 * - bug fix for graphical console popping up even if not included
 * @version 2018/08/23
 * - renamed to console .cpp/h to replace Java version
 * - separated out gconsolewindow.h/cpp
 * @version 2018/07/15
 * - initial version, based on io/console .cpp
 */

#define INTERNAL_INCLUDE 1

#include <cstdio>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

#ifdef SPL_HEADLESS_MODE

void clearConsole() {
    // empty
}

bool getConsoleClearEnabled() {
    return true;
}

/* GWindow::CloseOperation */ int getConsoleCloseOperation() {
    return 0;
}

bool getConsoleEcho() {
    return true;
}

bool getConsoleEnabled() {
    return true;
}

bool getConsoleEventOnClose() {
    return true;
}

bool getConsoleExitProgramOnClose() {
    return true;
}

std::string getConsoleFont() {
    return "";
}

double getConsoleHeight() {
    return 0;
}

bool getConsoleLocationSaved() {
    return false;
}

bool getConsolePrintExceptions() {
    return exceptions::getTopLevelExceptionHandlerEnabled();
}

bool getConsoleSettingsLocked() {
    return false;
}

double getConsoleWidth() {
    return 0;
}

std::string getConsoleWindowTitle() {
    return "";
}

void pause(double /*milliseconds*/) {
    // empty
}

void setConsoleClearEnabled(bool /*value*/) {
    // empty
}

void setConsoleCloseOperation(int /*op*/) {
    // empty
}

void setConsoleEcho(bool /*echo*/) {
    // empty
}

void setConsoleEnabled(bool /*enabled*/) {
    // empty
}

void setConsoleErrorColor(const std::string& /*color*/) {
    // empty
}

void setConsoleEventOnClose(bool /*eventOnClose*/) {
    // empty
}

void setConsoleExitProgramOnClose(bool /*exitOnClose*/) {
    // empty
}

void setConsoleFont(const std::string& /*font*/) {
    // empty
}

void setConsoleLocation(double /*x*/, double /*y*/) {
    // empty
}

void setConsoleLocationSaved(bool /*value*/) {
    // empty
}

void setConsoleOutputColor(const std::string& /*color*/) {
    // empty
}

void setConsolePrintExceptions(bool printExceptions, bool force) {
    if (getConsoleSettingsLocked()) { return; }
    exceptions::setTopLevelExceptionHandlerEnabled(printExceptions, force);
}

void setConsoleSettingsLocked(bool /*value*/) {
    // empty
}

void setConsoleSize(double /*width*/, double /*height*/) {
    // empty
}

void setConsoleWindowTitle(const std::string& /*title*/) {
    // empty
}

void shutdownConsole() {
    // empty
}

#else // SPL_HEADLESS_MODE

void clearConsole() {
    GConsoleWindow::instance()->clearConsole();
}

bool getConsoleClearEnabled() {
    return GConsoleWindow::instance()->isClearEnabled();
}

/* GWindow::CloseOperation */ int getConsoleCloseOperation() {
    return GConsoleWindow::instance()->getCloseOperation();
}

bool getConsoleEcho() {
    return GConsoleWindow::instance()->isEcho();
}

bool getConsoleEnabled() {
#ifdef __DONT_ENABLE_QT_GRAPHICAL_CONSOLE
    return false;
#else
    return GConsoleWindow::consoleEnabled();
#endif
}

bool getConsoleEventOnClose() {
    return true;
}

bool getConsoleExitProgramOnClose() {
    return GConsoleWindow::instance()->getCloseOperation() == GWindow::CLOSE_EXIT;
}

std::string getConsoleFont() {
#ifdef __DONT_ENABLE_QT_GRAPHICAL_CONSOLE
    return GConsoleWindow::getDefaultFont();
#else
    return GConsoleWindow::instance()->getFont();
#endif
}

double getConsoleHeight() {
    return GConsoleWindow::instance()->getHeight();
}

GPoint getConsoleLocation() {
    return GConsoleWindow::instance()->getLocation();
}

bool getConsoleLocationSaved() {
    return GConsoleWindow::instance()->isLocationSaved();
}

bool getConsolePrintExceptions() {
    return exceptions::getTopLevelExceptionHandlerEnabled();
}

bool getConsoleSettingsLocked() {
    return GConsoleWindow::isInitialized()
            && GConsoleWindow::instance()->isLocked();
}

GDimension getConsoleSize() {
    return GConsoleWindow::instance()->getSize();
}

double getConsoleWidth() {
    return GConsoleWindow::instance()->getWidth();
}

GConsoleWindow* getConsoleWindow() {
    return GConsoleWindow::instance();
}

std::string getConsoleWindowTitle() {
    return GConsoleWindow::instance()->getTitle();
}

void setConsoleClearEnabled(bool value) {
    if (getConsoleSettingsLocked()) { return; }
    GConsoleWindow::instance()->setClearEnabled(value);
}

void setConsoleCloseOperation(/*GWindow::CloseOperation*/ int op) {
    GWindow::CloseOperation gwcop = static_cast<GWindow::CloseOperation>(op);
    if (getConsoleSettingsLocked()) { return; }
    GConsoleWindow::instance()->setCloseOperation(gwcop);
}

void setConsoleEcho(bool echo) {
    if (getConsoleSettingsLocked()) { return; }
    GConsoleWindow::instance()->setEcho(echo);
}

void setConsoleEnabled(bool enabled) {
    GConsoleWindow::setConsoleEnabled(enabled);
}

void setConsoleErrorColor(const std::string& color) {
    if (getConsoleSettingsLocked()) { return; }
    GConsoleWindow::instance()->setErrorColor(color);
}

void setConsoleEventOnClose(bool /*eventOnClose*/) {
    // empty
}

void setConsoleExitProgramOnClose(bool exitOnClose) {
    if (getConsoleSettingsLocked()) { return; }
    GConsoleWindow::instance()->setExitOnClose(exitOnClose);
}

void setConsoleFont(const std::string& font) {
    if (getConsoleSettingsLocked()) { return; }
    GConsoleWindow::instance()->setFont(font);
}

void setConsoleLocation(double x, double y) {
    if (getConsoleSettingsLocked()) { return; }
    if (floatingPointEqual(x, -1) && floatingPointEqual(y, -1)) {
        GConsoleWindow::instance()->center();
    } else {
        GConsoleWindow::instance()->setLocation(x, y);
    }
}

void setConsoleLocationSaved(bool value) {
    GConsoleWindow::instance()->setLocationSaved(value);
}

void setConsoleOutputColor(const std::string& color) {
    GConsoleWindow::instance()->setOutputColor(color);
}

void setConsolePrintExceptions(bool printExceptions, bool force) {
    if (getConsoleSettingsLocked()) { return; }
    exceptions::setTopLevelExceptionHandlerEnabled(printExceptions, force);
}

void setConsoleSettingsLocked(bool value) {
    GConsoleWindow::instance()->setLocked(value);
}

void setConsoleSize(double width, double height) {
    if (getConsoleSettingsLocked()) { return; }
    GConsoleWindow::instance()->setConsoleSize(width, height);
}

void setConsoleWindowTitle(const std::string& title) {
    if (getConsoleSettingsLocked()) { return; }
    GConsoleWindow::instance()->setTitle(title);
}

void shutdownConsole() {
    if (getConsoleEnabled() && !GConsoleWindow::instance()->isLocked()) {
        GConsoleWindow::instance()->shutdown();
    }
}

#endif // SPL_HEADLESS_MODE

/*
 * Sets up console settings like window size, location, exit-on-close, etc.
 * based on compiler options set in the .pro file.
 */
void setConsolePropertiesQt() {
#if defined(SPL_CONSOLE_FONTSIZE)
    std::string fontStr = std::string("Monospaced-Bold-") + std::to_string(SPL_CONSOLE_FONTSIZE);
    setConsoleFont(fontStr);
#endif

#if defined(SPL_CONSOLE_WIDTH) && defined(SPL_CONSOLE_HEIGHT)
    setConsoleSize(SPL_CONSOLE_WIDTH, SPL_CONSOLE_HEIGHT);
#endif

#if defined(SPL_CONSOLE_X) && defined(SPL_CONSOLE_Y)
    setConsoleLocation(SPL_CONSOLE_X, SPL_CONSOLE_Y);
#endif

#if defined(SPL_CONSOLE_ECHO)
    setConsoleEcho(true);
#endif

#if defined(SPL_CONSOLE_EXIT_ON_CLOSE)
    setConsoleExitProgramOnClose(true);
#endif

#if defined(SPL_CONSOLE_LOCATION_SAVED)
    setConsoleLocationSaved(true);
#endif

#if defined(SPL_CONSOLE_PRINT_EXCEPTIONS)
    setConsolePrintExceptions(true);
#endif

#if defined(SPL_VERIFY_PROJECT_VERSION)
    version::ensureProjectVersion();
#endif
}

void initializeQtGraphicalConsole() {
#ifndef __DONT_ENABLE_QT_GRAPHICAL_CONSOLE
    // ensure that console is initialized only once
    static bool _initialized = false;
    if (_initialized) {
        return;
    }
    _initialized = true;

    // declaring this object ensures that std::cin, cout, cerr are initialized
    // properly before our lib tries to mess with them / redirect them
    static std::ios_base::Init ios_base_init;

#ifndef SPL_HEADLESS_MODE
    if (GConsoleWindow::consoleEnabled()) {
        GConsoleWindow::instance();   // ensure that console window is ready
        setConsolePropertiesQt();
    }
#endif // SPL_HEADLESS_MODE

#endif // __DONT_ENABLE_QT_GRAPHICAL_CONSOLE
}

/////////////////////// END code extracted from StanfordCPPLib/graphics/console.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/ArrayIntList.cpp ///////////////////////
/*
 * CS 106B, Marty Stepp
 * ArrayIntList.cpp implements the ArrayIntList class behavior declared in ArrayIntList.h.
 * 
 * @version 2016/08/23
 * - added initializer_list support to match other lib collections
 */

#define INTERNAL_INCLUDE 1



#undef INTERNAL_INCLUDE

/*
 * Constructs a new empty list (capacity 10).
 */
ArrayIntList::ArrayIntList() {
    elements = new int[10]();
    mysize = 0;
    capacity = 10;
}

/*
 * Constructs a new empty list with the given capacity.
 */
ArrayIntList::ArrayIntList(int cap) {
    elements = new int[cap]();
    mysize = 0;
    capacity = cap;
}

/*
 * Constructs a new empty list storing the given elements.
 */
ArrayIntList::ArrayIntList(std::initializer_list<int> list) {
    elements = new int[list.size()]();
    mysize = 0;
    capacity = list.size();
    for (int n : list) {
        add(n);
    }
}

/*
 * Destructor is called when an ArrayIntList object is destroyed
 * (when the closing } brace is reached in the function where
 * it is declared).
 */
ArrayIntList::~ArrayIntList() {
    delete[] elements;
}

/*
 * Appends the given value to the end of the list.
 */
void ArrayIntList::add(int value) {
    ensureCapacity(mysize + 1);
    elements[mysize] = value;
    mysize++;
}

/*
 * Removes all elements from the list.
 */
void ArrayIntList::clear() {
    mysize = 0;
}

/*
 * Returns the value at the given 0-based index of the list.
 */
int ArrayIntList::get(int index) const {
    checkIndex(index, 0, mysize - 1);
    return elements[index];
}

/*
 * Adds the given value just before the given 0-based index in the list,
 * shifting subsequent elements right as necessary to make room.
 * Throws a string exception if the index is out of bounds.
 */
void ArrayIntList::insert(int index, int value) {
    checkIndex(index, 0, mysize);
    ensureCapacity(mysize + 1);
    for (int i = mysize; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = value;
    mysize++;
}

/*
 * Returns true if there are no elements in the list.
 */
bool ArrayIntList::isEmpty() const {
    return mysize == 0;
}

/*
 * Removes the element at the given index from the list,
 * shifting elements left to make room.
 * Throws a string exception if the index is out of bounds.
 */
void ArrayIntList::remove(int index) {
    checkIndex(index, 0, mysize - 1);
    for (int i = index; i < mysize - 1; i++) {
        elements[i] = elements[i + 1];
    }
    mysize--;
}

/*
 * Stores the given value at the given index in the list.
 * Throws a string exception if the index is out of bounds.
 */
void ArrayIntList::set(int index, int value) {
    checkIndex(index, 0, mysize - 1);
    elements[index] = value;
}

/*
 * Returns the number of elements in the list.
 */
int ArrayIntList::size() const {
    return mysize;
}

/*
 * Prints the list to the given output stream, in a format such as:
 * {42, -7, 19, 106}
 */
ostream& operator <<(ostream& out, const ArrayIntList& list) {
    out << "{";
    if (!list.isEmpty()) {
        out << list.get(0);   // fencepost
        for (int i = 1; i < list.size(); i++) {
            out << ", " << list.get(i);
        }
    }
    out << "}";
    return out;
}

istream& operator >>(istream& input, ArrayIntList& list) {
    char ch = '\0';
    input >> ch;
    if (ch != '{') {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
        error("ArrayIntList::operator >>: Missing {");
#endif
        input.setstate(std::ios_base::failbit);
        return input;
    }
    list.clear();
    input >> ch;
    if (ch != '}') {
        input.unget();
        while (true) {
            int value;
            if (!readGenericValue(input, value)) {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
                error("ArrayIntList::operator >>: parse error");
#endif
                return input;
            }
            list.add(value);
            input >> ch;
            if (ch == '}') {
                break;
            } else if (ch != ',') {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
                error(std::string("ArrayIntList::operator >>: Unexpected character ") + ch);
#endif
                input.setstate(std::ios_base::failbit);
                return input;
            }
        }
    }
    return input;
}

/*
 * Throws a string exception if the given index is not between
 * min and max, inclusive.
 */
void ArrayIntList::checkIndex(int index, int min, int max) const {
    if (index < min || index > max) {
        throw "Index out of bounds: " + integerToString(index);
    }
}

/*
 * Grows the internal array to be at least as large as the given capacity.
 * Resizes by factors of 2 to ensure amortized O(1) add performance.
 */
void ArrayIntList::ensureCapacity(int cap) {
    if (capacity < cap) {
        while (capacity < cap) {
            capacity *= 2;
        }
        
        // copy all elements into a bigger array
        int* bigger = new int[capacity];
        for (int i = 0; i < mysize; i++) {
            bigger[i] = elements[i];
        }
        
        // swap in the new bigger array for the old one
        delete[] elements;
        elements = bigger;
    }
}

ArrayIntList& ArrayIntList::operator =(const ArrayIntList& src) {
    if (this != &src) {
        // deep copy
        clear();
        ensureCapacity(src.size());
        for (int i = 0; i < src.size(); i++) {
            add(src.get(i));
        }
    }
    return *this;
}

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/ArrayIntList.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/BinaryTree.cpp ///////////////////////
/*
 * This file contains the implementation of members of the BinaryTree class,
 * which defines a binary tree of integers.
 * See BinaryTree.h for a description of each member.
 *
 * @version 2015/07/21
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

BinaryTree::BinaryTree(BinaryTreeNode* root) {
    this->root = root;
}

BinaryTree::~BinaryTree() {
    // TODO: free memory
    root = nullptr;
}

static void binaryTreeClearHelper(BinaryTreeNode*& node) {
    if (node) {
        binaryTreeClearHelper(node->left);
        binaryTreeClearHelper(node->right);
        delete node;
        node = nullptr;
    }
}

void BinaryTree::clear() {
    binaryTreeClearHelper(root);
}

std::string BinaryTree::toString() {
    return toString(root);
}
std::string BinaryTree::toString(BinaryTreeNode* node) {
    if (!node) {
        return "/";
    } else if (node->left == nullptr && node->right == nullptr) {
        return integerToString(node->data);
    } else {
        return "(" + integerToString(node->data) + ", "
             + toString(node->left) + ", " + toString(node->right) + ")";
    }
}

void BinaryTree::deleteTree(BinaryTreeNode* node) {
    if (node) {
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
}

std::ostream& operator <<(std::ostream& out, const BinaryTree& tree) {
    return binaryTreeOpLtLtHelper(out, tree.root);
}

std::istream& operator >>(std::istream& input, BinaryTree& tree) {
    tree.clear();
    std::string line;
    if (getline(input, line)) {
        makeTreeFromString(line, tree.root);
    }
    return input;
}

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/BinaryTree.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/BinaryTreeMap.cpp ///////////////////////
/*
 * CS 106B, Marty Stepp
 * This file contains the implementation of the BinaryTreeMap class,
 * which defines a map from string->integer using a binary search tree.
 * See BinaryTreeMap.h for a description of each member.
 *
 * @version 2015/07/21
 */

#define INTERNAL_INCLUDE 1
#include <string>


#undef INTERNAL_INCLUDE

BinaryTreeMap::BinaryTreeMap() {
    m_root = nullptr;
}

BinaryTreeMap::~BinaryTreeMap() {
    // TODO: implement

}

bool BinaryTreeMap::containsKey(string key) const {
    return containsKey(m_root, key);
}

bool BinaryTreeMap::containsKey(BinaryTreeMapNode* node, string key) const {
    if (!node) {
        return false;
    } else if (key == node->key) {
        return true;
    } else if (key < node->key) {
        return containsKey(node->left, key);
    } else {  // key > node->key
        return containsKey(node->right, key);
    }
}

int BinaryTreeMap::get(string key) const {
    return get(m_root, key);
}

int BinaryTreeMap::get(BinaryTreeMapNode* node, string key) const {
    if (!node) {
        return 0;
    } else if (key == node->key) {
        return node->value;
    } else if (key < node->key) {
        return get(node->left, key);
    } else {  // key > node->key
        return get(node->right, key);
    }
}

bool BinaryTreeMap::isEmpty() const {
    return m_size == 0;
}

void BinaryTreeMap::put(string key, int value) {
    put(m_root, key, value);
}

void BinaryTreeMap::put(BinaryTreeMapNode*& node, string key, int value) {
    if (!node) {
        node = new BinaryTreeMapNode(key, value);
        m_size++;
    } else if (node->key == key) {
        node->value = value;
    } else if (key < node->key) {
        put(node->left, key, value);
    } else {  // key > node->key
        put(node->right, key, value);
    }
}

void BinaryTreeMap::remove(string key) {
    remove(m_root, key);
}

void BinaryTreeMap::remove(BinaryTreeMapNode*& node, string key) {
    if (!node) {
        // not here, nothing to do
    } else if (key == node->key) {
        // remove THIS node
        BinaryTreeMapNode* trash = nullptr;
        if (node->isLeaf()) {
            trash = node;
            node = nullptr;
        } else if (!node->right) {
            // left child only; replace me with left
            trash = node;
            node = node->left;
        } else if (!node->left) {
            // right child only; replace me with right
            trash = node;
            node = node->right;
        } else {
            // :-( both children alive
            BinaryTreeMapNode* rightMinNode = getMin(node->right);
            node->key = rightMinNode->key;
            node->value = rightMinNode->value;
            remove(node->right, rightMinNode->key);
        }

        m_size--;
        if (trash) {
            delete trash;
        }
    } else if (key < node->key) {
        remove(node->left, key);
    } else {  // key > node->key
        remove(node->right, key);
    }
}

BinaryTreeMapNode* BinaryTreeMap::getMin(BinaryTreeMapNode* node) const {
    if (!node || !node->left) {
        return node;
    } else {
        return getMin(node->left);
    }
}

int BinaryTreeMap::size() const {
    return m_size;
}

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/BinaryTreeMap.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/HashTableSet.cpp ///////////////////////
/*
 * CS 106B, Marty Stepp
 * This file contains the implementation of the HashTableSet class, which implements
 * a set of integers using a hash table.
 * See HashTableSet.h for the declarations of each member.
 *
 * @version 2015/07/21
 */

#define INTERNAL_INCLUDE 1
#include <iostream>
#include <iomanip>

#undef INTERNAL_INCLUDE

HashTableSet::HashTableSet() {
    m_size = 0;
    m_capacity = 10;
    m_elements = new HashTableNode*[m_capacity]();   // all null
}

void HashTableSet::add(int value) {
    if (!contains(value)) {
        int index = hashCode(value);
        HashTableNode* node = new HashTableNode(value);
        node->next = m_elements[index];
        m_elements[index] = node;
        m_size++;
    }
}

bool HashTableSet::contains(int value) const {
    int index = hashCode(value);
    HashTableNode* current = m_elements[index];
    while (current) {
        if (current->data == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}

int HashTableSet::hashCode(int value) const {
    return abs(value) % m_capacity;
}

void HashTableSet::remove(int /*value*/) {
    // not implemented
}

void HashTableSet::printStructure() const {
    for (int i = 0; i < m_capacity; i++) {
        std::cout << "[" << std::setw(2) << i << "]:";
        HashTableNode* curr = m_elements[i];
        while (curr) {
            std::cout << " -> " << std::setw(2) << curr->data;
            curr = curr->next;
        }
        std::cout << " /" << std::endl;
    }
    // cout << "size = " << m_size << ", load factor = " << loadFactor() << endl;
}

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/HashTableSet.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/HeapPriorityQueue.cpp ///////////////////////
/*
 * CS 106B, Marty Stepp
 * This file implements the HeapPriorityQueue class.
 *
 * @version 2015/07/29
 */

#define INTERNAL_INCLUDE 1

#include <string>



#undef INTERNAL_INCLUDE

HeapPriorityQueue::HeapPriorityQueue(PQEntry* elements, int capacity, int mysize) {
    this->elements = elements;
    this->capacity = capacity;
    this->mysize = mysize;
    this->hackPQ = new PriorityQueue<string>();
}

HeapPriorityQueue::~HeapPriorityQueue() {
    if (elements) {
        delete[] elements;
    }
    delete hackPQ;
}

void HeapPriorityQueue::changePriority(string value, double newPriority) {
    hackPQ->changePriority(value, newPriority);
}

void HeapPriorityQueue::clear() {
    hackPQ->clear();
    mysize = hackPQ->size();
}

string HeapPriorityQueue::dequeue() {
    string result = hackPQ->dequeue();
    mysize = hackPQ->size();
    return result;
}

void HeapPriorityQueue::enqueue(string value, double priority) {
    hackPQ->enqueue(value, priority);
    mysize = hackPQ->size();
}

bool HeapPriorityQueue::isEmpty() const {
    return hackPQ->isEmpty();
}

string HeapPriorityQueue::peek() const {
    return hackPQ->peek();
}

double HeapPriorityQueue::peekPriority() const {
    return hackPQ->peekPriority();
}

void HeapPriorityQueue::printSideways(int index, string indent) const {
    if (index <= size()) {
        printSideways(index*2+1, indent + "    ");   // right
        string value    = hackPQ->__getValueFromHeap(index-1);
        double priority = hackPQ->__getPriorityFromHeap(index-1);
        cout << indent << value << ":" << priority << endl;
        printSideways(index*2, indent + "    ");     // left
    }
}

int HeapPriorityQueue::size() const {
    return mysize;
}

string HeapPriorityQueue::toString() const {
    ostringstream out;
    out << *this;
    return out.str();
}

ostream& operator <<(ostream& out, const HeapPriorityQueue& pq) {
    out << *pq.hackPQ;
    return out;
}

istream& operator >>(istream& input, HeapPriorityQueue& pq) {
    char ch = '\0';
    input >> ch;
    if (ch != '{') {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
        error("HeapPriorityQueue::operator >>: Missing {");
#endif
        input.setstate(std::ios_base::failbit);
        return input;
    }
    pq.clear();
    input >> ch;
    if (ch != '}') {
        input.unget();
        while (true) {
            std::string value;
            if (!readGenericValue(input, value)) {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
                error("HeapPriorityQueue::operator >>: parse error");
#endif
                return input;
            }
            input >> ch;
            if (ch != ':') {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
                error("HeapPriorityQueue::operator >>: Missing colon after priority");
#endif
                input.setstate(std::ios_base::failbit);
                return input;
            }
            double priority = 0.0;
            input >> priority;
            pq.enqueue(value, priority);
            
            input >> ch;
            if (ch == '}') {
                break;
            }
            if (ch != ',') {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
                error(std::string("HeapPriorityQueue::operator >>: Unexpected character ") + ch);
#endif
                input.setstate(std::ios_base::failbit);
                return input;
            }
        }
    }
    return input;
}

void stringToPQ(HeapPriorityQueue& pq, string elements) {
    Vector<string> pairs = stringSplit(elements, ", ");
    for (string pair : pairs) {
        Vector<string> parts = stringSplit(pair, ":");
        string value = parts[0];
        int priority = stringToInteger(parts[1]);
        pq.enqueue(value, priority);
    }
}

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/HeapPriorityQueue.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/LinkedIntList.cpp ///////////////////////
/*
 * LinkedIntList.cpp implements the LinkedIntList class behavior declared in LinkedIntList.h.
 *
 * @version 2016/11/11
 * - made into template class
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

LinkedIntList::LinkedIntList()
        : front(nullptr), m_locked(false) {
    // empty
}

/*
 * Constructs a new empty list storing the given elements.
 */
LinkedIntList::LinkedIntList(std::initializer_list<int> list)
        : front(nullptr), m_locked(false) {
    for (int n : list) {
        add(n);
    }
}

LinkedIntList::~LinkedIntList() {
    m_locked = false;
    clear();
}

void LinkedIntList::add(int value) {
    checkLocked("add");
    if (!front) {
        // empty list: add this node as the new front
        front = new ListNode(value);
    } else {
        // non-empty list: move to end, attach new node
        ListNode* current = front;
        while (current->next) {
            current = current->next;
        }
        current->next = new ListNode(value);
    }
}

void LinkedIntList::clear() {
    checkLocked("clear");
    while (front) {
        ListNode* temp = front;
        front = front->next;
        delete temp;
    }
}

int LinkedIntList::get(int index) const {
    checkLocked("get");
    checkIndex(index, 0, size() - 1);
    ListNode* current = front;
    for (int i = 0; i < index; i++) {
        current = current->next;
    }
    return current->data;
}

void LinkedIntList::insert(int index, int value) {
    checkLocked("insert");
    checkIndex(index, 0, size());
    if (index == 0) {
        ListNode* temp = front;
        front = new ListNode(value, temp);
    } else {
        ListNode* current = front;
        for (int i = 0; i < index - 1; i++) {
            current = current->next;
        }
        ListNode* temp = current->next;
        current->next = new ListNode(value, temp);
    }
}

bool LinkedIntList::isEmpty() const {
    return front == nullptr;
}

void LinkedIntList::remove(int index) {
    checkLocked("remove");
    checkIndex(index, 0, size() - 1);
    ListNode* trash;
    if (index == 0) {
        trash = front;
        front = front->next;
    } else {
        ListNode* curr = front;
        for (int i = 0; i < index-1; i++) {
            curr = curr->next;
        }
        trash = curr->next;
        curr->next = curr->next->next;
    }
    delete trash;
}

void LinkedIntList::set(int index, int value) {
    checkLocked("set");
    checkIndex(index, 0, size() - 1);
    ListNode* current = front;
    for (int i = 0; i < index; i++) {
        current = current->next;
    }
    current->data = value;
}

int LinkedIntList::size() const {
    checkLocked("size");
    int count = 0;
    ListNode* current = front;
    while (current) {
        count++;
        current = current->next;
    }
    return count;
}

// TODO: put printing code into operator <<, call that from toString
std::string LinkedIntList::toString() const {
    std::ostringstream out;
    out << *this;
    return out.str();
}

void LinkedIntList::setLocked(bool locked) {
    m_locked = locked;
}

void LinkedIntList::checkIndex(int index, int min, int max) const {
    if (index < min || index > max) {
        throw std::string("Invalid index");
    }
}

void LinkedIntList::checkLocked(std::string memberName) const {
    if (m_locked) {
        error("LinkedIntList forbidden from calling member function " + memberName);
    }
}

LinkedIntList& LinkedIntList::operator =(const LinkedIntList& src) {
    if (this != &src) {
        // deep copy
        clear();
        for (int i = 0; i < src.size(); i++) {
            add(src.get(i));
        }
    }
    return *this;
}

std::ostream& operator <<(std::ostream& out, const LinkedIntList& list) {
    if (list.isEmpty()) {
        out << "{}";
    } else {
        out << list.front;
    }
    return out;
}

std::istream& operator >>(std::istream& input, LinkedIntList& list) {
    char ch = '\0';
    input >> ch;
    if (ch != '{') {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
        error("LinkedIntList::operator >>: Missing {");
#endif
        input.setstate(std::ios_base::failbit);
        return input;
    }
    list.clear();
    input >> ch;
    if (ch != '}') {
        input.unget();
        while (true) {
            int value;
            if (!readGenericValue(input, value)) {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
                error("LinkedIntList::operator >>: parse error");
#endif
                return input;
            }
            list.add(value);
            input >> ch;
            if (ch == '}') {
                break;
            } else if (ch != ',') {
#ifdef SPL_ERROR_ON_COLLECTION_PARSE
                error(std::string("LinkedIntList::operator >>: Unexpected character ") + ch);
#endif
                input.setstate(std::ios_base::failbit);
                return input;
            }
        }
    }
    return input;
}

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/LinkedIntList.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/graphsupport.cpp ///////////////////////
/*
 * @version 2017/10/24
 * - replaced null in uppercase with nullptr
 */

#define INTERNAL_INCLUDE 1

#include <iomanip>

#undef INTERNAL_INCLUDE

// definitions for colors
const int NUM_COLORS = 7;

const Color UNCOLORED = 0;
const Color WHITE = 1;
const Color GRAY = 2;
const Color YELLOW = 3;
const Color GREEN = 4;
const Color RED = 5;
const Color BLUE = 6;

const Color COLORS[7] = {
    UNCOLORED,
    WHITE,
    GRAY,
    YELLOW,
    GREEN,
    RED,
    BLUE
};

const string COLOR_NAMES[7] = {
    "uncolored",
    "white",
    "gray",
    "yellow",
    "green",
    "red",
    "blue"
};

bool graph_canReach(BasicGraph& graph, Vertex* start, Vertex* end, Set<Vertex*>& visited, Vector<Vertex*>* path) {
    // cout << "    canReach(graph, start=" << start->name << ", end=" << end->name << ")" << endl;
    if (start == end) {
        return true;
    } else if (visited.contains(start)) {
        return false;
    } else {
        visited.add(start);
        if (path) {
            path->add(start);
        }
        for (Vertex* neighbor : graph.getNeighbors(start->name)) {
            if (graph_canReach(graph, neighbor, end, visited, path)) {
                return true;
            }
        }
        visited.remove(start);
        if (path) {
            path->remove(path->size() - 1);
        }
        return false;
    }
}

bool graph_isConnected(BasicGraph& graph, bool checkWeak) {
    bool weak = false;
    for (Vertex* v1 : graph.getVertexSet()) {
        for (Vertex* v2 : graph.getVertexSet()) {
            if (v1 == v2) {
                continue;
            }
            // cout << "    " << v1->name << " ... " << v2->name << endl;
            graph.resetData();
            Set<Vertex*> visited;
            if (!graph_canReach(graph, v1, v2, visited)) {
                if (checkWeak && graph_canReach(graph, v2, v1, visited)) {
                    weak = true;
                    continue;
                }
                cout << "vertex " << v1->name << " cannot reach " << v2->name << endl;
                return false;
            }
        }
    }
    
    if (weak) {
        cout << "(weakly connected)" << endl;
    }
    return !weak;
}

bool graph_isCyclic(BasicGraph& graph) {
    for (Vertex* v : graph.getVertexSet()) {
        for (Vertex* neighbor : graph.getNeighbors(v)) {
            Vector<Vertex*> path;
            graph.resetData();
            Set<Vertex*> visited;
            if (graph_canReach(graph, neighbor, v, visited, &path)) {
                path.insert(0, v);
                path.add(v);
                cout << "cycle starting from " << v->name << ": " << graph_pathToString(path) << endl;
                return true;
            }
        }
    }
    
    return false;
}

void graph_printEdgeList(BasicGraph& graph) {
    cout << "edge list:" << endl;
    Vector<string> edgeList;
    for (Edge* edge : graph.getEdgeSet()) {
        string edgeStr = "" + edge->start->name + " -> " + edge->finish->name;
        if (!floatingPointEqual(edge->weight, 0.0)) {
            edgeStr += " : " + realToString(edge->weight);
        }
        cout << "  " << edgeStr << endl;
    }
}

void graph_printAdjacencyList(BasicGraph& graph) {
    cout << "adjacency list:" << endl;
    for (Vertex* v : graph.getVertexSet()) {
        cout << "  " << v->name << " : ";
        int count = 0;
        for (Vertex* neighbor : graph.getNeighbors(v)) {
            if (count > 0) {
                cout << ", ";
            }
            cout << "(" << neighbor->name;
            Edge* edge = graph.getEdge(v, neighbor);
            if (!floatingPointEqual(edge->weight, 0.0)) {
                cout << ":" << edge->weight;
            }
            count++;
            cout << ")";
        }
        cout << endl;
    }
}

void graph_printAdjacencyMatrix(BasicGraph& graph) {
    cout << "adjacency matrix:" << endl;
    
    const int COL_WIDTH = 5;
    
    // column headers
    cout << setw(COL_WIDTH) << "";
    for (Vertex* v1 : graph.getVertexSet()) {
        cout << setw(COL_WIDTH) << v1->name;
    }
    cout << endl;
    
    for (Vertex* v1 : graph.getVertexSet()) {
        // row header
        cout << setw(COL_WIDTH) << v1->name;
        
        for (Vertex* v2 : graph.getVertexSet()) {
            double toPrint = 0;
            if (graph.isNeighbor(v1, v2)) {
                Edge* edge = graph.getEdge(v1, v2);
                if (!floatingPointEqual(edge->weight, 0.0)) {
                    toPrint = edge->weight;
                } else {
                    toPrint = 1;
                }
            }
            cout << setw(COL_WIDTH) << toPrint;
        }
        cout << endl;
    }
}

void graph_printVertexDegrees(BasicGraph& graph) {
    cout << "vertex degrees:" << endl;
    for (Vertex* v : graph.getVertexSet()) {
        cout << "  " << v->name << " : ";
        int inDegree = 0;
        for (Vertex* v2 : graph.getVertexSet()) {
            if (graph.isNeighbor(v2, v)) {
                inDegree++;
            }
        }
        cout << "in-degree: " << inDegree;
        cout << ", out-degree: " << v->edges.size() << endl;
    }
}

string graph_pathToString(const Vector<Vertex*>& path) {
    Vector<string> path2;
    for (Vertex* v : path) {
        if (v) {
            path2.add(v->name);
        } else {
            path2.add("nullptr");
        }
    }
    return path2.toString();
}

void graph_printPath(const Vector<Vertex*>& path) {
    cout << "{";
    int i = 0;
    for (Vertex* v : path) {
        if (i > 0) {
            cout << ", ";
        }
        if (!v) {
            cout << "nullptr";
        } else {
            cout << v->name;
        }
        i++;
    }
    cout << "}" << endl;
}

void BasicGraph_fromString(BasicGraph& obj, string str) {
    istringstream input(str);
    input >> obj;
}

ostream& operator <<(ostream& out, const Vector<Vertex*>& path) {
    out << "{";
    int i = 0;
    for (Vertex* v : path) {
        if (i > 0) {
            out << ", ";
        }
        if (!v) {
            out << "nullptr";
        } else {
            out << v->name;
        }
        i++;
    }
    out << "}";
    return out;
}

ostream& operator <<(ostream& out, const Set<Vertex*>& set) {
    out << "{";
    int i = 0;
    for (Vertex* v : set) {
        if (i > 0) {
            out << ", ";
        }
        if (!v) {
            out << "nullptr";
        } else {
            out << v->name;
        }
        i++;
    }
    out << "}";
    return out;
}

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/graphsupport.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/types.cpp ///////////////////////
/*
 * Various support classes and types used in practice problems.
 *
 * @version 2015/08/10
 */

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

Domino::Domino(int f, int s) {
    first = f;
    second = s;
}

ostream& operator <<(ostream& out, const Domino& d) {
    return out << "(" << d.first << ":" << d.second << ")";
}

istream& operator >>(istream& input, Domino& d) {
    char ch = '\0';
    input >> ch;   // (
    input >> ch;   // first
    d.first = ch - '0';
    input >> ch;   // :
    input >> ch;   // second
    d.second = ch - '0';
    input >> ch;   // )
    return input;
}

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/types.cpp ///////////////////////

/////////////////////// BEGIN code extracted from StanfordCPPLib_CodeStepByStep_Project/src/codestepbystep.cpp ///////////////////////
/*
 * @version 2019/05/17
 * - add AssassinNode support
 * @version 2018/12/16
 * - improved printing of real numbers to XML output
 * @version 2017/11/12
 * - added output limit of 100k chars to avoid infinite student solution output
 * @version 2017/10/06
 * - hid POSIX signal handler behind preprocessor macro
 * @version 2016/12/07
 * - added assert* methods
 */

#include <climits>
#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#define INTERNAL_INCLUDE 1

#undef INTERNAL_INCLUDE

#ifndef SIGSTACK
#define SIGSTACK (static_cast<int>(0xdeadbeef))
#endif // SIGSTACK

extern void startupMainDontRunMain(int argc, char** argv);

namespace CodeStepByStep {
static std::string __testToRun = "";
static bool __runAllTests = false;
static std::string __xmlOutFilename;
static std::ofstream* __xout = nullptr;
static void (*old_terminate)() = nullptr;

// only use these if we can't use __getXmlOut (e.g. in a signal handler)
static FILE* __xfout = nullptr;

std::string testToRun() {
    return __testToRun;
}

bool runAllTests() {
    return __runAllTests;
}

std::string htmlDecode(const std::string& s) {
    return ::htmlDecode(s);
}

std::string htmlEncode(const std::string& s) {
    return ::htmlEncode(s);
}

std::ofstream& __getXmlOut() {
    if (!__xout) {
        __xout = new std::ofstream();
    }
    return *__xout;
}

void printXml(const std::string& s) {
    __getXmlOut() << s;
}

void printlnXml(const std::string& s) {
    __getXmlOut() << s << std::endl;
}

void printXml(bool b) {
    __getXmlOut() << std::boolalpha << b;
}

void printlnXml(bool b) {
    __getXmlOut() << std::boolalpha << b << std::endl;
}

void printXml(double d) {
    // stop C++ from printing large values in scientific notation
    // (the values below seem to be the thresholds at which auto scientific
    // notation starts to be used in printing output of real numbers)
    const double SCI_NOTATION_POS = 1.0e6;
    const double SCI_NOTATION_NEG = -1.0e6;

    std::string result;
    std::stringstream out;
    if (d >= SCI_NOTATION_POS || d <= SCI_NOTATION_NEG) {
        // in sci. notation range; print in 'fixed' precision mode
        // (need to manually set max precision to avoid truncation at ~6 digits)
        out << std::fixed << std::showpoint << std::setprecision(std::numeric_limits<double>::max_digits10) << d;
    } else {
        // not in sci. notation range; print in normal format, but
        // mandate decimal point, e.g. 4 => "4.0"
        out << std::showpoint << d;
    }
    result = out.str();

    // stop unnecessary 0 digits after decimal
    // e.g. "123.4560000" => "123.456"
    // e.g. "123.0000000" => "123.0"
    while (endsWith(result, "0")) {
        result.erase(result.length() - 1, 1);
    }
    if (result.empty() || endsWith(result, ".")) {
        result += "0";
    }

    // actually write the real number to the output stream
    __getXmlOut() << result;
}

void printlnXml(double d) {
    printXml(d);
    __getXmlOut() << std::endl;
}

// print in fixed mode, not scientific notation
void printXml(float f) {
    __getXmlOut() << std::fixed << std::showpoint << f;
}

void printlnXml(float f) {
    printXml(static_cast<double>(f));
    __getXmlOut() << std::endl;
}

std::string __stackTraceToString() {
    std::ostringstream out;
    exceptions::printStackTrace(out);
    return out.str();
}

void __printException(const std::string& type, const std::string& message,
                      const std::string& stacktrace, int lineNumber) {
    CodeStepByStep::__getXmlOut() << "<exception>\n"
            << "<type>" << type << "</type>" << std::endl
            << "<message>" << htmlEncode(message) << "</message>" << std::endl
            << "<line>" << lineNumber << "</line>" << std::endl
            << "<stacktrace>" << htmlEncode(stacktrace) << "</stacktrace>" << std::endl
            << "</exception>" << std::endl;
    CodeStepByStep::__getXmlOut().flush();
}

void __openXmlOldWay(const std::string& filename) {
    if (__xout) {
        __getXmlOut().flush();
        __getXmlOut().close();
        __xout = nullptr;
    }
    __xfout = fopen(filename.c_str(), "a+");   // open for appending
}

void __closeXml() {
    if (__xout) {
        __getXmlOut().close();
    }
    if (__xfout) {
        fclose(__xfout);
        __xfout = nullptr;
    }
}

void __printXml(const char* s) {
    fputs(s, __xfout);
    fflush(__xfout);
}

void __printXml(const std::string& s) {
    fputs(s.c_str(), __xfout);
    fflush(__xfout);
}

void __printlnXml(const char* s) {
    fputs(s, __xfout);
    fputs("\n", __xfout);
    fflush(__xfout);
}

void __printlnXml(const std::string& s) {
    fputs(s.c_str(), __xfout);
    fputs("\n", __xfout);
    fflush(__xfout);
}


// functions to parse various collections from strings
void ArrayIntList_fromString(ArrayIntList& list, const std::string& str) {
    std::istringstream input(str);
    input >> list;
}

void AssassinNode_fromString(AssassinNode*& ptr, const std::string& str) {
    std::istringstream input(str);
    input >> ptr;
}

void BasicGraph_fromString(BasicGraph& graph, const std::string& str) {
    std::istringstream input(str);
    input >> graph;
}

void BinaryTree_fromString(BinaryTree& tree, const std::string& str) {
    std::istringstream input(str);
    input >> tree;
}

void BinaryTreeNode_fromString(BinaryTreeNode*& root, const std::string& str) {
    std::istringstream input(str);
    input >> root;
}

void BinaryTreeNodeptr_fromString(BinaryTreeNode*& root, const std::string& str) {
    std::istringstream input(str);
    input >> root;
}

void BinaryTreeNodeChar_fromString(BinaryTreeNodeChar*& root, const std::string& str) {
    std::istringstream input(str);
    input >> root;
}

void BinaryTreeNodeCharptr_fromString(BinaryTreeNodeChar*& root, const std::string& str) {
    std::istringstream input(str);
    input >> root;
}

void BinaryTreeNodeDouble_fromString(BinaryTreeNodeDouble*& root, const std::string& str) {
    std::istringstream input(str);
    input >> root;
}

void BinaryTreeNodeString_fromString(BinaryTreeNodeString*& root, const std::string& str) {
    std::istringstream input(str);
    input >> root;
}

void HeapPriorityQueue_fromString(HeapPriorityQueue& pqueue, const std::string& str) {
    std::istringstream input(str);
    input >> pqueue;
}

void LinkedIntList_fromString(LinkedIntList& list, const std::string& str) {
    std::istringstream input(str);
    input >> list;
}

void ListNode_fromString(ListNode*& ptr, const std::string& str) {
    std::istringstream input(str);
    input >> ptr;
}

void ListNodeptr_fromString(ListNode*& ptr, const std::string& str) {
    std::istringstream input(str);
    input >> ptr;
}

void ListNodeDouble_fromString(ListNodeDouble*& ptr, const std::string& str) {
    std::istringstream input(str);
    input >> ptr;
}

void ListNodeDoubleptr_fromString(ListNodeDouble*& ptr, const std::string& str) {
    std::istringstream input(str);
    input >> ptr;
}

void ListNodeString_fromString(ListNodeString*& ptr, const std::string& str) {
    std::istringstream input(str);
    input >> ptr;
}

void ListNodeStringptr_fromString(ListNodeString*& ptr, const std::string& str) {
    std::istringstream input(str);
    input >> ptr;
}

Set<string> setFromFile(const std::string& filename, bool cache) {
    static Map<std::string, Set<string>> CACHE;
    if (cache && CACHE.containsKey(filename)) {
        return CACHE[filename];
    }

    ifstream input;
    input.open(filename.c_str());
    Set<string> result;
    string line;
    while (getline(input, line)) {
        result.add(toLowerCase(trim(line)));
    }
    if (cache) {
        CACHE[filename] = result;
    }
    return result;
}


// CODE FOR HANDLING SIGNALS (VARIOUS PROGRAM CRASHES)
void __codeStepByStepSignalHandler(int sig) {
    signal(sig, SIG_DFL);   // turn signal handler off

    // tailor the error message to the kind of signal that occurred
    CodeStepByStep::__closeXml();
    __openXmlOldWay(__xmlOutFilename);
    if (sig == SIGSEGV) {
        __printXml("<exception>\n<type>SIGSEGV</type>\n<message>segmentation fault</message>\n</exception>\n");
    } else if (sig == SIGABRT) {
        __printXml("<exception>\n<type>SIGABRT</type>\n<message>abort</message>\n</exception>\n");
    } else if (sig == SIGILL) {
        __printXml("<exception>\n<type>SIGILL</type>\n<message>illegal instruction</message>\n</exception>\n");
    } else if (sig == SIGFPE) {
        __printXml("<exception>\n<type>SIGFPE</type>\n<message>arithmetic error</message>\n</exception>\n");
    } else if (sig == SIGINT) {
        __printXml("<exception>\n<type>SIGINT</type>\n<message>interrupt error</message>\n</exception>\n");
    } else if (sig == SIGSTACK) {
        __printXml("<exception>\n<type>SIGSTACK</type>\n<message>stack overflow</message>\n</exception>\n");
    } else if (sig == SIGTERM) {
        __printXml("<exception>\n<type>SIGTERM</type>\n<message>terminated</message>\n</exception>\n");
    } else if (sig == SIGUSR1) {
        __printXml("<exception>\n<type>SIGUSR1</type>\n<message>Excessive output printed; you may have an infinite loop in your code.</message>\n</exception>\n");
    } else {
        __printXml("<exception>\n<type>SIGFATAL</type>\n<message>fatal error</message>\n</exception>\n");
    }

    if (__runAllTests) {
        __printXml("</test>\n");
        __printXml("</tests>\n");
    }

    __closeXml();
    std::exit(1);
}

#if !defined(_WIN32)
void __posixSignalHandler(int sig, siginfo_t* /*siginfo*/, void* /*context*/) {
    __codeStepByStepSignalHandler(sig);
}
#endif // !defined(_WIN32)

static void __setupSignalHandler() {
    bool handled = false;
#ifdef SHOULD_USE_SIGNAL_STACK
#if !defined(_WIN32)
    // alternate stack on Linux for stack overflows
    static uint8_t alternate_stack[SIGSTKSZ];
    stack_t ss = {};
    ss.ss_sp = (void*) alternate_stack;
    ss.ss_size = SIGSTKSZ;
    ss.ss_flags = 0;
    sigaltstack(&ss, nullptr);

    struct sigaction sig_action = {};
    sig_action.sa_sigaction = __posixSignalHandler;
    sigemptyset(&sig_action.sa_mask);
#ifdef __APPLE__
    // backtrace() doesn't work on OS X when we use an alternate stack
    sig_action.sa_flags = SA_SIGINFO;
#else
    sig_action.sa_flags = SA_SIGINFO | SA_ONSTACK;
#endif // __APPLE__
    sigaction(SIGSEGV, &sig_action, nullptr);
    sigaction(SIGFPE,  &sig_action, nullptr);
    sigaction(SIGILL,  &sig_action, nullptr);
    sigaction(SIGTERM, &sig_action, nullptr);
    sigaction(SIGINT,  &sig_action, nullptr);
    sigaction(SIGABRT, &sig_action, nullptr);
    sigaction(SIGUSR1, &sig_action, nullptr);
    handled = true;
#endif
#endif // SHOULD_USE_SIGNAL_STACK

    if (!handled) {
        signal(SIGABRT, CodeStepByStep::__codeStepByStepSignalHandler);
        signal(SIGFPE,  CodeStepByStep::__codeStepByStepSignalHandler);
        signal(SIGILL,  CodeStepByStep::__codeStepByStepSignalHandler);
        signal(SIGINT,  CodeStepByStep::__codeStepByStepSignalHandler);
        signal(SIGSEGV, CodeStepByStep::__codeStepByStepSignalHandler);
        signal(SIGTERM, CodeStepByStep::__codeStepByStepSignalHandler);
        signal(SIGUSR1, CodeStepByStep::__codeStepByStepSignalHandler);
    }
}

static void __disableSignalHandler() {
    signal(SIGABRT, SIG_DFL);
    signal(SIGFPE,  SIG_DFL);
    signal(SIGILL,  SIG_DFL);
    signal(SIGINT,  SIG_DFL);
    signal(SIGSEGV, SIG_DFL);
    signal(SIGTERM, SIG_DFL);
    signal(SIGUSR1, SIG_DFL);
}

static void __terminateHandler() {
    __disableSignalHandler();   // don't want both a signal AND a terminate() call

    std::string stackTrace;
    try {
        std::ostringstream out;
        exceptions::printStackTrace(out);
        stackTrace = out.str();
        throw;   // re-throws the exception that already occurred
    } catch (int value) {
        CodeStepByStep::__printException("int", integerToString(value), stackTrace);
    } catch (long value) {
        CodeStepByStep::__printException("long", longToString(value), stackTrace);
    } catch (float value) {
        CodeStepByStep::__printException("float", doubleToString((double) value), stackTrace);
    } catch (double value) {
        CodeStepByStep::__printException("double", doubleToString(value), stackTrace);
    } catch (bool value) {
        CodeStepByStep::__printException("bool", boolToString(value), stackTrace);
    } catch (char value) {
        CodeStepByStep::__printException("char", "'" + charToString(value) + "'", stackTrace);
    } catch (std::string value) {
        CodeStepByStep::__printException("string", value, stackTrace);
    } catch (const char* value) {
        CodeStepByStep::__printException("string", value, stackTrace);
    } catch (ErrorException value) {
        CodeStepByStep::__printException("ErrorException", value.what(), stackTrace);
    } catch (std::exception& value) {
        CodeStepByStep::__printException("exception", value.what(), stackTrace);
    } catch (...) {
        CodeStepByStep::__printException("unknown", "", stackTrace);
    }

    if (CodeStepByStep::__runAllTests) {
        CodeStepByStep::__getXmlOut() << "</test>" << std::endl;
        CodeStepByStep::__getXmlOut() << "</tests>" << std::endl;
    }
    CodeStepByStep::__closeXml();
}


void main_begin(int argc, char** argv) {
    // initialize Stanford library
    // TODO
    // __initializeStanfordCppLibrary(argc, argv);

    // set up signal handler to process serious errors
    CodeStepByStep::__setupSignalHandler();
    CodeStepByStep::old_terminate = std::set_terminate(CodeStepByStep::__terminateHandler);

    // echo console input
    plainconsole::setEcho(true);

    // max amount of output a solution can print before it should be halted
    const int __OUTPUT_PRINT_MAX = 100000;
    plainconsole::setOutputLimit(__OUTPUT_PRINT_MAX);

    // parse command-line args
    CodeStepByStep::__testToRun = "";
    for (int i = 1; i < argc; i++) {
        std::string arg = argv[i];
        if (i < argc - 1 && arg == "--test") {
            CodeStepByStep::__testToRun = argv[i + 1];
        } else if (arg == "--all") {
            CodeStepByStep::__testToRun = "--all";
            CodeStepByStep::__runAllTests = true;
        } else if (i < argc - 1 && arg == "--xml") {
            CodeStepByStep::__xmlOutFilename = argv[i + 1];
            CodeStepByStep::__getXmlOut().open(argv[i + 1]);
            // CodeStepByStep::__openXml(__xmlOutFilename);
        }
    }

    if (CodeStepByStep::__runAllTests) {
        // output XML prolog
        CodeStepByStep::__getXmlOut() << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>" << std::endl
                << "<tests>" << std::endl;
        CodeStepByStep::__getXmlOut().flush();
    }
}

void main_end() {
    if (CodeStepByStep::__runAllTests) {
        CodeStepByStep::__getXmlOut() << "</tests>" << std::endl;
        CodeStepByStep::__getXmlOut().flush();
    }

    CodeStepByStep::__closeXml();
}


namespace Assertions {
void assertEqualsBool(const std::string& msg, bool expected, bool actual) {
    assertEquals(msg, "bool", boolToString(expected), boolToString(actual));
}

void assertEqualsChar(const std::string& msg, char expected, char actual) {
    assertEquals(msg, "char", charToString(expected), charToString(actual));
}

void assertEqualsDouble(const std::string& msg, double expected, double actual, double tolerance) {
    Map<std::string, std::string> attrs;
    attrs["tolerance"] = doubleToString(tolerance);
    assertEquals(msg, "double", doubleToString(expected), doubleToString(actual), attrs);
}

void assertEqualsInt(const std::string& msg, int expected, int actual) {
    assertEquals(msg, "int", integerToString(expected), integerToString(actual));
}

void assertEqualsString(const std::string& msg, std::string expected, std::string actual) {
    assertEquals(msg, "string", expected, actual);
}

void assertTrue(const std::string& msg, bool test) {
    assertionPrint(msg, "assertTrue", "bool", "true", boolToString(test));
}

void assertFalse(const std::string& msg, bool test) {
    assertionPrint(msg, "assertFalse", "bool", "false", boolToString(test));
}

void assertFail(const std::string& msg) {
    assertionPrint(msg, "assertFail", "bool", /* expected */ "pass", /* actual */ "fail");
}

void setTestName(const std::string& name) {
    assertionPrint(/* message */ name, "setTestName", "string", /* expected */ "", /* actual */ "");
}

void assertionPrint(const std::string& msg,
                    const std::string& assertType,
                    const std::string& valueType,
                    const std::string& expected,
                    const std::string& actual,
                    Map<std::string, std::string> attrs) {
    CodeStepByStep::__getXmlOut() << "<assertion type=\"" << htmlEncode(assertType) << "\"";
    for (std::string attr : attrs) {
        CodeStepByStep::__getXmlOut() << " " << attr << "=\"" << htmlEncode(attrs[attr]) << "\"";
    }
    CodeStepByStep::__getXmlOut() << ">" << std::endl;
    CodeStepByStep::__getXmlOut() << "<message>" << htmlEncode(msg) << "</message>" << std::endl;
    CodeStepByStep::__getXmlOut() << "<type>" << htmlEncode(valueType) << "</type>" << std::endl;
    CodeStepByStep::__getXmlOut() << "<expected>" << htmlEncode(expected) << "</expected>" << std::endl;
    CodeStepByStep::__getXmlOut() << "<actual>" << htmlEncode(actual) << "</actual>" << std::endl;
    CodeStepByStep::__getXmlOut() << "</assertion>" << std::endl;
}
} // namespace CodeStepByStep::Assertions

} // namespace CodeStepByStep

/////////////////////// END code extracted from StanfordCPPLib_CodeStepByStep_Project/src/codestepbystep.cpp ///////////////////////