Inexor
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
cube_vector.hpp
Go to the documentation of this file.
1 
5 #pragma once
6 
7 #include "inexor/shared/cube_hash.hpp" // for htcmp
9 #include "inexor/shared/cube_tools.hpp" // for is_class, NULL
11 #include "inexor/shared/cube_types.hpp" //uchar
12 #include "inexor/network/legacy/buffer_types.hpp" // databuf
13 #include "inexor/util/random.hpp"
14 
15 #include <algorithm>
16 
17 template<class T>
18 static inline float heapscore(const T &n) { return n; }
19 
22 template <class T, int MINSIZE = 8> struct vector
23 {
24 
26  T *buf;
27 
29  int alen;
31  int ulen;
32 
35  vector() : buf(nullptr), alen(0), ulen(0)
36  {
37  }
38 
42  vector(const vector &v) : buf(nullptr), alen(0), ulen(0)
43  {
44  *this = v;
45  }
46 
50  {
51  shrink(0);
52  if(buf) free(buf);
53  }
54 
60  {
61  shrink(0);
62  if(v.length() > alen) growbuf(v.length());
63  loopv(v) add(v[i]);
64  return *this;
65  }
66 
73  T &add(const T &x)
74  {
75  if(ulen==alen) growbuf(ulen+1);
76  new (&buf[ulen]) T(x);
77  return buf[ulen++];
78  }
79 
85  T &add()
86  {
87  if(ulen==alen) growbuf(ulen+1);
88  new (&buf[ulen]) T;
89  return buf[ulen++];
90  }
91 
97  T &dup()
98  {
99  if(ulen==alen) growbuf(ulen+1);
100  new (&buf[ulen]) T(buf[ulen-1]);
101  return buf[ulen++];
102  }
103 
105  void move(vector<T> &v)
106  {
107  if(!ulen)
108  {
109  std::swap(buf, v.buf);
110  std::swap(ulen, v.ulen);
111  std::swap(alen, v.alen);
112  }
113  else
114  {
115  growbuf(ulen+v.ulen);
116  if(v.ulen) memcpy(&buf[ulen], (void *)v.buf, v.ulen*sizeof(T));
117  ulen += v.ulen;
118  v.ulen = 0;
119  }
120  }
121 
123  bool inrange(size_t i) const { return i<size_t(ulen); }
126  bool inrange(int i) const { return i>=0 && i<ulen; }
127 
129  T &pop() { return buf[--ulen]; }
131  T &last() { return buf[ulen-1]; }
132 
134  void drop()
135  {
136  ulen--;
137  buf[ulen].~T();
138  }
139 
141  bool empty() const { return ulen==0; }
142 
144  int capacity() const { return alen; }
146  int length() const { return ulen; }
147 
149  T &operator[](int i) { ASSERT(i>=0 && i<ulen); return buf[i]; }
150  const T &operator[](int i) const { ASSERT(i >= 0 && i<ulen); return buf[i]; }
151 
154  void disown()
155  {
156  buf = nullptr;
157  alen = ulen = 0;
158  }
159 
161  void shrink(int i) { ASSERT(i<=ulen); if(isclass<T>::no) ulen = i; else while(ulen>i) drop(); }
163  void setsize(int i) { ASSERT(i<=ulen); ulen = i; }
164 
165  void deletecontents() { while(!empty()) delete pop(); }
166  void deletearrays() { while(!empty()) delete[] pop(); }
167 
169  T *getbuf() { return buf; }
171  const T *getbuf() const { return buf; }
172  bool inbuf(const T *e) const { return e >= buf && e < &buf[ulen]; }
173 
175  template<class F>
176  void sort(F fun, int i = 0, int n = -1)
177  {
178  quicksort(&buf[i], n < 0 ? ulen-i : n, fun);
179  }
180 
181  void sort() { sort(sortless()); }
182  void sortname() { sort(sortnameless()); }
183 
185  void shuffle()
186  {
187  for(int i = 0; i < ulen; i++)
188  {
189  int indx = inexor::util::rnd<int>(ulen);
190  T temp = buf[i];
191  buf[i] = buf[indx];
192  buf[indx] = temp;
193  }
194  }
195 
197  void growbuf(int sz)
198  {
199  int olen = alen;
200  if(!alen) alen = std::max(MINSIZE, sz);
201  else while(alen < sz) alen += alen/2;
202  if(alen <= olen) return;
203  buf = (T *)realloc(buf, alen*sizeof(T));
204  if(!buf) abort();
205  }
206 
209  {
210  if(alen-ulen < sz) growbuf(ulen+sz);
211  return databuf<T>(&buf[ulen], sz);
212  }
213 
215  void advance(int sz)
216  {
217  ulen += sz;
218  }
219 
221  void addbuf(const databuf<T> &p)
222  {
223  advance(p.length());
224  }
225 
227  T *pad(int n)
228  {
229  T *buf = reserve(n).buf;
230  advance(n);
231  return buf;
232  }
233 
235  void put(const T &v)
236  {
237  add(v);
238  }
239  void put(const T *v, int n)
240  {
241  databuf<T> buf = reserve(n);
242  buf.put(v, n);
243  addbuf(buf);
244  }
245 
248  void remove(int i, int n)
249  {
250  for(int p = i+n; p<ulen; p++) buf[p-n] = buf[p];
251  ulen -= n;
252  }
253 
256  T remove(int i)
257  {
258  T e = buf[i];
259  for(int p = i+1; p<ulen; p++) buf[p-1] = buf[p];
260  ulen--;
261  return e;
262  }
264  {
265  T e = buf[i];
266  ulen--;
267  if(ulen>0) buf[i] = buf[ulen];
268  return e;
269  }
270 
272  template<class U>
273  int find(const U &o)
274  {
275  loopi(ulen) if(buf[i]==o) return i;
276  return -1;
277  }
278 
280  void addunique(const T &o)
281  {
282  if(find(o) < 0) add(o);
283  }
284 
286  void removeobj(const T &o)
287  {
288  loopi(ulen) if(buf[i] == o)
289  {
290  int dst = i;
291  for(int j = i+1; j < ulen; j++) if(!(buf[j] == o)) buf[dst++] = buf[j];
292  setsize(dst);
293  break;
294  }
295  }
296 
298  void replacewithlast(const T &o)
299  {
300  if(!ulen) return;
301  loopi(ulen-1) if(buf[i]==o)
302  {
303  buf[i] = buf[ulen-1];
304  break;
305  }
306  ulen--;
307  }
308 
310  T &insert(int i, const T &e)
311  {
312  add(T());
313  for(int p = ulen-1; p>i; p--) buf[p] = buf[p-1];
314  buf[i] = e;
315  return buf[i];
316  }
317  T *insert(int i, const T *e, int n)
318  {
319  if(alen-ulen < n) growbuf(ulen+n);
320  loopj(n) add(T());
321  for(int p = ulen-1; p>=i+n; p--) buf[p] = buf[p-n];
322  loopj(n) buf[i+j] = e[j];
323  return &buf[i];
324  }
325 
327  void reverse()
328  {
329  loopi(ulen/2) std::swap(buf[i], buf[ulen-1-i]);
330  }
331 
333  static int heapparent(int i) { return (i - 1) >> 1; }
334  static int heapchild(int i) { return (i << 1) + 1; }
335 
337  void buildheap()
338  {
339  for(int i = ulen/2; i >= 0; i--) downheap(i);
340  }
341 
343  int upheap(int i)
344  {
345  float score = heapscore(buf[i]);
346  while(i > 0)
347  {
348  int pi = heapparent(i);
349  if(score >= heapscore(buf[pi])) break;
350  std::swap(buf[i], buf[pi]);
351  i = pi;
352  }
353  return i;
354  }
355 
357  T &addheap(const T &x)
358  {
359  add(x);
360  return buf[upheap(ulen-1)];
361  }
362 
364  int downheap(int i)
365  {
366  float score = heapscore(buf[i]);
367  for(;;)
368  {
369  int ci = heapchild(i);
370  if(ci >= ulen) break;
371  float cscore = heapscore(buf[ci]);
372  if(score > cscore)
373  {
374  if(ci+1 < ulen && heapscore(buf[ci+1]) < cscore) { std::swap(buf[ci+1], buf[i]); i = ci+1; }
375  else { std::swap(buf[ci], buf[i]); i = ci; }
376  }
377  else if(ci+1 < ulen && heapscore(buf[ci+1]) < score) { std::swap(buf[ci+1], buf[i]); i = ci+1; }
378  else break;
379  }
380  return i;
381  }
382 
385  {
386  T e = removeunordered(0);
387  if(ulen) downheap(0);
388  return e;
389  }
390 
392  template<class K>
393  int htfind(const K &key)
394  {
395  loopi(ulen) if(htcmp(key, buf[i])) return i;
396  return -1;
397  }
398 };
399 
400 
void deletecontents()
Definition: cube_vector.hpp:165
bool empty() const
is this vector empty?
Definition: cube_vector.hpp:141
void put(const T &v)
write bytes to vector
Definition: cube_vector.hpp:235
Vector template.
Definition: cube_vector.hpp:22
vector()
Default constructor.
Definition: cube_vector.hpp:35
void put(const T &val)
put one element at the end of the buffer.
Definition: buffer_types.hpp:73
const T & max(const inexor::rpc::SharedVar< T > &a, const T &b)
Definition: SharedVar.hpp:224
template implementation of buffers (networking e.g.).
Definition: buffer_types.hpp:14
void shrink(int i)
shrink vector memory size AND DELETE UNUSED MEMORY
Definition: cube_vector.hpp:161
void sort()
Definition: cube_vector.hpp:181
void advance(int sz)
increase value of used bytes manually (?)
Definition: cube_vector.hpp:215
void sortname()
Definition: cube_vector.hpp:182
static int heapchild(int i)
Definition: cube_vector.hpp:334
int ulen
USED memory size.
Definition: cube_vector.hpp:31
int htfind(const K &key)
similar to find but uses hashtable keys
Definition: cube_vector.hpp:393
static int heapparent(int i)
?
Definition: cube_vector.hpp:333
T * getbuf()
get the whole vector
Definition: cube_vector.hpp:169
vector(const vector &v)
Copy constructor.
Definition: cube_vector.hpp:42
Check if a given type is a class.
Definition: cube_tools.hpp:34
T & last()
get the last index
Definition: cube_vector.hpp:131
static void quicksort(T *start, T *end, F fun)
Definition: cube_sort.hpp:54
void growbuf(int sz)
reallocate memory for vector (its size)
Definition: cube_vector.hpp:197
T & operator[](int i)
[] array access operators
Definition: cube_vector.hpp:149
bool inrange(size_t i) const
safety check: tests if index i exists in this vector
Definition: cube_vector.hpp:123
int length() const
receive amount of values in buffer.
Definition: buffer_types.hpp:110
void setsize(int i)
shrink vector memory size
Definition: cube_vector.hpp:163
else loopi(numargs)
Definition: command.cpp:3019
T & insert(int i, const T &e)
insertion functions
Definition: cube_vector.hpp:310
void drop()
decrement vector's size and call the DESTRUCTOR of the template in the last index ...
Definition: cube_vector.hpp:134
void addbuf(const databuf< T > &p)
increase value of used bytes by size of a vector
Definition: cube_vector.hpp:221
T & add(const T &x)
Add new index to vector.
Definition: cube_vector.hpp:73
T & dup()
Duplicate vector's last index.
Definition: cube_vector.hpp:97
static bool htcmp(const fileskey &x, const fileskey &y)
Definition: console.cpp:693
void sort(F fun, int i=0, int n=-1)
sort the vector using quicksort template and sort criteria F
Definition: cube_vector.hpp:176
T removeunordered(int i)
Definition: cube_vector.hpp:263
databuf< T > reserve(int sz)
reserved memory and returns vector of the reserved memory
Definition: cube_vector.hpp:208
Legacy Sorting algorithms.
Definition: cube_sort.hpp:11
int capacity() const
return size of reserved memory
Definition: cube_vector.hpp:144
int upheap(int i)
?
Definition: cube_vector.hpp:343
void disown()
resets all members to 0
Definition: cube_vector.hpp:154
T & addheap(const T &x)
?
Definition: cube_vector.hpp:357
int length() const
return size of used memory
Definition: cube_vector.hpp:146
int alen
ALLOCATED memory size.
Definition: cube_vector.hpp:29
T removeheap()
?
Definition: cube_vector.hpp:384
const T & operator[](int i) const
Definition: cube_vector.hpp:150
void deletearrays()
Definition: cube_vector.hpp:166
T * buf
data pointer
Definition: cube_vector.hpp:26
T * pad(int n)
Definition: cube_vector.hpp:227
vector< T > & operator=(const vector< T > &v)
Operator =.
Definition: cube_vector.hpp:59
void move(vector< T > &v)
copy vector from vector reference
Definition: cube_vector.hpp:105
Definition: cube_sort.hpp:18
const T * getbuf() const
get the whole vector as const value
Definition: cube_vector.hpp:171
bool inrange(int i) const
safety check: tests if index i exists in this vector integer version: i must be greater (or equal to)...
Definition: cube_vector.hpp:126
void buildheap()
?
Definition: cube_vector.hpp:337
#define loopj(m)
Definition: cube_loops.hpp:9
void removeobj(const T &o)
remove an element if equal to to given one.
Definition: cube_vector.hpp:286
void addunique(const T &o)
only add new element if it is unique.
Definition: cube_vector.hpp:280
void shuffle()
mix the vector's indices randomly
Definition: cube_vector.hpp:185
void put(const T *v, int n)
Definition: cube_vector.hpp:239
int find(const U &o)
find (first) index in vector.
Definition: cube_vector.hpp:273
T * insert(int i, const T *e, int n)
Definition: cube_vector.hpp:317
T & add()
Add new EMPTY index to vector.
Definition: cube_vector.hpp:85
static float heapscore(const T &n)
Legacy vector implementation.
Definition: cube_vector.hpp:18
int downheap(int i)
?
Definition: cube_vector.hpp:364
bool inbuf(const T *e) const
Definition: cube_vector.hpp:172
#define loopv(v)
Definition: cube_loops.hpp:21
T & pop()
get the last index and decrement the vector's size
Definition: cube_vector.hpp:129
~vector()
Destructor.
Definition: cube_vector.hpp:49
void reverse()
reverse all indices (first becomes last and so on...)
Definition: cube_vector.hpp:327
void replacewithlast(const T &o)
replace an index with the last vector index using a template parameter key
Definition: cube_vector.hpp:298
#define ASSERT(c)
Definition: cube_tools.hpp:12