|
40
|
1 module doodle.containers.list;
|
|
|
2
|
|
|
3 ///
|
|
|
4 /// Doubly-linked list.
|
|
|
5 /// Consists of a sequence of cells with references to the previous and next member.
|
|
|
6 /// List keeps track of its length.
|
|
|
7 ///
|
|
|
8 /// The list has two ends:
|
|
|
9 /// "head" and "tail".
|
|
|
10 /// There are two directions:
|
|
|
11 /// "forwards" -> towards the "head" and
|
|
|
12 /// "backwards" -> towards the "tail"
|
|
|
13 /// opApply works from the head to the tail.
|
|
|
14 /// opApplyReverse works from the tail to the head.
|
|
|
15 ///
|
|
|
16 /// When used as a queue, typically use addTail and removeHead.
|
|
|
17 ///
|
|
|
18 /// Design goals of list is to be completely symmetric and clear in its
|
|
|
19 /// forwards and backwards operations, and to be able to contain immutable types.
|
|
|
20 ///
|
|
|
21 class List(T) {
|
|
|
22
|
|
|
23 //
|
|
|
24 // Standard operations:
|
|
|
25 //
|
|
|
26
|
|
|
27 /// Construct an empty list
|
|
|
28 this() { }
|
|
|
29
|
|
|
30 /// Return a copy of the list
|
|
|
31 List!(T) dup() const {
|
|
|
32 auto l = new List!(T);
|
|
|
33 for (auto c = &mHead; c; c = &c.mBackward) {
|
|
|
34 l.addTail(c.mElement);
|
|
|
35 }
|
|
|
36 return l;
|
|
|
37 }
|
|
|
38
|
|
|
39 /// Return true if the list is empty
|
|
|
40 bool isEmpty() const {
|
|
|
41 return mLength == 0;
|
|
|
42 }
|
|
|
43
|
|
|
44 /// Return the length of the list
|
|
|
45 uint length() const {
|
|
|
46 return mLength;
|
|
|
47 }
|
|
|
48
|
|
|
49 /// Return the head of the list, asserting if the list is empty
|
|
|
50 T head() {
|
|
|
51 assert(!isEmpty());
|
|
|
52 return mHead.mElement;
|
|
|
53 }
|
|
|
54
|
|
|
55 /// Return the tail of the list, asserting if the list is empty
|
|
|
56 T tail() {
|
|
|
57 assert(!isEmpty());
|
|
|
58 return mTail.mElement;
|
|
|
59 }
|
|
|
60
|
|
|
61 /// Add to the head of the list
|
|
|
62 void addHead(T t) {
|
|
|
63 add(mHead, null, t);
|
|
|
64 }
|
|
|
65
|
|
|
66 /// Add to the tail of the list
|
|
|
67 void addTail(T t) {
|
|
|
68 add(null, mTail, t);
|
|
|
69 }
|
|
|
70
|
|
|
71 /// Remove the head of the list, asserting if the list is empty
|
|
|
72 T removeHead() {
|
|
|
73 return remove(mHead).mElement;
|
|
|
74 }
|
|
|
75
|
|
|
76 /// Remove the tail of the list, asserting of the list is empty
|
|
|
77 T removeTail() {
|
|
|
78 return remove(mTail).mElement;
|
|
|
79 }
|
|
|
80
|
|
|
81 // Clear the list (garbage collector does the rest)
|
|
|
82 void clear() {
|
|
|
83 mHead = mTail = null;
|
|
|
84 mLength = 0;
|
|
|
85 }
|
|
|
86
|
|
|
87 /// Iterate over the list from head to tail - used by foreach
|
|
|
88 int opApply(int delegate(ref T) dg) {
|
|
|
89 int result;
|
|
|
90
|
|
|
91 auto c = mHead;
|
|
|
92
|
|
|
93 while (c !is null) {
|
|
|
94 auto t = c.mElement;
|
|
|
95 result = dg(t);
|
|
|
96 if (result != 0) {
|
|
|
97 break;
|
|
|
98 }
|
|
|
99 c = c.mBackward;
|
|
|
100 }
|
|
|
101
|
|
|
102 return result;
|
|
|
103 }
|
|
|
104
|
|
|
105 /// Iterate over the list from tail to head - used by foreach_reverse
|
|
|
106 int opApplyReverse(int delegate(ref T) dg) {
|
|
|
107 int result;
|
|
|
108
|
|
|
109 auto c = mTail;
|
|
|
110
|
|
|
111 while (c !is null) {
|
|
|
112 auto t = c.mElement;
|
|
|
113 result = dg(t);
|
|
|
114 if (result != 0) {
|
|
|
115 break;
|
|
|
116 }
|
|
|
117 c = c.mForward;
|
|
|
118 }
|
|
|
119
|
|
|
120 return result;
|
|
|
121 }
|
|
|
122
|
|
|
123
|
|
|
124 //
|
|
|
125 // Iterator operations:
|
|
|
126 //
|
|
|
127
|
|
|
128 /// Return the first matching element going backward from head, or null
|
|
|
129 Iterator findHead(T t) {
|
|
|
130 for (auto c = mHead; c !is null; c = c.mBackward) {
|
|
|
131 if (c.mElement == t) {
|
|
|
132 return new Iterator(c);
|
|
|
133 }
|
|
|
134 }
|
|
|
135
|
|
|
136 return null;
|
|
|
137 }
|
|
|
138
|
|
|
139 /// Return the first matching element going forward from tail, or null
|
|
|
140 Iterator findTail(T t) {
|
|
|
141 for (auto c = mTail; c !is null; c = c.mForward) {
|
|
|
142 if (c.mElement == t) {
|
|
|
143 return new Iterator(c);
|
|
|
144 }
|
|
|
145 }
|
|
|
146
|
|
|
147 return null;
|
|
|
148 }
|
|
|
149
|
|
|
150 /// insert a new entry into list, forward of entry specified by iterator
|
|
|
151 void insertForward(Iterator i, T t) {
|
|
|
152 assert(i !is null);
|
|
|
153 add(i.mCell, i.mCell.mForward, t);
|
|
|
154 }
|
|
|
155
|
|
|
156 /// insert a new entry into list, backward of entry specified by iterator
|
|
|
157 void insertBackward(Iterator i, T t) {
|
|
|
158 assert(i !is null);
|
|
|
159 add(i.mCell.mBackward, i.mCell, t);
|
|
|
160 }
|
|
|
161
|
|
|
162 /// Remove specified entry from list, returning iterator to entry forward of removed one
|
|
|
163 Iterator eraseForward(Iterator i) {
|
|
|
164 assert(i !is null);
|
|
|
165 Cell cell = remove(i.mCell);
|
|
|
166 return cell.mForward ? new Iterator(cell.mForward) : null;
|
|
|
167 }
|
|
|
168
|
|
|
169 /// Remove specified entry from list, returning iterator to entry backward of removed one
|
|
|
170 Iterator eraseBackward(Iterator i) {
|
|
|
171 assert(i !is null);
|
|
|
172 Cell cell = remove(i.mCell);
|
|
|
173 return cell.mBackward ? new Iterator(cell.mBackward) : null;
|
|
|
174 }
|
|
|
175
|
|
|
176 ///
|
|
|
177 /// Iterator for a List
|
|
|
178 ///
|
|
|
179 class Iterator {
|
|
|
180
|
|
|
181 private Cell mCell;
|
|
|
182
|
|
|
183 private this(Cell cell) {
|
|
|
184 assert(cell !is null);
|
|
|
185 mCell = cell;
|
|
|
186 }
|
|
|
187
|
|
|
188 T element() {
|
|
|
189 return mCell.mElement;
|
|
|
190 }
|
|
|
191
|
|
|
192 void goForward() {
|
|
|
193 assert(mCell.mForward !is null);
|
|
|
194 mCell = mCell.mForward;
|
|
|
195 }
|
|
|
196
|
|
|
197 void goBackward() {
|
|
|
198 assert(mCell.mBackward !is null);
|
|
|
199 mCell = mCell.mBackward;
|
|
|
200 }
|
|
|
201
|
|
|
202 bool forwardValid() const {
|
|
|
203 return mCell.mForward !is null;
|
|
|
204 }
|
|
|
205
|
|
|
206 bool backwardValid() const {
|
|
|
207 return mCell.mBackward !is null;
|
|
|
208 }
|
|
|
209
|
|
|
210 override bool opEquals(Object other) const {
|
|
|
211 Iterator o = cast(Iterator) other;
|
|
|
212 if (!o) return 0;
|
|
|
213 return mCell is o.mCell;
|
|
|
214 }
|
|
|
215 }
|
|
|
216
|
|
|
217 //
|
|
|
218 // Implementation:
|
|
|
219 //
|
|
|
220
|
|
|
221 private {
|
|
|
222 Cell mHead;
|
|
|
223 Cell mTail;
|
|
|
224 uint mLength;
|
|
|
225
|
|
|
226 /// An entry in the list
|
|
|
227 class Cell {
|
|
|
228 Cell mForward, mBackward;
|
|
|
229 T mElement;
|
|
|
230
|
|
|
231 this(T element, Cell backward, Cell forward) {
|
|
|
232 mElement = element;
|
|
|
233 mBackward = backward;
|
|
|
234 mForward = forward;
|
|
|
235 }
|
|
|
236 }
|
|
|
237
|
|
|
238 /// Add new cell between backward and forward
|
|
|
239 void add(Cell backward, Cell forward, T t) {
|
|
|
240 Cell cell = new Cell(t, backward, forward);
|
|
|
241
|
|
|
242 if (backward) {
|
|
|
243 backward.mForward = cell;
|
|
|
244 }
|
|
|
245 else {
|
|
|
246 mTail = cell;
|
|
|
247 }
|
|
|
248
|
|
|
249 if (forward) {
|
|
|
250 forward.mBackward = cell;
|
|
|
251 }
|
|
|
252 else {
|
|
|
253 mHead = cell;
|
|
|
254 }
|
|
|
255
|
|
|
256 ++mLength;
|
|
|
257 }
|
|
|
258
|
|
|
259 /// Remove a cell from the list, returning the removed cell
|
|
|
260 Cell remove(Cell cell) {
|
|
|
261 if (cell.mBackward) {
|
|
|
262 cell.mBackward.mForward = cell.mForward;
|
|
|
263 }
|
|
|
264 else {
|
|
|
265 mTail = cell.mForward;
|
|
|
266 }
|
|
|
267
|
|
|
268 if (cell.mForward) {
|
|
|
269 cell.mForward.mBackward = cell.mBackward;
|
|
|
270 }
|
|
|
271 else {
|
|
|
272 mHead = cell.mBackward;
|
|
|
273 }
|
|
|
274
|
|
|
275 --mLength;
|
|
|
276
|
|
|
277 return cell;
|
|
|
278 }
|
|
|
279 }
|
|
|
280 }
|
