SuperTuxKart
ptr_vector.hpp
1 // SuperTuxKart - a fun racing game with go-kart
2 //
3 // Copyright (C) 2009-2015 Marianne Gagnon
4 //
5 // This program is free software; you can redistribute it and/or
6 // modify it under the terms of the GNU General Public License
7 // as published by the Free Software Foundation; either version 3
8 // of the License, or (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program; if not, write to the Free Software
17 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 
19 
20 /*
21  * I made this class to work like a regular vector, except that
22  * m_contents_vector are placed* one the heap so third-party
23  * m_contents_vector can keep pointers to them.
24  */
25 
26 #ifndef HEADER_PtrVector_HPP
27 #define HEADER_PtrVector_HPP
28 
29 #include <vector>
30 #include <assert.h>
31 #include <stdint.h>
32 
33 #include "utils/aligned_array.hpp"
34 
35 enum VECTOR_TYPE
36 {
37  REF,
38  HOLD
39 };
40 
41 
42 template<typename TYPE, VECTOR_TYPE type=HOLD>
43 class PtrVector
44 {
45 
46 public:
47  AlignedArray<TYPE*> m_contents_vector;
48 
49  PtrVector()
50  {
51  } // PtrVector
52 
53  // ------------------------------------------------------------------------
54 
55  ~PtrVector()
56  {
57  if(type == HOLD) clearAndDeleteAll();
58  } // ~PtrVector
59 
60  // ------------------------------------------------------------------------
61 
62  void push_back(TYPE* t)
63  {
64  m_contents_vector.push_back(t);
65  } // push_back
66 
67  // ------------------------------------------------------------------------
68  void swap(int ID1, int ID2)
69  {
70  assert(ID1 > -1);
71  assert((unsigned int)ID1 < m_contents_vector.size());
72  assert(ID2 > -1);
73  assert((unsigned int)ID2 < m_contents_vector.size());
74 
75 
76  TYPE* temp = m_contents_vector[ID2];
77 
78  m_contents_vector[ID2] = m_contents_vector[ID1];
79  m_contents_vector[ID1] = temp;
80  } // swap
81 
82  // ------------------------------------------------------------------------
83  TYPE* get(const int ID)
84  {
85  assert(ID > -1);
86  assert((unsigned int)ID < (unsigned int)m_contents_vector.size());
87 
88  return m_contents_vector[ID];
89  } // get
90 
91  // ------------------------------------------------------------------------
92  const TYPE* get(const int ID) const
93  {
94  assert(ID > -1);
95  assert((unsigned int)ID < (unsigned int)m_contents_vector.size());
96 
97  return m_contents_vector[ID];
98  } // get
99 
100  // ------------------------------------------------------------------------
101  unsigned int size() const
102  {
103  return (int) m_contents_vector.size();
104  } // size
105 
106  // ------------------------------------------------------------------------
107  void erase(const int ID)
108  {
109  assert(ID > -1);
110  assert((unsigned int)ID < (unsigned int)m_contents_vector.size());
111 
112  delete ( TYPE *) m_contents_vector[ID];
113 #ifdef USE_ALIGNED
114  const unsigned int amount = (unsigned int)m_contents_vector.size();
115  for(unsigned int i=ID; i<amount-1; i++)
116  {
117  m_contents_vector[i]=m_contents_vector[i+1];
118  }
119  m_contents_vector.pop_back();
120 #else
121  m_contents_vector.erase(m_contents_vector.begin()+ID);
122 #endif
123  } // erase
124 
125  // ------------------------------------------------------------------------
126  TYPE* remove(const int ID)
127  {
128  assert(ID > -1);
129  assert((unsigned int)ID < (unsigned int)m_contents_vector.size());
130 
131  TYPE* out = m_contents_vector[ID];
132 #ifdef USE_ALIGNED
133  const unsigned int amount = (unsigned int)m_contents_vector.size();
134  for(unsigned int i=ID; i<amount-1; i++)
135  {
136  m_contents_vector[i]=m_contents_vector[i+1];
137  }
138  m_contents_vector.pop_back();
139 #else
140  m_contents_vector.erase(m_contents_vector.begin()+ID);
141 #endif
142  return out;
143  } // remove
144 
145  // ------------------------------------------------------------------------
146  bool contains( const TYPE* instance ) const
147  {
148  const unsigned int amount = (unsigned int)m_contents_vector.size();
149  for (unsigned int n=0; n<amount; n++)
150  {
151  const TYPE * pointer = m_contents_vector[n];
152  if (pointer == instance) return true;
153  }
154 
155  return false;
156  } // contains
157 
158  // ------------------------------------------------------------------------
159  void clearAndDeleteAll()
160  {
161  for (unsigned int n=0; n<(unsigned int)m_contents_vector.size(); n++)
162  {
163  TYPE * pointer = m_contents_vector[n];
164  delete pointer;
165  m_contents_vector[n] = (TYPE*)(intptr_t)0xDEADBEEF;
166 
167  // When deleting, it's important that the same pointer cannot be
168  // twice in the vector, resulting in a double delete
169  assert( !contains(pointer) );
170  }
171  m_contents_vector.clear();
172  } // clearAndDeleteAll
173 
174  // ------------------------------------------------------------------------
175  TYPE& operator[](const unsigned int ID)
176  {
177  assert((unsigned int)ID < (unsigned int)m_contents_vector.size());
178 
179  return *(m_contents_vector[ID]);
180  } // operator[]
181 
182  // ------------------------------------------------------------------------
183  const TYPE& operator[](const unsigned int ID) const
184  {
185  assert((unsigned int)ID < (unsigned int)m_contents_vector.size());
186 
187  return *(m_contents_vector[ID]);
188  } // operator[]
189 
190  // ------------------------------------------------------------------------
191  void clearWithoutDeleting()
192  {
193  m_contents_vector.clear();
194  } // clearWithoutDeleting
195 
196  // ------------------------------------------------------------------------
200  void remove(TYPE* obj)
201  {
202  for(unsigned int n=0; n<(unsigned int)m_contents_vector.size(); n++)
203  {
204 
205  TYPE * pointer = m_contents_vector[n];
206  if(pointer == obj)
207  {
208 #ifdef USE_ALIGNED
209  const unsigned int amount =
210  (unsigned int)m_contents_vector.size();
211  for(unsigned int i=n; i<amount-1; i++)
212  {
213  m_contents_vector[i]=m_contents_vector[i+1];
214  }
215  m_contents_vector.pop_back();
216 #else
217  m_contents_vector.erase(m_contents_vector.begin()+n);
218 #endif
219  return;
220  }
221  } // for n < size()
222 
223  } // remove
224 
225  typename AlignedArray<TYPE*>::iterator begin()
226  {
227  return m_contents_vector.begin();
228  }
229 
230  typename AlignedArray<TYPE*>::iterator end()
231  {
232  return m_contents_vector.end();
233  }
234 
235  typename AlignedArray<TYPE*>::const_iterator begin() const
236  {
237  return m_contents_vector.begin();
238  }
239 
240  typename AlignedArray<TYPE*>::const_iterator end() const
241  {
242  return m_contents_vector.end();
243  }
244 
245  // ------------------------------------------------------------------------
250  bool erase(void* obj)
251  {
252  for(unsigned int n=0; n<(unsigned int)m_contents_vector.size(); n++)
253  {
254  TYPE * pointer = m_contents_vector[n];
255  if((void*)pointer == obj)
256  {
257 #ifdef USE_ALIGNED
258  const unsigned int amount =
259  (unsigned int)m_contents_vector.size();
260  for(unsigned int i=n; i<amount-1; i++)
261  {
262  m_contents_vector[i]=m_contents_vector[i+1];
263  }
264  m_contents_vector.pop_back();
265 #else
266  m_contents_vector.erase(m_contents_vector.begin()+n);
267 #endif
268  delete pointer;
269  return true;
270  }
271  } // for n < size()
272  return false;
273  } // erase
274 
275  // ------------------------------------------------------------------------
276  void insertionSort(unsigned int start=0, bool desc = false)
277  {
278  if (!desc)
279  {
280  // We should not used unsigned ints here, because if the vector is
281  // empty j needs to be compared against -1
282  for(int j=(int)start; j<(int)m_contents_vector.size()-1; j++)
283  {
284  if(*(m_contents_vector[j])<*(m_contents_vector[j+1])) continue;
285  // Now search the proper place for m_contents_vector[j+1]
286  // in the sorted section contentsVectot[start:j]
287  TYPE* t=m_contents_vector[j+1];
288  unsigned int i = j+1;
289  do
290  {
291  m_contents_vector[i] = m_contents_vector[i-1];
292  i--;
293  } while (i>start && *t<*(m_contents_vector[i-1]));
294  m_contents_vector[i]=t;
295  }
296  }
297  else
298  {
299  for(int j=(int)start; j<(int)m_contents_vector.size()-1; j++)
300  {
301  if(*(m_contents_vector[j+1])<*(m_contents_vector[j])) continue;
302  // Now search the proper place for m_contents_vector[j+1]
303  // in the sorted section contentsVectot[start:j]
304  TYPE* t=m_contents_vector[j+1];
305  unsigned int i = j+1;
306  do
307  {
308  m_contents_vector[i] = m_contents_vector[i-1];
309  i--;
310  } while (i>start && *(m_contents_vector[i-1]) <*t);
311  m_contents_vector[i]=t;
312  }
313  }
314  } // insertionSort
315 
316  bool empty() const
317  {
318  return m_contents_vector.empty();
319  }
320 
321 }; // class ptrVector
322 
323 
324 #define for_in( VAR, VECTOR ) for (unsigned int _foreach_i = 0; \
325  VAR = (_foreach_i < VECTOR.size() ? VECTOR.get(_foreach_i) : NULL),\
326  _foreach_i < VECTOR.size(); _foreach_i++)
327 #define for_var_in( TYPE, VAR, VECTOR ) TYPE VAR; for (unsigned int _foreach_i = 0; \
328  VAR = (_foreach_i < VECTOR.size() ? VECTOR.get(_foreach_i) : NULL), \
329  _foreach_i < VECTOR.size(); _foreach_i++)
330 
331 #endif
bool erase(void *obj)
Removes and deletes the given object.
Definition: ptr_vector.hpp:250
Definition: ptr_vector.hpp:43
void remove(TYPE *obj)
Removes without deleting.
Definition: ptr_vector.hpp:200