1224e7c42SIngo Weinhold// SLList.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 SL_LIST_H
29224e7c42SIngo Weinhold#define SL_LIST_H
30224e7c42SIngo Weinhold
31224e7c42SIngo Weinhold#include <new>
32224e7c42SIngo Weinhold
33224e7c42SIngo Weinhold// SLListStandardNode
34224e7c42SIngo Weinholdtemplate<typename Value>
35224e7c42SIngo Weinholdstruct SLListStandardNode {
36224e7c42SIngo Weinhold	SLListStandardNode(const Value &a)
37224e7c42SIngo Weinhold		: value(a),
38224e7c42SIngo Weinhold		  next(NULL)
39224e7c42SIngo Weinhold	{
40224e7c42SIngo Weinhold	}
41224e7c42SIngo Weinhold
42224e7c42SIngo Weinhold	Value						value;
43224e7c42SIngo Weinhold	SLListStandardNode<Value>	*next;
44224e7c42SIngo Weinhold};
45224e7c42SIngo Weinhold
46224e7c42SIngo Weinhold// SLListStandardNodeAllocator
47224e7c42SIngo Weinholdtemplate<typename Value, typename Node>
48224e7c42SIngo Weinholdclass SLListStandardNodeAllocator
49224e7c42SIngo Weinhold{
50224e7c42SIngo Weinholdpublic:
51224e7c42SIngo Weinhold	inline Node *Allocate(const Value &a) const
52224e7c42SIngo Weinhold	{
53224e7c42SIngo Weinhold		return new(nothrow) SLListStandardNode<Value>(a);
54224e7c42SIngo Weinhold	}
55224e7c42SIngo Weinhold
56224e7c42SIngo Weinhold	inline void Free(Node *node) const
57224e7c42SIngo Weinhold	{
58224e7c42SIngo Weinhold		delete node;
59224e7c42SIngo Weinhold	}
60224e7c42SIngo Weinhold};
61224e7c42SIngo Weinhold
62224e7c42SIngo Weinhold// SLListValueNodeAllocator
63224e7c42SIngo Weinholdtemplate<typename Value, typename Node>
64224e7c42SIngo Weinholdclass SLListValueNodeAllocator
65224e7c42SIngo Weinhold{
66224e7c42SIngo Weinholdpublic:
67224e7c42SIngo Weinhold	inline Node *Allocate(const Value &a) const
68224e7c42SIngo Weinhold	{
69224e7c42SIngo Weinhold		return a;
70224e7c42SIngo Weinhold	}
71224e7c42SIngo Weinhold
72224e7c42SIngo Weinhold	inline void Free(Node *node) const
73224e7c42SIngo Weinhold	{
74224e7c42SIngo Weinhold	}
75224e7c42SIngo Weinhold};
76224e7c42SIngo Weinhold
77224e7c42SIngo Weinhold// SLListStandardGetValue
78224e7c42SIngo Weinholdtemplate<typename Value, typename Node>
79224e7c42SIngo Weinholdclass SLListStandardGetValue
80224e7c42SIngo Weinhold{
81224e7c42SIngo Weinholdpublic:
82224e7c42SIngo Weinhold	inline Value &operator()(Node *node) const
83224e7c42SIngo Weinhold	{
84224e7c42SIngo Weinhold		return node->value;
85224e7c42SIngo Weinhold	}
86224e7c42SIngo Weinhold};
87224e7c42SIngo Weinhold
88224e7c42SIngo Weinhold// SLListValueNodeGetValue
89224e7c42SIngo Weinholdtemplate<typename Value, typename Node>
90224e7c42SIngo Weinholdclass SLListValueNodeGetValue
91224e7c42SIngo Weinhold{
92224e7c42SIngo Weinholdpublic:
93224e7c42SIngo Weinhold	inline Value &operator()(Node *node) const
94224e7c42SIngo Weinhold	{
95224e7c42SIngo Weinhold		return *node;
96224e7c42SIngo Weinhold	}
97224e7c42SIngo Weinhold};
98224e7c42SIngo Weinhold
99224e7c42SIngo Weinhold// for convenience
100224e7c42SIngo Weinhold#define SL_LIST_TEMPLATE_LIST template<typename Value, typename Node, \
101224e7c42SIngo Weinhold	typename NodeAllocator, typename GetValue>
102224e7c42SIngo Weinhold#define SL_LIST_CLASS_NAME SLList<Value, Node, NodeAllocator, GetValue>
103224e7c42SIngo Weinhold
104224e7c42SIngo Weinhold// SLList
105224e7c42SIngo Weinholdtemplate<typename Value, typename Node = SLListStandardNode<Value>,
106224e7c42SIngo Weinhold		 typename NodeAllocator = SLListStandardNodeAllocator<Value, Node>,
107224e7c42SIngo Weinhold		 typename GetValue = SLListStandardGetValue<Value, Node> >
108224e7c42SIngo Weinholdclass SLList {
109224e7c42SIngo Weinholdpublic:
110224e7c42SIngo Weinhold	class Iterator;
111224e7c42SIngo Weinhold
112224e7c42SIngo Weinholdpublic:
113224e7c42SIngo Weinhold	SLList();
114224e7c42SIngo Weinhold	SLList(const NodeAllocator &nodeAllocator, const GetValue &getValue);
115224e7c42SIngo Weinhold	~SLList();
116224e7c42SIngo Weinhold
117224e7c42SIngo Weinhold	bool Insert(const Value &value, Iterator *iterator = NULL);
118224e7c42SIngo Weinhold	bool Remove(const Value &value);
119224e7c42SIngo Weinhold	void Remove(Iterator &iterator);
120224e7c42SIngo Weinhold	void RemoveAll();
121224e7c42SIngo Weinhold
122224e7c42SIngo Weinhold	bool Find(const Value &value, Iterator *iterator = NULL) const;
123224e7c42SIngo Weinhold	void GetIterator(Iterator *iterator) const;
124224e7c42SIngo Weinhold
125224e7c42SIngo Weinholdprivate:
126224e7c42SIngo Weinhold	friend class Iterator;
127224e7c42SIngo Weinhold
128224e7c42SIngo Weinhold	Node			*fHead;
129224e7c42SIngo Weinhold	NodeAllocator	fNodeAllocator;
130224e7c42SIngo Weinhold	GetValue		fGetValue;
131224e7c42SIngo Weinhold};
132224e7c42SIngo Weinhold
133224e7c42SIngo Weinhold// Iterator
134224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
135224e7c42SIngo Weinholdclass SL_LIST_CLASS_NAME::Iterator {
136224e7c42SIngo Weinholdpublic:
137224e7c42SIngo Weinhold	Iterator() : fList(NULL), fCurrent(NULL)	{}
138224e7c42SIngo Weinhold	~Iterator()	{}
139224e7c42SIngo Weinhold
140224e7c42SIngo Weinhold	inline Value *GetCurrent()
141224e7c42SIngo Weinhold	{
142224e7c42SIngo Weinhold		return (fList && fCurrent ? &fList->fGetValue(fCurrent) : NULL);
143224e7c42SIngo Weinhold	}
144224e7c42SIngo Weinhold
145224e7c42SIngo Weinhold	inline Value *GetNext()
146224e7c42SIngo Weinhold	{
147224e7c42SIngo Weinhold		if (fCurrent)
148224e7c42SIngo Weinhold			fCurrent = fCurrent->next;
149224e7c42SIngo Weinhold		return GetCurrent();
150224e7c42SIngo Weinhold	}
151224e7c42SIngo Weinhold
152224e7c42SIngo Weinhold	inline void Remove()
153224e7c42SIngo Weinhold	{
154224e7c42SIngo Weinhold		if (fList)
155224e7c42SIngo Weinhold			fList->Remove(*this);
156224e7c42SIngo Weinhold	}
157224e7c42SIngo Weinhold
158224e7c42SIngo Weinholdprivate:
159224e7c42SIngo Weinhold	friend class SL_LIST_CLASS_NAME;
160224e7c42SIngo Weinhold
161224e7c42SIngo Weinhold	inline void _SetTo(SL_LIST_CLASS_NAME *list, Node *previous, Node *node)
162224e7c42SIngo Weinhold	{
163224e7c42SIngo Weinhold		fList = list;
164224e7c42SIngo Weinhold		fPrevious = previous;
165224e7c42SIngo Weinhold		fCurrent = node;
166224e7c42SIngo Weinhold	}
167224e7c42SIngo Weinhold
168224e7c42SIngo Weinhold	inline SL_LIST_CLASS_NAME *_GetList() const	{ return fList; }
169224e7c42SIngo Weinhold	inline Node *_GetPreviousNode() const		{ return fPrevious; }
170224e7c42SIngo Weinhold	inline Node *_GetCurrentNode() const		{ return fCurrent; }
171224e7c42SIngo Weinhold
172224e7c42SIngo Weinholdprivate:
173224e7c42SIngo Weinhold	SL_LIST_CLASS_NAME	*fList;
174224e7c42SIngo Weinhold	Node				*fPrevious;
175224e7c42SIngo Weinhold	Node				*fCurrent;
176224e7c42SIngo Weinhold};
177224e7c42SIngo Weinhold
178224e7c42SIngo Weinhold// constructor
179224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
180224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::SLList()
181224e7c42SIngo Weinhold	: fHead(NULL)/*,
182224e7c42SIngo Weinhold	  fNodeAllocator(),
183224e7c42SIngo Weinhold	  fGetValue()*/
184224e7c42SIngo Weinhold{
185224e7c42SIngo Weinhold}
186224e7c42SIngo Weinhold
187224e7c42SIngo Weinhold// constructor
188224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
189224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::SLList(const NodeAllocator &nodeAllocator,
190224e7c42SIngo Weinhold						   const GetValue &getValue)
191224e7c42SIngo Weinhold	: fHead(NULL),
192224e7c42SIngo Weinhold	  fNodeAllocator(nodeAllocator),
193224e7c42SIngo Weinhold	  fGetValue(getValue)
194224e7c42SIngo Weinhold{
195224e7c42SIngo Weinhold}
196224e7c42SIngo Weinhold
197224e7c42SIngo Weinhold// destructor
198224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
199224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::~SLList()
200224e7c42SIngo Weinhold{
201224e7c42SIngo Weinhold	RemoveAll();
202224e7c42SIngo Weinhold}
203224e7c42SIngo Weinhold
204224e7c42SIngo Weinhold// Insert
205224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
206224e7c42SIngo Weinholdbool
207224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::Insert(const Value &value, Iterator *iterator)
208224e7c42SIngo Weinhold{
209224e7c42SIngo Weinhold	Node *node = fNodeAllocator.Allocate(value);
210224e7c42SIngo Weinhold	if (node) {
211224e7c42SIngo Weinhold		node->next = fHead;
212224e7c42SIngo Weinhold		fHead = node;
213224e7c42SIngo Weinhold		if (iterator)
214224e7c42SIngo Weinhold			iterator->_SetTo(this, NULL, node);
215224e7c42SIngo Weinhold	}
216224e7c42SIngo Weinhold	return node;
217224e7c42SIngo Weinhold}
218224e7c42SIngo Weinhold
219224e7c42SIngo Weinhold// Remove
220224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
221224e7c42SIngo Weinholdbool
222224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::Remove(const Value &value)
223224e7c42SIngo Weinhold{
224224e7c42SIngo Weinhold	Iterator iterator;
225224e7c42SIngo Weinhold	bool result = Find(value, &iterator);
226224e7c42SIngo Weinhold	if (result)
227224e7c42SIngo Weinhold		iterator.Remove();
228224e7c42SIngo Weinhold	return result;
229224e7c42SIngo Weinhold}
230224e7c42SIngo Weinhold
231224e7c42SIngo Weinhold// Remove
232224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
233224e7c42SIngo Weinholdvoid
234224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::Remove(Iterator &iterator)
235224e7c42SIngo Weinhold{
236224e7c42SIngo Weinhold	Node *node = iterator._GetCurrentNode();
237224e7c42SIngo Weinhold	if (iterator._GetList() == this && node) {
238224e7c42SIngo Weinhold		Node *previous = iterator._GetPreviousNode();
239224e7c42SIngo Weinhold		iterator._SetTo(this, previous, node->next);
240224e7c42SIngo Weinhold		if (previous)
241224e7c42SIngo Weinhold			previous->next = node->next;
242224e7c42SIngo Weinhold		else
243224e7c42SIngo Weinhold			fHead = node->next;
244224e7c42SIngo Weinhold		fNodeAllocator.Free(node);
245224e7c42SIngo Weinhold	}
246224e7c42SIngo Weinhold}
247224e7c42SIngo Weinhold
248224e7c42SIngo Weinhold// RemoveAll
249224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
250224e7c42SIngo Weinholdvoid
251224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::RemoveAll()
252224e7c42SIngo Weinhold{
253224e7c42SIngo Weinhold	for (Node *node = fHead; node; ) {
254224e7c42SIngo Weinhold		Node *next = node->next;
255224e7c42SIngo Weinhold		fNodeAllocator.Free(node);
256224e7c42SIngo Weinhold		node = next;
257224e7c42SIngo Weinhold	}
258224e7c42SIngo Weinhold	fHead = NULL;
259224e7c42SIngo Weinhold}
260224e7c42SIngo Weinhold
261224e7c42SIngo Weinhold// Find
262224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
263224e7c42SIngo Weinholdbool
264224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::Find(const Value &value, Iterator *iterator) const
265224e7c42SIngo Weinhold{
266224e7c42SIngo Weinhold	Node *node = fHead;
267224e7c42SIngo Weinhold	Node *previous = NULL;
268224e7c42SIngo Weinhold	while (node && fGetValue(node) != value) {
269224e7c42SIngo Weinhold		previous = node;
270224e7c42SIngo Weinhold		node = node->next;
271224e7c42SIngo Weinhold	}
272224e7c42SIngo Weinhold	if (node && iterator) {
273224e7c42SIngo Weinhold		iterator->_SetTo(const_cast<SL_LIST_CLASS_NAME*>(this), previous,
274224e7c42SIngo Weinhold						 node);
275224e7c42SIngo Weinhold	}
276224e7c42SIngo Weinhold	return node;
277224e7c42SIngo Weinhold}
278224e7c42SIngo Weinhold
279224e7c42SIngo Weinhold// GetIterator
280224e7c42SIngo WeinholdSL_LIST_TEMPLATE_LIST
281224e7c42SIngo Weinholdvoid
282224e7c42SIngo WeinholdSL_LIST_CLASS_NAME::GetIterator(Iterator *iterator) const
283224e7c42SIngo Weinhold{
284224e7c42SIngo Weinhold	if (iterator)
285224e7c42SIngo Weinhold		iterator->_SetTo(const_cast<SL_LIST_CLASS_NAME*>(this), NULL, fHead);
286224e7c42SIngo Weinhold}
287224e7c42SIngo Weinhold
288224e7c42SIngo Weinhold#endif	// SL_LIST_H
289