1731be7ddSAugustin Cavalier/*
2731be7ddSAugustin Cavalier * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de.
3731be7ddSAugustin Cavalier * All rights reserved. Distributed under the terms of the MIT license.
4731be7ddSAugustin Cavalier */
5224e7c42SIngo Weinhold#ifndef LIST_H
6224e7c42SIngo Weinhold#define LIST_H
7224e7c42SIngo Weinhold
893344365SAlexander von Gluck IV#include <new>
9224e7c42SIngo Weinhold#include <stdlib.h>
10224e7c42SIngo Weinhold#include <string.h>
11224e7c42SIngo Weinhold
12224e7c42SIngo Weinhold#include <SupportDefs.h>
13224e7c42SIngo Weinhold
14224e7c42SIngo Weinholdtemplate<typename ITEM>
15224e7c42SIngo Weinholdclass DefaultDefaultItemCreator {
16224e7c42SIngo Weinholdpublic:
17224e7c42SIngo Weinhold	static inline ITEM GetItem() { return ITEM(0); }
18224e7c42SIngo Weinhold};
19224e7c42SIngo Weinhold
20224e7c42SIngo Weinhold/*!
21224e7c42SIngo Weinhold	\class List
22224e7c42SIngo Weinhold	\brief A generic list implementation.
23224e7c42SIngo Weinhold*/
24224e7c42SIngo Weinholdtemplate<typename ITEM,
25224e7c42SIngo Weinhold		 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> >
26224e7c42SIngo Weinholdclass List {
27224e7c42SIngo Weinholdpublic:
28224e7c42SIngo Weinhold	typedef ITEM					item_t;
29224e7c42SIngo Weinhold	typedef List					list_t;
30224e7c42SIngo Weinhold
31224e7c42SIngo Weinholdprivate:
32224e7c42SIngo Weinhold	static item_t					sDefaultItem;
33224e7c42SIngo Weinhold	static const size_t				kDefaultChunkSize = 10;
34224e7c42SIngo Weinhold	static const size_t				kMaximalChunkSize = 1024 * 1024;
35224e7c42SIngo Weinhold
36224e7c42SIngo Weinholdpublic:
37224e7c42SIngo Weinhold	List(size_t chunkSize = kDefaultChunkSize);
38224e7c42SIngo Weinhold	~List();
39224e7c42SIngo Weinhold
40224e7c42SIngo Weinhold	inline const item_t &GetDefaultItem() const;
41224e7c42SIngo Weinhold	inline item_t &GetDefaultItem();
42224e7c42SIngo Weinhold
43224e7c42SIngo Weinhold	bool AddItem(const item_t &item, int32 index);
44224e7c42SIngo Weinhold	bool AddItem(const item_t &item);
45224e7c42SIngo Weinhold//	bool AddList(list_t *list, int32 index);
46224e7c42SIngo Weinhold//	bool AddList(list_t *list);
47224e7c42SIngo Weinhold
48224e7c42SIngo Weinhold	bool RemoveItem(const item_t &item);
49224e7c42SIngo Weinhold	bool RemoveItem(int32 index);
50224e7c42SIngo Weinhold
51224e7c42SIngo Weinhold	bool ReplaceItem(int32 index, const item_t &item);
52224e7c42SIngo Weinhold
53224e7c42SIngo Weinhold	bool MoveItem(int32 oldIndex, int32 newIndex);
54224e7c42SIngo Weinhold
55224e7c42SIngo Weinhold	void MakeEmpty();
56224e7c42SIngo Weinhold
57224e7c42SIngo Weinhold	int32 CountItems() const;
58224e7c42SIngo Weinhold	bool IsEmpty() const;
59224e7c42SIngo Weinhold	const item_t &ItemAt(int32 index) const;
60224e7c42SIngo Weinhold	item_t &ItemAt(int32 index);
61224e7c42SIngo Weinhold	const item_t *Items() const;
62224e7c42SIngo Weinhold	int32 IndexOf(const item_t &item) const;
63224e7c42SIngo Weinhold	bool HasItem(const item_t &item) const;
64224e7c42SIngo Weinhold
65224e7c42SIngo Weinhold	// debugging
66224e7c42SIngo Weinhold	int32 GetCapacity() const	{ return fCapacity; }
67224e7c42SIngo Weinhold
68224e7c42SIngo Weinholdprivate:
69224e7c42SIngo Weinhold	inline static void _MoveItems(item_t* items, int32 offset, int32 count);
70224e7c42SIngo Weinhold	bool _Resize(size_t count);
71224e7c42SIngo Weinhold
72224e7c42SIngo Weinholdprivate:
73224e7c42SIngo Weinhold	size_t	fCapacity;
74224e7c42SIngo Weinhold	size_t	fChunkSize;
75224e7c42SIngo Weinhold	int32	fItemCount;
76224e7c42SIngo Weinhold	item_t	*fItems;
77224e7c42SIngo Weinhold};
78224e7c42SIngo Weinhold
79224e7c42SIngo Weinhold// sDefaultItem
80224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
81c7a72423SIngo Weinholdtypename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
82224e7c42SIngo Weinhold	List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
83224e7c42SIngo Weinhold		DEFAULT_ITEM_SUPPLIER::GetItem());
84224e7c42SIngo Weinhold
85224e7c42SIngo Weinhold// constructor
86224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
87224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::List(size_t chunkSize)
88224e7c42SIngo Weinhold	: fCapacity(0),
89224e7c42SIngo Weinhold	  fChunkSize(chunkSize),
90224e7c42SIngo Weinhold	  fItemCount(0),
91224e7c42SIngo Weinhold	  fItems(NULL)
92224e7c42SIngo Weinhold{
93224e7c42SIngo Weinhold	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
94224e7c42SIngo Weinhold		fChunkSize = kDefaultChunkSize;
95224e7c42SIngo Weinhold	_Resize(0);
96224e7c42SIngo Weinhold}
97224e7c42SIngo Weinhold
98224e7c42SIngo Weinhold// destructor
99224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
100224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::~List()
101224e7c42SIngo Weinhold{
102224e7c42SIngo Weinhold	MakeEmpty();
103224e7c42SIngo Weinhold	free(fItems);
104224e7c42SIngo Weinhold}
105224e7c42SIngo Weinhold
106224e7c42SIngo Weinhold// GetDefaultItem
107224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
108224e7c42SIngo Weinholdinline
109c7a72423SIngo Weinholdconst typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
110224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const
111224e7c42SIngo Weinhold{
112224e7c42SIngo Weinhold	return sDefaultItem;
113224e7c42SIngo Weinhold}
114224e7c42SIngo Weinhold
115224e7c42SIngo Weinhold// GetDefaultItem
116224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
117224e7c42SIngo Weinholdinline
118c7a72423SIngo Weinholdtypename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
119224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem()
120224e7c42SIngo Weinhold{
121224e7c42SIngo Weinhold	return sDefaultItem;
122224e7c42SIngo Weinhold}
123224e7c42SIngo Weinhold
124224e7c42SIngo Weinhold// _MoveItems
125224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
126224e7c42SIngo Weinholdinline
127224e7c42SIngo Weinholdvoid
128224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count)
129224e7c42SIngo Weinhold{
130224e7c42SIngo Weinhold	if (count > 0 && offset != 0)
131224e7c42SIngo Weinhold		memmove(items + offset, items, count * sizeof(item_t));
132224e7c42SIngo Weinhold}
133224e7c42SIngo Weinhold
134224e7c42SIngo Weinhold// AddItem
135224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
136224e7c42SIngo Weinholdbool
137224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index)
138224e7c42SIngo Weinhold{
139224e7c42SIngo Weinhold	bool result = (index >= 0 && index <= fItemCount
140224e7c42SIngo Weinhold				   && _Resize(fItemCount + 1));
141224e7c42SIngo Weinhold	if (result) {
142224e7c42SIngo Weinhold		_MoveItems(fItems + index, 1, fItemCount - index - 1);
143224e7c42SIngo Weinhold		new(fItems + index) item_t(item);
144224e7c42SIngo Weinhold	}
145224e7c42SIngo Weinhold	return result;
146224e7c42SIngo Weinhold}
147224e7c42SIngo Weinhold
148224e7c42SIngo Weinhold// AddItem
149224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
150224e7c42SIngo Weinholdbool
151224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item)
152224e7c42SIngo Weinhold{
153224e7c42SIngo Weinhold	bool result = true;
154224e7c42SIngo Weinhold	if ((int32)fCapacity > fItemCount) {
155224e7c42SIngo Weinhold		new(fItems + fItemCount) item_t(item);
156224e7c42SIngo Weinhold		fItemCount++;
157224e7c42SIngo Weinhold	} else {
158224e7c42SIngo Weinhold		if ((result = _Resize(fItemCount + 1)))
159224e7c42SIngo Weinhold			new(fItems + (fItemCount - 1)) item_t(item);
160224e7c42SIngo Weinhold	}
161224e7c42SIngo Weinhold	return result;
162224e7c42SIngo Weinhold}
163224e7c42SIngo Weinhold
164224e7c42SIngo Weinhold// These don't use the copy constructor!
165224e7c42SIngo Weinhold/*
166224e7c42SIngo Weinhold// AddList
167224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
168224e7c42SIngo Weinholdbool
169224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index)
170224e7c42SIngo Weinhold{
171224e7c42SIngo Weinhold	bool result = (list && index >= 0 && index <= fItemCount);
172224e7c42SIngo Weinhold	if (result && list->fItemCount > 0) {
173224e7c42SIngo Weinhold		int32 count = list->fItemCount;
174224e7c42SIngo Weinhold		result = _Resize(fItemCount + count);
175224e7c42SIngo Weinhold		if (result) {
176224e7c42SIngo Weinhold			_MoveItems(fItems + index, count, fItemCount - index - count);
177224e7c42SIngo Weinhold			memcpy(fItems + index, list->fItems,
178224e7c42SIngo Weinhold				   list->fItemCount * sizeof(item_t));
179224e7c42SIngo Weinhold		}
180224e7c42SIngo Weinhold	}
181224e7c42SIngo Weinhold	return result;
182224e7c42SIngo Weinhold}
183224e7c42SIngo Weinhold
184224e7c42SIngo Weinhold// AddList
185224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
186224e7c42SIngo Weinholdbool
187224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list)
188224e7c42SIngo Weinhold{
189224e7c42SIngo Weinhold	bool result = (list);
190224e7c42SIngo Weinhold	if (result && list->fItemCount > 0) {
191224e7c42SIngo Weinhold		int32 index = fItemCount;
192224e7c42SIngo Weinhold		int32 count = list->fItemCount;
193224e7c42SIngo Weinhold		result = _Resize(fItemCount + count);
194224e7c42SIngo Weinhold		if (result) {
195224e7c42SIngo Weinhold			memcpy(fItems + index, list->fItems,
196224e7c42SIngo Weinhold				   list->fItemCount * sizeof(item_t));
197224e7c42SIngo Weinhold		}
198224e7c42SIngo Weinhold	}
199224e7c42SIngo Weinhold	return result;
200224e7c42SIngo Weinhold}
201224e7c42SIngo Weinhold*/
202224e7c42SIngo Weinhold
203224e7c42SIngo Weinhold// RemoveItem
204224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
205224e7c42SIngo Weinholdbool
206224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item)
207224e7c42SIngo Weinhold{
208224e7c42SIngo Weinhold	int32 index = IndexOf(item);
209224e7c42SIngo Weinhold	bool result = (index >= 0);
210224e7c42SIngo Weinhold	if (result)
211224e7c42SIngo Weinhold		RemoveItem(index);
212224e7c42SIngo Weinhold	return result;
213224e7c42SIngo Weinhold}
214224e7c42SIngo Weinhold
215224e7c42SIngo Weinhold// RemoveItem
216224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
217224e7c42SIngo Weinholdbool
218224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index)
219224e7c42SIngo Weinhold{
220224e7c42SIngo Weinhold	if (index >= 0 && index < fItemCount) {
221224e7c42SIngo Weinhold		fItems[index].~item_t();
222224e7c42SIngo Weinhold		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
223224e7c42SIngo Weinhold		_Resize(fItemCount - 1);
224224e7c42SIngo Weinhold		return true;
225224e7c42SIngo Weinhold	}
226224e7c42SIngo Weinhold	return false;
227224e7c42SIngo Weinhold}
228224e7c42SIngo Weinhold
229224e7c42SIngo Weinhold// ReplaceItem
230224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
231224e7c42SIngo Weinholdbool
232224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item)
233224e7c42SIngo Weinhold{
234224e7c42SIngo Weinhold	if (index >= 0 && index < fItemCount) {
235224e7c42SIngo Weinhold		fItems[index] = item;
236224e7c42SIngo Weinhold		return true;
237224e7c42SIngo Weinhold	}
238224e7c42SIngo Weinhold	return false;
239224e7c42SIngo Weinhold}
240224e7c42SIngo Weinhold
241224e7c42SIngo Weinhold// MoveItem
242224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
243224e7c42SIngo Weinholdbool
244224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex)
245224e7c42SIngo Weinhold{
246224e7c42SIngo Weinhold	if (oldIndex >= 0 && oldIndex < fItemCount
247224e7c42SIngo Weinhold		&& newIndex >= 0 && newIndex <= fItemCount) {
248224e7c42SIngo Weinhold		if (oldIndex < newIndex - 1) {
249224e7c42SIngo Weinhold			item_t item = fItems[oldIndex];
250224e7c42SIngo Weinhold			_MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1);
251224e7c42SIngo Weinhold			fItems[newIndex] = item;
252224e7c42SIngo Weinhold		} else if (oldIndex > newIndex) {
253224e7c42SIngo Weinhold			item_t item = fItems[oldIndex];
254224e7c42SIngo Weinhold			_MoveItems(fItems + newIndex, 1, oldIndex - newIndex);
255224e7c42SIngo Weinhold			fItems[newIndex] = item;
256224e7c42SIngo Weinhold		}
257224e7c42SIngo Weinhold		return true;
258224e7c42SIngo Weinhold	}
259224e7c42SIngo Weinhold	return false;
260224e7c42SIngo Weinhold}
261224e7c42SIngo Weinhold
262224e7c42SIngo Weinhold// MakeEmpty
263224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
264224e7c42SIngo Weinholdvoid
265224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty()
266224e7c42SIngo Weinhold{
267224e7c42SIngo Weinhold	for (int32 i = 0; i < fItemCount; i++)
268224e7c42SIngo Weinhold		fItems[i].~item_t();
269224e7c42SIngo Weinhold	_Resize(0);
270224e7c42SIngo Weinhold}
271224e7c42SIngo Weinhold
272224e7c42SIngo Weinhold// CountItems
273224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
274224e7c42SIngo Weinholdint32
275224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
276224e7c42SIngo Weinhold{
277224e7c42SIngo Weinhold	return fItemCount;
278224e7c42SIngo Weinhold}
279224e7c42SIngo Weinhold
280224e7c42SIngo Weinhold// IsEmpty
281224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
282224e7c42SIngo Weinholdbool
283224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const
284224e7c42SIngo Weinhold{
285224e7c42SIngo Weinhold	return (fItemCount == 0);
286224e7c42SIngo Weinhold}
287224e7c42SIngo Weinhold
288224e7c42SIngo Weinhold// ItemAt
289224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
290c7a72423SIngo Weinholdconst typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
291224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const
292224e7c42SIngo Weinhold{
293224e7c42SIngo Weinhold	if (index >= 0 && index < fItemCount)
294224e7c42SIngo Weinhold		return fItems[index];
295224e7c42SIngo Weinhold	return sDefaultItem;
296224e7c42SIngo Weinhold}
297224e7c42SIngo Weinhold
298224e7c42SIngo Weinhold// ItemAt
299224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
300c7a72423SIngo Weinholdtypename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
301224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index)
302224e7c42SIngo Weinhold{
303224e7c42SIngo Weinhold	if (index >= 0 && index < fItemCount)
304224e7c42SIngo Weinhold		return fItems[index];
305224e7c42SIngo Weinhold	return sDefaultItem;
306224e7c42SIngo Weinhold}
307224e7c42SIngo Weinhold
308224e7c42SIngo Weinhold// Items
309224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
310c7a72423SIngo Weinholdconst typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
311224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
312224e7c42SIngo Weinhold{
313224e7c42SIngo Weinhold	return fItems;
314224e7c42SIngo Weinhold}
315224e7c42SIngo Weinhold
316224e7c42SIngo Weinhold// IndexOf
317224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
318224e7c42SIngo Weinholdint32
319224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const
320224e7c42SIngo Weinhold{
321224e7c42SIngo Weinhold	for (int32 i = 0; i < fItemCount; i++) {
322224e7c42SIngo Weinhold		if (fItems[i] == item)
323224e7c42SIngo Weinhold			return i;
324224e7c42SIngo Weinhold	}
325224e7c42SIngo Weinhold	return -1;
326224e7c42SIngo Weinhold}
327224e7c42SIngo Weinhold
328224e7c42SIngo Weinhold// HasItem
329224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
330224e7c42SIngo Weinholdbool
331224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
332224e7c42SIngo Weinhold{
333224e7c42SIngo Weinhold	return (IndexOf(item) >= 0);
334224e7c42SIngo Weinhold}
335224e7c42SIngo Weinhold
336224e7c42SIngo Weinhold// _Resize
337224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
338224e7c42SIngo Weinholdbool
339224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count)
340224e7c42SIngo Weinhold{
341224e7c42SIngo Weinhold	bool result = true;
342224e7c42SIngo Weinhold	// calculate the new capacity
343224e7c42SIngo Weinhold	int32 newSize = count;
344224e7c42SIngo Weinhold	if (newSize <= 0)
345224e7c42SIngo Weinhold		newSize = 1;
346224e7c42SIngo Weinhold	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
347224e7c42SIngo Weinhold	// resize if necessary
348224e7c42SIngo Weinhold	if ((size_t)newSize != fCapacity) {
349224e7c42SIngo Weinhold		item_t* newItems
350224e7c42SIngo Weinhold			= (item_t*)realloc(fItems, newSize * sizeof(item_t));
351224e7c42SIngo Weinhold		if (newItems) {
352224e7c42SIngo Weinhold			fItems = newItems;
353224e7c42SIngo Weinhold			fCapacity = newSize;
354224e7c42SIngo Weinhold		} else
355224e7c42SIngo Weinhold			result = false;
356224e7c42SIngo Weinhold	}
357224e7c42SIngo Weinhold	if (result)
358224e7c42SIngo Weinhold		fItemCount = count;
359224e7c42SIngo Weinhold	return result;
360224e7c42SIngo Weinhold}
361224e7c42SIngo Weinhold
362224e7c42SIngo Weinhold#endif	// LIST_H
363