"A nonempty, immutable sequence of values. The type
`Sequence<Element>` may be abbreviated `[Element+]`.
Given a possibly-empty sequence of type `[Element*]`, the
`if (nonempty ...)` construct, or, alternatively,
`assert (nonempty ...)`, may be used to narrow to a
sequence type to a nonempty sequence type:
[Integer*] nums = ... ;
if (nonempty nums) {
Integer first = nums.first;
Integer max = max(nums);
[Integer+] squares = nums.collect((Integer i) => i**2));
[Integer+] sorted = nums.sort(byIncreasing((Integer i) => i));
}
Operations like `first`, `max()`, `collect()`, and `sort()`,
which polymorphically produce a nonempty or non-null output
when given a nonempty input are called
_emptiness-preserving_.
`Sequence` has the following subtypes:
- [[ArraySequence]], a sequence backed by an [[Array]],
- [[Range]], an efficient representation of a sequence of
adjacent [[enumerable values|Enumerable]],
- [[Tuple]], a typed linked list, and
- [[Singleton]], a sequence of just one element."
see (`interface Empty`,
`class ArraySequence`,
`class Range`,
`class Tuple`,
`class Singleton`)
by ("Gavin")
tagged("Sequences")
shared sealed interface Sequence<out Element=Anything>
satisfies Element[] &
{Element+} {
"The first element of the sequence, that is, the element
with index `0`."
shared actual formal Element first;
"The last element of the sequence, that is, the element
with index `sequence.lastIndex`."
shared actual formal Element last;
"Returns `false`, since every `Sequence` contains at
least one element."
shared actual Boolean empty => false;
"The non-negative length of this sequence, that is, the
number of elements in this sequence."
shared actual formal Integer size;
"The index of the last element of the sequence."
see (`value size`)
shared actual default Integer lastIndex => size-1;
"An integer [[Range]] containing all indexes of this
sequence, that is, the range `0..sequence.lastIndex`."
shared actual default Range<Integer> keys => indexes();
"An integer [[Range]] containing all indexes of this
sequence, that is, the range `0..sequence.lastIndex`."
shared actual default Range<Integer> indexes()
=> 0..lastIndex;
"This nonempty sequence."
shared default actual [Element+] sequence() => this;
"The rest of the sequence, without the first element."
shared actual formal Element[] rest;
"A sequence containing the elements of this sequence in
reverse order to the order in which they occur in this
sequence."
shared default actual [Element+] reversed => Reverse();
"Produces a sequence formed by repeating the elements of
this sequence the given [[number of times|times]], or
the [[empty sequence|empty]] if `times<=0`."
shared default actual Element[] repeat(Integer times)
=> times>0 then Repeat(times) else [];
"This nonempty sequence."
shared actual default [Element+] clone() => this;
/*shared actual default Element[] repeat(Integer times) {
value resultSize = size*times;
value array = arrayOfSize(resultSize, first);
variable value i = 1;
while (i < resultSize) {
array.set(i, getElement(i%size));
}
return ArraySequence(array);
}*/
"A nonempty sequence containing the elements of this
container, sorted according to a function imposing a
partial order upon the elements."
shared default actual
[Element+] sort(
"The function comparing pairs of elements."
Comparison comparing(Element x, Element y)) {
value array = Array(this);
array.sortInPlace(comparing);
return ArraySequence(array);
}
"A nonempty sequence containing the results of applying
the given mapping to the elements of this sequence."
shared default actual
[Result+] collect<Result>(
"The transformation applied to the elements."
Result collecting(Element element)) {
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));
}
"Return a nonempty sequence containing the given
[[element]], followed by the elements of this
sequence."
shared actual default
[Other,Element+] withLeading<Other>(Other element)
=> [element, *this];
"Return a nonempty sequence containing the elements of
this sequence, followed by the given [[element]]."
shared actual default
[Element|Other+] withTrailing<Other>(Other element)
=> JoinedSequence(this, Singleton(element));
"Return a nonempty sequence containing the elements of
this sequence, followed by the given [[elements]]."
shared actual default
[Element|Other+] append<Other>(Other[] elements)
=> if (nonempty elements)
then JoinedSequence(this, elements)
else this;
"Return a nonempty sequence containing the given
[[elements]], followed by the elements of this
sequence."
shared actual default
[Element|Other+] prepend<Other>(Other[] elements)
=> if (nonempty elements)
then JoinedSequence(elements, this)
else this;
shared actual default
Boolean contains(Object element)
=> (super of List<Element>).contains(element);
shared actual default
Boolean shorterThan(Integer length)
=> (super of List<Element>).shorterThan(length);
shared actual default
Boolean longerThan(Integer length)
=> (super of List<Element>).longerThan(length);
shared default actual
Element? find(Boolean selecting(Element&Object elem))
=> (super of List<Element>).find(selecting);
shared default actual
Element? findLast(Boolean selecting(Element&Object elem))
=> (super of List<Element>).findLast(selecting);
shared actual default
[Element[],Element[]] slice(Integer index)
=> [this[...index-1], this[index...]];
shared actual default
Element[] measure(Integer from, Integer length)
=> if (length > 0)
then span(from, from + length - 1)
else [];
shared actual default
Element[] span(Integer from, Integer to) {
if (from <= to) {
return
if (to >= 0 && from <= lastIndex)
then ArraySequence(Array(sublist(from,to)))
else [];
}
else {
return
if (from >= 0 && to <= lastIndex)
then ArraySequence(Array(sublist(to,from).reversed))
else [];
}
}
shared actual default
Element[] spanFrom(Integer from) {
if (from <= 0) {
return this;
}
else if (from < size) {
return ArraySequence(Array(sublistFrom(from)));
}
else {
return [];
}
}
shared actual default
Element[] spanTo(Integer to) {
if (to >= lastIndex) {
return this;
}
else if (to >= 0) {
return ArraySequence(Array(sublistTo(to)));
}
else {
return [];
}
}
shared actual default
String string => (super of Sequential<Element>).string;
Element getElement(Integer index) {
if (exists element = getFromFirst(index)) {
return element;
}
else {
assert (is Element null);
return null;
}
}
class Reverse()
extends Object()
satisfies [Element+] {
size => outer.size;
first => outer.last;
last => outer.first;
rest => size==1 then [] else outer[size-2..0]; //TODO optimize!
reversed => outer;
getFromFirst(Integer index)
=> outer.getFromFirst(size-1-index);
measure(Integer from, Integer length)
=> if (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 (from<=endIndex)
then outer[endIndex-from..0]
else [];
spanTo(Integer to)
=> if (to>=0)
then let (endIndex = size-1)
outer[endIndex..endIndex-to]
else [];
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()";
};
}
class Repeat(Integer times)
extends Object()
satisfies [Element+] {
assert (times>0);
last => outer.last;
first => outer.first;
size => outer.size*times;
rest => sublistFrom(1).sequence(); //TODO!
getFromFirst(Integer index)
=> let (size = outer.size)
if (index<size*times)
then outer.getFromFirst(index%size)
else null;
iterator() => CycledIterator(outer,times);
}
}
"A [[nonempty sequence|Sequence]] of the given [[elements]],
or `null` if the given stream is empty. A non-null, but
possibly empty, [[sequence|Sequential]] may be obtained
using the `else` operator:
[Element*] sequenceOfElements = sequence(elements) else [];"
by ("Gavin")
see (`function Iterable.sequence`)
tagged("Sequences")
shared [Element+]|Absent sequence<Element,Absent=Null>
(Iterable<Element, Absent> elements)
given Absent satisfies Null {
if (nonempty sequence = elements.sequence()) {
return sequence;
}
else {
assert (is Absent null);
return null;
}
}
class JoinedSequence<Element>
([Element+] firstSeq, [Element+] secondSeq)
extends Object()
satisfies [Element+] {
size => firstSeq.size + secondSeq.size;
first => firstSeq.first;
last => secondSeq.last;
rest => firstSeq.rest.append(secondSeq);
getFromFirst(Integer index)
=> let (cutover = firstSeq.size)
if (index<cutover)
then firstSeq.getFromFirst(index)
else secondSeq.getFromFirst(index-cutover);
slice(Integer index)
=> if (index==firstSeq.size)
then [firstSeq, secondSeq]
else super.slice(index);
spanTo(Integer to)
=> if (to==firstSeq.size-1)
then firstSeq
else super.spanTo(to);
spanFrom(Integer from)
=> if (from==firstSeq.size)
then secondSeq
else super.spanFrom(from);
shared actual
Element[] measure(Integer from, Integer length) {
if (from==0 &&
length==firstSeq.size) {
return firstSeq;
}
else if (from==firstSeq.size &&
length>=secondSeq.size) {
return secondSeq;
}
else {
return super.measure(from, length);
}
}
shared actual
Element[] span(Integer from, Integer to) {
if (from<=0 &&
to==firstSeq.size-1) {
return firstSeq;
}
else if (from==firstSeq.size &&
to>=size-1) {
return secondSeq;
}
else {
return super.span(from, to);
}
}
iterator() => ChainedIterator(firstSeq,secondSeq);
}