headers/private/shared/Array.h

   1 /*
   2  * Copyright 2009-2011, Ingo Weinhold, ingo_weinhold@gmx.de.
   3  * Distributed under the terms of the MIT License.
   4  */
   5 #ifndef _ARRAY_H
   6 #define _ARRAY_H
   7
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12
  13 #include <SupportDefs.h>
  14
  15 #if DEBUG
  16 #       include <OS.h>
  17 #endif
  18
  19
  20 namespace BPrivate {
  21
  22
  23 template<typename Element>
  24 class Array {
  25 public:
  26         inline                                          Array();
  27                                                                 Array(const Array<Element>& other);
  28         inline                                          ~Array();
  29
  30         inline  int32                           Size() const            { return fSize; }
  31         inline  int32                           Count() const           { return fSize; }
  32         inline  bool                            IsEmpty() const         { return fSize == 0; }
  33         inline  Element*                        Elements() const        { return fElements; }
  34
  35         inline  bool                            Add(const Element& element);
  36         inline  bool                            AddUninitialized(int32 elementCount);
  37         inline  bool                            Insert(const Element& element, int32 index);
  38         inline  bool                            InsertUninitialized(int32 index, int32 count);
  39         inline  bool                            Remove(int32 index, int32 count = 1);
  40
  41                         void                            Clear();
  42         inline  void                            MakeEmpty();
  43
  44         inline  Element&                        ElementAt(int32 index);
  45         inline  const Element&          ElementAt(int32 index) const;
  46
  47         inline  Element&                        operator[](int32 index);
  48         inline  const Element&          operator[](int32 index) const;
  49
  50                         Array<Element>&         operator=(const Array<Element>& other);
  51
  52 private:
  53         static  const int32                     kMinCapacity = 8;
  54
  55                         bool                            _Resize(int32 index, int32 delta);
  56
  57 private:
  58                         Element*                        fElements;
  59                         int32                           fSize;
  60                         int32                           fCapacity;
  61 };
  62
  63
  64 template<typename Element>
  65 Array<Element>::Array()
  66         :
  67         fElements(NULL),
  68         fSize(0),
  69         fCapacity(0)
  70 {
  71 }
  72
  73
  74 template<typename Element>
  75 Array<Element>::Array(const Array<Element>& other)
  76         :
  77         fElements(NULL),
  78         fSize(0),
  79         fCapacity(0)
  80 {
  81         *this = other;
  82 }
  83
  84
  85 template<typename Element>
  86 Array<Element>::~Array()
  87 {
  88         free(fElements);
  89 }
  90
  91
  92 template<typename Element>
  93 bool
  94 Array<Element>::Add(const Element& element)
  95 {
  96         if (!_Resize(fSize, 1))
  97                 return false;
  98
  99         fElements[fSize] = element;
 100         fSize++;
 101         return true;
 102 }
 103
 104
 105 template<typename Element>
 106 inline bool
 107 Array<Element>::AddUninitialized(int32 elementCount)
 108 {
 109         return InsertUninitialized(fSize, elementCount);
 110 }
 111
 112
 113 template<typename Element>
 114 bool
 115 Array<Element>::Insert(const Element& element, int32 index)
 116 {
 117         if (index < 0 || index > fSize)
 118                 index = fSize;
 119
 120         if (!_Resize(index, 1))
 121                 return false;
 122
 123         fElements[index] = element;
 124         fSize++;
 125         return true;
 126 }
 127
 128
 129 template<typename Element>
 130 bool
 131 Array<Element>::InsertUninitialized(int32 index, int32 count)
 132 {
 133         if (index < 0 || index > fSize || count < 0)
 134                 return false;
 135         if (count == 0)
 136                 return true;
 137
 138         if (!_Resize(index, count))
 139                 return false;
 140
 141         fSize += count;
 142         return true;
 143 }
 144
 145
 146 template<typename Element>
 147 bool
 148 Array<Element>::Remove(int32 index, int32 count)
 149 {
 150         if (index < 0 || count < 0 || index + count > fSize) {
 151 #if DEBUG
 152                 char buffer[128];
 153                 snprintf(buffer, sizeof(buffer), "Array::Remove(): index: %" B_PRId32
 154                 ", count: %" B_PRId32 ", size: %" B_PRId32, index, count, fSize);
 155                 debugger(buffer);
 156 #endif
 157                 return false;
 158         }
 159         if (count == 0)
 160                 return true;
 161
 162         if (index + count < fSize) {
 163                 memmove(fElements + index, fElements + index + count,
 164                         sizeof(Element) * (fSize - index - count));
 165         }
 166
 167         _Resize(index, -count);
 168
 169         fSize -= count;
 170         return true;
 171 }
 172
 173
 174 template<typename Element>
 175 void
 176 Array<Element>::Clear()
 177 {
 178         if (fSize == 0)
 179                 return;
 180
 181         free(fElements);
 182
 183         fElements = NULL;
 184         fSize = 0;
 185         fCapacity = 0;
 186 }
 187
 188
 189 template<typename Element>
 190 void
 191 Array<Element>::MakeEmpty()
 192 {
 193         Clear();
 194 }
 195
 196
 197 template<typename Element>
 198 Element&
 199 Array<Element>::ElementAt(int32 index)
 200 {
 201         return fElements[index];
 202 }
 203
 204
 205 template<typename Element>
 206 const Element&
 207 Array<Element>::ElementAt(int32 index) const
 208 {
 209         return fElements[index];
 210 }
 211
 212
 213 template<typename Element>
 214 Element&
 215 Array<Element>::operator[](int32 index)
 216 {
 217         return fElements[index];
 218 }
 219
 220
 221 template<typename Element>
 222 const Element&
 223 Array<Element>::operator[](int32 index) const
 224 {
 225         return fElements[index];
 226 }
 227
 228
 229 template<typename Element>
 230 Array<Element>&
 231 Array<Element>::operator=(const Array<Element>& other)
 232 {
 233         Clear();
 234
 235         if (other.fSize > 0 && _Resize(0, other.fSize)) {
 236                 fSize = other.fSize;
 237                 memcpy(fElements, other.fElements, fSize * sizeof(Element));
 238         }
 239
 240         return *this;
 241 }
 242
 243
 244 template<typename Element>
 245 bool
 246 Array<Element>::_Resize(int32 index, int32 delta)
 247 {
 248         // determine new capacity
 249         int32 newSize = fSize + delta;
 250         int32 newCapacity = kMinCapacity;
 251         while (newCapacity < newSize)
 252                 newCapacity *= 2;
 253
 254         if (newCapacity == fCapacity) {
 255                 // the capacity doesn't change -- still make room for/remove elements
 256                 if (index < fSize) {
 257                         if (delta > 0) {
 258                                 // leave a gap of delta elements
 259                                 memmove(fElements + index + delta, fElements + index,
 260                                         (fSize - index) * sizeof(Element));
 261                         } else if (index < fSize + delta) {
 262                                 // drop -delta elements
 263                                 memcpy(fElements + index, fElements + index - delta,
 264                                         (fSize - index + delta) * sizeof(Element));
 265                         }
 266                 }
 267
 268                 return true;
 269         }
 270
 271         // allocate new array
 272         Element* elements = (Element*)malloc(newCapacity * sizeof(Element));
 273         if (elements == NULL)
 274                 return false;
 275
 276         if (index > 0)
 277                 memcpy(elements, fElements, index * sizeof(Element));
 278         if (index < fSize) {
 279                 if (delta > 0) {
 280                         // leave a gap of delta elements
 281                         memcpy(elements + index + delta, fElements + index,
 282                                 (fSize - index) * sizeof(Element));
 283                 } else if (index < fSize + delta) {
 284                         // drop -delta elements
 285                         memcpy(elements + index, fElements + index - delta,
 286                                 (fSize - index + delta) * sizeof(Element));
 287                 }
 288         }
 289
 290         free(fElements);
 291         fElements = elements;
 292         fCapacity = newCapacity;
 293         return true;
 294 }
 295
 296
 297 }       // namespace BPrivate
 298
 299
 300 using BPrivate::Array;
 301
 302
 303 #endif  // _ARRAY_H