src/misc/array.hpp

   1 /* $Id$ */
   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
  10 /** @file array.hpp Array without an explicit maximum size. */
  11
  12 #ifndef ARRAY_HPP
  13 #define ARRAY_HPP
  14
  15 #include "fixedsizearray.hpp"
  16 #include "str.hpp"
  17
  18 /**
  19  * Flexible array with size limit. Implemented as fixed size
  20  *  array of fixed size arrays
  21  */
  22 template <class T, uint B = 1024, uint N = B>
  23 class SmallArray {
  24 protected:
  25         typedef FixedSizeArray<T, B> SubArray; ///< inner array
  26         typedef FixedSizeArray<SubArray, N> SuperArray; ///< outer array
  27
  28         static const uint Tcapacity = B * N; ///< total max number of items
  29
  30         SuperArray data; ///< array of arrays of items
  31
  32         /** return first sub-array with free space for new item */
  33         inline SubArray& FirstFreeSubArray()
  34         {
  35                 uint super_size = data.Length();
  36                 if (super_size > 0) {
  37                         SubArray &s = data[super_size - 1];
  38                         if (!s.IsFull()) return s;
  39                 }
  40                 return *data.AppendC();
  41         }
  42
  43 public:
  44         /** implicit constructor */
  45         inline SmallArray()
  46         {
  47         }
  48
  49         /** Clear (destroy) all items */
  50         inline void Clear()
  51         {
  52                 data.Clear();
  53         }
  54
  55         /** Return actual number of items */
  56         inline uint Length() const
  57         {
  58                 uint super_size = data.Length();
  59                 if (super_size == 0) return 0;
  60                 uint sub_size = data[super_size - 1].Length();
  61                 return (super_size - 1) * B + sub_size;
  62         }
  63         /** return true if array is empty */
  64         inline bool IsEmpty()
  65         {
  66                 return data.IsEmpty();
  67         }
  68
  69         /** return true if array is full */
  70         inline bool IsFull()
  71         {
  72                 return data.IsFull() && data[N - 1].IsFull();
  73         }
  74
  75         /** allocate but not construct new item */
  76         inline T *Append()
  77         {
  78                 return FirstFreeSubArray().Append();
  79         }
  80
  81         /** allocate and construct new item */
  82         inline T *AppendC()
  83         {
  84                 return FirstFreeSubArray().AppendC();
  85         }
  86
  87         /** indexed access (non-const) */
  88         inline T& operator[](uint index)
  89         {
  90                 const SubArray &s = data[index / B];
  91                 T &item = s[index % B];
  92                 return item;
  93         }
  94         /** indexed access (const) */
  95         inline const T& operator[](uint index) const
  96         {
  97                 const SubArray &s = data[index / B];
  98                 const T &item = s[index % B];
  99                 return item;
 100         }
 101
 102         /**
 103          * Helper for creating a human readable output of this data.
 104          * @param dmp The location to dump to.
 105          */
 106         template <typename D> void Dump(D &dmp) const
 107         {
 108                 dmp.WriteLine("capacity = %d", Tcapacity);
 109                 uint num_items = Length();
 110                 dmp.WriteLine("num_items = %d", num_items);
 111                 CStrA name;
 112                 for (uint i = 0; i < num_items; i++) {
 113                         const T &item = (*this)[i];
 114                         name.Format("item[%d]", i);
 115                         dmp.WriteStructT(name.Data(), &item);
 116                 }
 117         }
 118 };
 119
 120 #endif /* ARRAY_HPP */