Source code for ./labs/lab11/middleearth.cpp (via source-highlight)

#include "middleearth.h"

#include <algorithm>
#include <array>
#include <cstdlib>
#include <cmath>

// New shuffle method that uses the Mersenne Twister engine
void shuffle (vector<string>::iterator first, vector<string>::iterator last, mt19937& g) {
    for (auto i=(last-first)-1; i>0; --i) {
        unsigned int n = (g() / (double) g.max())*distance(first,last);
        swap (first[i], first[n]);
    }
}

// The list of all the place names that we'll be using
const array<string, 40> all_city_names{
    // human towns, cities and strongholds
    "Bree",             // a human and hobbit town between the Shire and Rivendell
    "Isengard",         // the tower fortress where Saruman resided; Gandalf was imprisoned there.
    "Minas Tirith",     // capital of Gondor, the "white city"; home to Boromir, Denethor, and later, Aragorn
    "Osgiliath",        // city on the river Anduin; is at the other end of Pelennor Fields from M. Tirith
    "Edoras",           // the capital city of Rohan, where King Theoden resides
    "Helm's Deep",      // fortress of Rohan, it is where the people of Edoras fled to from the orc invasion
    "Dunharrow",        // a refuge of Rohan, it is where Elrond presents the sword to Aragorn in the movie
    // dwarf cities
    "Moria",            // the enormous dwarven underground complex that the Fellowship traveled through
    // elvish cities
    "Lothlorien",       // the elvish tree-city, home of Lady Galadriel and Lord Celeborn
    "Rivendell",        // the elvish city that is home to Lord Elrond
    "The Grey Havens",  // the port city on the western coast from which the elves travel westward
    // hobbit villages
    "Bucklebury",       // a Shire village, it has a ferry across the Brandywine River that the Hobbits use
    "Bywater",          // a Shire village, it is the site of the Battle of Bywater (removed from the movie)
    "Hobbiton",         // a Shire village, it is home to Bilbo and, later, Frodo
    "Michel Delving",   // a Shire village, it is the chief town of the Shire
    // Mordor places
    "Orodruin",         // Mount Doom in Mordor, it is where the Ring was made, and later, unmade
    "Barad-Dur",        // Sauron's fortress that was part castle, part mountain
    "Minas Morgul",     // formerly the Gondorian city of Minas Ithil; renamed when Sauron took it over
    "Cirith Ungol",     // the mountianous pass that Sam & Frodo went through; home of Shelob
    "Gorgoroth",        // the plains in Mordor that Frodo & Sam had to cross to reach Mount Doom
    // places that are not cities
    "Emyn Muil",        // the rocky region that Sam & Frodo climb through after leaving the Fellowship
    "Fangorn Forest",   // the forest where Treebeard (and the other Ents) live
    "Dagorlad",         // great plain/swamp between Emyn Muil & Mordor where a great battle was fought long ago
    "Weathertop",       // the tower between Bree and Rivendell where Aragorn and the Hobbits take refuge
    "Gladden Fields",   // this is where the Ring is lost in the River Anduin, after Isildur is ambushed and killed by Orcs
    "Entwash River",    // a river through Rohan, which flows through Fangorn Forest
    "River Isen",       // river through the Gap of Rohan; Theoden's son was slain in a battle here.
    "The Black Gate",   // huge gate to Mordor that Aragorn and company attack as the ring is destroyed
    "The Old Forest",   // a forest to the west of the Shire (adventures there were removed from the movie)
    "Trollshaws",       // area to the west of Rivendell that was home to the trolls that Bilbo met
    "Pelennor Fields",  // great plain between M. Tirith and Osgiliath; site of the Battle of M. Tirith
    "Hollin",           // the empty plains that the Fellowship crosses between Rivendell and Moria
    "Mirkwood",         // Legolas' forest home; Bilbo travels there in 'The Hobbit'.
    "Misty Mountains",  // the north-south moutain range that runs through Middle-earth
    "Prancing Pony",    // an inn in Bree where the hobbits tried to meet Gandalf, but meet Aragorn instead
    // places from the Hobbit book and movies
    "Laketown",         // also called Esgaorth, it is the town of men on the Long Lake near Erebor
    "Dale",             // the town of men outside Erebor, destroyed by Smaug long before the Hobbit story
    "Erebor",           // the Elvish name for the Lonely Mountain, where the dwarves had their fortress
    "Beorn's House",    // Beorn is the shape-shifter who shelters the dwarf party
    "Dol Guldur",       // fortress in Mirkwood where Sauron, as the Necromancer, hid during most of the Hobbit
};

