Category talk:Wren-seq

From Rosetta Code

Source code

/* Module "seq.wren" */

import "./trait" for Cloneable, CloneableSeq

/* Seq supplements the Sequence class with some other operations on sequences. */
class Seq {
    // Private helper method to check that 's' is a sequence and throw an error otherwise.
    static isSeq_(s) { (s is Sequence) ? true : Fiber.abort("Argument must be a sequence.") }

    // Returns true if a sequence contains ALL the elements of a sequence, false otherwise.
    static containsAll(s, elements) {
        isSeq_(s)
        for (element in elements) {
            if (!s.contains(element)) return false
        }
        return true
    }

    // Returns true if any adjacent elements of the sequence are duplicates, false otherwise.
    static hasAdjDup(s) {
        isSeq_(s)
        var iter = s.iterate(null)
        if (!iter) return false
        var prev = s.iteratorValue(iter)
        while (iter = s.iterate(iter)) {
            var next = s.iteratorValue(iter)
            if (next == prev) return true
            prev = next
        }
        return false
    }

    // Returns a new 'lazy' sequence that iterates only the last 'count' elements of
    // the original sequence.
    static takeLast(s, count) {
        isSeq_(s)
        if (!(count is Num) || !count.isInteger || count < 0) {
            Fiber.abort("Count must be a non-negative integer.")
        }
        count = s.count - count
        if (count <= 0) count = 0
        return SkipSequence.new(s, count)
    }

    // Returns a new 'lazy' sequence that skips the last 'count' elements of
    // the original sequence.
    static skipLast(s, count) {
        isSeq_(s)
        if (!(count is Num) || !count.isInteger || count < 0) {
            Fiber.abort("Count must be a non-negative integer.")
        }
        count = s.count - count
        if (count <= 0) count = 0
        return TakeSequence.new(s, count)
    }

    // Returns a new 'lazy' sequence that iterates the elements of
    // the original sequence only while they continue to satisfy a predicate.
    static takeWhile(s, pred) {
        isSeq_(s)
        if (!((pred is Fn) && pred.arity == 1)) {
            Fiber.abort("Predicate must be a function which takes a single argument.")
        }
        var count = 0
        for (e in s) {
            if (!pred.call(e)) break
            count = count + 1
        }
        return TakeSequence.new(s, count)
    }

    // Returns a new 'lazy' sequence that skips the elements of
    // the original sequence only while they continue to satisfy a predicate.
    static skipWhile(s, pred) {
        isSeq_(s)
        if (!((pred is Fn) && pred.arity == 1)) {
            Fiber.abort("Predicate must be a function which takes a single argument.")
        }
        var count = 0
        for (e in s) {
            if (!pred.call(e)) break
            count = count + 1
        }
        return SkipSequence.new(s, count)
    }

    // Returns the first element of a sequence without removing it.
    // Returns null if the sequence is empty.
    static peek(s) {
        isSeq_(s)
        for (value in s) {
            return value
        }
        return null
    }

    // Writes a sequence in list format to stdout 
    // but without having to convert it to a list first.
    static write(s) {
        isSeq_(s)
        System.write("[")
        for (e in s) System.write("%(e), ")
        System.write("\b\b]")
    }

    // As 'write' followed by a new line.
    static print(s) {
        write(s)
        System.print()
    }
}

/* Lst supplements the List class with various other operations on lists. */
class Lst {
    // Creates a list with 'cols' columns and assigns a copy of 'filler' to each element.
    // 'copier' is a function which takes a single argument and returns a copy of that argument.
    static filled(cols, filler, copier) {
        if (cols.type != Num || !cols.isInteger || cols < 0) {
            Fiber.abort("'cols' must be a non-negative integer.")
        }
        var lst
        if (!copier) {
            lst = List.filled(cols, filler)
        } else {
            lst = List.filled(cols, null)
            for (c in 0...cols) lst[c] = copier.call(filler)
        }
        return lst
    }

    // Creates a two dimensional list with 'rows' rows and 'cols' columns and assigns a copy
    // of 'filler' to each element.
    // 'copier' is a function which takes a single argument and returns a copy of that argument.
    static filled2(rows, cols, filler, copier) {
        if (rows.type != Num || !rows.isInteger || rows < 0) {
            Fiber.abort("'rows' must be a non-negative integer.")
        }
        if (cols.type != Num || !cols.isInteger || cols < 0) {
            Fiber.abort("'cols' must be a non-negative integer.")
        }
        var lst = List.filled(rows, null)
        for (r in 0...rows) {
            if (!copier) {
                lst[r] = List.filled(cols, filler)
            } else {
                lst[r] = List.filled(cols, null)
                for (c in 0...cols) lst[r][c] = copier.call(filler)
            }
        }
        return lst
    }

