ae.utils.container.list source code

1 /**
2  * Linked list containers
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 <ae@cy.md>
12  */
13 
14 module ae.utils.container.list;
15 
16 public import ae.utils.container.listnode;
17 
18 import ae.utils.alloc;
19 
20 /// Organizes a bunch of objects in a linked list.
21 /// Not very efficient for reference types, since it results in two allocations per object.
22 struct ListParts(T, bool HASPREV, bool HASTAIL, alias ALLOCATOR=heapAllocator)
23 {
24 	alias ListNode!(T, HASPREV) Node;
25 	enum ITEM_EXPR = q{.value};
26 
27 	struct Data
28 	{
29 		mixin ListCommon.Data!(Node*, HASPREV, HASTAIL);
30 	}
31 
32 	static template Impl(alias data)
33 	{
34 		mixin ListCommon.Impl!(Node*, HASPREV, HASTAIL, data) common;
35 
36 		Node* pushFront(T v)
37 		{
38 			auto node = ALLOCATOR.allocate!Node();
39 			node.value = v;
40 			common.pushFront(node);
41 			return node;
42 		}
43 
44 		static if (HASTAIL)
45 		Node* pushBack(T v)
46 		{
47 			auto node = ALLOCATOR.allocate!Node();
48 			node.value = v;
49 			common.pushBack(node);
50 			return node;
51 		}
52 
53 		static if (HASTAIL)
54 		deprecated alias pushBack add;
55 
56 		static if (HASPREV)
57 		void remove(Node* node)
58 		{
59 			common.remove(node);
60 			static if (is(typeof(&ALLOCATOR.free)))
61 				ALLOCATOR.free(node);
62 		}
63 	}
64 }
65 
66 alias PartsWrapper!ListParts List;
67 
68 /// Singly-ended singly-linked list. Usable as a stack.
69 template SList(T)
70 {
71 	alias List!(T, false, false) SList;
72 }
73 
74 /// Double-ended singly-linked list. Usable as a stack or queue.
75 template DESList(T)
76 {
77 	alias List!(T, false, true) DESList;
78 }
79 
80 /// Doubly-linked list. Usable as a stack, queue or deque.
81 template DList(T)
82 {
83 	alias List!(T, true, true) DList;
84 }
85 
86 /// Doubly-linked but single-ended list.
87 /// Can't be used as a queue or deque, but supports arbitrary removal.
88 template SEDList(T)
89 {
90 	alias List!(T, true, false) SEDList;
91 }
92 
93 unittest
94 {
95 	DList!int l;
96 	auto i1 = l.pushBack(1);
97 	auto i2 = l.pushBack(2);
98 	auto i3 = l.pushBack(3);
99 	l.remove(i2);
100 
101 	int[] a;
102 	foreach (i; l)
103 		a ~= i;
104 	assert(a == [1, 3]);
105 
106 	import std.algorithm;
107 	assert(equal(l.iterator, [1, 3]));
108 }
109