src/misc/array.hpp

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