"""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 indices 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 indices 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]]." 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) { for (index in 0:size) { if (exists elem = getFromFirst(index), elem==element) { return true; } } else { return false; } } "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 => Rest(1); "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; } if (is List<> that) { if (that.size==size) { for (index in 0:size) { value x = getFromFirst(index); value y = that.getFromFirst(index); if (exists x) { if (exists y) { if (x!=y) { return false; } } else { return false; } } else if (exists y) { return false; } } else { return true; } } else { return false; } } 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) => 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`) shared default List<Element> sublistFrom(Integer from) => from<=0 then this else Rest(from); "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`) shared default List<Element> sublistTo(Integer to) => to<0 then [] else Sublist(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." shared default List<Element> sublist(Integer from, Integer to) => sublistTo(to).sublistFrom(from); "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." 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) { if (sublist.size>size) { return false; } return 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) { if (sublist.size>size) { return false; } return 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`) 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`) 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`) 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 indices 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." shared default [List<Element>,List<Element>] 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) { if (from<=0) { return clone(); } else if (from<size) { return ArraySequence(Array(sublistFrom(from))); } else { return []; } } shared actual default List<Element> spanTo(Integer to) { if (to>=size-1) { return clone(); } else if (to>=0) { return ArraySequence(Array(sublistTo(to))); } else { return []; } } shared actual default List<Element> measure(Integer from, Integer length) => if (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; measure(Integer from, Integer length) => clone()[from:length]; span(Integer from, Integer to) => clone()[from..to]; spanFrom(Integer from) => clone()[from...]; spanTo(Integer to) => clone()[...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 Rest(Integer from) extends Object() satisfies List<Element> { assert (from>=0); sublistFrom(Integer from) => if (from>0) then outer.Rest(from+this.from) else this; getFromFirst(Integer index) => if (index<0) then null else outer.getFromFirst(index+from); lastIndex => let (size = outer.size-from) (size>0 then size-1); measure(Integer from, Integer length) => outer[from+this.from:length]; span(Integer from, Integer to) => outer[from+this.from..to+this.from]; spanFrom(Integer from) => outer[from+this.from...]; spanTo(Integer to) => outer[this.from..to+this.from]; clone() => outer.clone().Rest(from); iterator() => let (o = outer) object satisfies Iterator<Element> { variable value i=0; next() => if (i < outer.size) then o.getElement(from + i++) else finished; string => "``outer.string``.iterator()"; }; } class Sublist(Integer to) extends Object() satisfies List<Element> { assert (to>=0); sublistTo(Integer to) => if (to<0) then [] else if (to<this.to) then outer.Sublist(to) else this; getFromFirst(Integer index) => if (0<=index<=to) then outer.getFromFirst(index) else null; lastIndex => let (endIndex = outer.size-1) (endIndex>=0 then (endIndex<to then endIndex else to)); measure(Integer from, Integer length) => from+length-1>to then outer[from:to] else outer[from:length]; span(Integer from, Integer to) => to>this.to then outer[from..this.to] else outer[from..to]; spanFrom(Integer from) => outer[from..to]; spanTo(Integer to) => to>this.to then outer[...this.to] else outer[...to]; clone() => outer.clone().Sublist(to); iterator() => let (iter = outer.iterator()) object satisfies Iterator<Element> { variable value i=0; next() => i++>to then finished else iter.next(); string => "``outer.string``.iterator()"; }; } class Repeat(Integer times) extends Object() satisfies List<Element> { 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); size => outer.size+list.size-length; 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+length); clone() => outer.clone().Patch(list.clone(),from,length); 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:length) { 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; getFromFirst(Integer index) => if (size>0) then outer.getFromFirst(size-1-index) else null; measure(Integer from, Integer length) => if (size>0 && length>0) then let (start = size-1-from) outer[start..start-length+1] else []; span(Integer from, Integer to) => outer[to..from]; spanFrom(Integer from) => let (endIndex = size-1) if (endIndex>=0, from<=endIndex) then outer[endIndex-from..0] else []; spanTo(Integer to) => let (endIndex = size-1) if (endIndex>=0 && to>=0) then outer[endIndex..endIndex-to] else []; clone() => outer.clone().reversed; iterator() => let (outerList = outer) object satisfies Iterator<Element> { variable value index=outerList.size-1; next() => index<0 then finished else outerList.getElement(index--); string => "``outer.string``.iterator()"; }; } }