1 // =================================
  2 // Copyright (c) 2021 Seppo Laakko
  3 // Distributed under the MIT license
  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<TRP>
 40     {
 41         public typedef T ValueType;
 42         public typedef R ReferenceType;
 43         public typedef P PointerType;
 44         private typedef ForwardListNodeIterator<ValueTypeReferenceTypePointerType> 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==<TRP>(const ForwardListNodeIterator<TRP>& left const ForwardListNodeIterator<TRP>& 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<ValueTypeconst ValueType&const ValueType*> ConstIterator;
 96         public typedef ForwardListNodeIterator<ValueTypeValueType&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(headthat.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(headvalue);
184             return Iterator(head);
185         }
186         public Iterator InsertAfter(Iterator posconst 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(nulln->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>& leftconst 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>& leftconst ForwardList<T>& right) where T is TotallyOrdered
281     {
282         return LexicographicalCompare(left.CBegin()left.CEnd()right.CBegin()right.CEnd());
283     }
284 }