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