"A [[Range]] of adjacent [[Enumerable]] values generated by 
 two endpoints: [[first]] and [[last]]. The range includes 
 both endpoints, and all values falling _between_ the 
 endpoints."
by ("Gavin")
see (`class Measure`,
     `interface Enumerable`)
final class Span<Element>(first, last)
        extends Range<Element>()
        given Element satisfies Enumerable<Element> {
    
    "The start of the range."
    shared actual Element first;
    
    "The end of the range."
    shared actual Element last;
    
    shared actual String string 
            => first.string + ".." + last.string;
    
    shared actual Boolean increasing 
            = last.offsetSign(first)>=0;
    
    shared actual Boolean decreasing => !increasing;
    
    "Determines if the range is of recursive values, that 
     is, if successors wrap back on themselves. All 
     recursive ranges are [[increasing]]."
    Boolean recursive
            = first.offsetSign(first.successor)>0 &&
              last.predecessor.offsetSign(last)>0;
    
    Element next(Element x)
            => increasing then x.successor
                          else x.predecessor;
    
    Element nextStep(Element x, Integer step) 
            => increasing then x.neighbour(step) 
                          else x.neighbour(-step);
    
    Element fromFirst(Integer offset)
            => increasing then first.neighbour(offset)
                          else first.neighbour(-offset);
    
    Boolean afterLast(Element x)
            => increasing then x.offsetSign(last)>0
                          else x.offsetSign(last)<0;
    
    Boolean beforeLast(Element x)
            => increasing then x.offsetSign(last)<0
                          else x.offsetSign(last)>0;
    
    Boolean beforeFirst(Element x)
            => increasing then x.offsetSign(first)<0
                          else x.offsetSign(first)>0;
    
    Boolean afterFirst(Element x)
            => increasing then x.offsetSign(first)>0
                          else x.offsetSign(first)<0;
    
    "The nonzero number of elements in the range."
    shared actual Integer size 
            => last.offset(first).magnitude+1;
    
    shared actual Boolean longerThan(Integer length) {
        if (length<1) {
            return true;
        }
        else if (recursive) {
            return size>length;
        }
        else {
            return beforeLast(fromFirst(length-1));
        }
    }
    
    shared actual Boolean shorterThan(Integer length) {
        if (length<1) {
            return true;
        }
        else if (recursive) {
            return size<length;
        }
        else {
            return afterLast(fromFirst(length-1));
        }
    }
    
    "The index of the end of the range."
    shared actual Integer lastIndex => size-1; 
    
    "The rest of the range, without the start of the range."
    shared actual Element[] rest 
            => first==last then [] else next(first)..last;
    
    "This range in reverse, with [[first]] and [[last]]
     interchanged.
     
     For any two range endpoints, `x` and `y`: 
     
         `(x..y).reversed == y..x`
     
     except for [[recursive]] ranges, where the elements are
     evaluated and collected into a new sequence."
    //TODO: we should have a way to produce a decreasing
    //      recursive range
    shared actual [Element+] reversed
            => recursive then super.reversed
                         else last..first;
    
    "The element of the range that occurs [[index]] values 
     after the start of the range."
    shared actual Element? getFromFirst(Integer index) {
        if (index<0) {
            return null;
        }
        else if (recursive) {
            return index<size then fromFirst(index);
        }
        else {
            value result = fromFirst(index);
            return !afterLast(result) then result;
        }
    }
    
    "An iterator for the elements of the range. 
     The returned iterator produces elements from [[first]] and 
     continues producing elements until it reaches an element 
     whose `offset` from [[last] is zero."
    shared actual Iterator<Element> iterator() {
        
        object iterator 
                satisfies Iterator<Element> {
            variable Element|Finished current = first;
            shared actual Element|Finished next() {
                if (!is Finished c=current) {
                    if (c.offset(last) != 0) {
                        value result = c;
                        this.current = outer.next(c);
                        return result;
                    }
                    else {
                        value result = c;
                        this.current = finished;
                        return result;
                    }
                }
                else {
                    return current;
                }
            }
            string => "(``outer.string``).iterator()";
        }
        return iterator;
    
    }
    
    shared actual {Element+} by(Integer step) {
        "step size must be greater than zero"
        assert (step > 0);
        return step == 1 then this else By(step);
    }
    
    shared actual Span<Element> shifted(Integer shift) {
        if (shift==0) {
            return this;
        }
        else {
            value start = first.neighbour(shift);
            value end = last.neighbour(shift);
            return Span(start,end);
        }
    }
    
    shared actual Integer count(Boolean selecting(Element element)) {
        variable value element = first;
        variable value count = 0;
        while (containsElement(element)) {
            if (selecting(element)) {
                count++;
            }
            element = next(element);
        }
        return count;
    }
    
    "Determines if this range includes the given object."
    shared actual Boolean contains(Object element) {
        if (is Element element) {
            return containsElement(element);
        }
        else {
            return false;
        }
    }
    
    "Determines if this range includes the given value."
    shared actual Boolean occurs(Anything element) {
        if (is Element element) {
            return containsElement(element);
        }
        else {
            return false;
        }
    }
    
    "Determines if the range includes the given value."
    shared actual Boolean containsElement(Element x) 
            => recursive then x.offset(first) <= last.offset(first)
                         else !afterLast(x) && !beforeFirst(x);
    
    shared actual Boolean includes(List<Anything> sublist) {
        if (sublist.empty) {
            return true;
        }
        if (is Range<Element> sublist) {
            return includesRange(sublist);
        }
        else {
            return super.includes(sublist);
            /*if (is Element start = sublist.first) {
                if (decreasing
                        then start>first || start<last
                        else start<first || start>last) {
                    return false;
                }
                variable value current=start;
                for (element in sublist) {
                    if (exists element) {
                        if (element!=current ||
                            decreasing
                                then current<last
                                else current>last) {
                            return false;
                        }
                        current = next(current);
                    }
                    else {
                        return false;
                    }
                }
                else {
                    return true;
                }
             }
             else {
                return false;
             }*/
        }
    }
    
    shared actual Boolean includesRange(Range<Element> sublist) {
        switch (sublist)
        case (is Span<Element>) {
            if (recursive) {
                return sublist.first.offset(first)<size &&
                        sublist.last.offset(first)<size;
            }
            else {
                return increasing == sublist.increasing &&
                        !sublist.afterFirst(first) &&
                        !sublist.beforeLast(last);
            }
        }
        case (is Measure<Element>) {
            if (decreasing) {
                return false;
            }
            else {
                value offset = sublist.first.offset(first);
                return offset >= 0 && offset + sublist.size <= size;
            }
        }
    }
    
    shared actual Boolean equals(Object that) {
        if (is Span<Object> that) {
            //optimize for another Span
            return that.first==first && that.last==last;
        }
        else if (is Measure<Object> that) {
            return increasing && 
                    that.first == first && that.size == size;
        }
        else {
            //it might be another sort of List
            return super.equals(that);
        }
    }
    
    class By(Integer step) 
            satisfies {Element+} {
        
        size => 1 + (outer.size-1) / step;
        
        first => outer.first;
        
        string => "(``outer.string`` by ``step``)";
        
        shared actual Iterator<Element> iterator() {
            if (recursive) {
                object iterator
                        satisfies Iterator<Element> {
                    variable value count = 0;
                    variable value current = first;
                    shared actual Element|Finished next() {
                        if (++count>size) {
                            return finished;
                        }
                        else {
                            value result = current;
                            current = current.neighbour(step);
                            return result;
                        } 
                    }
                    string => "``outer.string``.iterator()";
                }
                return iterator;
            }
            else {
                object iterator 
                        satisfies Iterator<Element> {
                    variable value current = first; 
                    shared actual Element|Finished next() {
                        if (containsElement(current)) {
                            value result = current;
                            current = nextStep(current, step);
                            return result;
                        }
                        else {
                            return finished;
                        }
                    }
                    string => "``outer.string``.iterator()";
                }
                return iterator;
            }
        }
        
    }
    
    shared actual [Element*] measure(Integer from, Integer length) 
            => length<=0 then [] else span(from, from+length-1);
    
    shared actual [Element*] span(Integer from, Integer to) {
        if (from<=to) {
            if (to<0 || !longerThan(from)) {
                return [];
            }
            else {
                return (this[from] else first)..(this[to] else last);
            }
        }
        else {
            if (from<0 || !longerThan(to)) {
                return [];
            }
            else {
                value range = (this[to] else first)..(this[from] else last);
                return range.reversed;
            }
        }
    }
    
    shared actual [Element*] spanFrom(Integer from) {
        if (from<=0) {
            return this;
        }
        else if (longerThan(from)) {
            assert (exists first = this[from]);
            return first..last;
        }
        else {
            return [];
        }
    }
    
    shared actual [Element*] spanTo(Integer to) {
        if (to<0) {
            return [];
        }
        else if (longerThan(to+1)) {
            assert (exists last = this[to]);
            return first..last;
        }
        else {
            return this;
        }
    }
    
}

"Produces a [[Range]] of adjacent [[Enumerable]] values 
 generated by two endpoints: [[first]] and [[last]]. The 
 range includes both endpoints, and all values falling 
 _between_ the endpoints.
 
 - For a recursive enumerable type, a value falls between 
   the endpoints if its [[offset|Enumerable.offset]] from 
   `first` is less than the offset of `last` from `first`.
 - For a linear enumerable type, a value falls between the
   endpoints if the 
   [[sign of its offset|Enumerable.offsetSign]] from `first` 
   is the same as the sign of the offset of `last` from 
   `first` and the sign of its offset from `last` is the 
   opposite of the sign of the offset of `last` from `first`.
 
 More precisely, if `x`, `first`, and `last` are of 
 `Enumerable` type `X`, then `x in first..last` if and 
 only if:
 
 - `X` is recursive and `x.offset(first)<last.offset(first)`,
  or
 - `X` is linear and 
  `x.offsetSign(first)==last.offsetSign(first)` and
  `x.offsetSign(last)==-last.offsetSign(first)`.
 
 For a linear enumerable type, a range is either 
 [[increasing|Range.increasing]] or 
 [[decreasing|Range.decreasing]]:
 
 - in an increasing range, a value occurs before its 
  [[successor|Ordinal.successor]] and after its 
  [[predecessor|Ordinal.predecessor]], but
 - in a decreasing range, a value occurs after its 
  `successor` and before its `predecessor`.
 
 The direction of the range depends upon the sign of the
 offset of `last` from `first`: 
 
 - if `last.offsetSign(first)>=0` the range is increasing,
   but
 - if `last.offsetSign(first)<0`, the range is decreasing.
 
 A range for a recursive enumerable type is always 
 increasing.
 
 The _span operator_ `..` is an abbreviation for `span()`:
 
     for (i in min..max) { ... }
     if (char in 'A'..'Z') { ... }
 
 The span operator accepts the first and last values of 
 the range. It may produce an increasing range:
 
     0..5    // [0, 1, 2, 3, 4, 5]
     0..0    // [0]
 
 Or it may produce a decreasing range:
 
     5..0    // [5, 4, 3, 2, 1, 0]
     0..-5   // [0, -1, -2, -3, -4, -5]"
shared Range<Element> span<Element>
            (Element first, Element last) 
        given Element satisfies Enumerable<Element> 
        => Span(first, last);