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 nothrow ReferenceType operator*()
61 {
62 if (node == null)
63 {
64 ThrowNullPointerException();
65 }
66 return node->Value();
67 }
68 public inline nothrow PointerType operator->()
69 {
70 if (node == null)
71 {
72 ThrowNullPointerException();
73 }
74 return &(node->Value());
75 }
76 public inline nothrow Self& operator++()
77 {
78 if (node == null)
79 {
80 ThrowNullPointerException();
81 }
82 node = node->Next();
83 return *this;
84 }
85 public inline nothrow Self& operator--()
86 {
87 if (node == null)
88 {
89 if (list == null)
90 {
91 ThrowPreconditionViolationException();
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 nothrow 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 nothrow 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 nothrow void 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 if (prev != null)
295 {
296 prev->SetNext(next);
297 }
298 else
299 {
300 head = next;
301 }
302 if (next != null)
303 {
304 next->SetPrev(prev);
305 }
306 else
307 {
308 tail = prev;
309 }
310 delete n;
311 --count;
312 }
313 public nothrow void Remove(const ValueType& value)
314 {
315 Iterator i = Begin();
316 Iterator e = End();
317 while (i != e)
318 {
319 if (*i == value)
320 {
321 Iterator r = i;
322 ++i;
323 Remove(r);
324 }
325 else
326 {
327 ++i;
328 }
329 }
330 }
331 public inline nothrow const ValueType& Front() const
332 {
333 if (head == null)
334 {
335 ThrowPreconditionViolationException();
336 }
337 return head->Value();
338 }
339 public inline nothrow const ValueType& Back() const
340 {
341 if (tail == null)
342 {
343 ThrowPreconditionViolationException();
344 }
345 return tail->Value();
346 }
347 public inline nothrow LinkedListNode<ValueType>* Tail()
348 {
349 return tail;
350 }
351 private void CopyFrom(const LinkedList<ValueType>& that)
352 {
353 ConstIterator e = that.CEnd();
354 for (ConstIterator i = that.CBegin(); i != e; ++i;)
355 {
356 Add(*i);
357 }
358 }
359 private LinkedListNode<ValueType>* head;
360 private LinkedListNode<ValueType>* tail;
361 private long count;
362 }
363
364 public nothrow bool operator==<T>(const LinkedList<T>& left, const LinkedList<T>& right) where T is Regular
365 {
366 if (left.Count() != right.Count())
367 {
368 return false;
369 }
370 return Equal(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd());
371 }
372
373 public nothrow bool operator<<T>(const LinkedList<T>& left, const LinkedList<T>& right) where T is TotallyOrdered
374 {
375 return LexicographicalCompare(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd());
376 }
377 }