OpenTTD Source  1.11.2
smallmatrix_type.hpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * 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.
4  * 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.
5  * 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/>.
6  */
7 
10 #ifndef SMALLMATRIX_TYPE_HPP
11 #define SMALLMATRIX_TYPE_HPP
12 
13 #include "alloc_func.hpp"
14 #include "mem_func.hpp"
15 
37 template <typename T>
38 class SmallMatrix {
39 protected:
40  T *data;
41  uint width;
42  uint height;
43  uint capacity;
44 
45 public:
46 
47  SmallMatrix() : data(nullptr), width(0), height(0), capacity(0) {}
48 
53  SmallMatrix(const SmallMatrix &other) : data(nullptr), width(0), height(0), capacity(0)
54  {
55  this->Assign(other);
56  }
57 
58  ~SmallMatrix()
59  {
60  free(this->data);
61  }
62 
68  {
69  this->Assign(other);
70  return *this;
71  }
72 
76  inline void Assign(const SmallMatrix &other)
77  {
78  if (&other == this) return;
79 
80  this->height = other.Height();
81  this->width = other.Width();
82  uint num_items = this->width * this->height;
83  if (num_items > this->capacity) {
84  this->capacity = num_items;
85  free(this->data);
86  this->data = MallocT<T>(num_items);
87  MemCpyT(this->data, other[0], num_items);
88  } else if (num_items > 0) {
89  MemCpyT(this->data, other[0], num_items);
90  }
91  }
92 
96  inline void Clear()
97  {
98  /* In fact we just reset the width avoiding the need to
99  * probably reallocate the same amount of memory the matrix was
100  * previously using. */
101  this->width = 0;
102  }
103 
107  inline void Reset()
108  {
109  this->height = 0;
110  this->width = 0;
111  this->capacity = 0;
112  free(this->data);
113  this->data = nullptr;
114  }
115 
119  inline void Compact()
120  {
121  uint capacity = this->height * this->width;
122  if (capacity >= this->capacity) return;
123  this->capacity = capacity;
124  this->data = ReallocT(this->data, this->capacity);
125  }
126 
131  void EraseColumn(uint x)
132  {
133  if (x < --this->width) {
134  MemCpyT<T>(this->data + x * this->height,
135  this->data + this->width * this->height,
136  this->height);
137  }
138  }
139 
145  void EraseColumnPreservingOrder(uint x, uint count = 1)
146  {
147  if (count == 0) return;
148  assert(x < this->width);
149  assert(x + count <= this->width);
150  this->width -= count;
151  uint to_move = (this->width - x) * this->height;
152  if (to_move > 0) {
153  MemMoveT(this->data + x * this->height,
154  this->data + (x + count) * this->height, to_move);
155  }
156  }
157 
162  void EraseRow(uint y)
163  {
164  if (y < this->height - 1) {
165  for (uint x = 0; x < this->width; ++x) {
166  this->data[x * this->height + y] =
167  this->data[(x + 1) * this->height - 1];
168  }
169  }
170  this->Resize(this->width, this->height - 1);
171  }
172 
178  void EraseRowPreservingOrder(uint y, uint count = 1)
179  {
180  if (this->height > count + y) {
181  for (uint x = 0; x < this->width; ++x) {
182  MemMoveT(this->data + x * this->height + y,
183  this->data + x * this->height + y + count,
184  this->height - count - y);
185  }
186  }
187  this->Resize(this->width, this->height - count);
188  }
189 
194  inline void AppendRow(uint to_add = 1)
195  {
196  this->Resize(this->width, to_add + this->height);
197  }
198 
203  inline void AppendColumn(uint to_add = 1)
204  {
205  this->Resize(to_add + this->width, this->height);
206  }
207 
214  inline void Resize(uint new_width, uint new_height)
215  {
216  uint new_capacity = new_width * new_height;
217  T *new_data = nullptr;
218  void (*copy)(T *dest, const T *src, size_t count) = nullptr;
219  if (new_capacity > this->capacity) {
220  /* If the data doesn't fit into current capacity, resize and copy ... */
221  new_data = MallocT<T>(new_capacity);
222  copy = &MemCpyT<T>;
223  } else {
224  /* ... otherwise just move the columns around, if necessary. */
225  new_data = this->data;
226  copy = &MemMoveT<T>;
227  }
228  if (this->height != new_height || new_data != this->data) {
229  if (this->height > 0) {
230  if (new_height > this->height) {
231  /* If matrix is growing, copy from the back to avoid
232  * overwriting uncopied data. */
233  for (uint x = this->width; x > 0; --x) {
234  if (x * new_height > new_capacity) continue;
235  (*copy)(new_data + (x - 1) * new_height,
236  this->data + (x - 1) * this->height,
237  std::min(this->height, new_height));
238  }
239  } else {
240  /* If matrix is shrinking copy from the front. */
241  for (uint x = 0; x < this->width; ++x) {
242  if ((x + 1) * new_height > new_capacity) break;
243  (*copy)(new_data + x * new_height,
244  this->data + x * this->height,
245  std::min(this->height, new_height));
246  }
247  }
248  }
249  this->height = new_height;
250  if (new_data != this->data) {
251  free(this->data);
252  this->data = new_data;
253  this->capacity = new_capacity;
254  }
255  }
256  this->width = new_width;
257  }
258 
259  inline uint Height() const
260  {
261  return this->height;
262  }
263 
264  inline uint Width() const
265  {
266  return this->width;
267  }
268 
276  inline const T &Get(uint x, uint y) const
277  {
278  assert(x < this->width && y < this->height);
279  return this->data[x * this->height + y];
280  }
281 
289  inline T &Get(uint x, uint y)
290  {
291  assert(x < this->width && y < this->height);
292  return this->data[x * this->height + y];
293  }
294 
301  inline const T *operator[](uint x) const
302  {
303  assert(x < this->width);
304  return this->data + x * this->height;
305  }
306 
313  inline T *operator[](uint x)
314  {
315  assert(x < this->width);
316  return this->data + x * this->height;
317  }
318 };
319 
320 #endif /* SMALLMATRIX_TYPE_HPP */
SmallMatrix::AppendColumn
void AppendColumn(uint to_add=1)
Append rows.
Definition: smallmatrix_type.hpp:203
mem_func.hpp
SmallMatrix::operator=
SmallMatrix & operator=(const SmallMatrix &other)
Assignment.
Definition: smallmatrix_type.hpp:67
SmallMatrix::Get
const T & Get(uint x, uint y) const
Get item x/y (const).
Definition: smallmatrix_type.hpp:276
SmallMatrix::EraseColumnPreservingOrder
void EraseColumnPreservingOrder(uint x, uint count=1)
Remove columns from the matrix while preserving the order of other columns.
Definition: smallmatrix_type.hpp:145
MemCpyT
static void MemCpyT(T *destination, const T *source, size_t num=1)
Type-safe version of memcpy().
Definition: mem_func.hpp:23
SmallMatrix::Resize
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...
Definition: smallmatrix_type.hpp:214
SmallMatrix::Compact
void Compact()
Compact the matrix down to the smallest possible size.
Definition: smallmatrix_type.hpp:119
SmallMatrix
Simple matrix template class.
Definition: smallmatrix_type.hpp:38
SmallMatrix::EraseColumn
void EraseColumn(uint x)
Erase a column, replacing it with the last one.
Definition: smallmatrix_type.hpp:131
SmallMatrix::EraseRowPreservingOrder
void EraseRowPreservingOrder(uint y, uint count=1)
Remove columns from the matrix while preserving the order of other columns.
Definition: smallmatrix_type.hpp:178
SmallMatrix::width
uint width
Number of items over first axis.
Definition: smallmatrix_type.hpp:41
alloc_func.hpp
SmallMatrix::operator[]
const T * operator[](uint x) const
Get column "number" (const)
Definition: smallmatrix_type.hpp:301
ReallocT
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:111
SmallMatrix::Assign
void Assign(const SmallMatrix &other)
Assign items from other vector.
Definition: smallmatrix_type.hpp:76
SmallMatrix::Clear
void Clear()
Remove all rows from the matrix.
Definition: smallmatrix_type.hpp:96
SmallMatrix::data
T * data
The pointer to the first item.
Definition: smallmatrix_type.hpp:40
SmallMatrix::capacity
uint capacity
The available space for storing items.
Definition: smallmatrix_type.hpp:43
SmallMatrix::SmallMatrix
SmallMatrix(const SmallMatrix &other)
Copy constructor.
Definition: smallmatrix_type.hpp:53
free
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:456
SmallMatrix::height
uint height
Number of items over second axis.
Definition: smallmatrix_type.hpp:42
SmallMatrix::AppendRow
void AppendRow(uint to_add=1)
Append rows.
Definition: smallmatrix_type.hpp:194
MemMoveT
static void MemMoveT(T *destination, const T *source, size_t num=1)
Type-safe version of memmove().
Definition: mem_func.hpp:36
SmallMatrix::EraseRow
void EraseRow(uint y)
Erase a row, replacing it with the last one.
Definition: smallmatrix_type.hpp:162
SmallMatrix::Reset
void Reset()
Remove all items from the list and free allocated memory.
Definition: smallmatrix_type.hpp:107