1 /**
2  * Linked list common data structure and intrusive lists
3  *
4  * License:
5  *   This Source Code Form is subject to the terms of
6  *   the Mozilla Public License, v. 2.0. If a copy of
7  *   the MPL was not distributed with this file, You
8  *   can obtain one at http://mozilla.org/MPL/2.0/.
9  *
10  * Authors:
11  *   Vladimir Panteleev <vladimir@thecybershadow.net>
12  */
13 
14 module ae.utils.container.listnode;
15 
16 import ae.utils.meta.reference;
17 
18 struct ListCommon
19 {
20 	mixin template Data(NODEREF, bool HASPREV, bool HASTAIL)
21 	{
22 		// non-copyable because head/tail can go out of sync
23 		// commented-out until AAs can support non-copyable values
24 		//@disable this(this) {}
25 
26 		NODEREF head;
27 		static if (HASTAIL) NODEREF tail;
28 
29 		invariant()
30 		{
31 			static if (HASPREV) if (head) assert(!head.prev);
32 			static if (HASTAIL) if (tail) assert(!tail.next);
33 		}
34 	}
35 
36 	mixin template Impl(NODEREF, bool HASPREV, bool HASTAIL, alias data)
37 	{
38 		void pushFront(NODEREF node)
39 		{
40 			static if (HASPREV) node.prev = null;
41 			node.next = data.head;
42 			static if (HASPREV)
43 				if (data.head)
44 					data.head.prev = node;
45 			data.head = node;
46 			static if (HASTAIL)
47 				if (!data.tail)
48 					data.tail = node;
49 		}
50 
51 		static if (HASTAIL)
52 		void pushBack(NODEREF node)
53 		{
54 			node.next = null;
55 			static if (HASPREV) node.prev = data.tail;
56 			if (data.tail)
57 				data.tail.next = node;
58 			data.tail = node;
59 			if (data.head is null)
60 				data.head = node;
61 		}
62 
63 		static if (HASTAIL)
64 		deprecated alias pushBack add;
65 
66 		NODEREF popFront()
67 		{
68 			assert(data.head);
69 			auto result = data.head;
70 
71 			auto next = data.head.next;
72 			if (next)
73 			{
74 				static if (HASPREV) next.prev = null;
75 			}
76 			else
77 			{
78 				static if (HASTAIL) data.tail = null;
79 			}
80 			data.head = next;
81 			result.next = null;
82 			return result;
83 		}
84 
85 		static if (HASTAIL && HASPREV)
86 		NODEREF popBack()
87 		{
88 			assert(data.tail);
89 			auto result = data.tail;
90 
91 			auto prev = data.tail.prev;
92 			if (prev)
93 				prev.next = null;
94 			else
95 				data.head = null;
96 			data.tail = prev;
97 			result.prev = null;
98 			return result;
99 		}
100 
101 		static if (HASPREV)
102 		void remove(NODEREF node)
103 		{
104 			if (node.prev)
105 				node.prev.next = node.next;
106 			else
107 				data.head = node.next;
108 			if (node.next)
109 				node.next.prev = node.prev;
110 			else
111 				static if (HASTAIL) data.tail = node.prev;
112 			node.next = node.prev = null;
113 		}
114 
115 		static struct Iterator(bool FORWARD)
116 		{
117 			NODEREF cursor;
118 
119 			@property bool empty() { return !cursor; }
120 			@property auto ref front() { return mixin(q{cursor} ~ ITEM_EXPR); }
121 			void popFront()
122 			{
123 				static if (FORWARD)
124 					cursor = cursor.next;
125 				else
126 					cursor = cursor.prev;
127 			}
128 		}
129 
130 		alias Iterator!true ForwardIterator;
131 		import std.range : isInputRange;
132 		static assert(isInputRange!ForwardIterator);
133 
134 		static if (HASPREV)
135 			alias Iterator!false ReverseIterator;
136 
137 		@property auto iterator() { return ForwardIterator(data.head); }
138 		static if (HASPREV && HASTAIL)
139 		@property auto reverseIterator() { return ReverseIterator(data.tail); }
140 
141 		static if (HASPREV)
142 		void remove(I)(I iterator)
143 			if (is(I==ForwardIterator) || is(I==ReverseIterator))
144 		{
145 			return remove(iterator.cursor);
146 		}
147 
148 		int opApply(int delegate(ref typeof(mixin(q{NODEREF.init} ~ ITEM_EXPR))) dg)
149 		{
150 			int res = 0;
151 			for (auto node = data.head; node; node = node.next)
152 			{
153 				res = dg(mixin(q{node} ~ ITEM_EXPR));
154 				if (res)
155 					break;
156 			}
157 			return res;
158 		}
159 
160 		@property bool empty()
161 		{
162 			return data.head is null;
163 		}
164 
165 		@property auto ref front() { return mixin(q{data.head} ~ ITEM_EXPR); }
166 		static if (HASTAIL)
167 		@property auto ref back () { return mixin(q{data.tail} ~ ITEM_EXPR); }
168 	}
169 }
170 
171 /// Mixin containing the linked-list fields.
172 /// When using *ListContainer, inject it into your custom type.
173 mixin template ListLink(bool HASPREV)
174 {
175 	import ae.utils.meta : RefType;
176 	alias RefType!(typeof(this)) NODEREF;
177 	NODEREF next;
178 	static if (HASPREV) NODEREF prev;
179 }
180 
181 mixin template SListLink() { mixin ListLink!false; }
182 mixin template DListLink() { mixin ListLink!true ; }
183 deprecated alias DListLink DListItem;
184 
185 struct ListNode(T, bool HASPREV)
186 {
187 	mixin ListLink!(HASPREV);
188 	T value;
189 	deprecated alias value item;
190 }
191 
192 /// Container for user-specified list nodes.
193 /// Use together with *ListLink.
194 struct ListContainer(Node, bool HASPREV, bool HASTAIL)
195 {
196 	enum ITEM_EXPR = q{};
197 	mixin ListCommon.Data!(RefType!Node, HASPREV, HASTAIL) commonData;
198 	mixin ListCommon.Impl!(RefType!Node, HASPREV, HASTAIL, commonData) commonImpl;
199 }
200 
201 
202 /// *List variations for containers of user linked types.
203 template SListContainer(T)
204 {
205 	alias ListContainer!(T, false, false) SListContainer;
206 }
207 
208 /// ditto
209 template DESListContainer(T)
210 {
211 	alias ListContainer!(T, false, true) DESListContainer;
212 }
213 
214 /// ditto
215 template DListContainer(T)
216 {
217 	alias ListContainer!(T, true, true) DListContainer;
218 }
219 
220 /// ditto
221 template SEDListContainer(T)
222 {
223 	alias ListContainer!(T, true, false) SEDListContainer;
224 }
225 
226 unittest
227 {
228 	class C
229 	{
230 		mixin DListLink;
231 		int x;
232 		this(int p) { x = p; }
233 	}
234 
235 	DListContainer!C l;
236 
237 	auto c1 = new C(1);
238 	l.pushBack(c1);
239 	auto c2 = new C(2);
240 	l.pushBack(c2);
241 	auto c3 = new C(3);
242 	l.pushBack(c3);
243 
244 	l.remove(c2);
245 
246 	int[] a;
247 	foreach (c; l)
248 		a ~= c.x;
249 	assert(a == [1, 3]);
250 
251 	import std.algorithm;
252 	assert(equal(l.iterator.map!(c => c.x)(), [1, 3]));
253 }