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