1// SLList.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 SL_LIST_H
29#define SL_LIST_H
30
31#include <new>
32
33// SLListStandardNode
34template<typename Value>
35struct SLListStandardNode {
36	SLListStandardNode(const Value &a)
37		: value(a),
38		  next(NULL)
39	{
40	}
41
42	Value						value;
43	SLListStandardNode<Value>	*next;
44};
45
46// SLListStandardNodeAllocator
47template<typename Value, typename Node>
48class SLListStandardNodeAllocator
49{
50public:
51	inline Node *Allocate(const Value &a) const
52	{
53		return new(nothrow) SLListStandardNode<Value>(a);
54	}
55
56	inline void Free(Node *node) const
57	{
58		delete node;
59	}
60};
61
62// SLListValueNodeAllocator
63template<typename Value, typename Node>
64class SLListValueNodeAllocator
65{
66public:
67	inline Node *Allocate(const Value &a) const
68	{
69		return a;
70	}
71
72	inline void Free(Node *node) const
73	{
74	}
75};
76
77// SLListStandardGetValue
78template<typename Value, typename Node>
79class SLListStandardGetValue
80{
81public:
82	inline Value &operator()(Node *node) const
83	{
84		return node->value;
85	}
86};
87
88// SLListValueNodeGetValue
89template<typename Value, typename Node>
90class SLListValueNodeGetValue
91{
92public:
93	inline Value &operator()(Node *node) const
94	{
95		return *node;
96	}
97};
98
99// for convenience
100#define SL_LIST_TEMPLATE_LIST template<typename Value, typename Node, \
101	typename NodeAllocator, typename GetValue>
102#define SL_LIST_CLASS_NAME SLList<Value, Node, NodeAllocator, GetValue>
103
104// SLList
105template<typename Value, typename Node = SLListStandardNode<Value>,
106		 typename NodeAllocator = SLListStandardNodeAllocator<Value, Node>,
107		 typename GetValue = SLListStandardGetValue<Value, Node> >
108class SLList {
109public:
110	class Iterator;
111
112public:
113	SLList();
114	SLList(const NodeAllocator &nodeAllocator, const GetValue &getValue);
115	~SLList();
116
117	bool Insert(const Value &value, Iterator *iterator = NULL);
118	bool Remove(const Value &value);
119	void Remove(Iterator &iterator);
120	void RemoveAll();
121
122	bool Find(const Value &value, Iterator *iterator = NULL) const;
123	void GetIterator(Iterator *iterator) const;
124
125private:
126	friend class Iterator;
127
128	Node			*fHead;
129	NodeAllocator	fNodeAllocator;
130	GetValue		fGetValue;
131};
132
133// Iterator
134SL_LIST_TEMPLATE_LIST
135class SL_LIST_CLASS_NAME::Iterator {
136public:
137	Iterator() : fList(NULL), fCurrent(NULL)	{}
138	~Iterator()	{}
139
140	inline Value *GetCurrent()
141	{
142		return (fList && fCurrent ? &fList->fGetValue(fCurrent) : NULL);
143	}
144
145	inline Value *GetNext()
146	{
147		if (fCurrent)
148			fCurrent = fCurrent->next;
149		return GetCurrent();
150	}
151
152	inline void Remove()
153	{
154		if (fList)
155			fList->Remove(*this);
156	}
157
158private:
159	friend class SL_LIST_CLASS_NAME;
160
161	inline void _SetTo(SL_LIST_CLASS_NAME *list, Node *previous, Node *node)
162	{
163		fList = list;
164		fPrevious = previous;
165		fCurrent = node;
166	}
167
168	inline SL_LIST_CLASS_NAME *_GetList() const	{ return fList; }
169	inline Node *_GetPreviousNode() const		{ return fPrevious; }
170	inline Node *_GetCurrentNode() const		{ return fCurrent; }
171
172private:
173	SL_LIST_CLASS_NAME	*fList;
174	Node				*fPrevious;
175	Node				*fCurrent;
176};
177
178// constructor
179SL_LIST_TEMPLATE_LIST
180SL_LIST_CLASS_NAME::SLList()
181	: fHead(NULL)/*,
182	  fNodeAllocator(),
183	  fGetValue()*/
184{
185}
186
187// constructor
188SL_LIST_TEMPLATE_LIST
189SL_LIST_CLASS_NAME::SLList(const NodeAllocator &nodeAllocator,
190						   const GetValue &getValue)
191	: fHead(NULL),
192	  fNodeAllocator(nodeAllocator),
193	  fGetValue(getValue)
194{
195}
196
197// destructor
198SL_LIST_TEMPLATE_LIST
199SL_LIST_CLASS_NAME::~SLList()
200{
201	RemoveAll();
202}
203
204// Insert
205SL_LIST_TEMPLATE_LIST
206bool
207SL_LIST_CLASS_NAME::Insert(const Value &value, Iterator *iterator)
208{
209	Node *node = fNodeAllocator.Allocate(value);
210	if (node) {
211		node->next = fHead;
212		fHead = node;
213		if (iterator)
214			iterator->_SetTo(this, NULL, node);
215	}
216	return node;
217}
218
219// Remove
220SL_LIST_TEMPLATE_LIST
221bool
222SL_LIST_CLASS_NAME::Remove(const Value &value)
223{
224	Iterator iterator;
225	bool result = Find(value, &iterator);
226	if (result)
227		iterator.Remove();
228	return result;
229}
230
231// Remove
232SL_LIST_TEMPLATE_LIST
233void
234SL_LIST_CLASS_NAME::Remove(Iterator &iterator)
235{
236	Node *node = iterator._GetCurrentNode();
237	if (iterator._GetList() == this && node) {
238		Node *previous = iterator._GetPreviousNode();
239		iterator._SetTo(this, previous, node->next);
240		if (previous)
241			previous->next = node->next;
242		else
243			fHead = node->next;
244		fNodeAllocator.Free(node);
245	}
246}
247
248// RemoveAll
249SL_LIST_TEMPLATE_LIST
250void
251SL_LIST_CLASS_NAME::RemoveAll()
252{
253	for (Node *node = fHead; node; ) {
254		Node *next = node->next;
255		fNodeAllocator.Free(node);
256		node = next;
257	}
258	fHead = NULL;
259}
260
261// Find
262SL_LIST_TEMPLATE_LIST
263bool
264SL_LIST_CLASS_NAME::Find(const Value &value, Iterator *iterator) const
265{
266	Node *node = fHead;
267	Node *previous = NULL;
268	while (node && fGetValue(node) != value) {
269		previous = node;
270		node = node->next;
271	}
272	if (node && iterator) {
273		iterator->_SetTo(const_cast<SL_LIST_CLASS_NAME*>(this), previous,
274						 node);
275	}
276	return node;
277}
278
279// GetIterator
280SL_LIST_TEMPLATE_LIST
281void
282SL_LIST_CLASS_NAME::GetIterator(Iterator *iterator) const
283{
284	if (iterator)
285		iterator->_SetTo(const_cast<SL_LIST_CLASS_NAME*>(this), NULL, fHead);
286}
287
288#endif	// SL_LIST_H
289