1
2
3
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<ValueType, const ValueType&, const ValueType*> ConstIterator;
17 public typedef RandomAccessIter<ValueType, ValueType&, 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(items, that.items, count);
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 n, const 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 + i, value);
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(items, that.items, count);
55 }
56 public nothrow void operator=(Self&& that) where T is Movable
57 {
58 Swap(items, that.items);
59 Swap(count, that.count);
60 Swap(res, that.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 + i, ValueType());
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 + count, item);
119 ++count;
120 }
121 public void Add(ValueType&& item) where T is Movable
122 {
123 Reserve(count + 1);
124 construct<ValueType>(items + count, item);
125 ++count;
126 }
127 public Iterator Insert(Iterator pos, const 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(pos, end, end + 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 pos, ValueType&& 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(pos, end, end + 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 + 1, End(), 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(newItems, items, count);
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(items, count);
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>& left, const 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>& left, const 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* to, ValueType* from, long 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* to, ValueType* from, long count) where ValueType is MoveConstructible
386 {
387 for (long i = 0; i < count; ++i;)
388 {
389 construct<ValueType>(to, Rvalue(*from));
390 ++to;
391 ++from;
392 }
393 }
394
395 public nothrow void Destroy<ValueType>(ValueType* items, long 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& writer, const 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 }