"""A collection in which every element has a unique non-negative integer index. The elements of a nonempty list are indexed starting with `0` at the [[first]] element of the list, and ending with the index [[lastIndex]] at the [[last]] element of the list. - For any nonempty list, `lastIndex==size-1`. - For an empty list, `size==0` and the `lastIndex` is `null`. Thus, the range of indexes of the list is formed by the expression `0:list.size`. A `List` is a [[Collection]] of its elements, and a [[Correspondence]] from indexes to elements. Every list has a well-defined and stable iteration order. An [[iterator]] of a nonempty list is required to return the elements of the list in order of increasing index, beginning with the element at index `0`, and ending with the element at index `lastIndex`. Thus, every iterator of an immutable list produces exactly the same elements in exactly the same order. Direct access to a list element by index produces a value of optional type. The following idiom may be used instead of upfront bounds-checking, as long as the list element type is a non-`null` type: if (exists char = "hello world"[index]) { //do something with char } else { //out of bounds } When an algorithm guarantees that a list contains a given index, the following idiom may be used: assert (exists char = "hello world"[index]); //do something with char To iterate the indexes of a `List`, use the following idiom: for (i->char in "hello world".indexed) { ... } [[Strings|String]], [[sequences|Sequential]], [[tuples|Tuple]], and [[arrays|Array]] are all `List`s, and are all of fixed length. Variable-length mutable `List`s are also possible.""" see (`interface Sequence`, `interface Empty`, `class Array`) tagged("Collections") shared interface List<out Element=Anything> satisfies Collection<Element> & Correspondence<Integer,Element> & Ranged<Integer,Element,List<Element>> { "The first element of this `List`, if any." shared actual default Element? first => getFromFirst(0); "The last element of this `List`, if any." shared actual default Element? last => getFromLast(0); "Returns the element of this list with the given [[index]] if the index refers to an element of this list, that is, if `0<=index<=list.lastIndex`, or `null` otherwise. The first element of the list has index `0`, and the last element has index [[lastIndex]]." shared actual Element? get(Integer index) => getFromFirst(index); "Returns the element of this list with the given [[index]] if the index refers to an element of this list, that is, if `0<=index<=list.lastIndex`, or `null` otherwise. The first element of the list has index `0`, and the last element has index [[lastIndex]]." see (`function getFromLast`) shared actual formal Element? getFromFirst(Integer index); "Returns the element of this list with the given [[index]], where the list is indexed from the _end_ of the list instead of from the start, if the index refers to an element of this list, or `null` otherwise. The last element of the list has index `0`, and the first element has index [[lastIndex]]." since("1.1.0") shared default Element? getFromLast(Integer index) => getFromFirst(size-1-index); Element getElement(Integer index) { if (exists element = getFromFirst(index)) { return element; } else { assert (is Element null); return null; } } "The index of the last element of the list, or `null` if the list is empty. Always `size>0 then size-1`." see (`value List.size`) shared formal Integer? lastIndex; "The number of elements in this list, always `1 + (lastIndex else -1)`." see (`value List.lastIndex`) shared actual default Integer size => 1 + (lastIndex else -1); "Determines if the given index refers to an element of this list, that is, if `0<=index<=list.lastIndex`." shared actual default Boolean defines(Integer index) => 0 <= index < size; "Determines if this list contains the given value. Returns `true` for every element of this list." shared actual default Boolean contains(Object element) //TODO: delete this unnecessary refinement => super.contains(element); "The rest of the list, without the first element. This is a lazy operation returning a view of this list." shared actual default List<Element> rest => size>1 then Sublist(1,size-1) else []; //TODO: refine type of List.exceptLast //shared actual default List<Element> exceptLast // => size>1 then Sublist(0, size-2) else []; "A list containing all indexes of this list. This is a lazy operation returning a view of this list." see (`function indexes`) shared actual default List<Integer> keys => Indexes(); "A list containing the elements of this list in reverse order to the order in which they occur in this list. For every `index` of a reversed `list`: list.reversed[index]==list[size-1-index] This is a lazy operation returning a view of this list." shared default List<Element> reversed => Reversed(); "A shallow copy of this list, that is, a list with the same elements as this list, which do not change if the elements of this list change." shared actual default List<Element> clone() => sequence(); shared actual default Iterator<Element> iterator() { if (size>0) { return object satisfies Iterator<Element> { variable Integer index = 0; value size = outer.size; next() => index>=size then finished else getElement(index++); string => outer.string + ".iterator()"; }; } else { return emptyIterator; } } "Two `List`s are considered equal iff they have the same `size` and _entry sets_. The entry set of a list `list` is the set of elements of `list.indexed`. This definition is equivalent to the more intuitive notion that two lists are equal iff they have the same `size` and for every index either: - the lists both have the element `null`, or - the lists both have a non-null element, and the two elements are equal. As a special exception, a [[String]] is not equal to any list which is not also a [[String]]." shared actual default Boolean equals(Object that) { if (is String that) { return false; } else if (is List<> that) { if (this.size != that.size) { return false; } value thisIterator = this.iterator(); value thatIterator = that.iterator(); for (_ in 0:size) { value thisElement = thisIterator.next(); value thatElement = thatIterator.next(); if (exists thisElement) { if (!exists thatElement) { return false; } else if (thisElement != thatElement) { return false; } } else if (thatElement exists) { return false; } } else { return true; } } else { return false; } } shared actual default Integer hash { variable value hash = 1; for (elem in this) { hash *= 31; if (exists elem) { hash += elem.hash; } } return hash; } shared actual default Boolean shorterThan(Integer length) => size<length; shared actual default Boolean longerThan(Integer length) => size>length; "A list containing the elements of this list repeated the [[given number of times|times]], or an empty list if `times<=0`. For every `index` of a repeated `list`: list.repeat(n)[index]==list[index%n] This is a lazy operation returning a view of this list." shared actual default List<Element> repeat(Integer times) => switch (times<=>1) case (smaller) [] case (equal) this case (larger) Repeat(times); shared default actual Element? find( Boolean selecting(Element&Object elem)) { variable value index = 0; while (index<size) { if (exists elem = getFromFirst(index++)) { if (selecting(elem)) { return elem; } } } return null; } shared default actual Element? findLast( Boolean selecting(Element&Object elem)) { variable value index = size-1; while (index >= 0) { if (exists elem = getFromFirst(index--), selecting(elem)) { return elem; } } return null; } "A sublist of this list, starting at the element with the given [[index|from]]. This is a lazy operation, returning a view of this list." see (`function skip`, `function sublistTo`) since("1.1.0") shared default List<Element> sublistFrom(Integer from) => sublist(from, size-1); "A sublist of this list, ending at the element with the given [[index|to]]. This is a lazy operation, returning a view of this list." see (`function take`, `function initial`, `function sublistFrom`) since("1.1.0") shared default List<Element> sublistTo(Integer to) => sublist(0, to); "A sublist of this list, starting at the element with index [[from]], ending at the element with the index [[to]]. This is a lazy operation, returning a view of this list." see(`function sublistTo`, `function sublistFrom`) since("1.1.0") shared default List<Element> sublist(Integer from, Integer to) => from<=to && from<size && to>=0 then Sublist { from = Integer.largest(0, from); to = Integer.smallest(size-1, to); } else []; "Return a list formed by patching the given [[list]] in place of a segment of this list identified by the given [[starting index|from]] and [[length]]. This is a lazy operations, returning a view over this list and the given list. Four special cases are interesting: - If `length==0`, the patched list has the given values \"inserted\" into this list at the given index `from`. - If the given `list` is empty, the patched list has the measure of this list identified by `from:length` \"deleted\". - If `from==size`, the patched list is formed by appending the given list. - If `from==0`, the patched list is formed by prepending the given list. For example: - `(-2..2).patch([], 1, 3)` produces the list `{-2, 2}`, - `[-2, 2].patch(-1..1, 1)` produces the list `{-2, -1, 0, 1, 2}`, and - `0:3.patch(2..0)` produces the list `{0, 1, 2, 2, 1, 0}`. Finally, to patch a single element, leaving the `size` of the list unchanged, explicitly specify `length==1`: - `[0, 1, 0, 1].patch([-1], 2, 1)` produces the list `{0, 1, -1, 1}`. If `length<0`, or if `from` is outside the range `0..size`, return this list." since("1.1.0") shared default List<Element|Other> patch<Other>( "The list of new elements." List<Other> list, "The index at which the elements will occur, and the start index of the segment to replace." Integer from=size, "The length of the segment to replace." Integer length=0) => length>=0 && 0<=from<=size then Patch(list, from, length) else this; "Determine if the given [[list|sublist]] occurs at the start of this list." see (`function endsWith`) shared default Boolean startsWith(List<> sublist) => !shorterThan(sublist.size) && everyPair<Element,Anything>( (first, second) => if (exists first, exists second) then first==second else first exists == second exists, this, sublist); "Determine if the given [[list|sublist]] occurs at the end of this list." see (`function startsWith`) shared default Boolean endsWith(List<> sublist) => !shorterThan(sublist.size) && everyPair<Element,Anything>( (first, second) => if (exists first, exists second) then first==second else first exists == second exists, skip(size-sublist.size), sublist); "The indexes in this list for which the element is not null and satisfies the given [[predicate function|selecting]]." see (`function locations`) since("1.1.0") shared default {Integer*} indexesWhere( "The predicate function the indexed elements must satisfy." Boolean selecting(Element&Object element)) => { for (index in 0:size) if (exists element=getFromFirst(index), selecting(element)) index }; "The first index in this list for which the element is not null and satisfies the given [[predicate function|selecting]]." see (`function locate`) since("1.1.0") shared default Integer? firstIndexWhere( "The predicate function the indexed elements must satisfy." Boolean selecting(Element&Object element)) { variable value index = 0; while (index<size) { if (exists element=getFromFirst(index), selecting(element)) { return index; } index++; } return null; } "The last index in this list for which the element is not null and satisfies the given [[predicate function|selecting]]." see (`function locateLast`) since("1.1.0") shared default Integer? lastIndexWhere( "The predicate function the indexed elements must satisfy." Boolean selecting(Element&Object element)) { variable value index = size; while (index>0) { index--; if (exists element=getFromFirst(index), selecting(element)) { return index; } } return null; } "Trim the elements satisfying the given [[predicate function|trimming]], along with any null elements, from the start and end of this list, returning a list no longer than this list. This is an eager operation." shared default List<Element> trim( "The predicate function that the trimmed elements satisfy." Boolean trimming(Element&Object elem)) { if (size>0) { value end = size-1; variable Integer from=-1; variable Integer to=-1; for (index in 0..end) { if (exists elem=getFromFirst(index), !trimming(elem)) { from = index; break; } } else { return []; } for (index in end..0) { if (exists elem=getFromFirst(index), !trimming(elem)) { to = index; break; } } else { return []; } return this[from..to]; } else { return []; } } "Trim the elements satisfying the given [[predicate function|trimming]], along with any null elements, from the start of this list, returning a list no longer than this list. This is an eager operation." shared default List<Element> trimLeading( "The predicate function that the trimmed elements satisfy." Boolean trimming(Element&Object elem)) { if (size>0) { value end = size-1; for (index in 0..end) { if (exists elem=getFromFirst(index), !trimming(elem)) { return this[index..end]; } } } return []; } "Trim the elements satisfying the given [[predicate function|trimming]], along with any null elements, from the end of this list, returning a list no longer than this list. This is an eager operation." shared default List<Element> trimTrailing( "The predicate function that the trimmed elements satisfy." Boolean trimming(Element&Object elem)) { if (size>0) { value end = size-1; for (index in end..0) { if (exists elem=getFromFirst(index), !trimming(elem)) { return this[0..index]; } } } return []; } "Return two lists, the first containing the elements that occur before the given [[index]], the second with the elements that occur after the given `index`. If the given `index` is outside the range of indexes of this list, one of the returned lists will be empty. For any `list`, and for any integer `index`: list.slice(index) == [list[...index-1], list[index...]] This is an eager operation." since("1.1.0") shared default List<Element>[2] slice(Integer index) => [this[...index-1], this[index...]]; "Select the first elements of this list, returning a list no longer than the given length. If this list is shorter than the given length, return this list. Otherwise return a list of the given length. If `length<=0` return an empty list. For any `list`, and for any integer `length`: list.initial(length) == list[...length-1] == list[0:length] This is an eager operation." see (`function terminal`, `function sublistTo`, `function take`) shared default List<Element> initial(Integer length) => this[...length-1]; "Select the last elements of the list, returning a list no longer than the given length. If this list is shorter than the given length, return this list. Otherwise return a list of the given length. For any `list`, and for any integer `length`: list.terminal(length) == list[size-length...] This is an eager operation." see (`function initial`) shared default List<Element> terminal(Integer length) => this[size-length...]; shared actual default List<Element> span(Integer from, Integer to) { if (size>0) { value end = size-1; if (from <= to) { return if (to >= 0 && from <= end) then ArraySequence(Array(sublist(from,to))) else []; } else { return if (from >= 0 && to <= end) then ArraySequence(Array(sublist(to,from).reversed)) else []; } } else { return []; } } shared actual default List<Element> spanFrom(Integer from) => from<size then span(from, size-1) else []; shared actual default List<Element> spanTo(Integer to) => to>=0 then span(0, to) else []; shared actual default List<Element> measure(Integer from, Integer length) => length > 0 then span(from, from+length-1) else []; "A sequence containing the results of applying the given mapping to the elements of this list." shared default actual [Result+]|[] collect<Result>( "The transformation applied to the elements." Result collecting(Element element)) { if (empty) { return []; } else { object list extends Object() satisfies List<Result> { lastIndex => outer.lastIndex; size = outer.size; getFromFirst(Integer index) => if (0<=index<size) then collecting(outer.getElement(index)) else null; } return ArraySequence(Array(list)); } } class Indexes() extends Object() satisfies List<Integer> { lastIndex => outer.lastIndex; getFromFirst(Integer index) => defines(index) then index; clone() => 0:size; span(Integer from, Integer to) => clone()[from..to]; string => if (exists endIndex=lastIndex) then "{ 0, ... , ``endIndex`` }" else "{}"; iterator() => object satisfies Iterator<Integer> { variable value i=0; next() => i<size then i++ else finished; string => "``outer.string``.iterator()"; }; } class Sublist(Integer from, Integer to) extends Object() satisfies List<Element> { assert (from>=0, to>=0, from<=to); first => outer[from]; last => outer[to]; size => to-from+1; lastIndex => to-from; rest => size == 1 then [] else outer.Sublist(from+1, to); exceptLast => size == 1 then [] else outer.Sublist(from, to-1); getFromFirst(Integer index) => if (0<=index<=to-from) then outer.getFromFirst(index+from) else null; iterator() => let (o = outer) object satisfies Iterator<Element> { variable value i = from; next() => if (i <= to) then o.getElement(i++) else finished; string => "``outer.string``.iterator()"; }; clone() => outer[from..to]; sublist(Integer from, Integer to) => outer.sublist { from = Integer.largest(from+this.from,this.from); to = Integer.smallest(to+this.from,this.to); }; span(Integer from, Integer to) => from <= to then outer.span { from = Integer.largest(from+this.from,this.from); to = Integer.smallest(to+this.from,this.to); } else outer.span { from = Integer.smallest(from+this.from,this.to); to = Integer.largest(to+this.from,this.from); }; } class Repeat(Integer times) extends Object() satisfies List<Element> { assert (times>1); size => outer.size*times; lastIndex => let (size = this.size) (size>0 then size-1); getFromFirst(Integer index) => let (size = outer.size) if (index<size*times) then outer.getFromFirst(index%size) else null; clone() => outer.clone().Repeat(times); iterator() => CycledIterator(outer,times); string => "(``outer.string``).repeat(``times``)"; } class Patch<Other>(List<Other> list, Integer from, Integer length) extends Object() satisfies List<Element|Other> { assert (length>=0); assert (0<=from<=outer.size); value exactLength => smallest(length, outer.size-from); size => outer.size+list.size-exactLength; lastIndex => let (size = this.size) (size>0 then size-1); getFromFirst(Integer index) => if (index<from) then outer.getFromFirst(index) else if (index-from<list.size) then list.getFromFirst(index-from) else outer.getFromFirst(index-list.size+exactLength); clone() => outer.clone().Patch(list.clone(),from,exactLength); iterator() => let (iter = outer.iterator(), patchIter = list.iterator()) object satisfies Iterator<Element|Other> { variable value index = -1; shared actual Element|Other|Finished next() { if (++index==from) { for (skip in 0:exactLength) { iter.next(); } } return if (0<=index-from<list.size) then patchIter.next() else iter.next(); } string => "``outer.string``.iterator()"; }; } class Reversed() extends Object() satisfies List<Element> { lastIndex => outer.lastIndex; size => outer.size; first => outer.last; last => outer.first; reversed => outer; function outerIndex(Integer index) => size-1-index; getFromFirst(Integer index) => if (size>0) then outer.getFromFirst(outerIndex(index)) else null; span(Integer from, Integer to) => outer[outerIndex(from)..outerIndex(to)]; clone() => outer.clone().reversed; iterator() => let (outerList = outer) object satisfies Iterator<Element> { variable value index = outerIndex(0); next() => index<0 then finished else outerList.getElement(index--); string => "``outer.string``.iterator()"; }; } "Produces a list with the same indexes as this list. For every index, the element is the result of applying the given [[transformation|List.mapElements.mapping]] function to its associated element in this list. This is a lazy operation, returning a view of this list." since("1.3.0") shared default List<Result> mapElements<Result>( "The function that transforms an index/item pair of this list, producing the element of the resulting list." Result mapping(Integer index, Element item)) => object extends Object() satisfies List<Result> { shared actual Result? getFromFirst(Integer index) { if (0 <= index < size) { if (exists element = outer.getFromFirst(index)) { return mapping(index, element); } else { assert (is Element null); return mapping(index, null); } } else { return null; } } iterator() => let (it = outer.iterator()) object satisfies Iterator<Result> { variable value index = 0; next() => if (!is Finished element = it.next()) then mapping(index++, element) else finished; }; lastIndex => outer.lastIndex; size => outer.size; clone() => outer.clone().mapElements(mapping); }; }