1/*
2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * All rights reserved. Distributed under the terms of the MIT license.
4 */
5#ifndef LIST_H
6#define LIST_H
7
8#include <new>
9#include <stdlib.h>
10#include <string.h>
11
12#include <SupportDefs.h>
13
14template<typename ITEM>
15class DefaultDefaultItemCreator {
16public:
17	static inline ITEM GetItem() { return ITEM(0); }
18};
19
20/*!
21	\class List
22	\brief A generic list implementation.
23*/
24template<typename ITEM,
25		 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> >
26class List {
27public:
28	typedef ITEM					item_t;
29	typedef List					list_t;
30
31private:
32	static item_t					sDefaultItem;
33	static const size_t				kDefaultChunkSize = 10;
34	static const size_t				kMaximalChunkSize = 1024 * 1024;
35
36public:
37	List(size_t chunkSize = kDefaultChunkSize);
38	~List();
39
40	inline const item_t &GetDefaultItem() const;
41	inline item_t &GetDefaultItem();
42
43	bool AddItem(const item_t &item, int32 index);
44	bool AddItem(const item_t &item);
45//	bool AddList(list_t *list, int32 index);
46//	bool AddList(list_t *list);
47
48	bool RemoveItem(const item_t &item);
49	bool RemoveItem(int32 index);
50
51	bool ReplaceItem(int32 index, const item_t &item);
52
53	bool MoveItem(int32 oldIndex, int32 newIndex);
54
55	void MakeEmpty();
56
57	int32 CountItems() const;
58	bool IsEmpty() const;
59	const item_t &ItemAt(int32 index) const;
60	item_t &ItemAt(int32 index);
61	const item_t *Items() const;
62	int32 IndexOf(const item_t &item) const;
63	bool HasItem(const item_t &item) const;
64
65	// debugging
66	int32 GetCapacity() const	{ return fCapacity; }
67
68private:
69	inline static void _MoveItems(item_t* items, int32 offset, int32 count);
70	bool _Resize(size_t count);
71
72private:
73	size_t	fCapacity;
74	size_t	fChunkSize;
75	int32	fItemCount;
76	item_t	*fItems;
77};
78
79// sDefaultItem
80template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
81typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
82	List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
83		DEFAULT_ITEM_SUPPLIER::GetItem());
84
85// constructor
86template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
87List<ITEM, DEFAULT_ITEM_SUPPLIER>::List(size_t chunkSize)
88	: fCapacity(0),
89	  fChunkSize(chunkSize),
90	  fItemCount(0),
91	  fItems(NULL)
92{
93	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
94		fChunkSize = kDefaultChunkSize;
95	_Resize(0);
96}
97
98// destructor
99template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
100List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List()
101{
102	MakeEmpty();
103	free(fItems);
104}
105
106// GetDefaultItem
107template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
108inline
109const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
110List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const
111{
112	return sDefaultItem;
113}
114
115// GetDefaultItem
116template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
117inline
118typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
119List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem()
120{
121	return sDefaultItem;
122}
123
124// _MoveItems
125template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
126inline
127void
128List<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count)
129{
130	if (count > 0 && offset != 0)
131		memmove(items + offset, items, count * sizeof(item_t));
132}
133
134// AddItem
135template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
136bool
137List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index)
138{
139	bool result = (index >= 0 && index <= fItemCount
140				   && _Resize(fItemCount + 1));
141	if (result) {
142		_MoveItems(fItems + index, 1, fItemCount - index - 1);
143		new(fItems + index) item_t(item);
144	}
145	return result;
146}
147
148// AddItem
149template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
150bool
151List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item)
152{
153	bool result = true;
154	if ((int32)fCapacity > fItemCount) {
155		new(fItems + fItemCount) item_t(item);
156		fItemCount++;
157	} else {
158		if ((result = _Resize(fItemCount + 1)))
159			new(fItems + (fItemCount - 1)) item_t(item);
160	}
161	return result;
162}
163
164// These don't use the copy constructor!
165/*
166// AddList
167template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
168bool
169List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index)
170{
171	bool result = (list && index >= 0 && index <= fItemCount);
172	if (result && list->fItemCount > 0) {
173		int32 count = list->fItemCount;
174		result = _Resize(fItemCount + count);
175		if (result) {
176			_MoveItems(fItems + index, count, fItemCount - index - count);
177			memcpy(fItems + index, list->fItems,
178				   list->fItemCount * sizeof(item_t));
179		}
180	}
181	return result;
182}
183
184// AddList
185template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
186bool
187List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list)
188{
189	bool result = (list);
190	if (result && list->fItemCount > 0) {
191		int32 index = fItemCount;
192		int32 count = list->fItemCount;
193		result = _Resize(fItemCount + count);
194		if (result) {
195			memcpy(fItems + index, list->fItems,
196				   list->fItemCount * sizeof(item_t));
197		}
198	}
199	return result;
200}
201*/
202
203// RemoveItem
204template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
205bool
206List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item)
207{
208	int32 index = IndexOf(item);
209	bool result = (index >= 0);
210	if (result)
211		RemoveItem(index);
212	return result;
213}
214
215// RemoveItem
216template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
217bool
218List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index)
219{
220	if (index >= 0 && index < fItemCount) {
221		fItems[index].~item_t();
222		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
223		_Resize(fItemCount - 1);
224		return true;
225	}
226	return false;
227}
228
229// ReplaceItem
230template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
231bool
232List<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item)
233{
234	if (index >= 0 && index < fItemCount) {
235		fItems[index] = item;
236		return true;
237	}
238	return false;
239}
240
241// MoveItem
242template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
243bool
244List<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex)
245{
246	if (oldIndex >= 0 && oldIndex < fItemCount
247		&& newIndex >= 0 && newIndex <= fItemCount) {
248		if (oldIndex < newIndex - 1) {
249			item_t item = fItems[oldIndex];
250			_MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1);
251			fItems[newIndex] = item;
252		} else if (oldIndex > newIndex) {
253			item_t item = fItems[oldIndex];
254			_MoveItems(fItems + newIndex, 1, oldIndex - newIndex);
255			fItems[newIndex] = item;
256		}
257		return true;
258	}
259	return false;
260}
261
262// MakeEmpty
263template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
264void
265List<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty()
266{
267	for (int32 i = 0; i < fItemCount; i++)
268		fItems[i].~item_t();
269	_Resize(0);
270}
271
272// CountItems
273template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
274int32
275List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
276{
277	return fItemCount;
278}
279
280// IsEmpty
281template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
282bool
283List<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const
284{
285	return (fItemCount == 0);
286}
287
288// ItemAt
289template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
290const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
291List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const
292{
293	if (index >= 0 && index < fItemCount)
294		return fItems[index];
295	return sDefaultItem;
296}
297
298// ItemAt
299template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
300typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
301List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index)
302{
303	if (index >= 0 && index < fItemCount)
304		return fItems[index];
305	return sDefaultItem;
306}
307
308// Items
309template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
310const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
311List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
312{
313	return fItems;
314}
315
316// IndexOf
317template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
318int32
319List<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const
320{
321	for (int32 i = 0; i < fItemCount; i++) {
322		if (fItems[i] == item)
323			return i;
324	}
325	return -1;
326}
327
328// HasItem
329template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
330bool
331List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
332{
333	return (IndexOf(item) >= 0);
334}
335
336// _Resize
337template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
338bool
339List<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count)
340{
341	bool result = true;
342	// calculate the new capacity
343	int32 newSize = count;
344	if (newSize <= 0)
345		newSize = 1;
346	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
347	// resize if necessary
348	if ((size_t)newSize != fCapacity) {
349		item_t* newItems
350			= (item_t*)realloc(fItems, newSize * sizeof(item_t));
351		if (newItems) {
352			fItems = newItems;
353			fCapacity = newSize;
354		} else
355			result = false;
356	}
357	if (result)
358		fItemCount = count;
359	return result;
360}
361
362#endif	// LIST_H
363