// Iluvatar, the creator of Middle-Earth
MiddleEarth::MiddleEarth(int xsize, int ysize, int num_cities, int seed) {
    this->xsize = xsize;
    this->ysize = ysize;

    // set up the random number generator
    gen.seed(seed == -1 ? random_device{}() : seed);

    // count the number of cities in the array
    this->num_city_names = all_city_names.size();

    if (num_cities > num_city_names) {
        cout << "There are only " << num_city_names << " city names, so "
             << num_cities << " cities cannot be created." << endl;
        cout << "Exiting." << endl;
        exit(0);
    }

    if (num_cities < 5) {
        num_cities = 5;
    }

    // copy all the cities into a mutable vector
    this->cities = vector<string>(all_city_names.begin(), all_city_names.end());

    shuffle(cities.begin(), cities.end(), gen); // shuffle all the cities
    cities.erase(cities.begin() + num_cities, cities.end()); // then remove the ones we won't be using

    // compute random city positions
    for (auto city : cities) {
        xpos.emplace(city, (gen() / (double) gen.max()) * xsize);
        ypos.emplace(city, (gen() / (double) gen.max()) * ysize);
    }

    // compute the 2-d distance array
    // we assume that num_cities < xsize * ysize
    for (auto city1 : cities) {
        for (auto city2 : cities) {
            distances[city1].emplace(city2, sqrt((xpos[city2] - xpos[city1]) * (xpos[city2] - xpos[city1]) +
                                                 (ypos[city2] - ypos[city1]) * (ypos[city2] - ypos[city1])));
        }
    }
}

// The Mouth of Sauron!
// Prints out info on the created 'world'
void MiddleEarth::print() {
    cout << "there are " << num_city_names
         << " locations to choose from; we are using " << cities.size() << endl;
    cout << "they are: " << endl;
    for (auto city : cities) {
        cout << "\t" << city << " @ (" << xpos[city] << ", " << ypos[city]
             << ")" << endl;
    }
}

// Prints a tab-separated table of the distances,
// which can be loaded into Excel or similar
void MiddleEarth::printTable() {
    cout << "Table: " << endl << endl << "Location\txpos\typos\t";
    for (auto city : cities) {
        cout << city << "\t";
    }
    cout << endl;

    for (auto city1 : cities) {
        cout << city1 << "\t" << xpos[city1] << "\t" << ypos[city1] << "\t";
        for (auto city2 : cities) {
            cout << distances[city1][city2] << "\t";
        }
        cout << endl;
    }
}

// This method returns the distance between the two passed cities.
// If we assume that the hash table (i.e. the map) is O(1),
// then this method call is also O(1)
float MiddleEarth::getDistance(const string& city1, const string& city2) {
    return distances[city1][city2];
}

// Returns the list of cities to travel to.
// The first city is the original start point as well as the end point.
// The number of cities passed in does not include this start/end point
// (so there will be length+1 entries in the returned vector).
vector<string> MiddleEarth::getItinerary(unsigned int length) {
    // check parameter
    if (length >= cities.size()) {
        cout << "You have requested an itinerary of " << length
             << " cities; you cannot ask for an itinerary of more than length "
             << cities.size() - 1 << endl;
        exit(0);
    }

    length++; // to account for the start point

    // we need to make a deep copy of the cities vector
    vector<string> itinerary(cities.begin(), cities.end());

    // shuffle, erase unneeded ones, and return the itinerary
    shuffle(itinerary.begin(), itinerary.end(), gen);
    itinerary.erase(itinerary.begin() + length, itinerary.end());
    return itinerary;
}