1// List.h
2//
3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
4//
5// Permission is hereby granted, free of charge, to any person obtaining a
6// copy of this software and associated documentation files (the "Software"),
7// to deal in the Software without restriction, including without limitation
8// the rights to use, copy, modify, merge, publish, distribute, sublicense,
9// and/or sell copies of the Software, and to permit persons to whom the
10// Software is furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in
13// all copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21// DEALINGS IN THE SOFTWARE.
22//
23// Except as contained in this notice, the name of a copyright holder shall
24// not be used in advertising or otherwise to promote the sale, use or other
25// dealings in this Software without prior written authorization of the
26// copyright holder.
27
28#ifndef LIST_H
29#define LIST_H
30
31#include <stdlib.h>
32#include <string.h>
33
34#include <new>
35
36#include <SupportDefs.h>
37
38template<typename ITEM>
39class DefaultDefaultItemCreator {
40public:
41	static inline ITEM GetItem() { return ITEM(0); }
42};
43
44/*!
45	\class List
46	\brief A generic list implementation.
47*/
48template<typename ITEM,
49		 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> >
50class List {
51public:
52	typedef ITEM					item_t;
53	typedef List					list_t;
54
55private:
56	static item_t					sDefaultItem;
57	static const size_t				kDefaultChunkSize = 10;
58	static const size_t				kMaximalChunkSize = 1024 * 1024;
59
60public:
61	List(size_t chunkSize = kDefaultChunkSize);
62	~List();
63
64	inline const item_t &GetDefaultItem() const;
65	inline item_t &GetDefaultItem();
66
67	bool AddItem(const item_t &item, int32 index);
68	bool AddItem(const item_t &item);
69//	bool AddList(list_t *list, int32 index);
70//	bool AddList(list_t *list);
71
72	bool RemoveItem(const item_t &item);
73	bool RemoveItem(int32 index);
74
75	bool ReplaceItem(int32 index, const item_t &item);
76
77	bool MoveItem(int32 oldIndex, int32 newIndex);
78
79	void MakeEmpty();
80
81	int32 CountItems() const;
82	bool IsEmpty() const;
83	const item_t &ItemAt(int32 index) const;
84	item_t &ItemAt(int32 index);
85	const item_t *Items() const;
86	int32 IndexOf(const item_t &item) const;
87	bool HasItem(const item_t &item) const;
88
89	// debugging
90	int32 GetCapacity() const	{ return fCapacity; }
91
92private:
93	inline static void _MoveItems(item_t* items, int32 offset, int32 count);
94	bool _Resize(size_t count);
95
96private:
97	size_t	fCapacity;
98	size_t	fChunkSize;
99	int32	fItemCount;
100	item_t	*fItems;
101};
102
103// sDefaultItem
104template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
105typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
106	List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
107		DEFAULT_ITEM_SUPPLIER::GetItem());
108
109// constructor
110template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
111List<ITEM, DEFAULT_ITEM_SUPPLIER>::List(size_t chunkSize)
112	: fCapacity(0),
113	  fChunkSize(chunkSize),
114	  fItemCount(0),
115	  fItems(NULL)
116{
117	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
118		fChunkSize = kDefaultChunkSize;
119	_Resize(0);
120}
121
122// destructor
123template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
124List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List()
125{
126	MakeEmpty();
127	free(fItems);
128}
129
130// GetDefaultItem
131template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
132inline
133const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
134List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const
135{
136	return sDefaultItem;
137}
138
139// GetDefaultItem
140template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
141inline
142typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
143List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem()
144{
145	return sDefaultItem;
146}
147
148// _MoveItems
149template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
150inline
151void
152List<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count)
153{
154	if (count > 0 && offset != 0)
155		memmove(items + offset, items, count * sizeof(item_t));
156}
157
158// AddItem
159template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
160bool
161List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index)
162{
163	bool result = (index >= 0 && index <= fItemCount
164				   && _Resize(fItemCount + 1));
165	if (result) {
166		_MoveItems(fItems + index, 1, fItemCount - index - 1);
167		new(fItems + index) item_t(item);
168	}
169	return result;
170}
171
172// AddItem
173template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
174bool
175List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item)
176{
177	bool result = true;
178	if ((int32)fCapacity > fItemCount) {
179		new(fItems + fItemCount) item_t(item);
180		fItemCount++;
181	} else {
182		if ((result = _Resize(fItemCount + 1)))
183			new(fItems + (fItemCount - 1)) item_t(item);
184	}
185	return result;
186}
187
188// These don't use the copy constructor!
189/*
190// AddList
191template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
192bool
193List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index)
194{
195	bool result = (list && index >= 0 && index <= fItemCount);
196	if (result && list->fItemCount > 0) {
197		int32 count = list->fItemCount;
198		result = _Resize(fItemCount + count);
199		if (result) {
200			_MoveItems(fItems + index, count, fItemCount - index - count);
201			memcpy(fItems + index, list->fItems,
202				   list->fItemCount * sizeof(item_t));
203		}
204	}
205	return result;
206}
207
208// AddList
209template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
210bool
211List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list)
212{
213	bool result = (list);
214	if (result && list->fItemCount > 0) {
215		int32 index = fItemCount;
216		int32 count = list->fItemCount;
217		result = _Resize(fItemCount + count);
218		if (result) {
219			memcpy(fItems + index, list->fItems,
220				   list->fItemCount * sizeof(item_t));
221		}
222	}
223	return result;
224}
225*/
226
227// RemoveItem
228template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
229bool
230List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item)
231{
232	int32 index = IndexOf(item);
233	bool result = (index >= 0);
234	if (result)
235		RemoveItem(index);
236	return result;
237}
238
239// RemoveItem
240template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
241bool
242List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index)
243{
244	if (index >= 0 && index < fItemCount) {
245		fItems[index].~item_t();
246		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
247		_Resize(fItemCount - 1);
248		return true;
249	}
250	return false;
251}
252
253// ReplaceItem
254template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
255bool
256List<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item)
257{
258	if (index >= 0 && index < fItemCount) {
259		fItems[index] = item;
260		return true;
261	}
262	return false;
263}
264
265// MoveItem
266template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
267bool
268List<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex)
269{
270	if (oldIndex >= 0 && oldIndex < fItemCount
271		&& newIndex >= 0 && newIndex <= fItemCount) {
272		if (oldIndex < newIndex - 1) {
273			item_t item = fItems[oldIndex];
274			_MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1);
275			fItems[newIndex] = item;
276		} else if (oldIndex > newIndex) {
277			item_t item = fItems[oldIndex];
278			_MoveItems(fItems + newIndex, 1, oldIndex - newIndex);
279			fItems[newIndex] = item;
280		}
281		return true;
282	}
283	return false;
284}
285
286// MakeEmpty
287template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
288void
289List<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty()
290{
291	for (int32 i = 0; i < fItemCount; i++)
292		fItems[i].~item_t();
293	_Resize(0);
294}
295
296// CountItems
297template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
298int32
299List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
300{
301	return fItemCount;
302}
303
304// IsEmpty
305template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
306bool
307List<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const
308{
309	return (fItemCount == 0);
310}
311
312// ItemAt
313template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
314const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
315List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const
316{
317	if (index >= 0 && index < fItemCount)
318		return fItems[index];
319	return sDefaultItem;
320}
321
322// ItemAt
323template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
324typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
325List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index)
326{
327	if (index >= 0 && index < fItemCount)
328		return fItems[index];
329	return sDefaultItem;
330}
331
332// Items
333template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
334const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
335List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
336{
337	return fItems;
338}
339
340// IndexOf
341template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
342int32
343List<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const
344{
345	for (int32 i = 0; i < fItemCount; i++) {
346		if (fItems[i] == item)
347			return i;
348	}
349	return -1;
350}
351
352// HasItem
353template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
354bool
355List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
356{
357	return (IndexOf(item) >= 0);
358}
359
360// _Resize
361template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
362bool
363List<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count)
364{
365	bool result = true;
366	// calculate the new capacity
367	int32 newSize = count;
368	if (newSize <= 0)
369		newSize = 1;
370	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
371	// resize if necessary
372	if ((size_t)newSize != fCapacity) {
373		item_t* newItems
374			= (item_t*)realloc(fItems, newSize * sizeof(item_t));
375		if (newItems) {
376			fItems = newItems;
377			fCapacity = newSize;
378		} else
379			result = false;
380	}
381	if (result)
382		fItemCount = count;
383	return result;
384}
385
386#endif	// LIST_H
387