"""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()";
};
}
}