    // Creates a three dimensional list with 'pages' pages, 'rows' rows and 'cols' columns and assigns
    // a copy of 'filler' to each element.
    // 'copier' is a function which takes a single argument and returns a copy of that argument.
    static filled3(pages, rows, cols, filler, copier) {
        if (pages.type != Num || !pages.isInteger || pages < 0) {
            Fiber.abort("'pages' must be a non-negative integer.")
        }
        if (rows.type != Num || !rows.isInteger || rows < 0) {
            Fiber.abort("'rows' must be a non-negative integer.")
        }
        if (cols.type != Num || !cols.isInteger || cols < 0) {
            Fiber.abort("'cols' must be a non-negative integer.")
        }
        var lst = List.filled(pages, null)
        for (p in 0...pages) {
            lst[p] = List.filled(rows, null)
            for (r in 0...rows) {
                if (!copier) {
                    lst[p][r] = List.filled(cols, filler)
                } else {
                    lst[p][r] = List.filled(cols, null)
                    for (c in 0...cols) lst[p][r][c] = copier.call(filler)
                }
            }
        }
        return lst
    }

    // The following overloads of the above methods should normally only be used where the 'filler'
    // is of an immutable type and does not need to be copied.
    // No overload is required for 'filled' as List.filled suffices for such types.
    static filled2(rows, cols, filler) { filled2(rows, cols, filler, null) }
    static filled3(pages, rows, cols, filler) { filled3(pages, rows, cols, filler, null) }

    // The following analogous methods refill existing one, two or three dimensional lists with 'filler'
    // or, if appropriate, a copy thereof and return the list.
    static refill(a, filler, copier) {
        Lst.isList_(a)
        for (c in 0...a.count) a[c] = !copier ? filler : copier.call(filler)
        return a
    }

    static refill2(a, filler, copier) {
        Lst.isList_(a)
        for (r in 0...a.count) {
            for (c in 0...a[0].count) a[r][c] = !copier ? filler : copier.call(filler)
        }
        return a
    }

    static refill3(a, filler, copier) {
        isList_(a)
        for (p in 0...a.count) {
            for (r in 0...a[0].count) {
                for (c in 0...a[0][0].count) a[p][r][c] = !copier ? filler : copier.call(filler)
            }
        }
        return a
    }

    static refill (a, filler) { refill (a, filler, null) }
    static refill2(a, filler) { refill2(a, filler, null) }
    static refill3(a, filler) { refill3(a, filler, null) }

    // Creates a new list of size 'size' and copies all the elements (or the first 'size' elements)
    // of 'a' into it starting from index 0. Any remaining slots are filled by a copy of 'filler'.
    // 'copier' is a function which takes a single argument and returns a copy of that argument.
    static resize(a, size, filler, copier) {
        Lst.isList_(a)
        if (size.type != Num || !size.isInteger || size < 0) {
            Fiber.abort("'size' must be a non-negative integer.")
        }
        var res = List.filled(size, null)
        var rc = a.count.min(size)
        for (i in 0...rc) res[i] = !copier ? a[i] : copier.call(a[i])
        if (size > a.count) {
            for (i in rc...size) res[i] = !copier ? filler : copier.call(filler)
        }
        return res
    }

    // Overloads of above method where elements/filler are immutable, not needed or null.
    static resize(a, size, filler) { resize (a, size, filler, null) }
    static resize(a, size)         { resize (a, size, null, null) }

    // Creates a list and fills it with a series of numbers starting from 'start'
    // with a common difference of 'step'.
    static serialFill(cols, start, step) {
        if (cols.type != Num || !cols.isInteger || cols < 0) {
            Fiber.abort("'cols' must be a non-negative integer.")
        }
        if (start.type != Num) Fiber.abort("'start' must be a number.")
        if (step.type != Num)  Fiber.abort("'step' must be a number.")
        var lst = List.filled(cols, 0)
        for (i in 0...cols) lst[i] = start + i*step
        return lst
    }

    // Analogous method to serialFill which refills an existing list with a series of numbers and returns it.
    static serialRefill(a, start, step) {
        isList_(a)
        if (start.type != Num) Fiber.abort("'start' must be a number.")
        if (step.type != Num)  Fiber.abort("'step' must be a number.")
        for (i in 0...a.count) a[i] = start + i*step
        return a
    }

