1 package frost.collections
2
3 uses frost.unsafe.Pointer
4
5 ====================================================================================================
6 A random-access `CollectionView` with numbered elements. Each entry has an index, ranging from `0`
7 to `count - 1`, by which it can be accessed.
8
9 @see ListWriter
10 @see List
11 ====================================================================================================
12 interface ListView<T> : CollectionView<T> {
13 ================================================================================================
14 Returns an `Iterator` which returns `(index, value)` tuples. For example,
15 `["Hello", "Bonjour"].enumeration` returns an `Iterator<(Int, String)>` which produces
16 `(0, "Hello")` followed by `(1, "Bonjour")`.
17 ================================================================================================
18 property enumeration:Iterator<(Int, T)>
19
20 ================================================================================================
21 An `Iterator` of all possible permutations of this list. A permutation is a distinct ordering;
22 each possible shuffling of a deck of cards is a different permutation. As the number of
23 permutations is equal to the factorial of the number of elements in the list, it is only
24 practical to fully iterate the permutations of very small lists (a list with just 15 elements in
25 it has over a trillion permutations).
26
27 @returns an iterator which produces permutations of this list
28 ================================================================================================
29 property permutations:Iterator<ListView<T>>
30
31 ================================================================================================
32 Returns an `Iterator` which produces the elements of the power set of this list. The power set
33 of a list is the set of all possible subsets (including the empty list). For instance, the power
34 set of `[1, 2, 3]` is: `[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]`. The iteration
35 order is not guaranteed.
36
37 As the power set of a list with `n` elements contains 2^n entries, iterating over the power set
38 is only practical for small lists.
39
40 @returns an iterator which produces the power set of this list
41 ================================================================================================
42 property powerSet:Iterator<ListView<T>>
43
44 property last:T
45
46 @private
47 class ListIterator<T> : Iterator<T> {
48 var list:ListView<T>
49
50 var index := 0
51
52 init(list:ListView<T>) {
53 self.list := list
54 }
55
56 @override
57 function get_done():Bit {
58 return index = list.count
59 }
60
61 @override
62 function next():T {
63 index += 1
64 return list[index - 1]
65 }
66 }
67
68 @private
69 class PermutationIterator<T> : Iterator<ListView<T>> {
70 def list:ListView<T>
71
72 def choices:Array<Int>
73
74 init(list:ListView<T>) {
75 self.list := list
76 if list.count > 0 {
77 self.choices := Array<Int>(list.count, 0)
78 }
79 else {
80 self.choices := [-1]
81 }
82 }
83
84 @override
85 function get_done():Bit {
86 return choices[0] = -1
87 }
88
89 @override
90 function next():ListView<T> {
91 def result := Array<T>(list.count)
92 def copy := Array<T>(list)
93 for c in choices {
94 result.add(copy[c])
95 copy.removeIndex(c)
96 }
97 var i := 0
98 while i < choices.count &< choices.count & choices[i] = list.count - i - 1->Int {
99 choices[i] := 0
100 i += 1
101 }
102 if i = choices.count {
103 choices[0] := -1
104 }
105 else {
106 choices[i] += 1
107 }
108 return result
109 }
110 }
111
112 @private
113 class CombinationIterator<T> : Iterator<ListView<T>> {
114 def list:ListView<T>
115
116 def choices:List<Int>
117
118 var r := 0
119
120 var index := 0
121
122 @pre(count >= 0 & count <= list.count)
123 init(list:ListView<T>, count:Int) {
124 self.list := list
125 self.choices := Array<Int>(count)
126 for i in 0 .. count {
127 choices.add(i)
128 }
129 }
130
131 @override
132 function get_done():Bit {
133 for i in 0 .. choices.count {
134 if choices[i] + choices.count < list.count -< list.count - i {
135 return false
136 }
137 }
138 return true
139 }
140
141 @override
142 method next():ListView<T> {
143 loop {
144 if index <= list.count + r - choices.count {
145 choices[r] := index
146 if r = choices.count - 1->Int {
147 index += 1
148 def result := Array<T>(choices.count)
149 for c in choices {
150 result.add(list[c])
151 }
152 return result
153 }
154 else {
155 index := choices[r] + 1
156 r += 1
157 }
158 }
159 else {
160 r -= 1
161 if r > 0 {
162 index := choices[r] + 1
163 }
164 else {
165 index := choices[0] + 1
166 }
167 }
168 }
169 }
170 }
171
172 @private
173 class PowerSetIterator<T> : Iterator<ListView<T>> {
174 def list:ListView<T>
175
176 var mask:UInt64 := 0
177
178 var stop:UInt64
179
180 init(list:ListView<T>) {
181 self.list := list
182 self.stop := (1 << list.count).asUInt64
183 }
184
185 @override
186 function get_done():Bit {
187 return mask = stop
188 }
189
190 @override
191 method next():ListView<T> {
192 def result := Array<T>()
193 for i in 0 .. list.count {
194 if mask.bits[i] {
195 result.add(list[i])
196 }
197 }
198 mask += 1
199 return result
200 }
201 }
202
203 ================================================================================================
204 Returns an item from this list.
205
206 @param index the (zero-based) index of the item to return
207 ================================================================================================
208 @pre(index >= 0 & index < count)< count)
209 function [](index:Int):T
210
211 ================================================================================================
212 Returns a slice of the list, containing all of the elements specified by the range. The slice
213 is an independent copy of the list and elements may be added to and removed from the original
214 without affecting the copy. It is not, however, a deep copy, and thus both lists will refer
215 to the same objects.
216 ================================================================================================
217 @default
218 @pre(r.min >= 0 & (r.inclusive & r.min < count |< count | !r.inclusive & r.min <= count) &
219 r.max >= 0 & (r.inclusive & r.max < count |< count | !r.inclusive & r.max <= count))
220 @priority(1) -- FIXME shouldn't be needed
221 @unsafeAccess
222 function [](r:Range<Int>):ListView<T> {
223 var max := r.max
224 if r.inclusive {
225 max += 1
226 }
227 def count := max - r.min
228 def result := Pointer<T>.alloc(count)
229 for i in 0 .. count {
230 result[i] := self[r.min + i]
231 }
232 return Array<T>(result, count)
233 }
234
235 ================================================================================================
236 Returns a slice of the list, containing all of the elements specified by the range. The slice
237 is an independent copy of the list and elements may be added to and removed from the original
238 without affecting the copy. It is not, however, a deep copy, and thus both lists will refer
239 to the same objects.
240
241 As usual for `Range`, a null `min` starts from the beginning of the list, and a null `max` ends
242 at the end of the list.
243 ================================================================================================
244 @default
245 function [](r:Range<Int?>):ListView<T> {
246 def start:Int
247 if r.min !== null {
248 start := r.min
249 }
250 else {
251 start := 0
252 }
253
254 var end:Int
255 if r.max !== null {
256 end := r.max
257 }
258 else {
259 end := count
260 if r.inclusive {
261 end -= 1
262 }
263 }
264 return self[Range<Int>(start, end, r.inclusive)]
265 }
266
267 @private
268 @class
269 function inRange(r:SteppedRange<Int?, Int>, count:Int):Bit {
270 if r.start !== null {
271 if (r.start < 0< 0) {
272 return false
273 }
274 if r.inclusive & r.start >= count {
275 return false
276 }
277 if !r.inclusive & r.start > count {
278 return false
279 }
280 }
281 if r.end !== null {
282 if (r.end < 0< 0) {
283 return false
284 }
285 if r.inclusive & r.end >= count {
286 return false
287 }
288 if !r.inclusive & r.end > count {
289 return false
290 }
291 }
292 return true
293 }
294
295 ================================================================================================
296 Returns a slice of the list, containing all of the elements specified by the range. The slice
297 is an independent copy of the list and elements may be added to and removed from the original
298 without affecting the copy. It is not, however, a deep copy, and thus both lists will refer
299 to the same objects.
300 ================================================================================================
301 @default
302 @pre(inRange(r, count))
303 function [](r:SteppedRange<Int?, Int>):ListView<T> {
304 def step := r.step
305
306 var current:Int
307 if r.start !== null {
308 current := r.start
309 }
310 else if step > 0 {
311 current := 0
312 }
313 else {
314 current := count - 1
315 }
316
317 def end:Int
318 if r.end !== null {
319 end := r.end
320 }
321 else if step > 0 {
322 end := count
323 }
324 else {
325 end := 0
326 }
327
328 def result := Array<T>()
329 if r.step > 0 {
330 while current < end {< end {
331 result.add(self[current])
332 current += step
333 }
334 }
335 else {
336 assert r.step < 0< 0
337 while current > end {
338 result.add(self[current])
339 current += step
340 }
341 }
342 if (r.inclusive | r.end == null) & current = end & end < count {< count {
343 result.add(self[current])
344 }
345 return result
346 }
347
348 @override
349 @default
350 function get_first():T {
351 return self[0]
352 }
353
354 @default
355 function get_last():T {
356 return self[count - 1]
357 }
358
359 ================================================================================================
360 Returns a new list containing every entry in this list for which the `predicate` function
361 returns true. For instance, `[1, 7, -10, 5, -2].filter(x => x > 0)` returns `[1, 7, 5]`.
362 ================================================================================================
363 @default
364 @priority(1) -- FIXME I don't think I should need all these @priority annotations...
365 -- FIXME need an annotation for having to use the return value
366 function filter(predicate:(T)=>(Bit)):ListView<T> {
367 def result := Array<T>()
368 for v in self {
369 if predicate(v) {
370 result.add(v)
371 }
372 }
373 return result
374 }
375
376 @default
377 -- FIXME need an annotation for having to use the return value
378 method filter(predicate:(T)=&>(Bit)):ListView<T> {
379 def result := Array<T>()
380 for v in self {
381 if predicate(v) {
382 result.add(v)
383 }
384 }
385 return result
386 }
387
388 @default
389 @pre(count = other.count)
390 function combine<U>(other:ListView<U>):ListView<(T, U)> {
391 def result := Array<(T, U)>(count)
392 for i in 0 .. count {
393 result.add((self[i], other[i]))
394 }
395 return result
396 }
397
398 @default
399 @priority(1)
400 @pre(count = other.count)
401 function combine<U, V>(other:ListView<U>, f:(T, U)=>(V)):ListView<V> {
402 def result := Array<V>(count)
403 for i in 0 .. count {
404 result.add(f(self[i], other[i]))
405 }
406 return result
407 }
408
409 @default
410 @pre(count = other.count)
411 method combine<U, V>(other:ListView<U>, f:(T, U)=&>(V)):ListView<V> {
412 def result := Array<V>(count)
413 for i in 0 .. count {
414 result.add(f(self[i], other[i]))
415 }
416 return result
417 }
418
419 @default
420 @override
421 function get_iterator():Iterator<T> {
422 return ListIterator<T>(self)
423 }
424
425 @default
426 function get_enumeration():Iterator<(Int, T)> {
427 return iterator.enumeration
428 }
429
430 @default
431 function get_permutations():Iterator<ListView<T>> {
432 return PermutationIterator<T>(self)
433 }
434
435 ================================================================================================
436 Returns an `Iterator` of all possible `n`-combinations of this list. An `n`-combination of a
437 list is a selection of `n` distinct elements from the list; the set of 5-combinations of a deck
438 of cards is the set of all possible poker hands. The combinations are chosen in such a way as to
439 preserve order: the combinations of a sorted list will themselves be sorted. Elements are
440 considered "distinct" if they appear at different positions in the input list. This means that
441 the 2-combinations of [1, 2, 2] are [1, 2], [1, 2], and [2, 2], as the two occurrences of `2`
442 are considered distinct elements.
443
444 @returns an iterator which produces the `n`-combinations of this list
445 ================================================================================================
446 @default
447 @pre(count >= n)
448 function combinations(n:Int):Iterator<ListView<T>> {
449 if n = 0 {
450 return [[]]->Array<ListView<T>>.iterator
451 }
452 if n = count {
453 return [self].iterator
454 }
455 return CombinationIterator<T>(self, n)
456 }
457
458 @default
459 @pre(count < 64< 64)
460 function get_powerSet():Iterator<ListView<T>> {
461 return PowerSetIterator<T>(self)
462 }
463
464 ================================================================================================
465 Returns a sorted copy of the list using the provided comparison method. The list is sorted so
466 that the greatest elements, according to the `greater` function, are at the end (higher indices)
467 of the array. The sort algorithm used may be unstable, meaning equal values (that is, values for
468 which `greater(a, b)` and `greater(b, a)` both return `false`) may be arbitrarily reordered
469 during the sort.
470 ================================================================================================
471 -- FIXME write a better sort, create stableSort
472 -- FIXME need an annotation for having to use the return value
473 @default
474 method sort(greater:(T, T)=>(Bit)):ListView<T> {
475 def result := Array<T>(self)
476 MergeSort.sort(result, greater)
477 return result
478 }
479 }
480