import ceylon.language { internalFirst = first }

"""Abstract supertype of categories whose elements may be 
   iterated. An iterable category need not be finite, but
   its elements must at least be countable. There may not
   be a well-defined iteration order, and so the order of
   iterated elements may not be stable.
   
   The type `Iterable<Element,Null>`, usually abbreviated
   `{Element*}` represents a possibly-empty iterable 
   container. The type `Iterable<Element,Nothing>`, 
   usually abbreviated `{Element+}` represents a nonempty 
   iterable container.
   
   An instance of `Iterable` may be constructed by 
   surrounding a value list in braces:
   
       {String+} words = { "hello", "world" };
   
   An instance of `Iterable` may be iterated using a `for`
   loop:
   
       for (c in "hello world") { ... }
   
   `Iterable` and its subtypes define various operations
   that return other iterable objects. Such operations 
   come in two flavors:
   
   - _Lazy_ operations return a *view* of the receiving
     iterable object. If the underlying iterable object is
     mutable, then changes to the underlying object will
     be reflected in the resulting view. Lazy operations
     are usually efficient, avoiding memory allocation or
     iteration of the receiving iterable object.
   - _Eager_ operations return an immutable object. If the
     receiving iterable object is mutable, changes to this
     object will not be reflected in the resulting 
     immutable object. Eager operations are often 
     expensive, involving memory allocation and iteration
     of the receiving iterable object.
   
   Lazy operations are preferred, because they can be 
   efficiently chained. For example:
   
       string.filter((Character c) => c.letter)
             .map((Character c) => c.uppercased)
   
   is much less expensive than:
   
       string.select((Character c) => c.letter)
             .collect((Character c) => c.uppercased)
   
   Furthermore, it is always easy to produce a new 
   immutable iterable object given the view produced by a
   lazy operation. For example:
   
       [ *string.filter((Character c) => c.letter)
             .map((Character c) => c.uppercased) ]
   
   Lazy operations normally return an instance of 
   `Iterable` or `Map`.
   
   However, there are certain scenarios where an eager 
   operation is more useful, more convenient, or no more 
   expensive than a lazy operation, including:
   
   - sorting operations, which are eager by nature,
   - operations which preserve emptiness/nonemptiness of
     the receiving iterable object.
   
   Eager operations normally return a sequence."""