    // Overloads of the above methods
    static serialFill(cols, start) { serialFill(cols, start, 1) }  // step 1
    static serialFill(cols)        { serialFill(cols, 0, 1)     }  // start 0, step 1

    static serialRefill(a, start)  { serialRefill(a, start, 1)  }  // step 1
    static serialRefill(a)         { serialRefill(a, 0, 1)      }  // start 0, step 1

    // Private helper method to check that 'a' is a list and throw an error otherwise.
    static isList_(a) { (a is List) ? true : Fiber.abort("Argument must be a list.") }

    // Private helper method to check whether a start index is valid.
    static checkStart_(a, start) {
        if (start.type != Num || !start.isInteger) Fiber.abort("Start must be an integer.")
        var c = a.count
        if (start >= c || start < -c) Fiber.abort("Start is out of bounds.")
    }

    // Inserts all elements of a sequence 'other' into 'a' starting at index 'index'.
    static insertAll(a, other, index) {
        isList_(a)
        checkStart_(a, index)
        if (index < 0) index = index + a.count
        for (e in other) {
            a.insert(index, e)
            index = index + 1
        }
        return other
    }

    // Performs a circular shift of the elements of 'a' 'n' places to the left.
    // If 'n' is negative performs a circular right shift by '-n' places instead.
    // Returns 'a' after any mutation.
    static lshift(a, n) {
        Lst.isList_(a)
        if (!(n is Num) || !n.isInteger) Fiber.abort("'n' must be an integer.")
        var count = a.count
        if (count < 2) return a
        if (n < 0) return rshift(a, -n)
        n = n % count
        if (n == 0) return a
        for (i in 1..n) {
            var t = a[0]
            for (j in 0..count-2) a[j] = a[j+1]
            a[-1] = t
        }
        return a
    }

    // Performs a circular shift of the elements of 'a' 'n' places to the right.
    // If 'n' is negative performs a circular left shift by '-n' places instead.
    // Returns 'a' after any mutation.
    static rshift(a, n) {
        Lst.isList_(a)
        if (!(n is Num) || !n.isInteger) Fiber.abort("'n' must be an integer.")
        var count = a.count
        if (count < 2) return a
        if (n < 0) return lshift(a, -n)
        n = n % count
        if (n == 0) return a
        for (i in 1..n) {
            var t = a[-1]
            for (j in count-2..0) a[j+1] = a[j]
            a[0] = t
        }
        return a
    }

    // Convenience versions of the above methods which shift by just 1 place.
    static lshift(a) { lshift(a, 1) }
    static rshift(a) { rshift(a, 1) }

    // Searches an unsorted list linearly for a particular value from a start index.
    // If the start index is negative, it counts backwards from the end of the list.
    // Returns a list of three items:
    // The first item is a Bool indicating whether the value was found.
    // The second item is the number of times the value was found.
    // The third item is a list of indices at which the value was found.
    static indicesOf(a, value, start) {
        isList_(a)
        checkStart_(a, start)
        var count = a.count
        var indices = []
        if (count == 0) return [false, 0, indices]
        if (start < 0) start = count + start
        for (i in start...count) {
            if (a[i] == value) indices.add(i)
        }
        if (indices.isEmpty) return [false, 0, indices]
        return [true, indices.count, indices]
    }

    // Works similarly to 'indicesOf' but only returns the index of the first match
    // or -1 if there were no matches at all.
    static indexOf(a, value, start) {
        isList_(a)
        checkStart_(a, start)
        return indexOf_(a, value, start)
    }

    // Private helper method for 'indexOf' which avoids type and bounds checks.
    static indexOf_(a, value, start) {
        var count = a.count
        if (count == 0) return -1
        if (start < 0) start = count + start
        for (i in start...count) {
            if (a[i] == value) return i
        }
        return -1
    }

    // Returns the index of the last occurrence of 'value' in 'a' or -1 if no matches.
    static lastIndexOf(a, value) {
        if (a.count == 0) return 0
        for (i in a.count-1..0) {
            if (a[i] == value) return i
        }
        return -1
    }   

    // Works similarly to 'indexOf' but returns the index of the first match
    // of ANY of a sequence of values or -1 if none of them matched.
    static indexOfAny(a, values, start) {
        isList_(a)
        checkStart_(a, start)
        var i
        for (value in values) {
            if ((i = indexOf_(a, value, start)) >= 0) return i
        }
        return -1
    }

