forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
Copy pathgetWordInGrid.cpp.html
202 lines (184 loc) · 23.1 KB
/
getWordInGrid.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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
<!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>getWordInGrid.cpp</title>
</head>
<body style="background-color:white">
<pre><i><span style="color:#9A1900">/** This file defines and demonstrates two necessary components for</span></i>
<i><span style="color:#9A1900"> * the hash table lab for CS 2150. The first is the use of the</span></i>
<i><span style="color:#9A1900"> * getWordInGrid() function, which is used for retrieving a word in a</span></i>
<i><span style="color:#9A1900"> * grid of letters in one of the cardinal 8 directions (north,</span></i>
<i><span style="color:#9A1900"> * south-east, etc). The second is the use of file streams to read in</span></i>
<i><span style="color:#9A1900"> * input from a file, specifically one formatted as per the lab 6</span></i>
<i><span style="color:#9A1900"> * guidelines.</span></i>
<i><span style="color:#9A1900"> *</span></i>
<i><span style="color:#9A1900"> * Written by Aaron Bloomfield, 2009</span></i>
<i><span style="color:#9A1900"> */</span></i>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><iostream></span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><fstream></span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><string></span>
<b><span style="color:#0000FF">using</span></b> <b><span style="color:#0000FF">namespace</span></b> std<span style="color:#990000">;</span>
<i><span style="color:#9A1900">// We create a 2-D array of some big size, and assume that the grid</span></i>
<i><span style="color:#9A1900">// read in will be less than this size (a valid assumption for lab 6)</span></i>
<b><span style="color:#000080">#define</span></b> MAXROWS <span style="color:#993399">500</span>
<b><span style="color:#000080">#define</span></b> MAXCOLS <span style="color:#993399">500</span>
<span style="color:#009900">char</span> grid<span style="color:#990000">[</span>MAXROWS<span style="color:#990000">][</span>MAXCOLS<span style="color:#990000">];</span>
<i><span style="color:#9A1900">// Forward declarations</span></i>
<span style="color:#009900">bool</span> <b><span style="color:#000000">readInGrid</span></b><span style="color:#990000">(</span><span style="color:#008080">string</span> filename<span style="color:#990000">,</span> <span style="color:#009900">int</span><span style="color:#990000">&</span> rows<span style="color:#990000">,</span> <span style="color:#009900">int</span><span style="color:#990000">&</span> cols<span style="color:#990000">);</span>
<span style="color:#008080">string</span> <b><span style="color:#000000">getWordInGrid</span></b><span style="color:#990000">(</span><span style="color:#009900">int</span> startRow<span style="color:#990000">,</span> <span style="color:#009900">int</span> startCol<span style="color:#990000">,</span> <span style="color:#009900">int</span> dir<span style="color:#990000">,</span> <span style="color:#009900">int</span> len<span style="color:#990000">,</span>
<span style="color:#009900">int</span> numRows<span style="color:#990000">,</span> <span style="color:#009900">int</span> numCols<span style="color:#990000">);</span>
<i><span style="color:#9A1900">/** The main() function shows how to call both the readInGrid()</span></i>
<i><span style="color:#9A1900"> * function as well as the getWordInGrid() function.</span></i>
<i><span style="color:#9A1900"> */</span></i>
<span style="color:#009900">int</span> <b><span style="color:#000000">main</span></b><span style="color:#990000">()</span> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// to hold the number of rows and cols in the input file</span></i>
<span style="color:#009900">int</span> rows<span style="color:#990000">,</span> cols<span style="color:#990000">;</span>
<i><span style="color:#9A1900">// attempt to read in the file</span></i>
<span style="color:#009900">bool</span> result <span style="color:#990000">=</span> <b><span style="color:#000000">readInGrid</span></b><span style="color:#990000">(</span><span style="color:#FF0000">"5x8.grid.txt"</span><span style="color:#990000">,</span> rows<span style="color:#990000">,</span> cols<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// if there is an error, report it</span></i>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(!</span>result<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"Error reading in file!"</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<b><span style="color:#0000FF">return</span></b> <span style="color:#993399">1</span><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// Get a word (of length 10), starting at position (2,2) in the</span></i>
<i><span style="color:#9A1900">// array, in each of the 8 directions</span></i>
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><span style="color:#009900">int</span> i <span style="color:#990000">=</span> <span style="color:#993399">0</span><span style="color:#990000">;</span> i <span style="color:#990000"><</span> <span style="color:#993399">8</span><span style="color:#990000">;</span> i<span style="color:#990000">++)</span> <span style="color:#FF0000">{</span>
cout <span style="color:#990000"><<</span> i <span style="color:#990000"><<</span> <span style="color:#FF0000">": "</span> <span style="color:#990000"><<</span> <b><span style="color:#000000">getWordInGrid</span></b><span style="color:#990000">(</span><span style="color:#993399">2</span><span style="color:#990000">,</span> <span style="color:#993399">2</span><span style="color:#990000">,</span> i<span style="color:#990000">,</span> <span style="color:#993399">10</span><span style="color:#990000">,</span> rows<span style="color:#990000">,</span> cols<span style="color:#990000">)</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<b><span style="color:#0000FF">return</span></b> <span style="color:#993399">0</span><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">/** This function will read in a grid file, as per the format in the</span></i>
<i><span style="color:#9A1900"> * CS 2150 lab 6 document, into a global grid[][] array. It uses C++</span></i>
<i><span style="color:#9A1900"> * file streams, and thus requires the the </span></i><b><span style="color:#0000FF"><fstream></span></b><i><span style="color:#9A1900"> #include header.</span></i>
<i><span style="color:#9A1900"> *</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@return</span><i><span style="color:#9A1900"> true or false, depending on whether the file was</span></i>
<i><span style="color:#9A1900"> * successfully opened.</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> filename The file name to read in -- it's assumed to be in</span></i>
<i><span style="color:#9A1900"> * the file format described in the lab document.</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> rows The number of rows as specified in the input file;</span></i>
<i><span style="color:#9A1900"> * as this is a reference, it is set by the function.</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> cols The number of columns as specified in the input file;</span></i>
<i><span style="color:#9A1900"> * as this is a reference, it is set by the function.</span></i>
<i><span style="color:#9A1900"> */</span></i>
<span style="color:#009900">bool</span> <b><span style="color:#000000">readInGrid</span></b><span style="color:#990000">(</span><span style="color:#008080">string</span> filename<span style="color:#990000">,</span> <span style="color:#009900">int</span><span style="color:#990000">&</span> rows<span style="color:#990000">,</span> <span style="color:#009900">int</span><span style="color:#990000">&</span> cols<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// try to open the file</span></i>
<span style="color:#008080">ifstream</span> <b><span style="color:#000000">file</span></b><span style="color:#990000">(</span>filename<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// upon an error, return false</span></i>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(!</span>file<span style="color:#990000">.</span><b><span style="color:#000000">is_open</span></b><span style="color:#990000">())</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">return</span></b> <b><span style="color:#0000FF">false</span></b><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// first comes the number of rows</span></i>
file <span style="color:#990000">>></span> rows<span style="color:#990000">;</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"There are "</span> <span style="color:#990000"><<</span> rows <span style="color:#990000"><<</span> <span style="color:#FF0000">" rows."</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<i><span style="color:#9A1900">// then the columns</span></i>
file <span style="color:#990000">>></span> cols<span style="color:#990000">;</span>
cout <span style="color:#990000"><<</span> <span style="color:#FF0000">"There are "</span> <span style="color:#990000"><<</span> cols <span style="color:#990000"><<</span> <span style="color:#FF0000">" cols."</span> <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<i><span style="color:#9A1900">// and finally the grid itself</span></i>
<span style="color:#008080">string</span> data<span style="color:#990000">;</span>
file <span style="color:#990000">>></span> data<span style="color:#990000">;</span>
<i><span style="color:#9A1900">// close the file</span></i>
file<span style="color:#990000">.</span><b><span style="color:#000000">close</span></b><span style="color:#990000">();</span>
<i><span style="color:#9A1900">// convert the string read in to the 2-D grid format into the</span></i>
<i><span style="color:#9A1900">// grid[][] array.</span></i>
<i><span style="color:#9A1900">// In the process, we'll print the grid to the screen as well.</span></i>
<span style="color:#009900">int</span> pos <span style="color:#990000">=</span> <span style="color:#993399">0</span><span style="color:#990000">;</span> <i><span style="color:#9A1900">// the current position in the input data</span></i>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><span style="color:#009900">int</span> r <span style="color:#990000">=</span> <span style="color:#993399">0</span><span style="color:#990000">;</span> r <span style="color:#990000"><</span> rows<span style="color:#990000">;</span> r<span style="color:#990000">++)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><span style="color:#009900">int</span> c <span style="color:#990000">=</span> <span style="color:#993399">0</span><span style="color:#990000">;</span> c <span style="color:#990000"><</span> cols<span style="color:#990000">;</span> c<span style="color:#990000">++)</span> <span style="color:#FF0000">{</span>
grid<span style="color:#990000">[</span>r<span style="color:#990000">][</span>c<span style="color:#990000">]</span> <span style="color:#990000">=</span> data<span style="color:#990000">[</span>pos<span style="color:#990000">++];</span>
cout <span style="color:#990000"><<</span> grid<span style="color:#990000">[</span>r<span style="color:#990000">][</span>c<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>
<b><span style="color:#0000FF">return</span></b> <b><span style="color:#0000FF">true</span></b><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">/** This function will retrieve a word in a grid of letters in a given</span></i>
<i><span style="color:#9A1900"> * direction. If the end of the grid is encountered before the length</span></i>
<i><span style="color:#9A1900"> * of the desired string is reached, then a shorter string will be</span></i>
<i><span style="color:#9A1900"> * returned. The data is retrieved from a global char grid[][]</span></i>
<i><span style="color:#9A1900"> * array, which is assumed to be defined (and in scope). NOTE: The</span></i>
<i><span style="color:#9A1900"> * return value is a static string variable (for efficiency</span></i>
<i><span style="color:#9A1900"> * reasons), so a successive return value will overwrite a previous</span></i>
<i><span style="color:#9A1900"> * return value.</span></i>
<i><span style="color:#9A1900"> *</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@return</span><i><span style="color:#9A1900"> A STATIC string containing the letters in the provided direction.</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> startRow The starting (row,col) position to find the word.</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> startCol The starting (row,col) position to find the word.</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> dir The direction to move: 0 is north (upwards), 1 is</span></i>
<i><span style="color:#9A1900"> * northeast, and it rotates around clockwise until it</span></i>
<i><span style="color:#9A1900"> * reaches 7 for northwest.</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> len The desired length of the string to return (assuming</span></i>
<i><span style="color:#9A1900"> * the edge of the grid is not reached--if the edge of the</span></i>
<i><span style="color:#9A1900"> * grid is reached, it will return as many characters as</span></i>
<i><span style="color:#9A1900"> * possible up to the edge of the grid, so the returned</span></i>
<i><span style="color:#9A1900"> * string may not have the same length as this parameter</span></i>
<i><span style="color:#9A1900"> * indicates).</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> numRows The number of rows in the global char grid[][]</span></i>
<i><span style="color:#9A1900"> * array.</span></i>
<i><span style="color:#9A1900"> * </span></i><span style="color:#009900">@param</span><i><span style="color:#9A1900"> numCols The number of columns in the global char grid[][]</span></i>
<i><span style="color:#9A1900"> * array.</span></i>
<i><span style="color:#9A1900"> */</span></i>
<span style="color:#008080">string</span> <b><span style="color:#000000">getWordInGrid</span></b> <span style="color:#990000">(</span><span style="color:#009900">int</span> startRow<span style="color:#990000">,</span> <span style="color:#009900">int</span> startCol<span style="color:#990000">,</span> <span style="color:#009900">int</span> dir<span style="color:#990000">,</span> <span style="color:#009900">int</span> len<span style="color:#990000">,</span>
<span style="color:#009900">int</span> numRows<span style="color:#990000">,</span> <span style="color:#009900">int</span> numCols<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// the static-ness of this variable prevents it from being</span></i>
<i><span style="color:#9A1900">// re-declared upon each function invocation. It also prevents it</span></i>
<i><span style="color:#9A1900">// from being deallocated between invocations. It's probably not</span></i>
<i><span style="color:#9A1900">// good programming practice, but it's an efficient means to return</span></i>
<i><span style="color:#9A1900">// a value.</span></i>
<b><span style="color:#0000FF">static</span></b> <span style="color:#008080">string</span> output<span style="color:#990000">;</span>
output<span style="color:#990000">.</span><b><span style="color:#000000">clear</span></b><span style="color:#990000">();</span> <i><span style="color:#9A1900">// Since it's static we need to clear it</span></i>
output<span style="color:#990000">.</span><b><span style="color:#000000">reserve</span></b><span style="color:#990000">(</span><span style="color:#993399">256</span><span style="color:#990000">);</span> <i><span style="color:#9A1900">// Can't set capacity in the constructor so do it the first time here</span></i>
<i><span style="color:#9A1900">// the position in the output array, the current row, and the</span></i>
<i><span style="color:#9A1900">// current column</span></i>
<span style="color:#009900">int</span> r <span style="color:#990000">=</span> startRow<span style="color:#990000">,</span> c <span style="color:#990000">=</span> startCol<span style="color:#990000">;</span>
<i><span style="color:#9A1900">// iterate once for each character in the output</span></i>
<b><span style="color:#0000FF">for</span></b> <span style="color:#990000">(</span><span style="color:#009900">int</span> i <span style="color:#990000">=</span> <span style="color:#993399">0</span><span style="color:#990000">;</span> i <span style="color:#990000"><</span> len<span style="color:#990000">;</span> i<span style="color:#990000">++)</span> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// if the current row or column is out of bounds, then break</span></i>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>c <span style="color:#990000">>=</span> numCols <span style="color:#990000">||</span> r <span style="color:#990000">>=</span> numRows <span style="color:#990000">||</span> r <span style="color:#990000"><</span> <span style="color:#993399">0</span> <span style="color:#990000">||</span> c <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">break</span></b><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// set the next character in the output array to the next letter</span></i>
<i><span style="color:#9A1900">// in the grid</span></i>
output <span style="color:#990000">+=</span> grid<span style="color:#990000">[</span>r<span style="color:#990000">][</span>c<span style="color:#990000">];</span>
<i><span style="color:#9A1900">// move in the direction specified by the parameter</span></i>
<b><span style="color:#0000FF">switch</span></b> <span style="color:#990000">(</span>dir<span style="color:#990000">)</span> <span style="color:#FF0000">{</span> <i><span style="color:#9A1900">// assumes grid[0][0] is in the upper-left</span></i>
<b><span style="color:#0000FF">case</span></b> <span style="color:#993399">0</span><span style="color:#990000">:</span>
r<span style="color:#990000">--;</span>
<b><span style="color:#0000FF">break</span></b><span style="color:#990000">;</span> <i><span style="color:#9A1900">// north</span></i>
<b><span style="color:#0000FF">case</span></b> <span style="color:#993399">1</span><span style="color:#990000">:</span>
r<span style="color:#990000">--;</span>
c<span style="color:#990000">++;</span>
<b><span style="color:#0000FF">break</span></b><span style="color:#990000">;</span> <i><span style="color:#9A1900">// north-east</span></i>
<b><span style="color:#0000FF">case</span></b> <span style="color:#993399">2</span><span style="color:#990000">:</span>
c<span style="color:#990000">++;</span>
<b><span style="color:#0000FF">break</span></b><span style="color:#990000">;</span> <i><span style="color:#9A1900">// east</span></i>
<b><span style="color:#0000FF">case</span></b> <span style="color:#993399">3</span><span style="color:#990000">:</span>
r<span style="color:#990000">++;</span>
c<span style="color:#990000">++;</span>
<b><span style="color:#0000FF">break</span></b><span style="color:#990000">;</span> <i><span style="color:#9A1900">// south-east</span></i>
<b><span style="color:#0000FF">case</span></b> <span style="color:#993399">4</span><span style="color:#990000">:</span>
r<span style="color:#990000">++;</span>
<b><span style="color:#0000FF">break</span></b><span style="color:#990000">;</span> <i><span style="color:#9A1900">// south</span></i>
<b><span style="color:#0000FF">case</span></b> <span style="color:#993399">5</span><span style="color:#990000">:</span>
r<span style="color:#990000">++;</span>
c<span style="color:#990000">--;</span>
<b><span style="color:#0000FF">break</span></b><span style="color:#990000">;</span> <i><span style="color:#9A1900">// south-west</span></i>
<b><span style="color:#0000FF">case</span></b> <span style="color:#993399">6</span><span style="color:#990000">:</span>
c<span style="color:#990000">--;</span>
<b><span style="color:#0000FF">break</span></b><span style="color:#990000">;</span> <i><span style="color:#9A1900">// west</span></i>
<b><span style="color:#0000FF">case</span></b> <span style="color:#993399">7</span><span style="color:#990000">:</span>
r<span style="color:#990000">--;</span>
c<span style="color:#990000">--;</span>
<b><span style="color:#0000FF">break</span></b><span style="color:#990000">;</span> <i><span style="color:#9A1900">// north-west</span></i>
<span style="color:#FF0000">}</span>
<span style="color:#FF0000">}</span>
<b><span style="color:#0000FF">return</span></b> output<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
</pre>
</body>
</html>