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