OpenTTD
smallmatrix_type.hpp
Go to the documentation of this file.
1 /* $Id: smallmatrix_type.hpp 25256 2013-05-19 14:06:26Z rubidium $ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * OpenTTD 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, version 2.
6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
8  */
9 
12 #ifndef SMALLMATRIX_TYPE_HPP
13 #define SMALLMATRIX_TYPE_HPP
14 
15 #include "alloc_func.hpp"
16 #include "mem_func.hpp"
17 
39 template <typename T>
40 class SmallMatrix {
41 protected:
42  T *data;
43  uint width;
44  uint height;
45  uint capacity;
46 
47 public:
48 
49  SmallMatrix() : data(NULL), width(0), height(0), capacity(0) {}
50 
55  SmallMatrix(const SmallMatrix &other) : data(NULL), width(0), height(0), capacity(0)
56  {
57  this->Assign(other);
58  }
59 
60  ~SmallMatrix()
61  {
62  free(this->data);
63  }
64 
70  {
71  this->Assign(other);
72  return *this;
73  }
74 
78  inline void Assign(const SmallMatrix &other)
79  {
80  if (&other == this) return;
81 
82  this->height = other.Height();
83  this->width = other.Width();
84  uint num_items = this->width * this->height;
85  if (num_items > this->capacity) {
86  this->capacity = num_items;
87  free(this->data);
88  this->data = MallocT<T>(num_items);
89  MemCpyT(this->data, other[0], num_items);
90  } else if (num_items > 0) {
91  MemCpyT(this->data, other[0], num_items);
92  }
93  }
94 
98  inline void Clear()
99  {
100  /* In fact we just reset the width avoiding the need to
101  * probably reallocate the same amount of memory the matrix was
102  * previously using. */
103  this->width = 0;
104  }
105 
109  inline void Reset()
110  {
111  this->height = 0;
112  this->width = 0;
113  this->capacity = 0;
114  free(this->data);
115  this->data = NULL;
116  }
117 
121  inline void Compact()
122  {
123  uint capacity = this->height * this->width;
124  if (capacity >= this->capacity) return;
125  this->capacity = capacity;
126  this->data = ReallocT(this->data, this->capacity);
127  }
128 
133  void EraseColumn(uint x)
134  {
135  if (x < --this->width) {
136  MemCpyT<T>(this->data + x * this->height,
137  this->data + this->width * this->height,
138  this->height);
139  }
140  }
141 
147  void EraseColumnPreservingOrder(uint x, uint count = 1)
148  {
149  if (count == 0) return;
150  assert(x < this->width);
151  assert(x + count <= this->width);
152  this->width -= count;
153  uint to_move = (this->width - x) * this->height;
154  if (to_move > 0) {
155  MemMoveT(this->data + x * this->height,
156  this->data + (x + count) * this->height, to_move);
157  }
158  }
159 
164  void EraseRow(uint y)
165  {
166  if (y < this->height - 1) {
167  for (uint x = 0; x < this->width; ++x) {
168  this->data[x * this->height + y] =
169  this->data[(x + 1) * this->height - 1];
170  }
171  }
172  this->Resize(this->width, this->height - 1);
173  }
174 
180  void EraseRowPreservingOrder(uint y, uint count = 1)
181  {
182  if (this->height > count + y) {
183  for (uint x = 0; x < this->width; ++x) {
184  MemMoveT(this->data + x * this->height + y,
185  this->data + x * this->height + y + count,
186  this->height - count - y);
187  }
188  }
189  this->Resize(this->width, this->height - count);
190  }
191 
196  inline void AppendRow(uint to_add = 1)
197  {
198  this->Resize(this->width, to_add + this->height);
199  }
200 
205  inline void AppendColumn(uint to_add = 1)
206  {
207  this->Resize(to_add + this->width, this->height);
208  }
209 
216  inline void Resize(uint new_width, uint new_height)
217  {
218  uint new_capacity = new_width * new_height;
219  T *new_data = NULL;
220  void (*copy)(T *dest, const T *src, size_t count) = NULL;
221  if (new_capacity > this->capacity) {
222  /* If the data doesn't fit into current capacity, resize and copy ... */
223  new_data = MallocT<T>(new_capacity);
224  copy = &MemCpyT<T>;
225  } else {
226  /* ... otherwise just move the columns around, if necessary. */
227  new_data = this->data;
228  copy = &MemMoveT<T>;
229  }
230  if (this->height != new_height || new_data != this->data) {
231  if (this->height > 0) {
232  if (new_height > this->height) {
233  /* If matrix is growing, copy from the back to avoid
234  * overwriting uncopied data. */
235  for (uint x = this->width; x > 0; --x) {
236  if (x * new_height > new_capacity) continue;
237  (*copy)(new_data + (x - 1) * new_height,
238  this->data + (x - 1) * this->height,
239  min(this->height, new_height));
240  }
241  } else {
242  /* If matrix is shrinking copy from the front. */
243  for (uint x = 0; x < this->width; ++x) {
244  if ((x + 1) * new_height > new_capacity) break;
245  (*copy)(new_data + x * new_height,
246  this->data + x * this->height,
247  min(this->height, new_height));
248  }
249  }
250  }
251  this->height = new_height;
252  if (new_data != this->data) {
253  free(this->data);
254  this->data = new_data;
255  this->capacity = new_capacity;
256  }
257  }
258  this->width = new_width;
259  }
260 
261  inline uint Height() const
262  {
263  return this->height;
264  }
265 
266  inline uint Width() const
267  {
268  return this->width;
269  }
270 
278  inline const T &Get(uint x, uint y) const
279  {
280  assert(x < this->width && y < this->height);
281  return this->data[x * this->height + y];
282  }
283 
291  inline T &Get(uint x, uint y)
292  {
293  assert(x < this->width && y < this->height);
294  return this->data[x * this->height + y];
295  }
296 
303  inline const T *operator[](uint x) const
304  {
305  assert(x < this->width);
306  return this->data + x * this->height;
307  }
308 
315  inline T *operator[](uint x)
316  {
317  assert(x < this->width);
318  return this->data + x * this->height;
319  }
320 };
321 
322 #endif /* SMALLMATRIX_TYPE_HPP */
SmallMatrix(const SmallMatrix &other)
Copy constructor.
uint height
Number of items over second axis.
const T & Get(uint x, uint y) const
Get item x/y (const).
void EraseColumnPreservingOrder(uint x, uint count=1)
Remove columns from the matrix while preserving the order of other columns.
SmallMatrix & operator=(const SmallMatrix &other)
Assignment.
static void MemMoveT(T *destination, const T *source, size_t num=1)
Type-safe version of memmove().
Definition: mem_func.hpp:38
void Resize(uint new_width, uint new_height)
Set the size to a specific width and height, preserving item positions as far as possible in the proc...
Functions related to the allocation of memory.
void EraseRowPreservingOrder(uint y, uint count=1)
Remove columns from the matrix while preserving the order of other columns.
static T * ReallocT(T *t_ptr, size_t num_elements)
Simplified reallocation function that allocates the specified number of elements of the given type...
Definition: alloc_func.hpp:113
const T * operator[](uint x) const
Get column "number" (const)
void Compact()
Compact the matrix down to the smallest possible size.
static T min(const T a, const T b)
Returns the minimum of two values.
Definition: math_func.hpp:42
uint width
Number of items over first axis.
static void MemCpyT(T *destination, const T *source, size_t num=1)
Type-safe version of memcpy().
Definition: mem_func.hpp:25
uint capacity
The available space for storing items.
void EraseColumn(uint x)
Erase a column, replacing it with the last one.
T * data
The pointer to the first item.
void Clear()
Remove all rows from the matrix.
void EraseRow(uint y)
Erase a row, replacing it with the last one.
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: depend.cpp:114
void Assign(const SmallMatrix &other)
Assign items from other vector.
Simple matrix template class.
void AppendColumn(uint to_add=1)
Append rows.
void AppendRow(uint to_add=1)
Append rows.
Functions related to memory operations.
void Reset()
Remove all items from the list and free allocated memory.