    // Convenience versions of the above which use a value for 'start' of 0.
    static indicesOf(a, value)   { indicesOf(a, value, 0)   }
    static indexOf(a, value)     { indexOf(a, value, 0)     }
    static indexOfAny(a, values) { indexOfAny(a, values, 0) }

    // Returns the index at which the slice 's' is first found in 'a' or -1 if it is not present.
    static indexOfSlice(a, s) {
        isList_(a)
        isList_(s)
        var ac = a.count
        var sc = s.count
        if (ac == 0 || sc > ac) return -1
        if (sc == 0) return 0
        if (ac == 1) return (a[0] == s[0]) ? 0 : -1
        if (sc == 1) return a.indexOf(s[0])
        for (i in 0..ac-sc) {
            if (a[i] == s[0]) {
                var ok = true
                for (j in i+1...i + sc) {
                    if (a[j] != s[j - i]) {
                        ok = false
                        break
                    }
                }
                if (ok) return i
            }
        }
        return -1
    }

    // Returns true if 's' is a slice of 'a' or false otherwise.
    static isSliceOf(a, s) { indexOfSlice(a, s) >= 0 }

    // Returns true if 'a' contains ALL the values of a sequence, false otherwise.
    static containsAll(a, values) {
        isList_(a)
        return Seq.containsAll(a, values)
    }

    // Returns true if 'a' contains ANY of the values, false otherwise.
    static containsAny(a, values) { indexOfAny(a, values) >= 0 }

    // Returns true if 'a' contains NONE of the values, false otherwise.
    static containsNone(a, values) { !containsAny(a, values) }

    // Groups each individual element of a list by count and indices, preserving order.
    // Returns a list of three element lists, one for each individual element.
    // The content of each three element list is as follows:
    // The first item is the individual element itself.
    // The second item is the number of times the individual element was found.
    // The third item is a list of indices at which the individual element was found.
    static individuals(a) {
        isList_(a)
        var c = a.count
        var m = {}
        var g = []
        var ix = 0
        for (i in 0...c) {
            if (!m[a[i]]) {
                g.add([a[i], 1, [i]])
                m[a[i]] = ix
                ix = ix + 1
            } else {
                var v = g[m[a[i]]]
                v[1] = v[1] + 1
                v[2].add(i)
            }
        }
        return g
    }

    // Groups each element of a list by the result of applying a function to it preserving order.
    // Returns a two element list for each distinct result as follows:
    // The first element is the result itself.
    // The second element is a list of three element lists consisting of:
    // A distinct element in the group.
    // The number of times that element occurs.
    // The indices at which it occurs.
    static groups(a, fn) {
        isList_(a)
        var c = a.count
        var m = {}
        var g = []
        var ix = 0
        for (i in 0...c) {
            var k = fn.call(a[i])
            if (!m[k]) {
                g.add([k, [[a[i], 1, [i]]]])
                m[k] = ix
                ix = ix + 1
            } else {
                var v = g[m[k]]
                var existing = false
                for (e in v[1]) {
                   if (e[0] == a[i]) {
                        e[1] = e[1] + 1
                        e[2].add(i)
                        existing = true
                        break
                   }
                }
                if (!existing) v[1].add([a[i], 1, [i]])
            }
        }
        return g
    }

    // Applies a function to each element of a list to produce a key and returns a map of each
    // distinct key to a list of the corresponding elements. The latter retain their original
    // order within the list and the key must be a value type.
    static groupBy(a, fn) {
        isList_(a)
        var m = {}
        for (e in a) {
            var k = fn.call(e)
            if (!m.containsKey(k)) {
                m[k] = [e]
            } else {
                m[k].add(e)
            }
        }
        return m
    }

    // Splits a list into two partitions depending on whether an element 
    // satisfies a predicate function or not and preserving order.
    // Returns a two element list of these partitions, the 'true' partition first.
    static partitions(a, pf) {
        isList_(a)
        var res = [[], []]
        a.each { |e| pf.call(e) ? res[0].add(e) : res[1].add(e) }
        return res
    }

    // Finds those elements of a list which occur the most times, preserving order.
    // Returns a list of three element lists, one for each such element.
    // The format of each three element list is similar to the 'lowest' method.
    static modes(a) {
        var gr = individuals(a)
        var max = gr.reduce(0) { |acc, g| (g[1] > acc) ? g[1] : acc }
        var res = []
        for (g in gr) {
            if (g[1] == max) res.add(g)
        }
        return res
    }

