1/*
2 * Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
3 * Copyright 2005-2006, Ingo Weinhold, bonefish@users.sf.net. All rights reserved.
4 *
5 * Distributed under the terms of the MIT License.
6 */
7#ifndef KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
8#define KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
9
10
11#include <util/DoublyLinkedList.h>
12
13
14/*!
15	A doubly linked queue is like a doubly linked list, but only has a pointer
16	to the head of the list, none to its tail.
17*/
18
19
20#ifdef __cplusplus
21
22// for convenience
23#define DOUBLY_LINKED_QUEUE_CLASS_NAME DoublyLinkedQueue<Element, GetLink>
24
25
26template<typename Element,
27	typename GetLink = DoublyLinkedListStandardGetLink<Element> >
28class DoublyLinkedQueue {
29	private:
30		typedef DoublyLinkedQueue<Element, GetLink>	Queue;
31		typedef DoublyLinkedListLink<Element>		Link;
32
33	public:
34		class Iterator {
35			public:
36				Iterator(Queue *queue)
37					:
38					fQueue(queue)
39				{
40					Rewind();
41				}
42
43				Iterator(const Iterator &other)
44				{
45					*this = other;
46				}
47
48				bool HasNext() const
49				{
50					return fNext;
51				}
52
53				Element *Next()
54				{
55					fCurrent = fNext;
56					if (fNext)
57						fNext = fQueue->GetNext(fNext);
58					return fCurrent;
59				}
60
61				Element *Remove()
62				{
63					Element *element = fCurrent;
64					if (fCurrent) {
65						fQueue->Remove(fCurrent);
66						fCurrent = NULL;
67					}
68					return element;
69				}
70
71				Iterator &operator=(const Iterator &other)
72				{
73					fQueue = other.fQueue;
74					fCurrent = other.fCurrent;
75					fNext = other.fNext;
76					return *this;
77				}
78
79				void Rewind()
80				{
81					fCurrent = NULL;
82					fNext = fQueue->First();
83				}
84
85			private:
86				Queue	*fQueue;
87				Element	*fCurrent;
88				Element	*fNext;
89		};
90
91		class ConstIterator {
92			public:
93				ConstIterator(const Queue *queue)
94					:
95					fQueue(queue)
96				{
97					Rewind();
98				}
99
100				ConstIterator(const ConstIterator &other)
101				{
102					*this = other;
103				}
104
105				bool HasNext() const
106				{
107					return fNext;
108				}
109
110				Element *Next()
111				{
112					Element *element = fNext;
113					if (fNext)
114						fNext = fQueue->GetNext(fNext);
115					return element;
116				}
117
118				ConstIterator &operator=(const ConstIterator &other)
119				{
120					fQueue = other.fQueue;
121					fNext = other.fNext;
122					return *this;
123				}
124
125				void Rewind()
126				{
127					fNext = fQueue->First();
128				}
129
130			private:
131				const Queue	*fQueue;
132				Element		*fNext;
133		};
134
135	public:
136		DoublyLinkedQueue() : fFirst(NULL) {}
137		~DoublyLinkedQueue() {}
138
139		inline bool IsEmpty() const		{ return (fFirst == NULL); }
140
141		inline void Insert(Element *element);
142		inline void Insert(Element *before, Element *element);
143		inline void Add(Element *element);
144		inline void Remove(Element *element);
145
146		inline void Swap(Element *a, Element *b);
147
148		inline void MoveFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList);
149
150		inline void RemoveAll();
151		inline void MakeEmpty()			{ RemoveAll(); }
152
153		inline Element *First() const	{ return fFirst; }
154		inline Element *Head() const	{ return fFirst; }
155
156		inline Element *RemoveHead();
157
158		inline Element *GetPrevious(Element *element) const;
159		inline Element *GetNext(Element *element) const;
160
161		inline int32 Size() const;
162			// O(n)!
163
164		inline Iterator GetIterator()				{ return Iterator(this); }
165		inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
166
167	private:
168		Element	*fFirst;
169
170		static GetLink	sGetLink;
171};
172
173
174// inline methods
175
176// Insert
177DOUBLY_LINKED_LIST_TEMPLATE_LIST
178void
179DOUBLY_LINKED_QUEUE_CLASS_NAME::Insert(Element *element)
180{
181	if (element) {
182		Link *elLink = sGetLink(element);
183		elLink->previous = NULL;
184		elLink->next = fFirst;
185		if (fFirst)
186			sGetLink(fFirst)->previous = element;
187		fFirst = element;
188	}
189}
190
191// Insert
192DOUBLY_LINKED_LIST_TEMPLATE_LIST
193void
194DOUBLY_LINKED_QUEUE_CLASS_NAME::Insert(Element *before, Element *element)
195{
196	if (before == NULL) {
197		Insert(element);
198		return;
199	}
200	if (element == NULL)
201		return;
202
203	Link *beforeLink = sGetLink(before);
204	Link *link = sGetLink(element);
205
206	link->next = before;
207	link->previous = beforeLink->previous;
208	if (link->previous != NULL)
209		sGetLink(link->previous)->next = element;
210	beforeLink->previous = element;
211
212	if (fFirst == before)
213		fFirst = element;
214}
215
216// Add
217DOUBLY_LINKED_LIST_TEMPLATE_LIST
218void
219DOUBLY_LINKED_QUEUE_CLASS_NAME::Add(Element *element)
220{
221	Insert(element);
222}
223
224// Remove
225DOUBLY_LINKED_LIST_TEMPLATE_LIST
226void
227DOUBLY_LINKED_QUEUE_CLASS_NAME::Remove(Element *element)
228{
229	if (element) {
230		Link *elLink = sGetLink(element);
231		if (elLink->previous)
232			sGetLink(elLink->previous)->next = elLink->next;
233		else
234			fFirst = elLink->next;
235		if (elLink->next)
236			sGetLink(elLink->next)->previous = elLink->previous;
237
238		elLink->previous = NULL;
239		elLink->next = NULL;
240	}
241}
242
243// Swap
244DOUBLY_LINKED_LIST_TEMPLATE_LIST
245void
246DOUBLY_LINKED_QUEUE_CLASS_NAME::Swap(Element *a, Element *b)
247{
248	if (a && b && a != b) {
249		Link *aLink = sGetLink(a);
250		Link *bLink = sGetLink(b);
251		Element *aPrev = aLink->previous;
252		Element *bPrev = bLink->previous;
253		Element *aNext = aLink->next;
254		Element *bNext = bLink->next;
255		// place a
256		if (bPrev)
257			sGetLink(bPrev)->next = a;
258		else
259			fFirst = a;
260		if (bNext)
261			sGetLink(bNext)->previous = a;
262
263		aLink->previous = bPrev;
264		aLink->next = bNext;
265		// place b
266		if (aPrev)
267			sGetLink(aPrev)->next = b;
268		else
269			fFirst = b;
270		if (aNext)
271			sGetLink(aNext)->previous = b;
272
273		bLink->previous = aPrev;
274		bLink->next = aNext;
275	}
276}
277
278// MoveFrom
279DOUBLY_LINKED_LIST_TEMPLATE_LIST
280void
281DOUBLY_LINKED_QUEUE_CLASS_NAME::MoveFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList)
282{
283	if (fromList && fromList->fFirst) {
284		if (fFirst) {
285			Element *element = fFirst;
286			Link *elLink;
287			while ((elLink = sGetLink(element))->next) {
288				element = elLink->next;
289			}
290			elLink->next = fromList->fFirst;
291		} else {
292			fFirst = fromList->fFirst;
293		}
294		fromList->fFirst = NULL;
295	}
296}
297
298// RemoveAll
299DOUBLY_LINKED_LIST_TEMPLATE_LIST
300void
301DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveAll()
302{
303	Element *element = fFirst;
304	while (element) {
305		Link *elLink = sGetLink(element);
306		element = elLink->next;
307		elLink->previous = NULL;
308		elLink->next = NULL;
309	}
310	fFirst = NULL;
311}
312
313// RemoveHead
314DOUBLY_LINKED_LIST_TEMPLATE_LIST
315Element *
316DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveHead()
317{
318	Element *element = Head();
319	Remove(element);
320	return element;
321}
322
323// GetPrevious
324DOUBLY_LINKED_LIST_TEMPLATE_LIST
325Element *
326DOUBLY_LINKED_QUEUE_CLASS_NAME::GetPrevious(Element *element) const
327{
328	Element *result = NULL;
329	if (element)
330		result = sGetLink(element)->previous;
331	return result;
332}
333
334// GetNext
335DOUBLY_LINKED_LIST_TEMPLATE_LIST
336Element *
337DOUBLY_LINKED_QUEUE_CLASS_NAME::GetNext(Element *element) const
338{
339	Element *result = NULL;
340	if (element)
341		result = sGetLink(element)->next;
342	return result;
343}
344
345// Size
346DOUBLY_LINKED_LIST_TEMPLATE_LIST
347int32
348DOUBLY_LINKED_QUEUE_CLASS_NAME::Size() const
349{
350	int32 count = 0;
351	for (Element* element = First(); element; element = GetNext(element))
352		count++;
353	return count;
354}
355
356// sGetLink
357DOUBLY_LINKED_LIST_TEMPLATE_LIST
358GetLink DOUBLY_LINKED_QUEUE_CLASS_NAME::sGetLink;
359
360#endif	/* __cplusplus */
361
362#endif	// _KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
363