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 304