    // Finds all distinct elements of a list, preserving order.
    // Similar to 'individuals' but only returns a list of the distinct elements.
    static distinct(a) {
        var gr = individuals(a)
        var res = []
        for (g in gr) res.add(g[0])
        return res
    }

    // Removes consecutive repeated elements from a list (not a copy) and returns it.
    // If the list is sorted, it removes all duplicates.
    static prune(a) {
        isList_(a)
        var c = a.count
        if (c < 2) return a
        for (i in c-1..1) {
            if (a[i-1] == a[i]) a.removeAt(i)
        }
        return a
    }

    // Returns true if all elements of a list are the same, false otherwise.
    static allSame(a) { distinct(a).count == 1 }

    // Returns whether two lists a, b are the same length
    // and contain 'equal' elements (using the '==' operator)
    // in the same order.
    static areEqual(a, b) {
        isList_(a)
        isList_(b)
        if (a == b) return true
        var ac = a.count
        var bc = b.count
        if (ac != bc) return false
        for (i in 0...ac) {
            if (a[i] != b[i]) return false
        }
        return true
    }

    // Splits a list into chunks of not more than 'size' elements.
    // Returns a list of these chunks, preserving order.
    static chunks(a, size) {
        isList_(a)
        var c = a.count
        if (!(size is Num && size.isInteger && size > 0)) {
            Fiber.abort("Size must be a positive integer.")
        }
        if (size >= c) return [a]
        var res = []
        var n = (c/size).floor
        var final = c % size
        var first = 0
        var last  = first + size - 1
        for (i in 0...n) {
            res.add(a[first..last])
            first = last + 1
            last  = first + size - 1
        }
        if (final > 0) res.add(a[first..-1])
        return res
    }

    // Reverses a list in place and returns it.
    static reverse(a) {
        isList_(a)
        var c = a.count
        if (c < 2) return a
        var i = 0
        var j = a.count - 1
        while (i < j) {
            a.swap(i, j)
            i = i + 1
            j = j - 1
        }
        return a
    }

    // Replaces all occurrences of 'old' by 'swap' in 'a' and returns ['old', 'swap'].
    static replace(a, old, swap) {
        isList_(a)
        for (i in 0...a.count) {
            if (a[i] == old) a[i] = swap
        }
        return [old, swap]
    }

    // Removes all instances of 'value' from 'a'.
    // Returns 'value' if there were any removals, otherwise 'null'.
    static removeAll(a, value) {
        isList_(a)
        if (a.isEmpty) return null
        var found = false
        for (i in a.count-1..0) {
            if (a[i] == value) {
               a.removeAt(i)
               found = true
            }
        }
        return found ? value : null
    }

    // Removes all elements from 'a' which satisfy the predicate
    // function 'fn' and returns a list of the elements removed.  
    static removeBy(a, fn) {
        isList_(a)
        if (a.isEmpty) return []
        var removals = []
        for (i in a.count-1..0) {
            var e = a[i]
            if (fn.call(e)) {
                removals.add(a.remove(e))
            }
        }
        return reverse(removals)
    }

    // Removes all elements of 'a' between indices 'start' and 'end' inclusive and returns it.
    static clearPart(a, start, end) {
        isList_(a)
        if (a.isEmpty) return a
        checkStart_(a, start)
        checkStart_(a, end)
        if (start < 0) start = start + a.count
        if (end < 0) end = end + a.count
        if (end < start) Fiber.abort("'end' cannot be less than 'start'.")
        for (i in end..start) a.removeAt(i)
        return a
    }

    // Removes all elements of 'a' from index 'start' to the end and returns it.
    static truncate(a, start) { clearPart(a, start, -1) }

    // Expands a list 'a' in place to a length of 'newCount'
    // by adding 'element' the required number of times to it.
    // If the list's length is already >= newCount, does nothing.
    // Returns 'a'.
    static expand(a, newCount, element) {
        isList_(a)
        if (newCount.type != Num || !newCount.isInteger || newCount < 0) {
            Fiber.abort("newCount must be a non-negative integer.")
        }
        if (a.count >= newCount) return a
        for (i in a.count...newCount) a.add(element)
        return a
    }

    // Returns a clone of 'a' by recursively cloning any elements which are
    // themselves lists. However, at the scalar level elements cannot be deeply cloned
    // unless they are either immutable or inherit from the Cloneable trait.
    static clone(a) {
        isList_(a)
        var res = []
        clone_(res, a)
        return res
    }

