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