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 20namespace BPrivate { 21 22 23template<typename Element> 24class Array { 25public: 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 52private: 53 static const int32 kMinCapacity = 8; 54 55 bool _Resize(int32 index, int32 delta); 56 57private: 58 Element* fElements; 59 int32 fSize; 60 int32 fCapacity; 61}; 62 63 64template<typename Element> 65Array<Element>::Array() 66 : 67 fElements(NULL), 68 fSize(0), 69 fCapacity(0) 70{ 71} 72 73 74template<typename Element> 75Array<Element>::Array(const Array<Element>& other) 76 : 77 fElements(NULL), 78 fSize(0), 79 fCapacity(0) 80{ 81 *this = other; 82} 83 84 85template<typename Element> 86Array<Element>::~Array() 87{ 88 free(fElements); 89} 90 91 92template<typename Element> 93bool 94Array<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 105template<typename Element> 106inline bool 107Array<Element>::AddUninitialized(int32 elementCount) 108{ 109 return InsertUninitialized(fSize, elementCount); 110} 111 112 113template<typename Element> 114bool 115Array<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 129template<typename Element> 130bool 131Array<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 146template<typename Element> 147bool 148Array<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 174template<typename Element> 175void 176Array<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 189template<typename Element> 190void 191Array<Element>::MakeEmpty() 192{ 193 Clear(); 194} 195 196 197template<typename Element> 198Element& 199Array<Element>::ElementAt(int32 index) 200{ 201 return fElements[index]; 202} 203 204 205template<typename Element> 206const Element& 207Array<Element>::ElementAt(int32 index) const 208{ 209 return fElements[index]; 210} 211 212 213template<typename Element> 214Element& 215Array<Element>::operator[](int32 index) 216{ 217 return fElements[index]; 218} 219 220 221template<typename Element> 222const Element& 223Array<Element>::operator[](int32 index) const 224{ 225 return fElements[index]; 226} 227 228 229template<typename Element> 230Array<Element>& 231Array<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 244template<typename Element> 245bool 246Array<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 300using BPrivate::Array; 301 302 303#endif // _ARRAY_H 304