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