1224e7c42SIngo Weinhold// List.h
2224e7c42SIngo Weinhold//
3224e7c42SIngo Weinhold// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
4224e7c42SIngo Weinhold//
5224e7c42SIngo Weinhold// Permission is hereby granted, free of charge, to any person obtaining a
6224e7c42SIngo Weinhold// copy of this software and associated documentation files (the "Software"),
7224e7c42SIngo Weinhold// to deal in the Software without restriction, including without limitation
8224e7c42SIngo Weinhold// the rights to use, copy, modify, merge, publish, distribute, sublicense,
9224e7c42SIngo Weinhold// and/or sell copies of the Software, and to permit persons to whom the
10224e7c42SIngo Weinhold// Software is furnished to do so, subject to the following conditions:
11224e7c42SIngo Weinhold//
12224e7c42SIngo Weinhold// The above copyright notice and this permission notice shall be included in
13224e7c42SIngo Weinhold// all copies or substantial portions of the Software.
14224e7c42SIngo Weinhold//
15224e7c42SIngo Weinhold// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16224e7c42SIngo Weinhold// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17224e7c42SIngo Weinhold// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18224e7c42SIngo Weinhold// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19224e7c42SIngo Weinhold// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20224e7c42SIngo Weinhold// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21224e7c42SIngo Weinhold// DEALINGS IN THE SOFTWARE.
22224e7c42SIngo Weinhold//
23224e7c42SIngo Weinhold// Except as contained in this notice, the name of a copyright holder shall
24224e7c42SIngo Weinhold// not be used in advertising or otherwise to promote the sale, use or other
25224e7c42SIngo Weinhold// dealings in this Software without prior written authorization of the
26224e7c42SIngo Weinhold// copyright holder.
27224e7c42SIngo Weinhold
28224e7c42SIngo Weinhold#ifndef LIST_H
29224e7c42SIngo Weinhold#define LIST_H
30224e7c42SIngo Weinhold
3193344365SAlexander von Gluck IV#include <new>
32224e7c42SIngo Weinhold#include <stdlib.h>
33224e7c42SIngo Weinhold#include <string.h>
34224e7c42SIngo Weinhold
35224e7c42SIngo Weinhold#include <SupportDefs.h>
36224e7c42SIngo Weinhold
37224e7c42SIngo Weinholdtemplate<typename ITEM>
38224e7c42SIngo Weinholdclass DefaultDefaultItemCreator {
39224e7c42SIngo Weinholdpublic:
40224e7c42SIngo Weinhold	static inline ITEM GetItem() { return ITEM(0); }
41224e7c42SIngo Weinhold};
42224e7c42SIngo Weinhold
43224e7c42SIngo Weinhold/*!
44224e7c42SIngo Weinhold	\class List
45224e7c42SIngo Weinhold	\brief A generic list implementation.
46224e7c42SIngo Weinhold*/
47224e7c42SIngo Weinholdtemplate<typename ITEM,
48224e7c42SIngo Weinhold		 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> >
49224e7c42SIngo Weinholdclass List {
50224e7c42SIngo Weinholdpublic:
51224e7c42SIngo Weinhold	typedef ITEM					item_t;
52224e7c42SIngo Weinhold	typedef List					list_t;
53224e7c42SIngo Weinhold
54224e7c42SIngo Weinholdprivate:
55224e7c42SIngo Weinhold	static item_t					sDefaultItem;
56224e7c42SIngo Weinhold	static const size_t				kDefaultChunkSize = 10;
57224e7c42SIngo Weinhold	static const size_t				kMaximalChunkSize = 1024 * 1024;
58224e7c42SIngo Weinhold
59224e7c42SIngo Weinholdpublic:
60224e7c42SIngo Weinhold	List(size_t chunkSize = kDefaultChunkSize);
61224e7c42SIngo Weinhold	~List();
62224e7c42SIngo Weinhold
63224e7c42SIngo Weinhold	inline const item_t &GetDefaultItem() const;
64224e7c42SIngo Weinhold	inline item_t &GetDefaultItem();
65224e7c42SIngo Weinhold
66224e7c42SIngo Weinhold	bool AddItem(const item_t &item, int32 index);
67224e7c42SIngo Weinhold	bool AddItem(const item_t &item);
68224e7c42SIngo Weinhold//	bool AddList(list_t *list, int32 index);
69224e7c42SIngo Weinhold//	bool AddList(list_t *list);
70224e7c42SIngo Weinhold
71224e7c42SIngo Weinhold	bool RemoveItem(const item_t &item);
72224e7c42SIngo Weinhold	bool RemoveItem(int32 index);
73224e7c42SIngo Weinhold
74224e7c42SIngo Weinhold	bool ReplaceItem(int32 index, const item_t &item);
75224e7c42SIngo Weinhold
76224e7c42SIngo Weinhold	bool MoveItem(int32 oldIndex, int32 newIndex);
77224e7c42SIngo Weinhold
78224e7c42SIngo Weinhold	void MakeEmpty();
79224e7c42SIngo Weinhold
80224e7c42SIngo Weinhold	int32 CountItems() const;
81224e7c42SIngo Weinhold	bool IsEmpty() const;
82224e7c42SIngo Weinhold	const item_t &ItemAt(int32 index) const;
83224e7c42SIngo Weinhold	item_t &ItemAt(int32 index);
84224e7c42SIngo Weinhold	const item_t *Items() const;
85224e7c42SIngo Weinhold	int32 IndexOf(const item_t &item) const;
86224e7c42SIngo Weinhold	bool HasItem(const item_t &item) const;
87224e7c42SIngo Weinhold
88224e7c42SIngo Weinhold	// debugging
89224e7c42SIngo Weinhold	int32 GetCapacity() const	{ return fCapacity; }
90224e7c42SIngo Weinhold
91224e7c42SIngo Weinholdprivate:
92224e7c42SIngo Weinhold	inline static void _MoveItems(item_t* items, int32 offset, int32 count);
93224e7c42SIngo Weinhold	bool _Resize(size_t count);
94224e7c42SIngo Weinhold
95224e7c42SIngo Weinholdprivate:
96224e7c42SIngo Weinhold	size_t	fCapacity;
97224e7c42SIngo Weinhold	size_t	fChunkSize;
98224e7c42SIngo Weinhold	int32	fItemCount;
99224e7c42SIngo Weinhold	item_t	*fItems;
100224e7c42SIngo Weinhold};
101224e7c42SIngo Weinhold
102224e7c42SIngo Weinhold// sDefaultItem
103224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
104c7a72423SIngo Weinholdtypename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
105224e7c42SIngo Weinhold	List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
106224e7c42SIngo Weinhold		DEFAULT_ITEM_SUPPLIER::GetItem());
107224e7c42SIngo Weinhold
108224e7c42SIngo Weinhold// constructor
109224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
110224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::List(size_t chunkSize)
111224e7c42SIngo Weinhold	: fCapacity(0),
112224e7c42SIngo Weinhold	  fChunkSize(chunkSize),
113224e7c42SIngo Weinhold	  fItemCount(0),
114224e7c42SIngo Weinhold	  fItems(NULL)
115224e7c42SIngo Weinhold{
116224e7c42SIngo Weinhold	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
117224e7c42SIngo Weinhold		fChunkSize = kDefaultChunkSize;
118224e7c42SIngo Weinhold	_Resize(0);
119224e7c42SIngo Weinhold}
120224e7c42SIngo Weinhold
121224e7c42SIngo Weinhold// destructor
122224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
123224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::~List()
124224e7c42SIngo Weinhold{
125224e7c42SIngo Weinhold	MakeEmpty();
126224e7c42SIngo Weinhold	free(fItems);
127224e7c42SIngo Weinhold}
128224e7c42SIngo Weinhold
129224e7c42SIngo Weinhold// GetDefaultItem
130224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
131224e7c42SIngo Weinholdinline
132c7a72423SIngo Weinholdconst typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
133224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const
134224e7c42SIngo Weinhold{
135224e7c42SIngo Weinhold	return sDefaultItem;
136224e7c42SIngo Weinhold}
137224e7c42SIngo Weinhold
138224e7c42SIngo Weinhold// GetDefaultItem
139224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
140224e7c42SIngo Weinholdinline
141c7a72423SIngo Weinholdtypename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
142224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem()
143224e7c42SIngo Weinhold{
144224e7c42SIngo Weinhold	return sDefaultItem;
145224e7c42SIngo Weinhold}
146224e7c42SIngo Weinhold
147224e7c42SIngo Weinhold// _MoveItems
148224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
149224e7c42SIngo Weinholdinline
150224e7c42SIngo Weinholdvoid
151224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count)
152224e7c42SIngo Weinhold{
153224e7c42SIngo Weinhold	if (count > 0 && offset != 0)
154224e7c42SIngo Weinhold		memmove(items + offset, items, count * sizeof(item_t));
155224e7c42SIngo Weinhold}
156224e7c42SIngo Weinhold
157224e7c42SIngo Weinhold// AddItem
158224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
159224e7c42SIngo Weinholdbool
160224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index)
161224e7c42SIngo Weinhold{
162224e7c42SIngo Weinhold	bool result = (index >= 0 && index <= fItemCount
163224e7c42SIngo Weinhold				   && _Resize(fItemCount + 1));
164224e7c42SIngo Weinhold	if (result) {
165224e7c42SIngo Weinhold		_MoveItems(fItems + index, 1, fItemCount - index - 1);
166224e7c42SIngo Weinhold		new(fItems + index) item_t(item);
167224e7c42SIngo Weinhold	}
168224e7c42SIngo Weinhold	return result;
169224e7c42SIngo Weinhold}
170224e7c42SIngo Weinhold
171224e7c42SIngo Weinhold// AddItem
172224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
173224e7c42SIngo Weinholdbool
174224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item)
175224e7c42SIngo Weinhold{
176224e7c42SIngo Weinhold	bool result = true;
177224e7c42SIngo Weinhold	if ((int32)fCapacity > fItemCount) {
178224e7c42SIngo Weinhold		new(fItems + fItemCount) item_t(item);
179224e7c42SIngo Weinhold		fItemCount++;
180224e7c42SIngo Weinhold	} else {
181224e7c42SIngo Weinhold		if ((result = _Resize(fItemCount + 1)))
182224e7c42SIngo Weinhold			new(fItems + (fItemCount - 1)) item_t(item);
183224e7c42SIngo Weinhold	}
184224e7c42SIngo Weinhold	return result;
185224e7c42SIngo Weinhold}
186224e7c42SIngo Weinhold
187224e7c42SIngo Weinhold// These don't use the copy constructor!
188224e7c42SIngo Weinhold/*
189224e7c42SIngo Weinhold// AddList
190224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
191224e7c42SIngo Weinholdbool
192224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index)
193224e7c42SIngo Weinhold{
194224e7c42SIngo Weinhold	bool result = (list && index >= 0 && index <= fItemCount);
195224e7c42SIngo Weinhold	if (result && list->fItemCount > 0) {
196224e7c42SIngo Weinhold		int32 count = list->fItemCount;
197224e7c42SIngo Weinhold		result = _Resize(fItemCount + count);
198224e7c42SIngo Weinhold		if (result) {
199224e7c42SIngo Weinhold			_MoveItems(fItems + index, count, fItemCount - index - count);
200224e7c42SIngo Weinhold			memcpy(fItems + index, list->fItems,
201224e7c42SIngo Weinhold				   list->fItemCount * sizeof(item_t));
202224e7c42SIngo Weinhold		}
203224e7c42SIngo Weinhold	}
204224e7c42SIngo Weinhold	return result;
205224e7c42SIngo Weinhold}
206224e7c42SIngo Weinhold
207224e7c42SIngo Weinhold// AddList
208224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
209224e7c42SIngo Weinholdbool
210224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list)
211224e7c42SIngo Weinhold{
212224e7c42SIngo Weinhold	bool result = (list);
213224e7c42SIngo Weinhold	if (result && list->fItemCount > 0) {
214224e7c42SIngo Weinhold		int32 index = fItemCount;
215224e7c42SIngo Weinhold		int32 count = list->fItemCount;
216224e7c42SIngo Weinhold		result = _Resize(fItemCount + count);
217224e7c42SIngo Weinhold		if (result) {
218224e7c42SIngo Weinhold			memcpy(fItems + index, list->fItems,
219224e7c42SIngo Weinhold				   list->fItemCount * sizeof(item_t));
220224e7c42SIngo Weinhold		}
221224e7c42SIngo Weinhold	}
222224e7c42SIngo Weinhold	return result;
223224e7c42SIngo Weinhold}
224224e7c42SIngo Weinhold*/
225224e7c42SIngo Weinhold
226224e7c42SIngo Weinhold// RemoveItem
227224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
228224e7c42SIngo Weinholdbool
229224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item)
230224e7c42SIngo Weinhold{
231224e7c42SIngo Weinhold	int32 index = IndexOf(item);
232224e7c42SIngo Weinhold	bool result = (index >= 0);
233224e7c42SIngo Weinhold	if (result)
234224e7c42SIngo Weinhold		RemoveItem(index);
235224e7c42SIngo Weinhold	return result;
236224e7c42SIngo Weinhold}
237224e7c42SIngo Weinhold
238224e7c42SIngo Weinhold// RemoveItem
239224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
240224e7c42SIngo Weinholdbool
241224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index)
242224e7c42SIngo Weinhold{
243224e7c42SIngo Weinhold	if (index >= 0 && index < fItemCount) {
244224e7c42SIngo Weinhold		fItems[index].~item_t();
245224e7c42SIngo Weinhold		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
246224e7c42SIngo Weinhold		_Resize(fItemCount - 1);
247224e7c42SIngo Weinhold		return true;
248224e7c42SIngo Weinhold	}
249224e7c42SIngo Weinhold	return false;
250224e7c42SIngo Weinhold}
251224e7c42SIngo Weinhold
252224e7c42SIngo Weinhold// ReplaceItem
253224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
254224e7c42SIngo Weinholdbool
255224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item)
256224e7c42SIngo Weinhold{
257224e7c42SIngo Weinhold	if (index >= 0 && index < fItemCount) {
258224e7c42SIngo Weinhold		fItems[index] = item;
259224e7c42SIngo Weinhold		return true;
260224e7c42SIngo Weinhold	}
261224e7c42SIngo Weinhold	return false;
262224e7c42SIngo Weinhold}
263224e7c42SIngo Weinhold
264224e7c42SIngo Weinhold// MoveItem
265224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
266224e7c42SIngo Weinholdbool
267224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex)
268224e7c42SIngo Weinhold{
269224e7c42SIngo Weinhold	if (oldIndex >= 0 && oldIndex < fItemCount
270224e7c42SIngo Weinhold		&& newIndex >= 0 && newIndex <= fItemCount) {
271224e7c42SIngo Weinhold		if (oldIndex < newIndex - 1) {
272224e7c42SIngo Weinhold			item_t item = fItems[oldIndex];
273224e7c42SIngo Weinhold			_MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1);
274224e7c42SIngo Weinhold			fItems[newIndex] = item;
275224e7c42SIngo Weinhold		} else if (oldIndex > newIndex) {
276224e7c42SIngo Weinhold			item_t item = fItems[oldIndex];
277224e7c42SIngo Weinhold			_MoveItems(fItems + newIndex, 1, oldIndex - newIndex);
278224e7c42SIngo Weinhold			fItems[newIndex] = item;
279224e7c42SIngo Weinhold		}
280224e7c42SIngo Weinhold		return true;
281224e7c42SIngo Weinhold	}
282224e7c42SIngo Weinhold	return false;
283224e7c42SIngo Weinhold}
284224e7c42SIngo Weinhold
285224e7c42SIngo Weinhold// MakeEmpty
286224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
287224e7c42SIngo Weinholdvoid
288224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty()
289224e7c42SIngo Weinhold{
290224e7c42SIngo Weinhold	for (int32 i = 0; i < fItemCount; i++)
291224e7c42SIngo Weinhold		fItems[i].~item_t();
292224e7c42SIngo Weinhold	_Resize(0);
293224e7c42SIngo Weinhold}
294224e7c42SIngo Weinhold
295224e7c42SIngo Weinhold// CountItems
296224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
297224e7c42SIngo Weinholdint32
298224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
299224e7c42SIngo Weinhold{
300224e7c42SIngo Weinhold	return fItemCount;
301224e7c42SIngo Weinhold}
302224e7c42SIngo Weinhold
303224e7c42SIngo Weinhold// IsEmpty
304224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
305224e7c42SIngo Weinholdbool
306224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const
307224e7c42SIngo Weinhold{
308224e7c42SIngo Weinhold	return (fItemCount == 0);
309224e7c42SIngo Weinhold}
310224e7c42SIngo Weinhold
311224e7c42SIngo Weinhold// ItemAt
312224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
313c7a72423SIngo Weinholdconst typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
314224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const
315224e7c42SIngo Weinhold{
316224e7c42SIngo Weinhold	if (index >= 0 && index < fItemCount)
317224e7c42SIngo Weinhold		return fItems[index];
318224e7c42SIngo Weinhold	return sDefaultItem;
319224e7c42SIngo Weinhold}
320224e7c42SIngo Weinhold
321224e7c42SIngo Weinhold// ItemAt
322224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
323c7a72423SIngo Weinholdtypename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
324224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index)
325224e7c42SIngo Weinhold{
326224e7c42SIngo Weinhold	if (index >= 0 && index < fItemCount)
327224e7c42SIngo Weinhold		return fItems[index];
328224e7c42SIngo Weinhold	return sDefaultItem;
329224e7c42SIngo Weinhold}
330224e7c42SIngo Weinhold
331224e7c42SIngo Weinhold// Items
332224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
333c7a72423SIngo Weinholdconst typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
334224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
335224e7c42SIngo Weinhold{
336224e7c42SIngo Weinhold	return fItems;
337224e7c42SIngo Weinhold}
338224e7c42SIngo Weinhold
339224e7c42SIngo Weinhold// IndexOf
340224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
341224e7c42SIngo Weinholdint32
342224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const
343224e7c42SIngo Weinhold{
344224e7c42SIngo Weinhold	for (int32 i = 0; i < fItemCount; i++) {
345224e7c42SIngo Weinhold		if (fItems[i] == item)
346224e7c42SIngo Weinhold			return i;
347224e7c42SIngo Weinhold	}
348224e7c42SIngo Weinhold	return -1;
349224e7c42SIngo Weinhold}
350224e7c42SIngo Weinhold
351224e7c42SIngo Weinhold// HasItem
352224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
353224e7c42SIngo Weinholdbool
354224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
355224e7c42SIngo Weinhold{
356224e7c42SIngo Weinhold	return (IndexOf(item) >= 0);
357224e7c42SIngo Weinhold}
358224e7c42SIngo Weinhold
359224e7c42SIngo Weinhold// _Resize
360224e7c42SIngo Weinholdtemplate<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
361224e7c42SIngo Weinholdbool
362224e7c42SIngo WeinholdList<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count)
363224e7c42SIngo Weinhold{
364224e7c42SIngo Weinhold	bool result = true;
365224e7c42SIngo Weinhold	// calculate the new capacity
366224e7c42SIngo Weinhold	int32 newSize = count;
367224e7c42SIngo Weinhold	if (newSize <= 0)
368224e7c42SIngo Weinhold		newSize = 1;
369224e7c42SIngo Weinhold	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
370224e7c42SIngo Weinhold	// resize if necessary
371224e7c42SIngo Weinhold	if ((size_t)newSize != fCapacity) {
372224e7c42SIngo Weinhold		item_t* newItems
373224e7c42SIngo Weinhold			= (item_t*)realloc(fItems, newSize * sizeof(item_t));
374224e7c42SIngo Weinhold		if (newItems) {
375224e7c42SIngo Weinhold			fItems = newItems;
376224e7c42SIngo Weinhold			fCapacity = newSize;
377224e7c42SIngo Weinhold		} else
378224e7c42SIngo Weinhold			result = false;
379224e7c42SIngo Weinhold	}
380224e7c42SIngo Weinhold	if (result)
381224e7c42SIngo Weinhold		fItemCount = count;
382224e7c42SIngo Weinhold	return result;
383224e7c42SIngo Weinhold}
384224e7c42SIngo Weinhold
385224e7c42SIngo Weinhold#endif	// LIST_H
386