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