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 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<TRP>
 48     {
 49         public typedef T ValueType;
 50         public typedef R ReferenceType;
 51         public typedef P PointerType;
 52         private typedef LinkedListNodeIterator<ValueTypeReferenceTypePointerType> 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==<TRP>(const LinkedListNodeIterator<TRP>& leftconst LinkedListNodeIterator<TRP>& 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<ValueTypeValueType&ValueType*> Iterator;
118         public typedef LinkedListNodeIterator<ValueTypeconst 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(headthat.head);
141             Swap(tailthat.tail);
142             Swap(countthat.count);
143         }
144         public ~LinkedList()
145         {
146             Clear();
147         }
148         public inline nothrow Iterator Begin()
149         {
150             return Iterator(thishead);
151         }
152         public inline nothrow ConstIterator Begin() const
153         {
154             return ConstIterator(thishead);
155         }
156         public inline nothrow ConstIterator CBegin() const
157         {
158             return ConstIterator(thishead);
159         }
160         public inline nothrow Iterator End()
161         {
162             return Iterator(thisnull);
163         }
164         public inline nothrow ConstIterator End() const
165         {
166             return ConstIterator(thisnull);
167         }
168         public inline nothrow ConstIterator CEnd() const
169         {
170             return ConstIterator(thisnull);
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>(valuenullnull);
198                 tail = head;
199             }
200             else
201             {
202                 head = new LinkedListNode<ValueType>(valuenullhead);
203                 head->Next()->SetPrev(head);
204             }
205             ++count;
206             return Iterator(thishead);
207         }
208         public Iterator Insert(Iterator posconst 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>(valueprevnext);
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(thisn);
226             }
227             else
228             {
229                 Add(value);
230                 return Iterator(thistail);
231             }
232         }
233         public void Add(const ValueType& value)
234         {
235             if (tail == null)
236             {
237                 tail = new LinkedListNode<ValueType>(valuenullnull);
238                 head = tail;
239             }
240             else
241             {
242                 tail = new LinkedListNode<ValueType>(valuetailnull);
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(thisnext);
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>& leftconst 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>& leftconst LinkedList<T>& right) where T is TotallyOrdered
376     {
377         return LexicographicalCompare(left.CBegin()left.CEnd()right.CBegin()right.CEnd());
378     }
379 }