"""Represents a collection in which every element has a unique non-negative integer index. A `List` is a `Collection` of its elements, and a `Correspondence` from indices to elements. 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: value char = "hello world"[index]; if (exists char) { /*do something*/ } else { /*out of bounds*/ } To iterate the indexes of a `List`, use the following idiom: for (i->char in "hello world".indexed) { ... }""" see (`interface Sequence`, `interface Empty`, `class Array`) shared interface List<out Element> satisfies Collection<Element> & Correspondence<Integer,Element> & Ranged<Integer,List<Element>> & Cloneable<List<Element>> { "The index of the last element of the list, or null if the list is empty." see (`value List.size`) shared formal Integer? lastIndex; "The number of elements in this sequence, always `sequence.lastIndex+1`." see (`value List.lastIndex`) shared actual default Integer size => (lastIndex else -1) + 1; shared actual default Boolean shorterThan(Integer length) => size<length; shared actual default Boolean longerThan(Integer length) => size>length; "The rest of the list, without the first element." shared actual formal List<Element> rest; "Determines if the given index refers to an element of this sequence, that is, if `index<=sequence.lastIndex`." shared actual default Boolean defines(Integer index) => index <= (lastIndex else -1); "Returns the element of this sequence with the given index, or `null` if the given index is past the end of the sequence, that is, if `index>sequence.lastIndex`. The first element of the sequence has index `0`." shared actual formal Element? get(Integer index); shared actual default Iterator<Element> iterator() { object listIterator satisfies Iterator<Element> { variable Integer index = 0; shared actual Element|Finished next() { if (index <= (lastIndex else -1)) { assert (is Element elem = outer.get(index++)); return elem; } else { return finished; } } } return listIterator; } "Reverse this list, returning a new list." shared formal List<Element> reversed; "Two `List`s are considered equal iff they have the same `size` and _entry sets_. The entry set of a list `l` is the set of elements of `l.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." shared actual default Boolean equals(Object that) { if (is List<Anything> that) { if (that.size==size) { for (i in 0..size-1) { value x = this[i]; value y = that[i]; if (exists x) { if (exists y) { if (x!=y) { return false; } } else { return false; } } else if (exists y) { return false; } } else { return true; } } } 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 default actual Element? findLast( Boolean selecting(Element elem)) { if (exists l=lastIndex) { variable value index = l; while (index >= 0) { if (exists elem = this[index--]) { if (selecting(elem)) { return elem; } } } } return null; } "Returns the first element of this `List`, if any." shared actual default Element? first => this[0]; "Returns the last element of this `List`, if any." shared actual default Element? last { if (exists i = lastIndex) { return this[i]; } else { return null; } } "Returns a new `List` that starts with the specified element, followed by the elements of this `List`." see (`function following`) shared default [Element|Other+] withLeading<Other>( "The first element of the resulting sequence." Other element) { value sb = SequenceBuilder<Element|Other>(); sb.append(element); if (!empty) { sb.appendAll(this); } assert (nonempty seq=sb.sequence); return seq; } "Returns a new `List` that contains the specified element appended to the end of the elements of this `List`." shared default [Element|Other+] withTrailing<Other>( "The last element of the resulting sequence." Other element) { value sb = SequenceBuilder<Element|Other>(); if (!empty) { sb.appendAll(this); } sb.append(element); assert (nonempty seq=sb.sequence); return seq; } "Determine if the given list occurs at the start of this list." shared default Boolean startsWith(List<Anything> sublist) => includesAt(0, sublist); "Determine if the given list occurs at the end of this list." shared default Boolean endsWith(List<Anything> sublist) => includesAt(size-sublist.size, sublist); "Determine if the given list occurs at the given index of this list." shared default Boolean includesAt( "The index at which this list might occur" Integer index, List<Anything> sublist) { for (i in 0:sublist.size) { value x = this[index+i]; value y = sublist[i]; if (exists x) { if (exists y) { if (x!=y) { return false; } } else { return false; } } else if (exists y) { return false; } } else { return true; } } "Determine if the given list occurs at some index in this list." shared default Boolean includes(List<Anything> sublist) { for (index in 0:size) { if (includesAt(index,sublist)) { return true; } } return false; } "The indexes in this list at which the given list occurs." shared default {Integer*} inclusions(List<Anything> sublist) => { for (index in 0:size) if (includesAt(index,sublist)) index }; "The first index in this list at which the given list occurs." shared default Integer? firstInclusion(List<Anything> sublist) { for (index in 0:size) { if (includesAt(index,sublist)) { return index; } } else { return null; } } "The last index in this list at which the given list occurs." shared default Integer? lastInclusion(List<Anything> sublist) { for (index in (0:size).reversed) { if (includesAt(index,sublist)) { return index; } } else { return null; } } "Determines if the given value occurs at the given index in this list." shared default Boolean occursAt(Integer index, Anything element) { value elem = this[index]; if (exists element) { if (exists elem) { return elem==element; } else { return false; } } else { return !elem exists; } } "Determines if the given value occurs as an element in this list." shared default Boolean occurs(Anything element) { for (index in 0:size) { if (occursAt(index,element)) { return true; } } return false; } "Determines if this list contains the given value. Equivalent to `occurs()`." see (`function occurs`) shared actual default Boolean contains(Object element) => occurs(element); "The indexes in this list at which the given element occurs." shared default {Integer*} occurrences(Anything element) => { for (index in 0:size) if (occursAt(index,element)) index }; "The first index in this list at which the given element occurs." shared default Integer? firstOccurrence(Anything element) { for (index in 0:size) { if (occursAt(index,element)) { return index; } } else { return null; } } "The last index in this list at which the given element occurs." shared default Integer? lastOccurrence(Anything element) { for (index in (0:size).reversed) { if (occursAt(index,element)) { return index; } } else { return null; } } "The indexes in this list for which the element satisfies the given predicate." shared default {Integer*} indexes( "The predicate the indexed elements must satisfy" Boolean selecting(Element element)) => { for (index in 0:size) //TODO: fix this awful hack if (selecting(this[index] else nothing)) index }; "Trim the elements satisfying the given predicate function from the start and end of this list, returning a list no longer than this list." shared default List<Element> trim(Boolean trimming(Element elem)) { if (exists l=lastIndex) { variable Integer from=-1; variable Integer to=-1; for (index in 0..l) { if (!trimming(this[index] else nothing)) { from = index; break; } } else { return []; } for (index in l..0) { if (!trimming(this[index] else nothing)) { to = index; break; } } else { return []; } return this[from..to]; } else { return []; } } "Trim the elements satisfying the given predicate function from the start of this list, returning a list no longer than this list." shared default List<Element> trimLeading(Boolean trimming(Element elem)) { if (exists l=lastIndex) { for (index in 0..l) { if (!trimming(this[index] else nothing)) { return this[index..l]; } } } return []; } "Trim the elements satisfying the given predicate function from the end of this list, returning a list no longer than this list." shared default List<Element> trimTrailing(Boolean trimming(Element elem)) { if (exists l=lastIndex) { for (index in l..0) { if (!trimming(this[index] else nothing)) { return this[0..index]; } } } return []; } "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." see (`function List.terminal`) shared default List<Element> initial(Integer length) => this[0:length]; "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." see (`function List.initial`) shared default List<Element> terminal(Integer length) { if (exists l = lastIndex, length>0) { return this[l-length+1..l]; } else { return []; } } /*"Select the elements between the given indices. If the start index is the same as the end index, return a list with a single element. If the start index is larger than the end index, return the elements in the reverse order from the order in which they appear in this list. If both the start index and the end index are larger than the last index in the list, return an empty list. Otherwise, if the last index is larger than the last index in the list, return all elements from the start index to last element of the list." shared actual formal List<Element> span(Integer from, Integer? to); "Returns a list containing the elements beginning from the given index, with the given length." shared actual formal List<Element> segment(Integer from, Integer length);*/ }