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
Size()30 inline int32 Size() const { return fSize; }
Count()31 inline int32 Count() const { return fSize; }
IsEmpty()32 inline bool IsEmpty() const { return fSize == 0; }
Elements()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>
Array()65 Array<Element>::Array()
66 :
67 fElements(NULL),
68 fSize(0),
69 fCapacity(0)
70 {
71 }
72
73
74 template<typename Element>
Array(const Array<Element> & other)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>
~Array()86 Array<Element>::~Array()
87 {
88 free(fElements);
89 }
90
91
92 template<typename Element>
93 bool
Add(const Element & element)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
AddUninitialized(int32 elementCount)107 Array<Element>::AddUninitialized(int32 elementCount)
108 {
109 return InsertUninitialized(fSize, elementCount);
110 }
111
112
113 template<typename Element>
114 bool
Insert(const Element & element,int32 index)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
InsertUninitialized(int32 index,int32 count)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
Remove(int32 index,int32 count)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
Clear()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
MakeEmpty()191 Array<Element>::MakeEmpty()
192 {
193 Clear();
194 }
195
196
197 template<typename Element>
198 Element&
ElementAt(int32 index)199 Array<Element>::ElementAt(int32 index)
200 {
201 return fElements[index];
202 }
203
204
205 template<typename Element>
206 const Element&
ElementAt(int32 index)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
_Resize(int32 index,int32 delta)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