00001
00002
00003
00004 #ifndef CAJUN_GRID_BASE_H
00005 #define CAJUN_GRID_BASE_H
00006
00007
00008 #include <list>
00009
00010 #if (__GNUC__ >= 4 && __GNUC_MINOR__ >= 1)
00011 #include <tr1/unordered_map>
00012 #define HashMap ::std::tr1::unordered_map
00013 #else
00014 #include <ext/hash_map>
00015 #define HashMap ::__gnu_cxx::hash_map
00016 #endif \
00017
00018 namespace cajun
00019 {
00020 class grid_base_t
00021 {
00022 public:
00023 grid_base_t () : m_lru_limit (600), m_lru_sequence (0) {}
00024
00025 void lru_limit (unsigned limit_) { m_lru_limit = limit_; }
00026 void lru_update () { m_lru_sequence++; }
00027 void lru_flush ();
00028
00029 protected:
00030 static int const TILE_SIZE = 32;
00031
00032 void split_coord (int coord_,
00033 int &tile_coord_, int &cell_coord_)
00034 {
00035 tile_coord_ = coord_ / TILE_SIZE;
00036 cell_coord_ = coord_ % TILE_SIZE;
00037 if (coord_ < 0 && cell_coord_)
00038 {
00039 tile_coord_--;
00040 cell_coord_ += TILE_SIZE;
00041 }
00042 }
00043
00044 virtual ~grid_base_t ();
00045
00046 class iterator_base_t;
00047
00048 class tile_base_t
00049 {
00050 public:
00051 int x () const { return m_x * TILE_SIZE; }
00052 int y () const { return m_y * TILE_SIZE; }
00053 bool lru_visited () const
00054 {
00055 return m_lru_sequence ==
00056 m_grid->m_lru_sequence;
00057 }
00058
00059 protected:
00060 tile_base_t ();
00061 virtual ~tile_base_t () {}
00062
00063 grid_base_t *m_grid;
00064
00065 int m_x;
00066 int m_y;
00067 tile_base_t *m_neighbor[4];
00068
00069 private:
00070 unsigned m_lru_sequence;
00071 std::list<tile_base_t *>::iterator m_lru_iter;
00072
00073 friend class grid_base_t;
00074 friend class iterator_base_t;
00075 };
00076
00077 class iterator_base_t
00078 {
00079 public:
00080 bool operator== (iterator_base_t const *v_) const
00081 {
00082 return m_tile == v_->m_tile &&
00083 m_x == v_->m_x && m_y == v_->m_y;
00084 }
00085 bool operator!= (iterator_base_t const *v_) const
00086 {
00087 return m_tile != v_->m_tile ||
00088 m_x != v_->m_x || m_y != v_->m_y;
00089 }
00090
00091 int x () const { return m_tile->x () + m_x; }
00092 int y () const { return m_tile->y () + m_y; }
00093
00094 void neighbor (int dx_, int dy_)
00095 {
00096 m_x += dx_;
00097 m_y += dy_;
00098
00099 if (m_x < 0 || m_x >= TILE_SIZE ||
00100 m_y < 0 || m_y >= TILE_SIZE)
00101 normalize ();
00102 }
00103 bool neighbor_if_exist (int dx_, int dy_)
00104 {
00105 m_x += dx_;
00106 m_y += dy_;
00107
00108 if (m_x < 0 || m_x >= TILE_SIZE ||
00109 m_y < 0 || m_y >= TILE_SIZE)
00110 return normalize_if_only_exist ();
00111 return true;
00112 }
00113 bool is_valid ()
00114 {
00115 if (m_x < 0 || m_x >= TILE_SIZE ||
00116 m_y < 0 || m_y >= TILE_SIZE)
00117 return normalize_if_only_exist ();
00118 return true;
00119
00120 }
00121 protected:
00122 tile_base_t *m_tile;
00123 int m_x;
00124 int m_y;
00125
00126 void normalize ();
00127 bool normalize_if_only_exist ();
00128
00129 friend class grid_base_t;
00130 };
00131 void find (iterator_base_t *iter_, int x_, int y_);
00132
00133 virtual tile_base_t *create_tile () = 0;
00134 private:
00135 struct key_t
00136 {
00137 public:
00138 key_t (int x_, int y_) : x (x_), y (y_) {}
00139
00140 bool operator== (key_t const &key_) const
00141 { return x == key_.x && y == key_.y; }
00142
00143 int x;
00144 int y;
00145 };
00146
00147 struct key_hash_t
00148 {
00149 int operator() (key_t const &key_) const
00150 { return (key_.x ^ key_.y); }
00151 };
00152
00153 void init_tile (int tx_, int ty_);
00154
00155 unsigned m_lru_limit;
00156 unsigned m_lru_sequence;
00157 std::list<tile_base_t *> m_lru_list;
00158
00159 void use_tile (tile_base_t *tile_)
00160 {
00161 tile_->m_lru_sequence = m_lru_sequence;
00162 m_lru_list.splice (m_lru_list.end (),
00163 m_lru_list, tile_->m_lru_iter);
00164 tile_->m_lru_iter = --m_lru_list.end ();
00165 }
00166
00167 protected:
00168
00169
00170 typedef HashMap<key_t, tile_base_t *, key_hash_t> index_t;
00171
00172 index_t m_index;
00173 };
00174 };
00175
00176
00177 #endif