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