    // Private worker method for 'clone' method.
    static clone_(res, a) {
        for (e in a) {
            res.add ((e is List) ? clone(e) :
                     (e is Cloneable || e is CloneableSeq) ? e.clone() : e)
        }
    }

    // Creates and returns a new FrozenList from 'a'.
    static freeze(a) { FrozenList.new(a) }

    // Returns a list of scalar elements by recursively flattening any elements
    // which are themselves lists.
    static flatten(a) {
        isList_(a)
        var res = []
        flatten_(res, a)
        return res
    }

    // Private worker method for 'flatten' method.
    static flatten_(res, a) {
        for (e in a) {
            if (e is List) flatten_(res, e) else res.add(e)
        }
    }

    // Applies a function to each element of a list and then flattens and returns the results.
    static flatMap(a, fn) {
        var res = a.map { |e| fn.call(e) }.toList
        res = flatten(res)
        return res
    }

    // Returns a list of two element lists consisting of each element of a list
    // and the result of applying a function to that element.
    static associate(a, af) { a.map { |e| [e, af.call(e)] } }

    // Returns a list of all elements which are in 'a1' but are not in 'a2'.
    static except(a1, a2) {
        isList_(a1)
        isList_(a2)
        var a3 = a1.toList
        for (e in a2) {
            var ix = a3.indexOf(e)
            if (ix >= 0) a3.removeAt(ix)
        }
        return a3
    }

    // Returns a list of all elements which are in both 'a1' and 'a2'.
    static intersect(a1, a2) { Lst.except(a1, Lst.except(a1, a2)) }

    // Returns a list of two element lists consisting of each element of 'a1' and
    // the corresponding element of 'a2' with the same index. If the two lists are of
    // unequal length, then only pairs which have a common index are returned.
    static zip(a1, a2) {
        isList_(a1)
        isList_(a2)
        var c1 = a1.count
        var c2 = a2.count
        var len = (c1 < c2) ? c1 : c2
        var res = []
        for (i in 0...len) res.add([a1[i], a2[i]])
        return res
    }

    // Performs the reverse operation to 'zip' returning the two unzipped lists.
    static unzip(a) {
        isList_(a)
        var a1 = []
        var a2 = []
        for (t in e) {
            a1.add(t[0])
            a2.add(t[1])
        }
        return [a1, a2]
    }

    // Extends the functionality of the built-in List.sort() method
    // by allowing only part of 'a' from indices 'start' to 'end' inclusive
    // to be sorted in place using 'comparer'. Returns 'a' after sorting.
    static sortPart(a, start, end, comparer) {
        isList_(a)
        a.quicksort_(start, end, comparer)
        return a
    }

    // As 'sortPart' above but uses the default comparer: {|i, j| i < j }.
    static sortPart(a, start, end) { sortPart(a, start, end) {|i, j| i < j } }

    // Returns a list of numbers between 'start' and 'end' inclusive
    // having a positive step of 'step' between successive numbers.
    // If 'ascend' is true, the numbers are incremented by 'step'
    // otherwise they are decremented by 'step'.
    // If `ascend' is true and start > end, an empty list is returned.
    // If 'ascend' is false and start < end, an empty list is returned.
    static between(start, end, step, ascend) {
        if (step <= 0) Fiber.abort("Step must be a positive number.")
        if ((start > end && ascend) || (start < end && !ascend)) return []
        var lst = []
        var i = start
        if (ascend) {
            while (i <= end) {
                lst.add(i)
                i = i + step
            }
        } else {
            while (i >= end) {
                lst.add(i)
                i = i - step
            }
        }
        return lst
    }

    // Convenience versions of the above method which use default values for some parameters.
    static between(start, end, step) { between(start, end, step, start <= end) }
    static between(start, end)       { between(start, end, 1, start <= end)    }

    // Generates and returns a list of 'n' numbers starting from and including 'first'
    // where each term is found by multiplying the previous one by 'multiplier'.
    static multiples(first, n, multiplier) {
        if (!(first is Num)) Fiber.abort("'first' must be a number.")
        if (!(n is Num) || !n.isInteger || n < 1) {
            Fiber.abort("'n' must be a positive integer.")
        }
        if (!(multiplier is Num)) Fiber.abort("'multiplier' must be a number.")
        var lst = List.filled(n, 0)
        lst[0] = first
        if (n == 1) return lst
        for (i in 1...n) {
            first = first * multiplier
            lst[i] = first
        }
        return lst
    }

