src/base/tl/array.h

   1 /* (c) Magnus Auvinen. See licence.txt in the root of the distribution for more information. */
   2 /* If you are missing that file, acquire a complete release at teeworlds.com.                */
   3 #ifndef BASE_TL_ARRAY_H
   4 #define BASE_TL_ARRAY_H
   5
   6 #include "range.h"
   7 #include "allocator.h"
   8
   9
  10 /*
  11         Class: array
  12                 Normal dynamic array class
  13
  14         Remarks:
  15                 - Grows 50% each time it needs to fit new items
  16                 - Use set_size() if you know how many elements
  17                 - Use optimize() to reduce the needed space.
  18 */
  19 template <class T, class ALLOCATOR = allocator_default<T> >
  20 class array : private ALLOCATOR
  21 {
  22         void init()
  23         {
  24                 list = 0x0;
  25                 clear();
  26         }
  27
  28 public:
  29         typedef plain_range<T> range;
  30
  31         /*
  32                 Function: array constructor
  33         */
  34         array()
  35         {
  36                 init();
  37         }
  38
  39         /*
  40                 Function: array copy constructor
  41         */
  42         array(const array &other)
  43         {
  44                 init();
  45                 set_size(other.size());
  46                 for(int i = 0; i < size(); i++)
  47                         (*this)[i] = other[i];
  48         }
  49
  50
  51         /*
  52                 Function: array destructor
  53         */
  54         ~array()
  55         {
  56                 ALLOCATOR::free_array(list);
  57                 list = 0x0;
  58         }
  59
  60
  61         /*
  62                 Function: delete_all
  63
  64                 Remarks:
  65                         - Invalidates ranges
  66         */
  67         void delete_all()
  68         {
  69                 for(int i = 0; i < size(); i++)
  70                         delete list[i];
  71                 clear();
  72         }
  73
  74
  75         /*
  76                 Function: clear
  77
  78                 Remarks:
  79                         - Invalidates ranges
  80         */
  81         void clear()
  82         {
  83                 ALLOCATOR::free_array(list);
  84                 list_size = 1;
  85                 list = ALLOCATOR::alloc_array(list_size);
  86                 num_elements = 0;
  87         }
  88
  89         /*
  90                 Function: size
  91         */
  92         int size() const
  93         {
  94                 return num_elements;
  95         }
  96
  97         /*
  98                 Function: remove_index_fast
  99
 100                 Remarks:
 101                         - Invalidates ranges
 102         */
 103         void remove_index_fast(int index)
 104         {
 105                 list[index] = list[num_elements-1];
 106                 set_size(size()-1);
 107         }
 108
 109         /*
 110                 Function: remove_fast
 111
 112                 Remarks:
 113                         - Invalidates ranges
 114         */
 115         void remove_fast(const T& item)
 116         {
 117                 for(int i = 0; i < size(); i++)
 118                         if(list[i] == item)
 119                         {
 120                                 remove_index_fast(i);
 121                                 return;
 122                         }
 123         }
 124
 125         /*
 126                 Function: remove_index
 127
 128                 Remarks:
 129                         - Invalidates ranges
 130         */
 131         void remove_index(int index)
 132         {
 133                 for(int i = index+1; i < num_elements; i++)
 134                         list[i-1] = list[i];
 135
 136                 set_size(size()-1);
 137         }
 138
 139         /*
 140                 Function: remove
 141
 142                 Remarks:
 143                         - Invalidates ranges
 144         */
 145         bool remove(const T& item)
 146         {
 147                 for(int i = 0; i < size(); i++)
 148                         if(list[i] == item)
 149                         {
 150                                 remove_index(i);
 151                                 return true;
 152                         }
 153                 return false;
 154         }
 155
 156         /*
 157                 Function: add
 158                         Adds an item to the array.
 159
 160                 Arguments:
 161                         item - Item to add.
 162
 163                 Remarks:
 164                         - Invalidates ranges
 165                         - See remarks about <array> how the array grows.
 166         */
 167         int add(const T& item)
 168         {
 169                 incsize();
 170                 set_size(size()+1);
 171                 list[num_elements-1] = item;
 172                 return num_elements-1;
 173         }
 174
 175         /*
 176                 Function: insert
 177                         Inserts an item into the array at a specified location.
 178
 179                 Arguments:
 180                         item - Item to insert.
 181                         r - Range where to insert the item
 182
 183                 Remarks:
 184                         - Invalidates ranges
 185                         - See remarks about <array> how the array grows.
 186         */
 187         int insert(const T& item, range r)
 188         {
 189                 if(r.empty())
 190                         return add(item);
 191
 192                 int index = (int)(&r.front()-list);
 193                 incsize();
 194                 set_size(size()+1);
 195
 196                 for(int i = num_elements-1; i > index; i--)
 197                         list[i] = list[i-1];
 198
 199                 list[index] = item;
 200
 201                 return num_elements-1;
 202         }
 203
 204         /*
 205                 Function: operator[]
 206         */
 207         T& operator[] (int index)
 208         {
 209                 return list[index];
 210         }
 211
 212         /*
 213                 Function: const operator[]
 214         */
 215         const T& operator[] (int index) const
 216         {
 217                 return list[index];
 218         }
 219
 220         /*
 221                 Function: base_ptr
 222         */
 223         T *base_ptr()
 224         {
 225                 return list;
 226         }
 227
 228         /*
 229                 Function: base_ptr
 230         */
 231         const T *base_ptr() const
 232         {
 233                 return list;
 234         }
 235
 236         /*
 237                 Function: set_size
 238                         Resizes the array to the specified size.
 239
 240                 Arguments:
 241                         new_size - The new size for the array.
 242         */
 243         void set_size(int new_size)
 244         {
 245                 if(list_size < new_size)
 246                         alloc(new_size);
 247                 num_elements = new_size;
 248         }
 249
 250         /*
 251                 Function: hint_size
 252                         Allocates the number of elements wanted but
 253                         does not increase the list size.
 254
 255                 Arguments:
 256                         hint - Size to allocate.
 257
 258                 Remarks:
 259                         - If the hint is smaller then the number of elements, nothing will be done.
 260                         - Invalidates ranges
 261         */
 262         void hint_size(int hint)
 263         {
 264                 if(num_elements < hint)
 265                         alloc(hint);
 266         }
 267
 268
 269         /*
 270                 Function: optimize
 271                         Removes unnessasary data, returns how many bytes was earned.
 272
 273                 Remarks:
 274                         - Invalidates ranges
 275         */
 276         int optimize()
 277         {
 278                 int before = memusage();
 279                 alloc(num_elements);
 280                 return before - memusage();
 281         }
 282
 283         /*
 284                 Function: memusage
 285                         Returns how much memory this dynamic array is using
 286         */
 287         int memusage()
 288         {
 289                 return sizeof(array) + sizeof(T)*list_size;
 290         }
 291
 292         /*
 293                 Function: operator=(array)
 294
 295                 Remarks:
 296                         - Invalidates ranges
 297         */
 298         array &operator = (const array &other)
 299         {
 300                 set_size(other.size());
 301                 for(int i = 0; i < size(); i++)
 302                         (*this)[i] = other[i];
 303                 return *this;
 304         }
 305
 306         /*
 307                 Function: all
 308                         Returns a range that contains the whole array.
 309         */
 310         range all() { return range(list, list+num_elements); }
 311 protected:
 312
 313         void incsize()
 314         {
 315                 if(num_elements == list_size)
 316                 {
 317                         if(list_size < 2)
 318                                 alloc(list_size+1);
 319                         else
 320                                 alloc(list_size+list_size/2);
 321                 }
 322         }
 323
 324         void alloc(int new_len)
 325         {
 326                 list_size = new_len;
 327                 T *new_list = ALLOCATOR::alloc_array(list_size);
 328
 329                 int end = num_elements < list_size ? num_elements : list_size;
 330                 for(int i = 0; i < end; i++)
 331                         new_list[i] = list[i];
 332
 333                 ALLOCATOR::free_array(list);
 334
 335                 num_elements = num_elements < list_size ? num_elements : list_size;
 336                 list = new_list;
 337         }
 338
 339         T *list;
 340         int list_size;
 341         int num_elements;
 342 };
 343
 344 #endif // TL_FILE_ARRAY_HPP