StanfordCPPLib
gridlocation.h
1 /*
2  * File: gridlocation.h
3  * --------------------
4  * This file exports the <code>GridLocation</code> structure, which is a small
5  * structure representing a row and column.
6  * The row/column values are allowed to be negative or out of bounds; if an
7  * out-of-bounds location is passed to a grid, the grid will throw an error.
8  *
9  * Several members of the <code>Grid</code> and <code>SparseGrid</code> classes
10  * have been retrofitted to accept <code>GridLocation</code>s in place of integers
11  * for row/column indexes.
12  *
13  * This file also declares the <code>GridLocationRange</code> class,
14  * which represents a 2D range of grid locations that can be looped over.
15  *
16  * See gridlocation.cpp for the implementation of each member.
17  *
18  * @version 2018/03/12
19  * - initial version
20  */
21 
22 #include "private/init.h" // ensure that Stanford C++ lib is initialized
23 
24 #ifndef INTERNAL_INCLUDE
25 #include "private/initstudent.h" // insert necessary included code by student
26 #endif // INTERNAL_INCLUDE
27 
28 #ifndef _gridlocation_h
29 #define _gridlocation_h
30 
31 #include <iostream>
32 #include <iterator>
33 #include <string>
34 
35 #define INTERNAL_INCLUDE 1
36 #include "error.h"
37 #undef INTERNAL_INCLUDE
38 
39 class GridLocationRange; // forward declaration
40 
41 struct GridLocation {
42 public:
43  /*
44  * Constructs a location representing the given row and column (default 0).
45  * Any indexes are allowed, including negatives and out-of-bounds indexes.
46  */
47  GridLocation(int row = 0, int col = 0);
48 
49  /*
50  * Returns a range of locations that are <= the given range away from this one.
51  * For example, if you pass 1, will return the 9 locations in range (r-1, c-1) thru (r+1, c+1).
52  * The rowMajor parameter indicates whether the range will emit its members
53  * in row-major (default) or column-major order.
54  */
55  GridLocationRange neighbors(int range = 1, bool rowMajor = true) const;
56 
57  /*
58  * Returns a string representation of this location, such as "r2c17".
59  */
60  string toString() const;
61 
62  /* row and column data - may be directly accessed or modified */
63  int row;
64  int col;
65 };
66 
67 /*
68  * Returns an integer hash code for this grid location.
69  */
70 int hashCode(const GridLocation& loc);
71 
72 /*
73  * Relational operators for comparing grid locations.
74  */
75 bool operator <(const GridLocation& loc1, const GridLocation& loc2);
76 bool operator <=(const GridLocation& loc1, const GridLocation& loc2);
77 bool operator ==(const GridLocation& loc1, const GridLocation& loc2);
78 bool operator !=(const GridLocation& loc1, const GridLocation& loc2);
79 bool operator >(const GridLocation& loc1, const GridLocation& loc2);
80 bool operator >=(const GridLocation& loc1, const GridLocation& loc2);
81 
82 /*
83  * I/O stream operators for reading or writing locations in their toString format.
84  */
85 std::ostream& operator <<(std::ostream& out, const GridLocation& loc);
86 std::istream& operator >>(std::istream& input, GridLocation& loc);
87 
88 
89 /*
90  * Represents a range of grid locations.
91  * The actual individual grid locations are not all created and stored in
92  * this object; that would require a lot of memory usage.
93  * Instead, we primarily use this class for for-each looping over a given range
94  * of locations using its internal iterator.
95  *
96  * Common usage pattern:
97  * GridLocationRange range(0, 0, 10, 5);
98  * for (GridLocation loc : range) { ... }
99  *
100  * or, if you have a Grid collection, its locations() method returns a GridLocationRange
101  * object that you can loop over directly.
102  *
103  * for (GridLocation loc : grid.locations()) { ... }
104  */
106 private:
107  /*
108  * Internal iterator over range of indexes.
109  */
110  class GridLocationRangeIterator : public std::iterator<std::input_iterator_tag, GridLocation> {
111  private:
112  const GridLocationRange* glr;
113  GridLocation loc;
114 
115  public:
116  GridLocationRangeIterator(const GridLocationRange* glr, bool end)
117  : glr(glr) {
118  if (end) {
119  loc.row = glr->endRow() + 1;
120  loc.col = glr->endCol() + 1;
121  } else {
122  loc = glr->startLocation();
123  }
124  }
125 
126  GridLocationRangeIterator(const GridLocationRangeIterator& itr)
127  : glr(itr.glr),
128  loc(itr.loc) {
129  // empty
130  }
131 
132  GridLocationRangeIterator& operator ++() {
133  if (glr->isRowMajor()) {
134  loc.col++;
135  if (loc.col > glr->endCol()) {
136  loc.col = glr->startCol();
137  loc.row++;
138  }
139  } else {
140  loc.row++;
141  if (loc.row > glr->endRow()) {
142  loc.row = glr->startRow();
143  loc.col++;
144  }
145  }
146  if (!glr->contains(loc)) {
147  loc.row = glr->endRow() + 1;
148  loc.col = glr->endCol() + 1;
149  }
150  return *this;
151  }
152 
153  GridLocationRangeIterator operator ++(int) {
154  GridLocationRangeIterator copy(*this);
155  operator++();
156  return copy;
157  }
158 
159  GridLocationRangeIterator& operator --() {
160  if (glr->isRowMajor()) {
161  loc.col--;
162  if (loc.col < glr->startCol()) {
163  loc.col = glr->endCol();
164  loc.row--;
165  }
166  } else {
167  loc.row--;
168  if (loc.row < glr->startRow()) {
169  loc.row = glr->endRow();
170  loc.col--;
171  }
172  }
173  return *this;
174  }
175 
176  GridLocationRangeIterator operator --(int) {
177  GridLocationRangeIterator copy(*this);
178  operator--();
179  return copy;
180  }
181 
182  bool operator ==(const GridLocationRangeIterator& rhs) const {
183  return loc == rhs.loc;
184  }
185 
186  bool operator !=(const GridLocationRangeIterator& rhs) const {
187  return !(*this == rhs);
188  }
189 
190  bool operator <(const GridLocationRangeIterator& rhs) const {
191  if (glr != rhs.glr) {
192  error("GridLocationRange Iterator::operator <: Iterators are in different ranges");
193  }
194  return loc < rhs.loc;
195  }
196 
197  bool operator <=(const GridLocationRangeIterator& rhs) const {
198  if (glr != rhs.glr) {
199  error("GridLocationRange Iterator::operator <=: Iterators are in different ranges");
200  }
201  return loc <= rhs.loc;
202  }
203 
204  bool operator >(const GridLocationRangeIterator& rhs) const {
205  if (glr != rhs.glr) {
206  error("GridLocationRange Iterator::operator >: Iterators are in different ranges");
207  }
208  return loc > rhs.loc;
209  }
210 
211  bool operator >=(const GridLocationRangeIterator& rhs) const {
212  if (glr != rhs.glr) {
213  error("GridLocationRange Iterator::operator >=: Iterators are in different ranges");
214  }
215  return loc >= rhs.loc;
216  }
217 
218  const GridLocation& operator *() const {
219  return loc;
220  }
221 
222  const GridLocation* operator ->() const {
223  return &loc;
224  }
225  };
226 
227  GridLocation _start;
228  GridLocation _end;
229  bool _isRowMajor;
230 
231 public:
232  /*
233  * Constructs a range over the given start/end locations, inclusive.
234  * The isRowMajor flag indicates whether we will loop over the range in
235  * row-major order (true, default) or column-major order (false).
236  */
237  GridLocationRange(int startRow = 0, int startCol = 0, int endRow = 0, int endCol = 0, bool isRowMajor = true);
238 
239  /*
240  * Constructs a range over the given start/end locations, inclusive.
241  * The isRowMajor flag indicates whether we will loop over the range in
242  * row-major order (true, default) or column-major order (false).
243  */
244  GridLocationRange(const GridLocation& startLoc, const GridLocation& endLoc, bool isRowMajor = true);
245 
246  /*
247  * Returns an iterator over the range.
248  */
249  GridLocationRangeIterator begin() const;
250 
251  /*
252  * Returns true if this range entirely contains the given other range.
253  */
254  bool contains(const GridLocation& loc) const;
255 
256  /*
257  * Returns an iterator at the end of the range.
258  */
259  GridLocationRangeIterator end() const;
260 
261  /*
262  * Returns the last column in this range, inclusive.
263  */
264  int endCol() const;
265 
266  /*
267  * Returns the last row/column location in this range, inclusive.
268  */
269  const GridLocation& endLocation() const;
270 
271  /*
272  * Returns the last row in this range, inclusive.
273  */
274  int endRow() const;
275 
276  /*
277  * Returns true if this range contains no rows or columns.
278  */
279  bool isEmpty() const;
280 
281  /*
282  * Returns true if this range should be traversed in row-major order,
283  * as specified at time of construction (default true).
284  */
285  bool isRowMajor() const;
286 
287  /*
288  * Returns the first column in this range.
289  */
290  int startCol() const;
291 
292  /*
293  * Returns the first row/column location in this range.
294  */
295  const GridLocation& startLocation() const;
296 
297  /*
298  * Returns the first row in this range.
299  */
300  int startRow() const;
301 
302  /*
303  * Returns a string representation of this range,
304  * such as "[r1c3 .. r4c7]".
305  */
306  string toString() const;
307 };
308 
309 /*
310  * I/O stream operators for writing location ranges in their toString format.
311  */
312 std::ostream& operator <<(std::ostream& out, const GridLocationRange& range);
313 
314 #endif // _gridlocation_h
int startCol() const
Definition: gridlocation.cpp:148
bool contains(const GridLocation &loc) const
Definition: gridlocation.cpp:120
string toString() const
Definition: gridlocation.cpp:160
Definition: gridlocation.h:105
int startRow() const
Definition: gridlocation.cpp:156
GridLocationRange neighbors(int range=1, bool rowMajor=true) const
Definition: gridlocation.cpp:24
Definition: gridlocation.h:41
GridLocationRangeIterator begin() const
Definition: gridlocation.cpp:116
int endCol() const
Definition: gridlocation.cpp:128
GridLocationRange(int startRow=0, int startCol=0, int endRow=0, int endCol=0, bool isRowMajor=true)
Definition: gridlocation.cpp:102
bool isEmpty() const
Definition: gridlocation.cpp:140
const GridLocation & startLocation() const
Definition: gridlocation.cpp:152
GridLocation(int row=0, int col=0)
Definition: gridlocation.cpp:19
bool isRowMajor() const
Definition: gridlocation.cpp:144
int row
Definition: gridlocation.h:63
string toString() const
Definition: gridlocation.cpp:28
int col
Definition: gridlocation.h:64
GridLocationRangeIterator end() const
Definition: gridlocation.cpp:124
const GridLocation & endLocation() const
Definition: gridlocation.cpp:132
int endRow() const
Definition: gridlocation.cpp:136