"""A _tuple_ is a typed linked list. Each instance of 
   `Tuple` represents the value and type of a single link.
   The attributes `first` and `rest` allow us to retrieve
   a value form the list without losing its static type 
   information.
   
       value point = Tuple(0.0, Tuple(0.0, Tuple("origin")));
       Float x = point.first;
       Float y = point.rest.first;
       String label = point.rest.rest.first;
   
   Usually, we abbreviate code involving tuples.
   
       [Float,Float,String] point = [0.0, 0.0, "origin"];
       Float x = point[0];
       Float y = point[1];
       String label = point[2];
   
   A list of types enclosed in brackets is an abbreviated 
   tuple type. An instance of `Tuple` may be constructed 
   by surrounding a value list in brackets:
   
       [String,String] words = ["hello", "world"];
   
   The index operator with a literal integer argument is a 
   shortcut for a chain of evaluations of `rest` and 
   `first`. For example, `point[1]` means `point.rest.first`.
   
   A _terminated_ tuple type is a tuple where the type of
   the last link in the chain is `Empty`. An _unterminated_ 
   tuple type is a tuple where the type of the last link
   in the chain is `Sequence` or `Sequential`. Thus, a 
   terminated tuple type has a length that is known
   statically. For an unterminated tuple type only a lower
   bound on its length is known statically.
   
   Here, `point` is an unterminated tuple:
   
       String[] labels = ... ;
       [Float,Float,String*] point = [0.0, 0.0, *labels];
       Float x = point[0];
       Float y = point[1];
       String? firstLabel = point[2];
       String[] allLabels = point[2...];"""
by ("Gavin")
shared final class Tuple<out Element, out First, out Rest=[]>
            (first, rest)
        extends Object()
        satisfies [Element+] & 
                  Cloneable<Tuple<Element,First,Rest>>
        given First satisfies Element
        given Rest satisfies Element[] {
    
    "The first element of this tuple."
    shared actual First first;
    
    "A tuple with the elements of this tuple, except
     for the first element."
    shared actual Rest rest;
    
    size => 1 + rest.size;
    
    shared actual Element? get(Integer index) {
        switch (index<=>0)
        case (smaller) { return null; }
        case (equal) { return first; }
        case (larger) { return rest[index-1]; }
    }
    
    shared actual Integer lastIndex {
        if (exists restLastIndex = rest.lastIndex) {
            return restLastIndex+1;
        }
        else {
            return 0;
        }
    }
    
    shared actual Element last {
        if (nonempty rest) {
            return rest.last;
        }
        else {
            return first;
        }
    }
    
    shared actual Element[] segment(Integer from, Integer length) {
        if(length <= 0){
            return [];
        }
        Integer realFrom = from < 0 then 0 else from;
        if (realFrom==0) {
            return length==1 then [first]
                else rest[0:length+realFrom-1]
                        .withLeading(first);
        }
        return rest[realFrom-1:length];
    }
    
    shared actual Element[] span(Integer from, Integer end) {
        if (from<0 && end<0) { return []; }
        Integer realFrom = from < 0 then 0 else from;
        Integer realEnd = end < 0 then 0 else end;
        return realFrom<=realEnd then this[from:realEnd-realFrom+1] 
                else this[realEnd:realFrom-realEnd+1].reversed.sequence;
    }
    
    spanTo(Integer to) => to<0 then [] else span(0, to);
    
    spanFrom(Integer from) => span(from, size);
    
    clone => this;
    
    reversed => rest.reversed.withTrailing(first);
    
    shared actual Iterator<Element> iterator() {
        object iterator satisfies Iterator<Element> {
            variable Element[] current = outer;
            shared actual Element|Finished next() {
                if (nonempty c = current) {
                    current = c.rest;
                    return c.first;
                }
                else {
                    return finished;
                }
            } 
        }
        return iterator;
    }
    
    shared actual Boolean contains(Object element) {
        if (exists first, first==element) {
            return true;
        }
        else {
            return element in rest;
        }
    }
    
    "Returns a new tuple that starts with the specified
     element, followed by the elements of this tuple."
    shared actual 
    Tuple<Element|Other,Other,Tuple<Element,First,Rest>> 
    withLeading<Other>(
            "The first element of the resulting tuple."
            Other element) => Tuple(element, this);
    
}