1 // =================================
  2 // Copyright (c) 2021 Seppo Laakko
  3 // Distributed under the MIT license
  4 // =================================
  5 
  6 using System;
  7 using System.Concepts;
  8 using System.IO;
  9 
 10 namespace System.Collections
 11 {
 12     public class List<T> where T is Semiregular
 13     {
 14         public typedef T ValueType;
 15         private typedef List<ValueType> Self;
 16         public typedef RandomAccessIter<ValueTypeconst ValueType&const ValueType*> ConstIterator;
 17         public typedef RandomAccessIter<ValueTypeValueType&ValueType*> Iterator;
 18 
 19         public nothrow List() : items(null)count(0)res(0)
 20         {
 21         }
 22         public List(const Self& that) : items(null)count(that.count)res(0) where T is Copyable
 23         {
 24             if (count > 0)
 25             {
 26                 Reserve(count);
 27                 ConstructiveCopy(itemsthat.itemscount);
 28             }
 29         }
 30         public nothrow List(Self&& that) : items(that.items)count(that.count)res(that.res) where T is Movable
 31         {
 32             that.items = null;
 33             that.count = 0;
 34             that.res = 0;
 35         }
 36         public List(long nconst ValueType& value) : items(null)count(0)res(0) where T is Copyable
 37         {
 38             if (n < 0)
 39             {
 40                 ThrowInvalidParameterException();
 41             }
 42             count = n;
 43             Reserve(count);
 44             for (long i = 0; i < n; ++i;)
 45             {
 46                 construct<ValueType>(items + ivalue);
 47             }
 48         }
 49         public void operator=(const Self& that) where T is Copyable
 50         {
 51             Destroy();
 52             count = that.count;
 53             Reserve(count);
 54             ConstructiveCopy(itemsthat.itemscount);
 55         }
 56         public nothrow void operator=(Self&& that) where T is Movable
 57         {
 58             Swap(itemsthat.items);
 59             Swap(countthat.count);
 60             Swap(resthat.res);
 61         }
 62         public ~List()
 63         {
 64             Destroy();
 65         }
 66         public void Reserve(long minRes)
 67         {
 68             if (minRes > res)
 69             {
 70                 Grow(minRes);
 71             }
 72         }
 73         public void Resize(long newCount) where T is Movable
 74         {
 75             if (newCount < 0)
 76             {
 77                 ThrowInvalidParameterException();
 78             }
 79             if (newCount != count)
 80             {
 81                 if (newCount < count)
 82                 {
 83                     for (long i = newCount; i < count; ++i;)
 84                     {
 85                         destroy(items + i);
 86                     }
 87                 }
 88                 else if (newCount > count)
 89                 {
 90                     Reserve(newCount);
 91                     for (long i = count; i < newCount; ++i;)
 92                     {
 93                         construct<ValueType>(items + iValueType());
 94                     }
 95                 }
 96                 count = newCount;
 97             }
 98         }
 99         public inline nothrow long Count() const
100         {
101             return count;
102         }
103         public inline nothrow long Capacity() const
104         {
105             return res;
106         }
107         public inline nothrow bool IsEmpty() const
108         {
109             return count == 0;
110         }
111         public nothrow void Clear()
112         {
113             Destroy();
114         }
115         public void Add(const ValueType& item) where T is Copyable
116         {
117             Reserve(count + 1);
118             construct<ValueType>(items + countitem);
119             ++count;
120         }
121         public void Add(ValueType&& item) where T is Movable
122         {
123             Reserve(count + 1);
124             construct<ValueType>(items + countitem);
125             ++count;
126         }
127         public Iterator Insert(Iterator posconst ValueType& item) where T is Copyable
128         {
129             long p = pos - Begin();
130             Reserve(count + 1);
131             pos = Begin() + p;
132             Iterator end = End();
133             if (count > 0)
134             {
135                 construct<ValueType>(end.Ptr()ValueType());
136                 MoveBackward(posendend + 1);
137                 *pos = item;
138             }
139             else
140             {
141                 construct<ValueType>(end.Ptr()item);
142                 pos = end;
143             }
144            ++count;
145            return pos;
146         }
147         public Iterator Insert(Iterator posValueType&& item) where T is Movable
148         {
149             long p = pos - Begin();
150             Reserve(count + 1);
151             pos = Begin() + p;
152             Iterator end = End();
153             if (count > 0)
154             {
155                 construct<ValueType>(end.Ptr()ValueType());
156                 MoveBackward(posendend + 1);
157                 *pos = item;
158             }
159             else
160             {
161                 construct<ValueType>(end.Ptr()item);
162                 pos = end;
163             }
164            ++count;
165            return pos;
166         }
167         public Iterator InsertFront(const ValueType& item) where T is Copyable
168         {
169             return Insert(Begin()item);
170         }
171         public Iterator InsertFront(ValueType&& item) where T is Movable
172         {
173             return Insert(Begin()item);
174         }
175         public ValueType Remove(Iterator pos)
176         {
177             if (pos < Begin() || pos >= End())
178             {
179                 ThrowInvalidParameterException();
180             }
181             ValueType result = Rvalue(*pos);
182             Move(pos + 1End()pos);
183             --count;
184             Iterator end = End();
185             destroy(end.Ptr());
186             return result;
187         }
188         public ValueType RemoveFirst()
189         {
190             return Remove(Begin());
191         }
192         public ValueType RemoveLast()
193         {
194             if (IsEmpty())
195             {
196                 ThrowPreconditionViolationException();
197             }
198             --count;
199             Iterator end = End();
200             ValueType result = Rvalue(*end);
201             destroy(end.Ptr());
202             return result;
203         }
204         public void Remove(const ValueType& item)
205         {
206             Iterator i = Begin();
207             Iterator e = End();
208             Iterator p = i;
209             while (i != e)
210             {
211                 if (*i == item)
212                 {
213                     ++i;
214                 }
215                 else if (i != p)
216                 {
217                     *p++ = *i++;
218                 }
219                 else
220                 {
221                     ++i;
222                     ++p;
223                 }
224             }
225             while (p != e)
226             {
227                 destroy(p.Ptr());
228                 --count;
229                 ++p;
230             }
231         }
232         public inline const ValueType& operator[](long index) const
233         {
234             if (index < 0 || index >= count)
235             {
236                 ThrowIndexOutOfBoundsException();
237             }
238             return items[index];
239         }
240         public inline ValueType& operator[](long index)
241         {
242             if (index < 0 || index >= count)
243             {
244                 ThrowIndexOutOfBoundsException();
245             }
246             return items[index];
247         }
248         public inline nothrow Iterator Begin()
249         {
250             return Iterator(items);
251         }
252         public inline nothrow ConstIterator Begin() const
253         {
254             return ConstIterator(items);
255         }
256         public inline nothrow ConstIterator CBegin() const
257         {
258             return ConstIterator(items);
259         }
260         public inline nothrow Iterator End()
261         {
262             if (items != null)
263             {
264                 return Iterator(items + count);
265             }
266             return Iterator(null);
267         }
268         public inline nothrow ConstIterator End() const
269         {
270             if (items != null)
271             {
272                 return ConstIterator(items + count);
273             }
274             return ConstIterator(null);
275         }
276         public inline nothrow ConstIterator CEnd() const
277         {
278             if (items != null)
279             {
280                 return ConstIterator(items + count);
281             }
282             return ConstIterator(null);
283         }
284         public inline const ValueType& Front() const
285         {
286             if (IsEmpty())
287             {
288                 ThrowPreconditionViolationException();
289             }
290             return *Begin();
291         }
292         public inline ValueType& Front()
293         {
294             if (IsEmpty())
295             {
296                 ThrowPreconditionViolationException();
297             }
298             return *Begin();
299         }
300         public inline const ValueType& Back() const
301         {
302             if (IsEmpty())
303             {
304                 ThrowPreconditionViolationException();
305             }
306             return *(End() - 1);
307         }
308         public inline ValueType& Back()
309         {
310             if (IsEmpty())
311             {
312                 ThrowPreconditionViolationException();
313             }
314             return *(End() - 1);
315         }
316         private void Grow(long minRes)
317         {
318             minRes = MemGrow(minRes);
319         #if (MEM_DEBUG)
320             ValueType* newItems = cast<ValueType*>(MemAlloc(minRes * sizeof(ValueType)typename(*this)));
321         #else
322             ValueType* newItems = cast<ValueType*>(MemAlloc(minRes * sizeof(ValueType)));
323         #endif
324             if (items != null)
325             {
326                 ConstructiveMove(newItemsitemscount);
327                 long saveCount = count;
328                 Destroy();
329                 count = saveCount;
330             }
331             items = newItems;
332             res = minRes;
333         }
334         private nothrow void Destroy()
335         {
336             if (count > 0)
337             {
338                 Destroy(itemscount);
339                 count = 0;
340             }
341             if (res > 0)
342             {
343                 MemFree(items);
344                 items = null;
345                 res = 0;
346             }
347         }
348         private ValueType* items;
349         private long count;
350         private long res;
351     }
352 
353     public nothrow bool operator==<T>(const List<T>& leftconst List<T>& right) where T is Regular
354     {
355         long n = left.Count();
356         if (n != right.Count())
357         {
358             return false;
359         }
360         for (long i = 0; i < n; ++i;)
361         {
362             if (left[i] != right[i])
363             {
364                 return false;
365             }
366         }
367         return true;
368     }
369 
370     public nothrow bool operator<<T>(const List<T>& leftconst List<T>& right) where T is TotallyOrdered
371     {
372         return LexicographicalCompare(left.Begin()left.End()right.Begin()right.End());
373     }
374 
375     public void ConstructiveCopy<ValueType>(ValueType* toValueType* fromlong count) where ValueType is CopyConstructible
376     {
377         for (long i = 0; i < count; ++i;)
378         {
379             construct<ValueType>(to*from);
380             ++to;
381             ++from;
382         }
383     }
384 
385     public void ConstructiveMove<ValueType>(ValueType* toValueType* fromlong count) where ValueType is MoveConstructible
386     {
387         for (long i = 0; i < count; ++i;)
388         {
389             construct<ValueType>(toRvalue(*from));
390             ++to;
391             ++from;
392         }
393     }
394 
395     public nothrow void Destroy<ValueType>(ValueType* itemslong count) where ValueType is Destructible
396     {
397         for (long i = 0; i < count; ++i;)
398         {
399             destroy(items);
400             ++items;
401         }
402     }
403 
404     [system_default="true"]
405     public TextWriter& operator<<<T>(TextWriter& writerconst List<T>& list)
406     {
407         writer << "[";
408         bool first = true;
409         for (const T& element : list)
410         {
411             if (first)
412             {
413                 first = false;
414             }
415             else
416             {
417                 writer << ", ";
418             }
419             writer << element;
420         }
421         writer << "]";
422         return writer;
423     }
424 }