1
2
3
4
5
6 using System;
7 using System.Concepts;
8
9 namespace System.Collections
10 {
11 public class LinkedListNode<T>
12 {
13 public typedef T ValueType;
14
15 public LinkedListNode(const ValueType& value_, LinkedListNode<T>* prev_, LinkedListNode<T>* next_) : value(value_), prev(prev_), next(next_)
16 {
17 }
18 public LinkedListNode(ValueType&& value_, LinkedListNode<T>* prev_, LinkedListNode<T>* next_) : value(value_), prev(prev_), next(next_)
19 {
20 }
21 public inline const ValueType& Value() const
22 {
23 return value;
24 }
25 public inline ValueType& Value()
26 {
27 return value;
28 }
29 public inline LinkedListNode<T>* Prev() const
30 {
31 return prev;
32 }
33 public inline void SetPrev(LinkedListNode<T>* prev_)
34 {
35 prev = prev_;
36 }
37 public inline LinkedListNode<T>* Next() const
38 {
39 return next;
40 }
41 public inline void SetNext(LinkedListNode<T>* next_)
42 {
43 next = next_;
44 }
45 private ValueType value;
46 private LinkedListNode<T>* prev;
47 private LinkedListNode<T>* next;
48 }
49
50 public class LinkedListNodeIterator<T, R, P>
51 {
52 public typedef T ValueType;
53 public typedef R ReferenceType;
54 public typedef P PointerType;
55 private typedef LinkedListNodeIterator<ValueType, ReferenceType, PointerType> Self;
56
57 public LinkedListNodeIterator() : list(null), node(null)
58 {
59 }
60 public LinkedListNodeIterator(LinkedList<ValueType>* list_, LinkedListNode<ValueType>* node_) : list(list_), node(node_)
61 {
62 }
63 public inline ReferenceType operator*()
64 {
65 #assert(node != null);
66 return node->Value();
67 }
68 public inline PointerType operator->()
69 {
70 #assert(node != null);
71 return &(node->Value());
72 }
73 public inline Self& operator++()
74 {
75 #assert(node != null);
76 node = node->Next();
77 return *this;
78 }
79 public inline Self& operator--()
80 {
81 if (node == null)
82 {
83 #assert(list != null);
84 node = list->Tail();
85 }
86 else
87 {
88 node = node->Prev();
89 }
90 return *this;
91 }
92 public inline LinkedListNode<ValueType>* Node() const
93 {
94 return node;
95 }
96 private LinkedList<ValueType>* list;
97 private LinkedListNode<ValueType>* node;
98 }
99
100 public inline bool operator==<T, R, P>(const LinkedListNodeIterator<T, R, P>& left, const LinkedListNodeIterator<T, R, P>& right)
101 {
102 return left.Node() == right.Node();
103 }
104
105 public class LinkedList<T> where T is Regular
106 {
107 public typedef T ValueType;
108 public typedef LinkedListNodeIterator<ValueType, ValueType&, ValueType*> Iterator;
109 public typedef LinkedListNodeIterator<ValueType, const ValueType&, const ValueType*> ConstIterator;
110
111 public LinkedList() : head(null), tail(null), count(0)
112 {
113 }
114 public LinkedList(const LinkedList<ValueType>& that) : head(null), tail(null), count(0)
115 {
116 CopyFrom(that);
117 }
118 public LinkedList(LinkedList<ValueType>&& that) : head(that.head), tail(that.tail), count(that.count)
119 {
120 that.head = null;
121 that.tail = null;
122 that.count = 0;
123 }
124 public void operator=(const LinkedList<ValueType>& that)
125 {
126 Clear();
127 CopyFrom(that);
128 }
129 public void operator=(LinkedList<ValueType>&& that)
130 {
131 Swap(head, that.head);
132 Swap(tail, that.tail);
133 Swap(count, that.count);
134 }
135 public ~LinkedList()
136 {
137 Clear();
138 }
139 public inline Iterator Begin()
140 {
141 return Iterator(this, head);
142 }
143 public inline ConstIterator Begin() const
144 {
145 return ConstIterator(this, head);
146 }
147 public inline ConstIterator CBegin() const
148 {
149 return ConstIterator(this, head);
150 }
151 public inline Iterator End()
152 {
153 return Iterator(this, null);
154 }
155 public inline ConstIterator End() const
156 {
157 return ConstIterator(this, null);
158 }
159 public inline ConstIterator CEnd() const
160 {
161 return ConstIterator(this, null);
162 }
163 public inline long Count() const
164 {
165 return count;
166 }
167 public inline bool IsEmpty() const
168 {
169 return count == 0;
170 }
171 public void Clear()
172 {
173 LinkedListNode<ValueType>* n = head;
174 while (n != null)
175 {
176 LinkedListNode<ValueType>* next = n->Next();
177 delete n;
178 n = next;
179 }
180 head = null;
181 tail = null;
182 count = 0;
183 }
184 public Iterator InsertFront(const ValueType& value)
185 {
186 if (head == null)
187 {
188 head = new LinkedListNode<ValueType>(value, null, null);
189 tail = head;
190 }
191 else
192 {
193 head = new LinkedListNode<ValueType>(value, null, head);
194 head->Next()->SetPrev(head);
195 }
196 ++count;
197 return Iterator(this, head);
198 }
199 public Iterator Insert(Iterator pos, const ValueType& value)
200 {
201 LinkedListNode<ValueType>* next = pos.Node();
202 if (next != null)
203 {
204 LinkedListNode<ValueType>* prev = next->Prev();
205 LinkedListNode<ValueType>* n = new LinkedListNode<ValueType>(value, prev, next);
206 next->SetPrev(n);
207 if (prev != null)
208 {
209 prev->SetNext(n);
210 }
211 else
212 {
213 head = n;
214 }
215 ++count;
216 return Iterator(this, n);
217 }
218 else
219 {
220 Add(value);
221 return Iterator(this, tail);
222 }
223 }
224 public void Add(const ValueType& value)
225 {
226 if (tail == null)
227 {
228 tail = new LinkedListNode<ValueType>(value, null, null);
229 head = tail;
230 }
231 else
232 {
233 tail = new LinkedListNode<ValueType>(value, tail, null);
234 tail->Prev()->SetNext(tail);
235 }
236 ++count;
237 }
238 public void Add(ValueType&& value)
239 {
240 if (tail == null)
241 {
242 tail = new LinkedListNode<ValueType>(value, null, null);
243 head = tail;
244 }
245 else
246 {
247 tail = new LinkedListNode<ValueType>(value, tail, null);
248 tail->Prev()->SetNext(tail);
249 }
250 ++count;
251 }
252 public void RemoveFirst()
253 {
254 #assert(head != null);
255 LinkedListNode<ValueType>* n = head;
256 head = head->Next();
257 if (head != null)
258 {
259 head->SetPrev(null);
260 }
261 else
262 {
263 tail = null;
264 }
265 delete n;
266 --count;
267 }
268 public void RemoveLast()
269 {
270 #assert(tail != null);
271 LinkedListNode<ValueType>* n = tail;
272 tail = tail->Prev();
273 if (tail != null)
274 {
275 tail->SetNext(null);
276 }
277 else
278 {
279 head = null;
280 }
281 delete n;
282 --count;
283 }
284 public Iterator Remove(Iterator pos)
285 {
286 LinkedListNode<ValueType>* n = pos.Node();
287 #assert(n != null);
288 LinkedListNode<ValueType>* prev = n->Prev();
289 LinkedListNode<ValueType>* next = n->Next();
290 Iterator nxt(this, next);
291 if (prev != null)
292 {
293 prev->SetNext(next);
294 }
295 else
296 {
297 head = next;
298 }
299 if (next != null)
300 {
301 next->SetPrev(prev);
302 }
303 else
304 {
305 tail = prev;
306 }
307 delete n;
308 --count;
309 return nxt;
310 }
311 public void Remove(const ValueType& value)
312 {
313 Iterator i = Begin();
314 Iterator e = End();
315 while (i != e)
316 {
317 if (*i == value)
318 {
319 Iterator r = i;
320 ++i;
321 Remove(r);
322 }
323 else
324 {
325 ++i;
326 }
327 }
328 }
329 public inline const ValueType& Front() const
330 {
331 #assert(head != null);
332 return head->Value();
333 }
334 public inline const ValueType& Back() const
335 {
336 #assert(tail != null);
337 return tail->Value();
338 }
339 public inline LinkedListNode<ValueType>* Tail()
340 {
341 return tail;
342 }
343 private void CopyFrom(const LinkedList<ValueType>& that)
344 {
345 ConstIterator e = that.CEnd();
346 for (ConstIterator i = that.CBegin(); i != e; ++i;)
347 {
348 Add(*i);
349 }
350 }
351 private LinkedListNode<ValueType>* head;
352 private LinkedListNode<ValueType>* tail;
353 private long count;
354 }
355
356 public bool operator==<T>(const LinkedList<T>& left, const LinkedList<T>& right) where T is Regular
357 {
358 if (left.Count() != right.Count())
359 {
360 return false;
361 }
362 return Equal(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd());
363 }
364
365 public bool operator<<T>(const LinkedList<T>& left, const LinkedList<T>& right) where T is TotallyOrdered
366 {
367 return LexicographicalCompare(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd());
368 }