1 //
2 // Copyright (c) 2006, Brian Frank and Andy Frank
3 // Licensed under the Academic Free License version 3.0
4 //
5 // History:
6 // 4 Jan 06 Brian Frank Creation
7 //
8
9 **
10 ** List represents an liner sequence of Objects indexed by an Int.
11 **
12 final class List
13 {
14
15 //////////////////////////////////////////////////////////////////////////
16 // Constructor
17 //////////////////////////////////////////////////////////////////////////
18
19 **
20 ** Constructor with of type and initial capacity.
21 **
22 new make(Type of, Int capacity)
23
24 **
25 ** Constructor for Obj[] with initial capacity.
26 **
27 new makeObj(Int capacity)
28
29 //////////////////////////////////////////////////////////////////////////
30 // Identity
31 //////////////////////////////////////////////////////////////////////////
32
33 **
34 ** Two Lists are equal if they have the same number of items and all
35 ** the items at each index return true for equals().
36 **
37 override Bool equals(Obj that)
38
39 **
40 ** Return platform dependent hashcode based a hash of the items
41 ** of the list.
42 **
43 override Int hash()
44
45 **
46 ** Get the item Type of this List.
47 **
48 ** Examples:
49 ** ["hi"].of -> Str.type
50 ** [[2, 3]].of -> Int[].type
51 **
52 Type of()
53
54 //////////////////////////////////////////////////////////////////////////
55 // Access
56 //////////////////////////////////////////////////////////////////////////
57
58 **
59 ** Return if size == 0. This method is idempotent.
60 **
61 Bool isEmpty()
62
63 **
64 ** The number of items in the list. If the size is set greater than
65 ** the current size then the list is automatically grown to be a sparse
66 ** list with new items defaulting to null. If the size is set less than
67 ** the current size then any items with indices past the new size are
68 ** automatically removed. Changing size automatically allocates new
69 ** storage so that capacity exactly matches the new size. Getting size
70 ** is idempotent, setting size throws ReadonlyErr if readonly.
71 **
72 Int size
73
74 **
75 ** The number of items this list can hold without allocating more memory.
76 ** Capacity is always greater or equal to size. If adding a large
77 ** number of items, it may be more efficient to manually set capacity.
78 ** See the trim() method to automatically set capacity to size. Throw
79 ** ArgErr if attempting to set capacity less than size. Getting capacity
80 ** is idempotent, setting capacity throws ReadonlyErr if readonly.
81 **
82 Int capacity
83
84 **
85 ** Get is used to return the item at the specified the index. A
86 ** negative index may be used to access an index from the end of the
87 ** list. For example get(-1) is translated into get(size()-1). The
88 ** get method is accessed via the [] shortcut operator. Throw
89 ** IndexErr if index is out of range. This method is idempotent.
90 **
91 V get(Int index)
92
93 **
94 ** Return a sub-list based on the specified range. Negative indexes
95 ** may be used to access from the end of the list. This method
96 ** is accessed via the [] operator. This method is idempotent.
97 ** Throw IndexErr if range illegal.
98 **
99 ** Examples:
100 ** list := [0, 1, 2, 3]
101 ** list[0..2] -> [0, 1, 2]
102 ** list[3..3] -> [3]
103 ** list[-2..-1] -> [2, 3]
104 ** list[0...2] -> [0, 1]
105 ** list[1..-2] -> [1, 2]
106 **
107 L slice(Range range)
108
109 **
110 ** Return if this list contains the specified item using
111 ** the == operator (shortcut for equals method) to check
112 ** for equality. This method is idempotent.
113 **
114 Bool contains(V item)
115
116 **
117 ** Return if this list contains every item in the specified
118 ** list using the == operator (shortcut for equals method).
119 ** This method is idempotent.
120 **
121 Bool containsAll(L list)
122
123 **
124 ** Return the integer index of the specified item using
125 ** the == operator (shortcut for equals method) to check
126 ** for equality. The search starts at the specified offset
127 ** and returns the first match. The offset may be negative
128 ** to access from end of list. Throw IndexErr if offset is
129 ** out of range. If the item is not found return null.
130 ** This method is idempotent.
131 **
132 Int index(V item, Int offset := 0)
133
134 **
135 ** Return the item at index 0, or if empty return null.
136 ** This method is idempotent.
137 **
138 V first()
139
140 **
141 ** Return the item at index-1, or if empty return null.
142 ** This method is idempotent.
143 **
144 V last()
145
146 **
147 ** Create a shallow duplicate copy of this List. The items
148 ** themselves are not duplicated. This method is idempotent.
149 **
150 L dup()
151
152 //////////////////////////////////////////////////////////////////////////
153 // Modification
154 //////////////////////////////////////////////////////////////////////////
155
156 **
157 ** Set is used to overwrite the item at the specified the index. A
158 ** negative index may be used to access an index from the end of the
159 ** list. The set method is accessed via the []= shortcut operator.
160 ** If you wish to use List as a sparse array and set values greater
161 ** then size, then manually set size larger. Return this. Throw
162 ** IndexErr if index is out of range. Throw ReadonlyErr if readonly.
163 **
164 L set(Int index, V item)
165
166 **
167 ** Add the specified item to the end of the list. The item will have
168 ** an index of size. Size is incremented by 1. Return this. Throw
169 ** ReadonlyErr if readonly.
170 **
171 L add(V item)
172
173 **
174 ** Add all the items in the specified list to the end of this list.
175 ** Size is incremented by list.size. Return this. Throw ReadonlyErr
176 ** if readonly.
177 **
178 L addAll(L list)
179
180 **
181 ** Insert the item at the specified index. A negative index may be
182 ** used to access an index from the end of the list. Size is incremented
183 ** by 1. Return this. Throw IndexErr if index is out of range. Throw
184 ** ReadonlyErr if readonly.
185 **
186 L insert(Int index, V item)
187
188 **
189 ** Insert all the items in the specified list into this list at the
190 ** specified index. A negative index may be used to access an index
191 ** from the end of the list. Size is incremented by list.size. Return
192 ** this. Throw IndexErr if index is out of range. Throw ReadonlyErr
193 ** if readonly.
194 **
195 L insertAll(Int index, L list)
196
197 **
198 ** Remove the specified value from the list. The value is compared
199 ** using the == operator (shortcut for equals method). Return the
200 ** removed value and decrement size by 1. If the value is not found,
201 ** then return null. Throw ReadonlyErr if readonly.
202 **
203 V remove(V item)
204
205 **
206 ** Remove the object at the specified index. A negative index may be
207 ** used to access an index from the end of the list. Size is decremented
208 ** by 1. Return the item removed. Throw IndexErr if index is out of
209 ** range. Throw ReadonlyErr if readonly.
210 **
211 V removeAt(Int index)
212
213 **
214 ** Remove all items from the list and set size to 0. Return this.
215 ** Throw ReadonlyErr if readonly.
216 **
217 L clear()
218
219 **
220 ** Trim the capacity such that the underlying storage is optimized
221 ** for the current size. Return this. Throw ReadonlyErr if readonly.
222 **
223 L trim()
224
225 //////////////////////////////////////////////////////////////////////////
226 // Stack
227 //////////////////////////////////////////////////////////////////////////
228
229 **
230 ** Return the item at index-1, or if empty return null.
231 ** This method has the same semantics as last(). This method
232 ** is idempotent.
233 **
234 V peek()
235
236 **
237 ** Remove the last item and return it, or return null if the list
238 ** is empty. This method as the same semantics as remove(-1), with
239 ** the exception of has an empty list is handled. Throw ReadonlyErr
240 ** if readonly.
241 **
242 V pop()
243
244 **
245 ** Add the specified item to the end of the list. Return this.
246 ** This method has the same semantics as add(item). Throw ReadonlyErr
247 ** if readonly.
248 **
249 L push(V item)
250
251 //////////////////////////////////////////////////////////////////////////
252 // Iterators
253 //////////////////////////////////////////////////////////////////////////
254
255 **
256 ** Call the specified function for every item in the list starting
257 ** with index 0 and incrementing up to size-1. This method is
258 ** idempotent.
259 **
260 ** Example:
261 ** ["a", "b", "c"].each |Str s| { echo(s) }
262 **
263 Void each(|V item, Int index| c)
264
265 **
266 ** Reverse each - call the specified function for every item in
267 ** the list starting with index size-1 and decrementing down
268 ** to 0. This method is idempotent.
269 **
270 ** Example:
271 ** ["a", "b", "c"].eachr |Str s| { echo(s) }
272 **
273 Void eachr(|V item, Int index| c)
274
275 **
276 ** Return the first item in the list for which c returns true.
277 ** If c returns false for every item, then return null. This
278 ** method is idempotent.
279 **
280 ** Example:
281 ** list := [0, 1, 2, 3, 4]
282 ** list.find |Int v->Bool| { return v.toStr == "3" } -> 3
283 ** list.find |Int v->Bool| { return v.toStr == "7" } -> null
284 **
285 V find(|V item, Int index->Bool| c)
286
287 **
288 ** Return a new list containing the items for which c returns
289 ** true. If c returns false for every item, then return an
290 ** empty list. The inverse of this method is exclude(). This
291 ** method is idempotent.
292 **
293 ** Example:
294 ** list := [0, 1, 2, 3, 4]
295 ** list.findAll |Int v->Bool| { return v%2==0 } -> [0, 2, 4]
296 **
297 L findAll(|V item, Int index->Bool| c)
298
299 **
300 ** Return a new list containing all the items which are an instance
301 ** of the specified type such that item.type.fits(t) is true. Any null
302 ** items are automatically excluded. If none of the items are instance
303 ** of the specified type, then an empty list is returned. The returned
304 ** list will be a list of t. This method is idempotent.
305 **
306 ** Example:
307 ** list := ["a", 3, "foo", 5sec, null]
308 ** list.findType(Str.type) -> Str["a", "foo"]
309 **
310 L findType(Type t)
311
312 **
313 ** Return a new list containing the items for which c returns
314 ** false. If c returns true for every item, then return an
315 ** empty list. The inverse of this method is findAll(). This
316 ** method is idempotent.
317 **
318 ** Example:
319 ** list := [0, 1, 2, 3, 4]
320 ** list.exclude |Int v->Bool| { return v%2==0 } -> [1, 3]
321 **
322 L exclude(|V item, Int index->Bool| c)
323
324 **
325 ** Return true if c returns true for any of the items in
326 ** the list. If the list is empty, return false. This method
327 ** is idempotent.
328 **
329 ** Example:
330 ** list := ["ant", "bear"]
331 ** list.any |Str v->Bool| { return v.size >= 4 } -> true
332 ** list.any |Str v->Bool| { return v.size >= 5 } -> false
333 **
334 Bool any(|V item, Int index->Bool| c)
335
336 **
337 ** Return true if c returns true for all of the items in
338 ** the list. If the list is empty, return true. This method
339 ** is idempotent.
340 **
341 ** Example:
342 ** list := ["ant", "bear"]
343 ** list.all |Str v->Bool| { return v.size >= 3 } -> true
344 ** list.all |Str v->Bool| { return v.size >= 4 } -> false
345 **
346 Bool all(|V item, Int index->Bool| c)
347
348 **
349 ** Append to acc the result of calling c for every item in
350 ** this list. Return acc. This method is idempotent.
351 **
352 ** Example:
353 ** list := [3, 4, 5]
354 ** list.map(Int[,]) |Int v->Obj| { return v*2 } -> [6, 8, 10]
355 **
356 List map(List acc, |V item, Int index->Obj| c)
357
358 **
359 ** Reduce is used to iterate through every item in the list
360 ** to reduce the list into a single value called the reduction.
361 ** The initial value of the reduction is passed in as the init
362 ** parameter, then passed back to the closure along with each
363 ** item. This method is idempotent.
364 **
365 ** Example:
366 ** list := [1, 2, 3]
367 ** list.reduce(0) |Obj r, Int v->Obj| { return (Int)r + v } -> 6
368 **
369 Obj reduce(Obj init, |Obj reduction, V item, Int index->Obj| c)
370
371 **
372 ** Return the minimum value of the list. If c is provided, then it
373 ** implements the comparator returning -1, 0, or 1. If c is null
374 ** then the <=> operator is used (shortcut for compare method). If
375 ** the list is empty, return null. This method is idempotent.
376 **
377 ** Example:
378 ** list := ["albatross", "dog", "horse"]
379 ** list.min -> "albatross"
380 ** list.min |Str a, Str b->Int| { return a.size <=> b.size } -> "dog"
381 **
382 V min(|V a, V b->Int| c := null)
383
384 **
385 ** Return the maximum value of the list. If c is provided, then it
386 ** implements the comparator returning -1, 0, or 1. If c is null
387 ** then the <=> operator is used (shortcut for compare method). If
388 ** the list is empty, return null. This method is idempotent.
389 **
390 ** Example:
391 ** list := ["albatross", "dog", "horse"]
392 ** list.max -> "horse"
393 ** list.max |Str a, Str b->Int| { return a.size <=> b.size } -> "albatross"
394 **
395 V max(|V a, V b->Int| c := null)
396
397 **
398 ** Returns a new list with all duplicate items removed such that the
399 ** resulting list is a proper set. Duplicates are detected using hash()
400 ** and the == operator (shortcut for equals method). This method is
401 ** idempotent.
402 **
403 ** Example:
404 ** ["a", "a", "b", "c", "b", "b"].unique -> ["a", "b", "c"]
405 **
406 L unique()
407
408 **
409 ** Return a new list which is the union of this list and the given list.
410 ** The union is defined as the unique items which are in *either* list.
411 ** The resulting list is ordered first by this list's order, and secondarily
412 ** by that's order. The new list is guaranteed to be unique with no duplicate
413 ** values. Equality is determined using hash() and the == operator
414 ** (shortcut for equals method). This method is idempotent.
415 **
416 ** Example:
417 ** [1, 2].union([3, 2]) -> [1, 2, 3]
418 **
419 L union(L that)
420
421 **
422 ** Return a new list which is the intersection of this list and the
423 ** given list. The intersection is defined as the unique items which
424 ** are in *both* lists. The new list will be ordered according to this
425 ** list's order. The new list is guaranteed to be unique with no duplicate
426 ** values. Equality is determined using hash() and the == operator
427 ** (shortcut for equals method). This method is idempotent.
428 **
429 ** Example:
430 ** [0, 1, 2, 3].intersection([5, 3, 1]) -> [1, 3]
431 ** [0, null, 2].intersection([null, 0, 1, 2, 3]) -> [0, null, 2]
432 **
433 L intersection(L that)
434
435 //////////////////////////////////////////////////////////////////////////
436 // Utils
437 //////////////////////////////////////////////////////////////////////////
438
439 **
440 ** Perform an in-place sort on this list. If a method is provided
441 ** it implements the comparator returning -1, 0, or 1. If the
442 ** comparator method is null then sorting is based on the
443 ** value's <=> operator (shortcut for compare method). Return this.
444 ** Throw ReadonlyErr if readonly.
445 **
446 ** Example:
447 ** s := ["candy", "ate", "he"]
448 **
449 ** s.sort
450 ** // s now evaluates to [ate, candy, he]
451 **
452 ** s.sort |Str a, Str b->Int| { return a.size <=> b.size }
453 ** // s now evaluates to ["he", "ate", "candy"]
454 **
455 L sort(|V a, V b->Int| c := null)
456
457 **
458 ** Reverse sort - perform an in-place reverse sort on this list. If
459 ** a method is provided it implements the comparator returning -1,
460 ** 0, or 1. If the comparator method is null then sorting is based
461 ** on the items <=> operator (shortcut for compare method). Return
462 ** this. Throw ReadonlyErr if readonly.
463 **
464 ** Example:
465 ** [3, 2, 4, 1].sortr -> [4, 3, 2, 1]
466 **
467 L sortr(|V a, V b->Int| c := null)
468
469 **
470 ** Reverse the order of the items of this list in-place. Return this.
471 ** Throw ReadonlyErr if readonly.
472 **
473 ** Example:
474 ** [1, 2, 3, 4].sort -> [4, 3, 2, 1]
475 **
476 L reverse()
477
478 **
479 ** Swap the items at the two specified indexes. Negative indexes may
480 ** used to access an index from the end of the list. Return this.
481 ** Throw ReadonlyErr if readonly.
482 **
483 L swap(Int indexA, Int indexB)
484
485 //////////////////////////////////////////////////////////////////////////
486 // Conversion
487 //////////////////////////////////////////////////////////////////////////
488
489 **
490 ** Return a string representation the list. This method is idempotent.
491 **
492 override Str toStr()
493
494 **
495 ** Return a string by concatenating each item's toStr result
496 ** using the the specified separator string. If c is non-null
497 ** then it is used to format each item into a string, otherwise
498 ** Obj.toStr is used. This method is idempotent.
499 **
500 ** Example:
501 ** ["a", "b", "c"].join -> "abc"
502 ** ["a", "b", "c"].join("-") -> "a-b-c"
503 ** ["a", "b", "c"].join("-") |Str s->Str| { return "($s)" } -> "(a)-(b)-(c)"
504 **
505 Str join(Str separator := "", |V item, Int index->Str| c := null)
506
507 // TODO
508 // flatten, fill, binarySearch
509
510 //////////////////////////////////////////////////////////////////////////
511 // Readonly
512 //////////////////////////////////////////////////////////////////////////
513
514 **
515 ** Return if this List is readonly. A readonly List is guaranteed to
516 ** be immutable (although its items may be mutable themselves). Any
517 ** attempt to modify a readonly List will result in ReadonlyErr. Use
518 ** rw() to get a read-write List from a readonly List. Methods
519 ** documented as idempotent may be used safely with a readonly List.
520 ** This method is idempotent.
521 **
522 Bool isRO()
523
524 **
525 ** Return if this List is read-write. A read-write List is mutable
526 ** and may be modified. Use ro() to get a readonly List from a
527 ** read-write List. This method is idempotent.
528 **
529 Bool isRW()
530
531 **
532 ** Get a readonly, immutable List instance with the same contents
533 ** as this List (although the items may be mutable themselves). If
534 ** this List is already readonly, then return this. Only methods
535 ** documented as idempotent may be used safely with a readonly List,
536 ** all others will throw ReadonlyErr. This method is idempotent.
537 ** See isImmutable and toImmutable for deep immutability.
538 **
539 L ro()
540
541 **
542 ** Get a read-write, mutable List instance with the same contents
543 ** as this List. If this List is already read-write, then return this.
544 ** This method is idempotent.
545 **
546 L rw()
547
548 **
549 ** Return an immutable List which returns true for Obj.isImmtable.
550 ** If this List is already immutable, then return this. This method
551 ** is effectively a "deep ro()" which guarantees that if any items
552 ** are Lists or Maps, then they are made immutable by recursively calling
553 ** toImmutable. All other items must return true for Obj.isImmutable,
554 ** otherwise NotImmutableErr is thrown. This method must be used
555 ** whenever setting a const List field. This method is idempotent.
556 **
557 L toImmutable()
558
559 }