1
2
3
4
5
6 using System;
7 using System.Concepts;
8
9 namespace System.Collections
10 {
11 public class ForwardListNode<T> where T is Semiregular
12 {
13 private typedef T ValueType;
14 private typedef ForwardListNode<ValueType> Self;
15
16 public ForwardListNode(Self* next_, const ValueType& value_) : next(next_), value(value_)
17 {
18 }
19 public inline nothrow Self* Next() const
20 {
21 return next;
22 }
23 public inline nothrow void SetNext(Self* next_)
24 {
25 next = next_;
26 }
27 public inline nothrow const ValueType& Value() const
28 {
29 return value;
30 }
31 public inline nothrow ValueType& Value()
32 {
33 return value;
34 }
35 private ValueType value;
36 private Self* next;
37 }
38
39 public class ForwardListNodeIterator<T, R, P>
40 {
41 public typedef T ValueType;
42 public typedef R ReferenceType;
43 public typedef P PointerType;
44 private typedef ForwardListNodeIterator<ValueType, ReferenceType, PointerType> Self;
45 private typedef ForwardListNode<ValueType> NodeType;
46 private typedef NodeType* NodePtr;
47
48 public nothrow ForwardListNodeIterator() : node(null)
49 {
50 }
51 public nothrow ForwardListNodeIterator(NodePtr node_) : node(node_)
52 {
53 }
54 public inline ReferenceType operator*()
55 {
56 if (node == null)
57 {
58 ThrowNullPointerException();
59 }
60 return node->Value();
61 }
62 public inline PointerType operator->()
63 {
64 if (node == null)
65 {
66 ThrowNullPointerException();
67 }
68 return &(node->Value());
69 }
70 public inline Self& operator++()
71 {
72 if (node == null)
73 {
74 ThrowNullPointerException();
75 }
76 node = node->Next();
77 return *this;
78 }
79 public inline nothrow NodePtr Node() const
80 {
81 return node;
82 }
83 private NodePtr node;
84 }
85
86 public inline nothrow bool operator==<T, R, P>(const ForwardListNodeIterator<T, R, P>& left, const ForwardListNodeIterator<T, R, P>& right)
87 {
88 return left.Node() == right.Node();
89 }
90
91 public class ForwardList<T> where T is Regular
92 {
93 public typedef T ValueType;
94 private typedef ForwardList<ValueType> Self;
95 public typedef ForwardListNodeIterator<ValueType, const ValueType&, const ValueType*> ConstIterator;
96 public typedef ForwardListNodeIterator<ValueType, ValueType&, ValueType*> Iterator;
97 private typedef ForwardListNode<ValueType> NodeType;
98 private typedef NodeType* NodePtr;
99
100 public nothrow ForwardList() : head(null)
101 {
102 }
103 public ~ForwardList()
104 {
105 Clear();
106 }
107 public ForwardList(const Self& that) : head(null)
108 {
109 CopyFrom(that);
110 }
111 public nothrow ForwardList(Self&& that) : head(that.head)
112 {
113 that.head = null;
114 }
115 public void operator=(const Self& that)
116 {
117 Clear();
118 CopyFrom(that);
119 }
120 public nothrow void operator=(Self&& that)
121 {
122 Clear();
123 Swap(head, that.head);
124 }
125 public inline nothrow bool IsEmpty() const
126 {
127 return head == null;
128 }
129 public nothrow long Count() const
130 {
131 long count = 0;
132 NodePtr node = head;
133 while (node != null)
134 {
135 node = node->Next();
136 ++count;
137 }
138 return count;
139 }
140 public nothrow void Clear()
141 {
142 while (head != null)
143 {
144 NodePtr toRemove = head;
145 head = head->Next();
146 delete toRemove;
147 }
148 }
149 public inline nothrow Iterator Begin()
150 {
151 return Iterator(head);
152 }
153 public inline nothrow Iterator End()
154 {
155 return Iterator(null);
156 }
157 public inline nothrow ConstIterator Begin() const
158 {
159 return ConstIterator(head);
160 }
161 public inline nothrow ConstIterator End() const
162 {
163 return ConstIterator(null);
164 }
165 public inline nothrow ConstIterator CBegin() const
166 {
167 return ConstIterator(head);
168 }
169 public inline nothrow ConstIterator CEnd() const
170 {
171 return ConstIterator(null);
172 }
173 public inline const ValueType& Front() const
174 {
175 if (head == null)
176 {
177 ThrowNullPointerException();
178 }
179 return head->Value();
180 }
181 public inline Iterator InsertFront(const ValueType& value)
182 {
183 head = new NodeType(head, value);
184 return Iterator(head);
185 }
186 public Iterator InsertAfter(Iterator pos, const ValueType& value)
187 {
188 NodePtr node = pos.Node();
189 if (node == null)
190 {
191 return InsertFront(value);
192 }
193 node->SetNext(new NodeType(node->Next(), value));
194 return Iterator(node->Next());
195 }
196 public void RemoveFront()
197 {
198 if (head == null)
199 {
200 throw NullPointerException();
201 }
202 NodePtr node = head;
203 head = head->Next();
204 delete node;
205 }
206 public void RemoveAfter(Iterator pos)
207 {
208 NodePtr node = pos.Node();
209 if (node == null)
210 {
211 ThrowInvalidParameterException();
212 }
213 NodePtr toRemove = node->Next();
214 if (toRemove == null)
215 {
216 ThrowNullPointerException();
217 }
218 node->SetNext(toRemove->Next());
219 delete toRemove;
220 }
221 public void Remove(const ValueType& value)
222 {
223 NodePtr prev = null;
224 NodePtr node = head;
225 while (node != null)
226 {
227 if (node->Value() == value)
228 {
229 if (node == head)
230 {
231 head = head->Next();
232 delete node;
233 node = head;
234 }
235 else
236 {
237 if (prev == null)
238 {
239 ThrowNullPointerException();
240 }
241 prev->SetNext(node->Next());
242 delete node;
243 node = prev->Next();
244 }
245 }
246 else
247 {
248 prev = node;
249 node = node->Next();
250 }
251 }
252 }
253 private void CopyFrom(const Self& that)
254 {
255 NodePtr n = that.head;
256 NodePtr last = null;
257 while (n != null)
258 {
259 if (head == null)
260 {
261 InsertFront(n->Value());
262 last = head;
263 }
264 else
265 {
266 last->SetNext(new NodeType(null, n->Value()));
267 last = last->Next();
268 }
269 n = n->Next();
270 }
271 }
272 private NodePtr head;
273 }
274
275 public bool operator==<T>(const ForwardList<T>& left, const ForwardList<T>& right) where T is Regular
276 {
277 return Equal(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd());
278 }
279
280 public bool operator<<T>(const ForwardList<T>& left, const ForwardList<T>& right) where T is TotallyOrdered
281 {
282 return LexicographicalCompare(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd());
283 }
284 }