see (`interface Collection`)
by ("Gavin")
shared interface Iterable<out Element, out Absent=Null>
        satisfies Category
        given Absent satisfies Null {
    
    "An iterator for the elements belonging to this 
     container."
    shared formal Iterator<Element> iterator();
    
    "Determines if the iterable object is empty, that is
     to say, if the iterator returns no elements."
    shared default Boolean empty =>
            iterator().next() is Finished;
    
    "The number of elements returned by the iterator of
     this iterable object, if the iterator terminates.
     In the case of an iterable whose elements are not
     countable, this operation never terminates."
    shared default Integer size => count((Element e) => true);
    
    "Determines if this iterable object has more elements
     than the given length. This is an efficient operation 
     for iterable objects with many elements."
    see (`value size`)
    shared default Boolean longerThan(Integer length) {
        if (length<0) {
            return true;
        }
        variable value count=0;
        for (element in this) {
            if (count++==length) {
                return true;
            }
        }
        return false;
    }
    
    "Determines if this iterable object has fewer elements
     than the given length. This is an efficient operation 
     for iterable objects with many elements."
    see (`value size`)
    shared default Boolean shorterThan(Integer length) {
        if (length<=0) {
            return false;
        }
        variable value count=0;
        for (element in this) {
            if (++count==length) {
                return false;
            }
        }
        return true;
    }
    
    shared actual default Boolean contains(Object element) => 
            any(ifExists(element.equals));
    
    "The first element returned by the iterator, if any,
     of `null` if the iterable object is empty."
    shared default Absent|Element first =>
            internalFirst(this);
    
    "The last element returned by the iterator, if any,
     of `null` if the iterable object is empty. Iterable
     objects are potentially infinite, so calling this
     might never return; also, this implementation will
     iterate through all the elements, which might be
     very time-consuming."
    shared default Absent|Element last {
        variable Absent|Element e = first;
        for (x in this) {
            e = x;
        }
        return e;
    }
    
    "Returns an iterable object containing all but the 
     first element of this container."
    shared default {Element*} rest => skipping(1);
    
    "A sequence containing the elements returned by the
     iterator."
    shared default Element[] sequence => [ for (x in this) x ];
    
    "An `Iterable` containing the results of applying
     the given mapping to the elements of to this 
     container."
    see (`function collect`)
    shared default Iterable<Result,Absent> map<Result>(
            "The mapping to apply to the elements."
            Result collecting(Element elem)) =>
                    { for (elem in this) collecting(elem) };
    
    /*shared default Callable<{Result*},Args> spread<Result,Args>(
            Callable<Result,Args> method(Element elem)) 
            given Args satisfies Anything[] =>
                flatten((Args args) => 
                    { for (elem in this) unflatten(method(elem))(args) });*/
    
    "An `Iterable` containing the elements of this 
     container that satisfy the given predicate."
    see (`function select`)
    shared default {Element*} filter(
            "The predicate the elements must satisfy."
            Boolean selecting(Element elem)) =>
                    { for (elem in this) if (selecting(elem)) elem };
    
    "The result of applying the accumulating function to 
     each element of this container in turn." 
    shared default Result fold<Result>(Result initial,
            "The accumulating function that accepts an
             intermediate result, and the next element."
            Result accumulating(Result partial, Element elem)) {
        variable value r = initial;
        for (e in this) {
            r = accumulating(r, e);
        }
        return r;
    }
    
    "The first element which satisfies the given 
     predicate, if any, or `null` otherwise."
    shared default Element? find(
            "The predicate the element must satisfy."
            Boolean selecting(Element elem)) {
        for (e in this) {
            if (selecting(e)) {
                return e;
            }
        }
        return null;
    }
    
    "The last element which satisfies the given
     predicate, if any, or `null` otherwise."
    shared default Element? findLast(
            "The predicate the element must satisfy."
            Boolean selecting(Element elem)) {
        variable Element? last = null;
        for (e in this) {
            if (selecting(e)) {
                last = e;
            }
        }
        return last;
    }
    
    "A sequence containing the elements of this
     container, sorted according to a function 
     imposing a partial order upon the elements.
     
     For convenience, the functions `byIncreasing()` 
     and `byDecreasing()` produce a suitable 
     comparison function:
     
         \"Hello World!\".sort(byIncreasing((Character c) => c.lowercased))
     
     This operation is eager by nature."
    see (`function byIncreasing`, `function byDecreasing`)
    shared default Element[] sort(
            "The function comparing pairs of elements."
            Comparison comparing(Element x, Element y)) =>
                    internalSort(comparing, this);
    
    "A sequence containing the results of applying the
     given mapping to the elements of this container. An 
     eager counterpart to `map()`."
    see (`function map`)
    shared default Result[] collect<Result>(
            "The transformation applied to the elements."
            Result collecting(Element element)) =>
                    map(collecting).sequence;
    
    "A sequence containing the elements of this 
     container that satisfy the given predicate. An 
     eager counterpart to `filter()`."
    see (`function filter`)
    shared default Element[] select(
            "The predicate the elements must satisfy."
            Boolean selecting(Element element)) =>
                    filter(selecting).sequence;
    
    "Return `true` if at least one element satisfies the
     predicate function."
    shared default Boolean any(
            "The predicate that at least one element 
             must satisfy."
            Boolean selecting(Element e)) {
        for (e in this) {
            if (selecting(e)) {
                return true;
            }
        }
        return false;
    }
    
    "Return `true` if all elements satisfy the predicate
     function."
    shared default Boolean every(
            "The predicate that all elements must 
             satisfy."
            Boolean selecting(Element e)) {
        for (e in this) {
            if (!selecting(e)) {
                return false;
            }
        }
        return true;
    }
    
    "Produce an `Iterable` containing the elements of
     this iterable object, after skipping the first 
     `skip` elements. If this iterable object does not 
     contain more elements than the specified number of 
     elements, the `Iterable` contains no elements."
    shared default {Element*} skipping(Integer skip) {
        if (skip <= 0) { 
            return this;
        }
        else {
            object iterable satisfies {Element*} {
                shared actual Iterator<Element> iterator() {
                    value iter = outer.iterator();
                    variable value i=0;
                    while (i++<skip && 
                            !iter.next() is Finished) {}
                    return iter;
                }
            }
            return iterable;
        }
    }
    
    "Produce an `Iterable` containing the first `take`
     elements of this iterable object. If the specified 
     number of elements is larger than the number of 
     elements of this iterable object, the `Iterable` 
     contains the same elements as this iterable object."
    shared default {Element*} taking(Integer take) {
        if (take <= 0) { 
            return {}; 
        }
        else {
            object iterable satisfies {Element*} {
                shared actual Iterator<Element> iterator() {
                    value iter = outer.iterator();
                    object iterator satisfies Iterator<Element> {
                        variable value i=0;
                        actual shared Element|Finished next() {
                            return ++i>take then finished 
                                    else iter.next();
                        }
                    }
                    return iterator;
                }
                shared actual Element? first => outer.first;
            }
            return iterable;
        }
    }
    
    "Produce an `Iterable` containing the elements of
     this iterable object, after skipping the leading 
     elements until the given predicate function returns
     `false`."
    shared default {Element*} skippingWhile(Boolean skip(Element elem)) {
        object iterable satisfies {Element*} {
            shared actual Iterator<Element> iterator() {
                value iter = outer.iterator();
                while (!is Finished elem=iter.next()) {
                    if (!skip(elem)) {
                        object iterator satisfies Iterator<Element> {
                            variable Boolean first=true;
                            actual shared Element|Finished next() {
                                if (first) {
                                    first=false;
                                    return elem;
                                }
                                else {
                                    return iter.next();
                                }
                            }
                        }
                        return iterator;
                    }
                }
                return emptyIterator;
            }
        }
        return iterable;
    }
    
    "Produce an `Iterable` containing the leading elements 
     of this iterable object until the given predicate 
     function returns `false`."
    shared default {Element*} takingWhile(Boolean take(Element elem)) {
        object iterable satisfies {Element*} {
            shared actual Iterator<Element> iterator() {
                value iter = outer.iterator();
                object iterator satisfies Iterator<Element> {
                    variable Boolean alive = true;
                    actual shared Element|Finished next() {
                        if (alive, !is Finished next = iter.next()) {
                            if (take(next)) {
                                return next;
                            }
                            else {
                                alive = false;
                            }
                        }
                        return finished;
                    }
                }
                return iterator;
            }
        }
        return iterable;
    }
    
    "Produce an `Iterable` containing every `step`th 
     element of this iterable object. If the step size 
     is `1`, the `Iterable` contains the same elements 
     as this iterable object. The step size must be 
     greater than zero. The expression
     
         (0..10).by(3)
     
     results in an iterable object with the elements
     `0`, `3`, `6`, and `9` in that order."
    throws (`class AssertionException`, 
            "if the given step size is nonpositive, 
             i.e. `step<1`")
    shared default Iterable<Element,Absent> by(Integer step) {
        "step size must be greater than zero"
        assert (step > 0);
        if (step == 1) {
            return this;
        } 
        else {
            object iterable satisfies Iterable<Element,Absent> {
                shared actual Iterator<Element> iterator() {
                    value iter = outer.iterator();
                    object iterator satisfies Iterator<Element> {
                        shared actual Element|Finished next() {
                            value next = iter.next();
                            variable value i=0;
                            while (++i<step && 
                                    !iter.next() is Finished) {}
                            return next;
                        }
                    }
                    return iterator;
                }
            }
            return iterable;
        }
    }
    
    "Return the number of elements in this `Iterable` 
     that satisfy the predicate function."
    shared default Integer count(
            "The predicate satisfied by the elements to
             be counted."
            Boolean selecting(Element element)) {
        variable value count=0;
        for (elem in this) {
            if (exists elem, 
                selecting(elem)) {
                count++;
            }
        }
        return count;
    }
    
    "The non-null elements of this `Iterable`, in their
     original order. For null elements of the original 
     `Iterable`, there is no entry in the resulting 
     iterable object."
    shared default {Element&Object*} coalesced =>
            { for (e in this) if (exists e) e };
    
    "All entries of form `index->element` where `index` 
     is the position at which `element` occurs, for every
     non-null element of this `Iterable`, ordered by
     increasing `index`. For a null element at a given
     position in the original `Iterable`, there is no 
     entry with the corresponding index in the resulting 
     iterable object. The expression 
     
         { \"hello\", null, \"world\" }.indexed
         
     results in an iterable object with the entries
     `0->\"hello\"` and `2->\"world\"`."
    shared default {<Integer->Element&Object>*} indexed {
        object indexes
                satisfies {<Integer->Element&Object>*} {
            value orig => outer;
            shared actual Iterator<Integer->Element&Object> iterator() {
                object iterator satisfies Iterator<Integer->Element&Object> {
                    value iter = orig.iterator();
                    variable value i=0;
                    shared actual <Integer->Element&Object>|Finished next() {
                        variable value next = iter.next();
                        while (!next exists) {
                            i++;
                            next = iter.next();
                        }
                        assert (exists n = next);
                        if (!is Finished n) {
                            return i++->n;
                        }
                        else {
                            return finished;
                        }
                    }
                }
                return iterator;
            }
        }
        return indexes;
    }
    
    "An `Iterable` with the given inital element followed 
     by the elements of this iterable object."
    shared default {Element|Other+} following<Other>(Other head) {
        //TODO: should be {leading,*outer} when that is efficient
        object cons satisfies {Element|Other+} {
            shared actual Iterator<Element|Other> iterator() {
                value iter = outer.iterator();
                object iterator satisfies Iterator<Element|Other> {
                    variable Boolean first = true;
                    shared actual Element|Other|Finished next() {
                        if (first) {
                            first=false;
                            return head;
                        }
                        else {
                            return iter.next();
                        }
                    }
                }
                return iterator;
            }
        }
        return cons;
    }
    
    "The elements of this iterable object, in their
     original order, followed by the elements of the 
     given iterable object also in their original order."
    shared default Iterable<Element|Other,Absent&OtherAbsent> 
    chain<Other,OtherAbsent>(Iterable<Other,OtherAbsent> other) 
             given OtherAbsent satisfies Null {
        object chained 
                satisfies Iterable<Element|Other,Absent&OtherAbsent> {
            shared actual Iterator<Element|Other> iterator() =>
                    ChainedIterator(outer, other);
        }
        return chained;
    }
    
    "An `Iterable` that produces the elements of this 
     iterable object, replacing every `null` element 
     with the given default value. The resulting iterable
     object does not produce the value `null`."
    shared default Iterable<Element&Object|Default,Absent>
    defaultNullElements<Default>(
            "A default value that replaces `null` elements."
            Default defaultValue)
        => { for (elem in this) elem else defaultValue };
    
    /*"Creates a Map that contains this `Iterable`'s
         elements, grouped in `Sequence`s under the
         keys provided by the grouping function."
    shared default native Map<Grouping,[Element+]> group<Grouping>(
                "A function that must return the key under
                 which to group the specified element."
                Grouping grouping(Element elem))
            given Grouping satisfies Object;*/
        
    "A string of form `\"{ x, y, z }\"` where `x`, `y`, 
     and `z` are the `string` representations of the 
     elements of this collection, as produced by the
     iterator of the collection, or the string `\"{}\"` 
     if this iterable is empty. If the number of items
     is very large only a certain amount of them might
     be shown followed by \"...\"."
    shared actual default String string {
        if (empty) {
            return "{}";
        }
        else {
            String list = commaList(taking(30));
            return "{ `` longerThan(30) 
                        then list + ", ..." 
                        else list `` }"; 
        }
    }
    
    "A non-finite iterable object that produces the elements 
     of this iterable object, repeatedly."
    see (`function cycle`)
    shared default Iterable<Element,Absent> cycled {
        object iterable satisfies Iterable<Element,Absent> {
            value orig => outer;
            shared actual Iterator<Element> iterator() {
                object iterator satisfies Iterator<Element> {
                    variable Iterator<Element> iter = emptyIterator;
                    shared actual Element|Finished next() {
                        if (!is Finished next = iter.next()) {
                            return next;
                        }
                        else {
                            iter = orig.iterator();
                            return iter.next();
                        }
                        
                    }
                }
                return iterator;
            }
        }
        return iterable;
    }
    
    "A finite iterable object that produces the elements of 
     this iterable object, repeatedly, the given number of
     times."
    see (`value cycled`, `function repeat`)
    shared default Iterable<Element,Absent> cycle(Integer times) {
        object iterable satisfies Iterable<Element,Absent> {
            value orig => outer;
            shared actual Iterator<Element> iterator() {
                object iterator satisfies Iterator<Element> {
                    variable Iterator<Element> iter = emptyIterator;
                    variable Integer count=0;
                    shared actual Element|Finished next() {
                        if (!is Finished next = iter.next()) {
                            return next;
                        }
                        else {
                            if (count<times) {
                                count++;
                                iter = orig.iterator();
                            }
                            else {
                                iter = emptyIterator;
                            }
                            return iter.next();
                        }
                        
                    }
                }
                return iterator;
            }
        }
        return iterable;
    }
    
    "Returns a list formed by repeating the elements of this
     iterable object the given number of times, or an empty 
     list if `times<=0`. An eager counterpart to `cycle()`."
    see (`function cycle`)
    shared default List<Element> repeat(Integer times) {
        value sb = SequenceBuilder<Element>();
        variable value count=0;
        while (count++<times) {
            sb.appendAll(this);
        }
        return sb.sequence;
    }
    
}

String commaList({Anything*} elements) =>
        ", ".join { for (element in elements)
                    element?.string else "null" };

Boolean ifExists(Boolean predicate(Object val))(Anything val) {
    if (exists val) {
        return predicate(val);
    }
    else {
        return false;
    }
}