    // As 'multiples' but where 'first' and 'multiplier' are the same.
    static powers(first, n) { multiples(first, n, first) }

    // Builds and returns a list of corresponding columns from a non-empty list 'a'
    // of rows, where each row is a non-empty list of any element type. The number
    // of columns in each row must be the same.
    static columns(a) {
        var nr = a.count
        if (nr == 0) Fiber.abort("List must contain at least one row.")
        var nc = a[0].count
        if (nc == 0) Fiber.abort("Rows must have at least one column.")
        if (a.skip(1).any { |e| e.count != nc }) {
            Fiber.abort("Rows must all have the same number of columns.")
        }
        var cols = List.filled(nc, null)
        for (j in 0...nc) {
            cols[j] = List.filled(nr, 0)
            for (i in 0...nr) cols[j][i] = a[i][j]
        }
        return cols
    }
}

/* FrozenList represents a List which cannot be changed after it has been constructed
   provided the underlying scalar type(s) are immutable or inherit from the Cloneable trait.
*/
class FrozenList is CloneableSeq {
    // Constructs a new frozen list from a List.
    construct new(a) {
        if (!(a is List)) Fiber.abort("Argument must be a list.")
        _a = Lst.clone(a) // clone it so it (hopefully) cannot be mutated externally
    }

    // Returns the number of elements in the frozen list.
    count { _a.count }

    // Clones this frozen list.
    clone() { Lst.freeze(_a) }

    // Private helper method which clones an element before allowing access to it.
    cloned_(e) { (e is List) ? Lst.clone(e) :
                 (e is Cloneable || e is CloneableSeq) ? e.clone() : e }

    // Gets the element at 'index.' If index is negative, it counts backwards from the end of
    // the frozen list where -1 is the last element.
    [index] { cloned_(_a[index]) }

    // Returns the index of 'value' in the current instance or -1 if 'value' is not found.
    indexOf(value) { _a.indexOf(value) }

    // Iterator protocol methods.
    iterate(iterator) { _a.iterate(iterator) }
    iteratorValue(iterator) { cloned_(_a.iteratorValue(iterator)) }

    // Returns the string representation of the underlying list.
    toString { _a.toString }
}

/* Stack represents a LIFO list of values. */ 
class Stack is CloneableSeq {
    // Constructs a new empty stack.
    construct new() { _stack = [] }

    // Returns the number of elements in the stack.
    count { _stack.count }

    // Returns whether or not the stack is empty.
    isEmpty { count == 0 }

    // Removes all elements from the stack.
    clear() { _stack.clear() }

    // Returns the last item on the stack without removing it.
    // Returns null if the stack is empty.
    peek() { (!isEmpty) ? _stack[-1] : null }

    // Adds 'item' to the stack and returns it.
    push(item) { _stack.add(item) }

    // Adds a sequence of 'items' (in order) to the stack and returns them.
    pushAll(items) { _stack.addAll(items) }

    // Removes the last item from the stack and returns it.
    // Returns null if the stack is empty.
    pop() {
        var item = peek()
        if (!(item is Null)) {
            _stack.removeAt(-1)
        }
        return item
    }

    // Clones the stack.
    clone() {
        var s = Stack.new()
        s.pushAll(Lst.clone(_stack))
        return s
    }

    // Iterator protocol methods.
    iterate(iterator) { _stack.iterate(iterator) }
    iteratorValue(iterator) { _stack.iteratorValue(iterator) }

    // Returns the string representation of the underlying list.
    toString { _stack.toString }
}

/* View represents a fixed window into a list and behaves for many purposes like a slice.
   However, unlike a slice, it does not create a new list but references the existing one
   which saves memory and reduces pressure on the garbage collector.
 
   Indexing of the view always starts at 0, and setting/swapping/sorting elements of
   of the view will be reflected in the underlying list and vice versa. However, deletions
   from the underlying list may invalidate the view bounds and insertions may 'move' it.
   As in the case of the List class, views support negative indices.
 
   There is inevitably a performance penalty when indexing the elements of the View compared
   to indexing the elements of the underlying list directly. To mitigate this penalty,
   unsafe get, set and switch methods are provided which do not check their arguments.
*/
class View is Sequence {
    // Creates a new View of a list between indices 'start' and 'end' inclusive.
    construct new(lst, start, end) {
        Lst.isList_(lst)
        var c = lst.count
        if (c == 0) Fiber.abort("List cannot be empty.")
        if (start < 0) start = c + start
        if (!(start is Num && start.isInteger && start>= 0 && start < c)) {
            Fiber.abort("'start' is out of range.")
        }
        if (end < 0) end = c + end
        if (!(end is Num && end.isInteger && end >= 0 && end < c)) {
            Fiber.abort("'end' is out of range.")
        }
        if (start > end) {
            Fiber.abort("'end' cannot be before 'start'.")
        }
        _lst = lst
        _start = start
        _end   = end
        _count = end - start + 1
    }
 
