forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
middleearth.cpp.html
184 lines (164 loc) · 31 KB
/
middleearth.cpp.html
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
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="GNU source-highlight
by Lorenzo Bettini
http://www.lorenzobettini.it
http://www.gnu.org/software/src-highlite">
<title>middleearth.cpp</title>
</head>
<body style="background-color:white">
<pre><b><span style="color:#000080">#include</span></b> <span style="color:#FF0000">"middleearth.h"</span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><algorithm></span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><array></span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><cstdlib></span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><cmath></span>
<i><span style="color:#9A1900">// New shuffle method that uses the Mersenne Twister engine</span></i>
<span style="color:#009900">void</span> <b><span style="color:#000000">shuffle</span></b> <span style="color:#990000">(</span>vector<span style="color:#990000"><</span>string<span style="color:#990000">>::</span><span style="color:#008080">iterator</span> first<span style="color:#990000">,</span> vector<span style="color:#990000"><</span>string<span style="color:#990000">>::</span><span style="color:#008080">iterator</span> last<span style="color:#990000">,</span> mt19937<span style="color:#990000">&</span> g<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><b><span style="color:#0000FF">auto</span></b> i<span style="color:#990000">=(</span>last<span style="color:#990000">-</span>first<span style="color:#990000">)-</span><span style="color:#993399">1</span><span style="color:#990000">;</span> i<span style="color:#990000">></span><span style="color:#993399">0</span><span style="color:#990000">;</span> <span style="color:#990000">--</span>i<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<span style="color:#009900">unsigned</span> <span style="color:#009900">int</span> n <span style="color:#990000">=</span> <span style="color:#990000">(</span><b><span style="color:#000000">g</span></b><span style="color:#990000">()</span> <span style="color:#990000">/</span> <span style="color:#990000">(</span><span style="color:#009900">double</span><span style="color:#990000">)</span> g<span style="color:#990000">.</span><b><span style="color:#000000">max</span></b><span style="color:#990000">())*</span><b><span style="color:#000000">distance</span></b><span style="color:#990000">(</span>first<span style="color:#990000">,</span>last<span style="color:#990000">);</span>
<b><span style="color:#000000">swap</span></b> <span style="color:#990000">(</span>first<span style="color:#990000">[</span>i<span style="color:#990000">],</span> first<span style="color:#990000">[</span>n<span style="color:#990000">]);</span>
<span style="color:#FF0000">}</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// The list of all the place names that we'll be using</span></i>
<b><span style="color:#0000FF">const</span></b> <span style="color:#008080">array<string, 40></span> all_city_names<span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// human towns, cities and strongholds</span></i>
<span style="color:#FF0000">"Bree"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// a human and hobbit town between the Shire and Rivendell</span></i>
<span style="color:#FF0000">"Isengard"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the tower fortress where Saruman resided; Gandalf was imprisoned there.</span></i>
<span style="color:#FF0000">"Minas Tirith"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// capital of Gondor, the "white city"; home to Boromir, Denethor, and later, Aragorn</span></i>
<span style="color:#FF0000">"Osgiliath"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// city on the river Anduin; is at the other end of Pelennor Fields from M. Tirith</span></i>
<span style="color:#FF0000">"Edoras"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the capital city of Rohan, where King Theoden resides</span></i>
<span style="color:#FF0000">"Helm's Deep"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// fortress of Rohan, it is where the people of Edoras fled to from the orc invasion</span></i>
<span style="color:#FF0000">"Dunharrow"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// a refuge of Rohan, it is where Elrond presents the sword to Aragorn in the movie</span></i>
<i><span style="color:#9A1900">// dwarf cities</span></i>
<span style="color:#FF0000">"Moria"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the enormous dwarven underground complex that the Fellowship traveled through</span></i>
<i><span style="color:#9A1900">// elvish cities</span></i>
<span style="color:#FF0000">"Lothlorien"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the elvish tree-city, home of Lady Galadriel and Lord Celeborn</span></i>
<span style="color:#FF0000">"Rivendell"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the elvish city that is home to Lord Elrond</span></i>
<span style="color:#FF0000">"The Grey Havens"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the port city on the western coast from which the elves travel westward</span></i>
<i><span style="color:#9A1900">// hobbit villages</span></i>
<span style="color:#FF0000">"Bucklebury"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// a Shire village, it has a ferry across the Brandywine River that the Hobbits use</span></i>
<span style="color:#FF0000">"Bywater"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// a Shire village, it is the site of the Battle of Bywater (removed from the movie)</span></i>
<span style="color:#FF0000">"Hobbiton"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// a Shire village, it is home to Bilbo and, later, Frodo</span></i>
<span style="color:#FF0000">"Michel Delving"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// a Shire village, it is the chief town of the Shire</span></i>
<i><span style="color:#9A1900">// Mordor places</span></i>
<span style="color:#FF0000">"Orodruin"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// Mount Doom in Mordor, it is where the Ring was made, and later, unmade</span></i>
<span style="color:#FF0000">"Barad-Dur"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// Sauron's fortress that was part castle, part mountain</span></i>
<span style="color:#FF0000">"Minas Morgul"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// formerly the Gondorian city of Minas Ithil; renamed when Sauron took it over</span></i>
<span style="color:#FF0000">"Cirith Ungol"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the mountianous pass that Sam & Frodo went through; home of Shelob</span></i>
<span style="color:#FF0000">"Gorgoroth"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the plains in Mordor that Frodo & Sam had to cross to reach Mount Doom</span></i>
<i><span style="color:#9A1900">// places that are not cities</span></i>
<span style="color:#FF0000">"Emyn Muil"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the rocky region that Sam & Frodo climb through after leaving the Fellowship</span></i>
<span style="color:#FF0000">"Fangorn Forest"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the forest where Treebeard (and the other Ents) live</span></i>
<span style="color:#FF0000">"Dagorlad"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// great plain/swamp between Emyn Muil & Mordor where a great battle was fought long ago</span></i>
<span style="color:#FF0000">"Weathertop"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the tower between Bree and Rivendell where Aragorn and the Hobbits take refuge</span></i>
<span style="color:#FF0000">"Gladden Fields"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// this is where the Ring is lost in the River Anduin, after Isildur is ambushed and killed by Orcs</span></i>
<span style="color:#FF0000">"Entwash River"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// a river through Rohan, which flows through Fangorn Forest</span></i>
<span style="color:#FF0000">"River Isen"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// river through the Gap of Rohan; Theoden's son was slain in a battle here.</span></i>
<span style="color:#FF0000">"The Black Gate"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// huge gate to Mordor that Aragorn and company attack as the ring is destroyed</span></i>
<span style="color:#FF0000">"The Old Forest"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// a forest to the west of the Shire (adventures there were removed from the movie)</span></i>
<span style="color:#FF0000">"Trollshaws"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// area to the west of Rivendell that was home to the trolls that Bilbo met</span></i>
<span style="color:#FF0000">"Pelennor Fields"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// great plain between M. Tirith and Osgiliath; site of the Battle of M. Tirith</span></i>
<span style="color:#FF0000">"Hollin"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the empty plains that the Fellowship crosses between Rivendell and Moria</span></i>
<span style="color:#FF0000">"Mirkwood"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// Legolas' forest home; Bilbo travels there in 'The Hobbit'.</span></i>
<span style="color:#FF0000">"Misty Mountains"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the north-south moutain range that runs through Middle-earth</span></i>
<span style="color:#FF0000">"Prancing Pony"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// an inn in Bree where the hobbits tried to meet Gandalf, but meet Aragorn instead</span></i>
<i><span style="color:#9A1900">// places from the Hobbit book and movies</span></i>
<span style="color:#FF0000">"Laketown"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// also called Esgaorth, it is the town of men on the Long Lake near Erebor</span></i>
<span style="color:#FF0000">"Dale"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the town of men outside Erebor, destroyed by Smaug long before the Hobbit story</span></i>
<span style="color:#FF0000">"Erebor"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// the Elvish name for the Lonely Mountain, where the dwarves had their fortress</span></i>
<span style="color:#FF0000">"Beorn's House"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// Beorn is the shape-shifter who shelters the dwarf party</span></i>
<span style="color:#FF0000">"Dol Guldur"</span><span style="color:#990000">,</span> <i><span style="color:#9A1900">// fortress in Mirkwood where Sauron, as the Necromancer, hid during most of the Hobbit</span></i>
<span style="color:#FF0000">}</span><span style="color:#990000">;</span>
<i><span style="color:#9A1900">// Iluvatar, the creator of Middle-Earth</span></i>
MiddleEarth<span style="color:#990000">::</span><b><span style="color:#000000">MiddleEarth</span></b><span style="color:#990000">(</span><span style="color:#009900">int</span> xsize<span style="color:#990000">,</span> <span style="color:#009900">int</span> ysize<span style="color:#990000">,</span> <span style="color:#009900">int</span> num_cities<span style="color:#990000">,</span> <span style="color:#009900">int</span> seed<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">this</span></b><span style="color:#990000">-></span>xsize <span style="color:#990000">=</span> xsize<span style="color:#990000">;</span>
<b><span style="color:#0000FF">this</span></b><span style="color:#990000">-></span>ysize <span style="color:#990000">=</span> ysize<span style="color:#990000">;</span>
<i><span style="color:#9A1900">// set up the random number generator</span></i>
gen<span style="color:#990000">.</span><b><span style="color:#000000">seed</span></b><span style="color:#990000">(</span>seed <span style="color:#990000">==</span> <span style="color:#990000">-</span><span style="color:#993399">1</span> <span style="color:#990000">?</span> random_device<span style="color:#FF0000">{}</span><span style="color:#990000">()</span> <span style="color:#990000">:</span> seed<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// count the number of cities in the array</span></i>
<b><span style="color:#0000FF">this</span></b><span style="color:#990000">-></span>num_city_names <span style="color:#990000">=</span> all_city_names<span style="color:#990000">.</span><b><span style="color:#000000">size</span></b><span style="color:#990000">();</span>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>num_cities <span style="color:#990000">></span> num_city_names<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"There are only "</span> <span style="color:#990000"><<</span> num_city_names <span style="color:#990000"><<</span> <span style="color:#FF0000">" city names, so "</span>
<span style="color:#990000"><<</span> num_cities <span style="color:#990000"><<</span> <span style="color:#FF0000">" cities cannot be created."</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"Exiting."</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<b><span style="color:#000000">exit</span></b><span style="color:#990000">(</span><span style="color:#993399">0</span><span style="color:#990000">);</span>
<span style="color:#FF0000">}</span>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>num_cities <span style="color:#990000"><</span> <span style="color:#993399">5</span><span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
num_cities <span style="color:#990000">=</span> <span style="color:#993399">5</span><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// copy all the cities into a mutable vector</span></i>
<b><span style="color:#0000FF">this</span></b><span style="color:#990000">-></span>cities <span style="color:#990000">=</span> vector<span style="color:#990000"><</span>string<span style="color:#990000">>(</span>all_city_names<span style="color:#990000">.</span><b><span style="color:#000000">begin</span></b><span style="color:#990000">(),</span> all_city_names<span style="color:#990000">.</span><b><span style="color:#000000">end</span></b><span style="color:#990000">());</span>
<b><span style="color:#000000">shuffle</span></b><span style="color:#990000">(</span>cities<span style="color:#990000">.</span><b><span style="color:#000000">begin</span></b><span style="color:#990000">(),</span> cities<span style="color:#990000">.</span><b><span style="color:#000000">end</span></b><span style="color:#990000">(),</span> gen<span style="color:#990000">);</span> <i><span style="color:#9A1900">// shuffle all the cities</span></i>
cities<span style="color:#990000">.</span><b><span style="color:#000000">erase</span></b><span style="color:#990000">(</span>cities<span style="color:#990000">.</span><b><span style="color:#000000">begin</span></b><span style="color:#990000">()</span> <span style="color:#990000">+</span> num_cities<span style="color:#990000">,</span> cities<span style="color:#990000">.</span><b><span style="color:#000000">end</span></b><span style="color:#990000">());</span> <i><span style="color:#9A1900">// then remove the ones we won't be using</span></i>
<i><span style="color:#9A1900">// compute random city positions</span></i>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><b><span style="color:#0000FF">auto</span></b> city <span style="color:#990000">:</span> cities<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
xpos<span style="color:#990000">.</span><b><span style="color:#000000">emplace</span></b><span style="color:#990000">(</span>city<span style="color:#990000">,</span> <span style="color:#990000">(</span><b><span style="color:#000000">gen</span></b><span style="color:#990000">()</span> <span style="color:#990000">/</span> <span style="color:#990000">(</span><span style="color:#009900">double</span><span style="color:#990000">)</span> gen<span style="color:#990000">.</span><b><span style="color:#000000">max</span></b><span style="color:#990000">())</span> <span style="color:#990000">*</span> xsize<span style="color:#990000">);</span>
ypos<span style="color:#990000">.</span><b><span style="color:#000000">emplace</span></b><span style="color:#990000">(</span>city<span style="color:#990000">,</span> <span style="color:#990000">(</span><b><span style="color:#000000">gen</span></b><span style="color:#990000">()</span> <span style="color:#990000">/</span> <span style="color:#990000">(</span><span style="color:#009900">double</span><span style="color:#990000">)</span> gen<span style="color:#990000">.</span><b><span style="color:#000000">max</span></b><span style="color:#990000">())</span> <span style="color:#990000">*</span> ysize<span style="color:#990000">);</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// compute the 2-d distance array</span></i>
<i><span style="color:#9A1900">// we assume that num_cities < xsize * ysize</span></i>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><b><span style="color:#0000FF">auto</span></b> city1 <span style="color:#990000">:</span> cities<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><b><span style="color:#0000FF">auto</span></b> city2 <span style="color:#990000">:</span> cities<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
distances<span style="color:#990000">[</span>city1<span style="color:#990000">].</span><b><span style="color:#000000">emplace</span></b><span style="color:#990000">(</span>city2<span style="color:#990000">,</span> <b><span style="color:#000000">sqrt</span></b><span style="color:#990000">((</span>xpos<span style="color:#990000">[</span>city2<span style="color:#990000">]</span> <span style="color:#990000">-</span> xpos<span style="color:#990000">[</span>city1<span style="color:#990000">])</span> <span style="color:#990000">*</span> <span style="color:#990000">(</span>xpos<span style="color:#990000">[</span>city2<span style="color:#990000">]</span> <span style="color:#990000">-</span> xpos<span style="color:#990000">[</span>city1<span style="color:#990000">])</span> <span style="color:#990000">+</span>
<span style="color:#990000">(</span>ypos<span style="color:#990000">[</span>city2<span style="color:#990000">]</span> <span style="color:#990000">-</span> ypos<span style="color:#990000">[</span>city1<span style="color:#990000">])</span> <span style="color:#990000">*</span> <span style="color:#990000">(</span>ypos<span style="color:#990000">[</span>city2<span style="color:#990000">]</span> <span style="color:#990000">-</span> ypos<span style="color:#990000">[</span>city1<span style="color:#990000">])));</span>
<span style="color:#FF0000">}</span>
<span style="color:#FF0000">}</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// The Mouth of Sauron!</span></i>
<i><span style="color:#9A1900">// Prints out info on the created 'world'</span></i>
<span style="color:#009900">void</span> MiddleEarth<span style="color:#990000">::</span><b><span style="color:#000000">print</span></b><span style="color:#990000">()</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"there are "</span> <span style="color:#990000"><<</span> num_city_names
<span style="color:#990000"><<</span> <span style="color:#FF0000">" locations to choose from; we are using "</span> <span style="color:#990000"><<</span> cities<span style="color:#990000">.</span><b><span style="color:#000000">size</span></b><span style="color:#990000">()</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"they are: "</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><b><span style="color:#0000FF">auto</span></b> city <span style="color:#990000">:</span> cities<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">"</span> <span style="color:#990000"><<</span> city <span style="color:#990000"><<</span> <span style="color:#FF0000">" @ ("</span> <span style="color:#990000"><<</span> xpos<span style="color:#990000">[</span>city<span style="color:#990000">]</span> <span style="color:#990000"><<</span> <span style="color:#FF0000">", "</span> <span style="color:#990000"><<</span> ypos<span style="color:#990000">[</span>city<span style="color:#990000">]</span>
<span style="color:#990000"><<</span> <span style="color:#FF0000">")"</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// Prints a tab-separated table of the distances,</span></i>
<i><span style="color:#9A1900">// which can be loaded into Excel or similar</span></i>
<span style="color:#009900">void</span> MiddleEarth<span style="color:#990000">::</span><b><span style="color:#000000">printTable</span></b><span style="color:#990000">()</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"Table: "</span> <span style="color:#990000"><<</span> endl <span style="color:#990000"><<</span> endl <span style="color:#990000"><<</span> <span style="color:#FF0000">"Location</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">xpos</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">ypos</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">"</span><span style="color:#990000">;</span>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><b><span style="color:#0000FF">auto</span></b> city <span style="color:#990000">:</span> cities<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> city <span style="color:#990000"><<</span> <span style="color:#FF0000">"</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">"</span><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
cout <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><b><span style="color:#0000FF">auto</span></b> city1 <span style="color:#990000">:</span> cities<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> city1 <span style="color:#990000"><<</span> <span style="color:#FF0000">"</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">"</span> <span style="color:#990000"><<</span> xpos<span style="color:#990000">[</span>city1<span style="color:#990000">]</span> <span style="color:#990000"><<</span> <span style="color:#FF0000">"</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">"</span> <span style="color:#990000"><<</span> ypos<span style="color:#990000">[</span>city1<span style="color:#990000">]</span> <span style="color:#990000"><<</span> <span style="color:#FF0000">"</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">"</span><span style="color:#990000">;</span>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><b><span style="color:#0000FF">auto</span></b> city2 <span style="color:#990000">:</span> cities<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> distances<span style="color:#990000">[</span>city1<span style="color:#990000">][</span>city2<span style="color:#990000">]</span> <span style="color:#990000"><<</span> <span style="color:#FF0000">"</span><span style="color:#CC33CC">\t</span><span style="color:#FF0000">"</span><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
cout <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// This method returns the distance between the two passed cities.</span></i>
<i><span style="color:#9A1900">// If we assume that the hash table (i.e. the map) is O(1),</span></i>
<i><span style="color:#9A1900">// then this method call is also O(1)</span></i>
<span style="color:#009900">float</span> MiddleEarth<span style="color:#990000">::</span><b><span style="color:#000000">getDistance</span></b><span style="color:#990000">(</span><b><span style="color:#0000FF">const</span></b> string<span style="color:#990000">&</span> city1<span style="color:#990000">,</span> <b><span style="color:#0000FF">const</span></b> string<span style="color:#990000">&</span> city2<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">return</span></b> distances<span style="color:#990000">[</span>city1<span style="color:#990000">][</span>city2<span style="color:#990000">];</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// Returns the list of cities to travel to.</span></i>
<i><span style="color:#9A1900">// The first city is the original start point as well as the end point.</span></i>
<i><span style="color:#9A1900">// The number of cities passed in does not include this start/end point</span></i>
<i><span style="color:#9A1900">// (so there will be length+1 entries in the returned vector).</span></i>
<span style="color:#008080">vector<string></span> MiddleEarth<span style="color:#990000">::</span><b><span style="color:#000000">getItinerary</span></b><span style="color:#990000">(</span><span style="color:#009900">unsigned</span> <span style="color:#009900">int</span> length<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// check parameter</span></i>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>length <span style="color:#990000">>=</span> cities<span style="color:#990000">.</span><b><span style="color:#000000">size</span></b><span style="color:#990000">())</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"You have requested an itinerary of "</span> <span style="color:#990000"><<</span> length
<span style="color:#990000"><<</span> <span style="color:#FF0000">" cities; you cannot ask for an itinerary of more than length "</span>
<span style="color:#990000"><<</span> cities<span style="color:#990000">.</span><b><span style="color:#000000">size</span></b><span style="color:#990000">()</span> <span style="color:#990000">-</span> <span style="color:#993399">1</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<b><span style="color:#000000">exit</span></b><span style="color:#990000">(</span><span style="color:#993399">0</span><span style="color:#990000">);</span>
<span style="color:#FF0000">}</span>
length<span style="color:#990000">++;</span> <i><span style="color:#9A1900">// to account for the start point</span></i>
<i><span style="color:#9A1900">// we need to make a deep copy of the cities vector</span></i>
<span style="color:#008080">vector<string></span> <b><span style="color:#000000">itinerary</span></b><span style="color:#990000">(</span>cities<span style="color:#990000">.</span><b><span style="color:#000000">begin</span></b><span style="color:#990000">(),</span> cities<span style="color:#990000">.</span><b><span style="color:#000000">end</span></b><span style="color:#990000">());</span>
<i><span style="color:#9A1900">// shuffle, erase unneeded ones, and return the itinerary</span></i>
<b><span style="color:#000000">shuffle</span></b><span style="color:#990000">(</span>itinerary<span style="color:#990000">.</span><b><span style="color:#000000">begin</span></b><span style="color:#990000">(),</span> itinerary<span style="color:#990000">.</span><b><span style="color:#000000">end</span></b><span style="color:#990000">(),</span> gen<span style="color:#990000">);</span>
itinerary<span style="color:#990000">.</span><b><span style="color:#000000">erase</span></b><span style="color:#990000">(</span>itinerary<span style="color:#990000">.</span><b><span style="color:#000000">begin</span></b><span style="color:#990000">()</span> <span style="color:#990000">+</span> length<span style="color:#990000">,</span> itinerary<span style="color:#990000">.</span><b><span style="color:#000000">end</span></b><span style="color:#990000">());</span>
<b><span style="color:#0000FF">return</span></b> itinerary<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
</pre>
</body>
</html>