Show gridmap.h syntax highlighted
/***************************************************************************
gridmap.h - description
-------------------
begin : Sun Feb 2 2003
copyright : (C) 2003 by Brendon Higgins
email : freepop-devel@lists.sourceforge.net
***************************************************************************/
/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/
#ifndef GRIDMAP_H_INCLUDED
#define GRIDMAP_H_INCLUDED
#include <list>
#include <algorithm>
template<typename T, typename RT, typename G, typename Li>
class gridmap_iterator;
template<typename T, typename RT, typename G, typename Li>
class gridmap_radialiterator;
/**
* Place things on a grid so you can iterate through them radially.
* This container class allows you to efficiently iterate through its contents
* based on their distance from a given point. It aims to look reasonably
* similar to the standard containers templates.
*/
template<typename T>
class gridmap {
public:
/**
* Type contained.
*/
typedef T value_type;
/**
* Pointer to type contained.
*/
typedef value_type* pointer;
/**
* Const pointer to type contained.
*/
typedef const value_type* const_pointer;
/**
* Reference to type contained.
*/
typedef value_type& reference;
/**
* Const reference to type contained.
*/
typedef const value_type& const_reference;
/**
* The list type used for each grid point.
*/
typedef std::list<value_type> list_type;
/**
* The iterator for list_type.
*/
typedef typename list_type::iterator list_type_iterator;
/**
* The const list type used for each grid point.
*/
typedef const list_type const_list_type;
/**
* The iterator for const_list_type.
*/
typedef typename const_list_type::iterator const_list_type_iterator;
/**
* Standard linear iterator for this container.
*/
typedef gridmap_iterator<T, T, gridmap<T>, list_type_iterator> iterator;
/**
* Const standard linear iterator for this container.
*/
typedef gridmap_iterator<const T, T, const gridmap<T>,
const_list_type_iterator> const_iterator;
/**
* Radial iterator for this container.
*/
typedef gridmap_radialiterator<T, T, gridmap<T>,
list_type_iterator> radialiterator;
/**
* Const radial iterator for this container.
*/
typedef gridmap_radialiterator<const T, T, const gridmap<T>,
const_list_type_iterator> const_radialiterator;
friend class iterator;
friend class const_iterator;
friend class radialiterator;
friend class const_radialiterator;
private:
list_type *c;
int w;
int h;
public:
/**
* Constructor.
*/
gridmap(int width, int height)
: c(new list_type[width * height]), w(width), h(height) {
}
/**
* Destructor.
*/
~gridmap() {
delete[] c;
}
/**
* Return a regular iterator from the beginning.
*/
iterator begin() {
int pos = 0;
typename list_type::iterator i(c[pos].begin());
while (pos != w * h - 1 && i == c[pos].end()) {
++pos;
i = c[pos].begin();
}
return iterator(this, pos, i);
}
/**
* Return a regular const_iterator from the beginning.
*/
const_iterator begin() const {
int pos = 0;
typename list_type::iterator i(c[pos].begin());
while (pos != w * h - 1 && i == c[pos].end()) {
++pos;
i = c[pos].begin();
}
return const_iterator(this, pos, i);
}
/**
* Return a regular iterator from the end.
*/
iterator end() {
return iterator(this, w * h - 1, c[w * h - 1].end());
}
/**
* Return a regular const_iterator from the end.
*/
const_iterator end() const {
return const_iterator(this, w * h - 1, c[w * h - 1].end());
}
/**
* Insert the element at the given position on the grid.
*/
void push(const T& t, int x, int y) {
c[x + y * w].push_back(t);
}
/**
* Move the given element to another point on the grid.
* \note This causes reordering of the container, and thus using
* this while progressively iterating through the elements is
* a bad idea.
*
* \param i Location of element to move.
* \param nx The new x.
* \param ny The new y.
*/
iterator move(const iterator& i, int nx, int ny) {
push(*i, nx, ny);
return erase(i);
}
/**
* Remove an element from the container.
*
* \return Iterator to the next element, or end.
*/
iterator erase(const iterator& i) {
typename list_type::iterator li(c[i.pos].erase(i.i));
int pos = i.pos;
while (li == c[pos].end() && pos != (w * h - 1)) {
++pos;
li = c[pos].begin();
}
return iterator(this, pos, li);
}
/**
* Search for the position of a given element at a given position on the
* grid.
*/
iterator find_at(int x, int y, const value_type v) {
return iterator(this, x + y * w, std::find(c[x + y * w].begin(),
c[x + y * w].end(), v));
}
/**
* Begin iterating radially from the given point.
*/
radialiterator radiate_begin(int x, int y) {
return radialiterator(this, x, y);
}
/**
* Begin iterating radially from the given point.
*/
const_radialiterator radiate_begin(int x, int y) const {
return const_radialiterator(this, x, y);
}
};
/**
* Regular gridmap iterator. Performs standard iteration through the elements
* in a gridmap.
*/
template<typename T, typename RT, typename G, typename Li>
class gridmap_iterator {
public:
/**
* Type contained.
*/
typedef T value_type;
/**
* Pointer to type contained.
*/
typedef value_type* pointer;
/**
* Const pointer to type contained.
*/
typedef const value_type* const_pointer;
/**
* Reference to type contained.
*/
typedef value_type& reference;
/**
* Const reference to type contained.
*/
typedef const value_type& const_reference;
/**
* The iterator for list_type.
*/
typedef Li list_type_iterator;
/**
* The type of gridmap this iterator refers to.
*/
typedef G gridmap_type;
private:
gridmap_type* p;
int pos;
list_type_iterator i;
friend class gridmap<RT>;
/**
* Constructor. Used by gridmap.
*/
gridmap_iterator(gridmap_type* _p, int _pos, list_type_iterator _i)
: p(_p), pos(_pos), i(_i) {
}
public:
/**
* Constructor.
*/
gridmap_iterator(): p(NULL) {
}
/**
* Copy constructor.
*/
gridmap_iterator(const gridmap_iterator& x) {
p = x.p;
pos = x.pos;
i = x.i;
}
/**
* Copy operator.
*/
gridmap_iterator& operator=(const gridmap_iterator& x) {
p = x.p;
pos = x.pos;
i = x.i;
return *this;
}
/**
* Advance to the next element.
*/
gridmap_iterator& operator++() {
++i;
while (i == p->c[pos].end() && pos != (p->w * p->h - 1)) {
++pos;
i = p->c[pos].begin();
}
return *this;
}
/**
* Inequlaity.
*/
bool operator!=(const gridmap_iterator& x) const {
return pos != x.pos || i != x.i;
}
/**
* Equality.
*/
bool operator==(const gridmap_iterator& x) const {
return pos == x.pos && i == x.i;
}
/**
* Dereference.
* \return Reference to the element this iterator points to.
*/
reference operator*() {
return *i;
}
/**
* Dereference.
* \return Reference to the element this iterator points to.
*/
const_reference operator*() const {
return *i;
}
/**
* Dereference.
* \return Pointer to the element this iterator points to.
*/
pointer operator->() {
return &(*i);
}
/**
* Dereference.
* \return Pointer to the element this iterator points to.
*/
const_pointer operator->() const {
return &(*i);
}
};
/**
* Iterate based on distance from a point. Allows you to iterate around a given
* starting location, meaning you can stop if gone too far from the original
* point. This iterator behaves slightly different from a regular iterator.
* \todo Keep a static list of possible coords so that we don't have to
* generate one for each iterator.
*/
template<typename T, typename RT, typename G, typename Li>
class gridmap_radialiterator {
public:
/**
* Type contained.
*/
typedef T value_type;
/**
* Pointer to type contained.
*/
typedef value_type* pointer;
/**
* Const pointer to type contained.
*/
typedef const value_type* const_pointer;
/**
* Reference to type contained.
*/
typedef value_type& reference;
/**
* Const reference to type contained.
*/
typedef const value_type& const_reference;
/**
* The iterator for list_type.
*/
typedef Li list_type_iterator;
/**
* The type of gridmap this iterator refers to.
*/
typedef G gridmap_type;
private:
/**
* The type of list used for results.
*/
typedef std::list<pointer> resultlist_type;
/**
* The type of pair for coords.
*/
typedef std::pair<int, int> coordpair_type;
/**
* The type of list for coords to check.
*/
typedef std::list<coordpair_type> coordlist_type;
gridmap_type* p;
const int startx;
const int starty;
resultlist_type results;
coordpair_type loc;
coordlist_type coords;
/**
* How many corners have we seen? 4 (&& results.empty()) == end
*/
int corners;
friend class gridmap<RT>;
class dist_compare {
public:
bool operator()(coordpair_type x, coordpair_type y) const {
return x.first * x.first + x.second * x.second
< y.first * y.first + y.second * y.second;
}
};
coordpair_type next_coords() {
coordpair_type next = coords.front();
coords.pop_front();
if (next.second == 0) {
coordpair_type p(next.first + 1, 0);
coords.insert(std::lower_bound(coords.begin(), coords.end(), p, dist_compare()), p);
}
if (next.first != next.second) {
coordpair_type p(next.first, next.second + 1);
coords.insert(std::lower_bound(coords.begin(), coords.end(), p, dist_compare()), p);
}
return next;
}
gridmap_radialiterator(gridmap_type* _p, int _startx, int _starty)
: p(_p), startx(_startx), starty(_starty), loc(0, 0), corners(0) {
coords.push_back(coordpair_type(1, 0));
get_results(startx, starty);
if (results.empty()) {
get_next();
}
}
/**
* Records pointers to the elements at a given pos into results.
* Ignores coords that are out of range.
*/
void get_results(int x, int y) {
if (x < 0 || y < 0 || x >= p->w || y >= p->h) {
return;
}
if ((x == 0 || x == p->w - 1)
&& (y == 0 || y == p->h - 1)) {
// Checking a corner!
++corners;
}
list_type_iterator end(p->c[x + y * p->w].end());
for (list_type_iterator i(p->c[x + y * p->w].begin()); i != end; ++i) {
results.push_back(&(*i));
}
}
/**
* Gets results from position specified by loc and startx/starty.
*/
void next_results() {
// at least 8 alternatives to each pair (some may be duplicates):
// given (a, b) you get (a, b), (-a, b), (a, -b), (-a, -b),
// (b, a), (b, -a), (-b, a), and (-b, -a).
// if a == b this reduces to: or a == 0 (also applies to b):
// (a, b), (-a, b), (a, -b), (-a, -b) (0, b), (0, -b), (b, 0), (-b, 0)
// if a == 0 (also applies to b):
// (0, 0) - This should never happen!
// You gotta add them all (except for the duplicates).
if (loc.first == loc.second) {
get_results(startx + loc.first, starty + loc.second);
get_results(startx - loc.first, starty + loc.second);
get_results(startx + loc.first, starty - loc.second);
get_results(startx - loc.first, starty - loc.second);
} else if (loc.first == 0 || loc.second == 0) {
if (loc.second == 0) {
loc.second = loc.first;
loc.first = 0;
}
get_results(startx, starty + loc.second);
get_results(startx, starty - loc.second);
get_results(startx + loc.second, starty);
get_results(startx - loc.second, starty);
} else {
get_results(startx + loc.first, starty + loc.second);
get_results(startx - loc.first, starty + loc.second);
get_results(startx + loc.first, starty - loc.second);
get_results(startx - loc.first, starty - loc.second);
get_results(startx + loc.second, starty + loc.first);
get_results(startx - loc.second, starty + loc.first);
get_results(startx + loc.second, starty - loc.first);
get_results(startx - loc.second, starty - loc.first);
}
}
void get_next() {
while (results.empty() && corners < 4) {
loc = next_coords();
next_results();
}
}
public:
/**
* Constructor.
*/
gridmap_radialiterator(): p(NULL) {
// "You'd better gimme something to work with
// soon, else I'll throw a SEGV on yo ass."
}
/**
* Copy constructor.
*/
gridmap_radialiterator(const gridmap_radialiterator& x): p(x.p), startx(x.startx),
starty(x.starty), results(x.results), coords(x.coords), loc(x.loc),
corners(x.corners) {
}
/**
* Copy operator.
*/
gridmap_radialiterator& operator=(const gridmap_radialiterator& x) {
p = x.p;
startx = x.startx;
starty = x.starty;
results = x.results;
coords = x.coords;
loc = x.loc;
corners = x.corners;
return *this;
}
/**
* Is at the end?
*/
bool is_end() const {
return corners == 4 && results.empty();
}
/**
* Next.
*/
gridmap_radialiterator& operator++() {
results.pop_front();
get_next();
return *this;
}
/**
* \return Square of the distance from the original pos.
*/
int dist_sq() const {
return loc.first * loc.first + loc.second * loc.second;
}
/**
* Dereference.
*/
reference operator*() {
return *results.front();
}
/**
* Const dereference.
*/
const_reference operator*() const {
return *results.front();
}
/**
* Dereference.
*/
pointer operator->() {
return results.first();
}
/**
* Const dereference.
*/
const_pointer operator->() const {
return results.first();
}
};
#endif /* ndef GRIDMAP_H_INCLUDED */
See more files for this project here