doc "Represents the range of totally ordered, ordinal values 
     generated by two endpoints of type `Ordinal` and 
     `Comparable`. If the first value is smaller than the
     last value, the range is increasing. If the first value
     is larger than the last value, the range is decreasing.
     If the two values are equal, the range contains exactly
     one element. The range is always nonempty, containing 
     at least one value.
     
     A range may be produced using the `..` operator:
     
         for (i in min..max) { ... }
         if (char in `A`..`Z`) { ... }
     "
by "Gavin"
shared class Range<Element>(first, last) 
        extends Object() 
        satisfies Sequence<Element> & Category
        given Element satisfies Ordinal<Element> & 
                                Comparable<Element> { 
    
    doc "The start of the range."
    shared actual Element first;
    
    doc "The end of the range."
    shared actual Element last;

    shared actual String string {
        return first.string + ".." + last.string;
    }
    
    doc "Determines if the range is decreasing."
    shared Boolean decreasing { 
        return last<first; 
    }
    
    Element next(Element x) {
        return decreasing then x.predecessor 
                else x.successor;
    }

    value distance = last.distanceFrom(first);

    doc "The nonzero number of elements in the range."
    shared actual Integer size = (distance.positive then distance else -distance)+1;
    
    doc "The index of the end of the range."
    shared actual Integer lastIndex { 
        return size-1; 
    }
    
    doc "The rest of the range, without the start of the
         range."
    shared actual Element[] rest {
        Element n = next(first);
        return n==last then {} else Range<Element>(n,last);
    }
    
    doc "The element of the range that occurs `n` values after
         the start of the range. Note that this operation 
         is inefficient for large ranges."
    shared actual Element? item(Integer n) {
        //optimize this for numbers!
        variable Integer index:=0;
        variable Element x:=first;
        while (index<n) {
            if (x==last) {
                return null;
            }
            else {
                ++index;
                x:=next(x);
            }
        }
        return x;
    }
    
    doc "An iterator for the elements of the range."
    shared actual Iterator<Element> iterator {
        class RangeIterator()
                satisfies Iterator<Element> {
            variable Element|Finished current := first;
            shared actual Element|Finished next() {
                Element|Finished result = current;
                if (is Element curr = current) {
                    if (curr == last) {
                        current := exhausted;
                    } 
                    else {
                        current := outer.next(curr);
                    }
                }
                return result;
            }
            shared actual String string {
                return "RangeIterator";
            }
        }
        return RangeIterator();
    }
    
    doc "Determines if the range includes the given object."
    shared actual Boolean contains(Object element) {
        if (is Element element) {
            return includes(element);
        }
        else {
            return false;
        }
    }
    
    shared actual Integer count(Boolean selecting(Element element)) {
        variable value e := first;
        variable value c := 0;
        while (includes(e)) {
            if (selecting(e)) {
                c++;
            }
            e := next(e);
        }
        return c;
    }
    
    doc "Determines if the range includes the given value."
    shared Boolean includes(Element x) {
        return decreasing then x<=first && x>=last
                else x>=first && x<=last;
    }
    
    /*shared Element[] excludingLast {
        throw; //todo!
    }*/

    /*shared Integer? index(Element x) {
    if (!includes(x)) {
        return null;
    }
    else {
        //optimize this for numbers!
        variable Integer index:=0;
        variable Element value:=first;
        while (value<x) {
            ++index;
            ++value;
        }
        return index;
    }
    }*/

    doc "Determines if two ranges are the same by comparing
         their endpoints."
    shared actual Boolean equals(Object that) {
        if (is Range<Element> that) {
            //optimize for another Range
            return that.first==first && that.last==last;
        }
        else {
            //it might be another sort of List
            return that.equals(this);
        }
    }
    
    doc "Returns the range itself, since ranges are 
         immutable."
    shared actual Range<Element> clone {
        return this;
    }
    
    shared actual Range<Element>|Empty segment(
            Integer from, 
            Integer length) {
        if (length<=0 || from>lastIndex) {
            return {};
        }
        variable value x:=first;
        variable value i:=0;
        while (i++<from) { x:=next(x); }
        variable value y:=x;
        variable value j:=1;
        while (j++<length && y<last) { y:=next(y); }
        return Range<Element>(x, y);
    }
    
    shared actual Range<Element>|Empty span(
            Integer from, 
            Integer? to) {
        variable value toIndex:=to else lastIndex;
        variable value fromIndex:=from;
        if (toIndex<0) {
            if (fromIndex<0) {
                return {};
            }
            toIndex:=0;
        }
        else if (toIndex>lastIndex) {
            if (fromIndex>lastIndex) {
                return {};
            }
            toIndex:=lastIndex;
        }
        if (fromIndex<0) {
            fromIndex:=0;
        }
        else if (fromIndex>lastIndex) {
            fromIndex:=lastIndex;
        }
        variable value x:=first;
        variable value i:=0;
        while (i++<fromIndex) { x:=next(x); }
        variable value y:=first;
        variable value j:=0;
        while (j++<toIndex) { y:=next(y); }
        return Range<Element>(x, y);
    }
    
    doc "Reverse this range, returning a new range."
    shared actual Range<Element> reversed {
        return Range(last,first);
    }

    shared actual Range<Element>|Empty skipping(Integer skip) {
        variable value x:=0;
        variable value e := first;
        while (x++<skip) {
            e:=next(e);
        }
        return includes(e) then Range(e, last) else {};
    }
    shared actual Range<Element>|Empty taking(Integer take) {
        if (take == 0) {
            return {};
        }
        variable value x:=0;
        variable value e:=first;
        while (++x<take) {
            e:=next(e);
        }
        return includes(e) then Range(first, e) else this;
    }

    doc "Returns the range itself, since a Range cannot
         contain nulls."
    shared actual Range<Element> coalesced {
        return this;
    }

}