    // Private constructor which does not check the arguments.
    construct new_(lst, start, end) {
        _lst = lst
        _start = start
        _end   = end
        _count = end - start + 1
    }
 
    // Self-evident properties
    primary { _lst   }
    start   { _start }
    end     { _end   }
    count   { _count }
 
    // Converts the view to a new independent list.
    toList { _lst[_start.._end] }
 
    // Gets or sets the value at index 'i' of the view (zero based).
    [i] {
        if (i < 0) i = _count + i
        if (i < 0 || i > _count) Fiber.abort("Index is out of range.")
        return _lst[i + _start]
    }
 
    [i]=(v) {
        if (i < 0) i = _count + i
        if (i < 0 || i > _count) Fiber.abort("Index is out of range.")
        _lst[i + _start] = v
    }
 
    // Unsafe versions of the above indexers which are much quicker as the index is
    // not adjusted if negative nor checked to be within the view's bounds before
    // being passed (after adding _start) to the underlying list.
    // Only use when certain this adjustment/check is unnecessary.
    get(i) { _lst[i + _start] }
 
    set(i, v) {
        _lst[i + _start] = v
    }
 
    // Returns a new View which is a slice of this one.
    slice(start, end) {
        if (start < 0) start = _count + start
        if (start < 0 || start > _count) Fiber.abort("'start' is out of range.")
        if (end < 0) end = _count + end
        if (end < start || end > _count) Fiber.abort("'end' is out of range.")
        return View.new_(_lst, start + _start, end + _start)
    }
 
    // Copies this to a new otherwise identical View.
    copy() { View.new_(_lst, _start, _end) }
 
    // Returns the index of 'v' in the view or -1 if it does not exist.
    indexOf(v) {
        for (i in 0..._count) {
            if (_lst[i + _start] == v) return i
        }
        return -1
    }
 
    // Returns the last index of 'v' in the view or -1 if it does not exist.
    lastIndexOf(v) {
        for (i in _count-1..0) {
            if (_lst[i + _start] == v) return i
        }
        return -1
    }
 
    // Returns whether or not the view contains the value 'v'
    contains(v) { indexOf(v) >= 0 }
 
    // Swaps the elements at indices 'i' and 'j' in the view.
    swap(i, j) {
        if (i < 0) i = _count + i
        if (i < 0 || i > _count) Fiber.abort("First index is out of range.")
        if (j < 0) j = _count + j
        if (j < 0 || j > _count) Fiber.abort("Second index is out of range.")
        _lst.swap(i + _start, j + _start)
    }
 
    // Unsafe version of 'swap' above which is much quicker as the indices are
    // not adjusted if negative nor checked to be within the view's bounds before
    // being passed (after adding _start) to the underlying list.
    // Only use when certain these adjustments/checks are unnecessary.
    switch(i, j) {
       _lst.swap(i + _start, j + _start)
    }
 
    // Sorts the elements of the view in place using 'comparer' and returns it.
    sort(comparer) {
        Lst.sortPart(_lst, _start, _end, comparer)
        return this
    }
 
    // Sorts the elements of the view in place using the default comparer and returns it.
    sort() {
        Lst.sortPart(_lst, _start, _end)
        return this
    }
 
    // Sets all the elements of the view to the value 'v'.
    setAll(v) {
        for (i in _start.._end) _lst[i] = v
    }
 
    // Checks whether the view bounds are still valid following deletions from the underlying list.
    // If false, do not use unless and until the view becomes valid again.
    isValid { _end < _lst.count }
 
    // Iteration protocol methods. Note that the indices returned (although not normally exposed)
    // are those into the underlying list not the view itself.
    iterate(iterator) {
        if (!iterator) {
            _taken = 1
            return _start
        }
        _taken = _taken + 1
        return _taken > _count ? null : _lst.iterate(iterator)
    }
 
    iteratorValue(iterator) { _lst.iteratorValue(iterator) }
 
    // Returns the string representation of the view.
    toString { "[" + _lst.skip(_start).take(_count).join(", ") + "]" }
}