Category talk:Wren-seq: Difference between revisions
m
→Source code: Now uses Wren S/H lexer.
(→Source code: Added indexOf method to FrozenList class.) |
m (→Source code: Now uses Wren S/H lexer.) |
||
| (29 intermediate revisions by the same user not shown) | |||
Line 1:
===Source code===
<
import "./trait" for Cloneable, CloneableSeq
/* Seq supplements the Sequence class with some other operations on sequences. */
Line 17:
}
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
}
Line 28 ⟶ 42:
count = s.count - count
if (count <= 0) count = 0
return
}
Line 38 ⟶ 52:
Fiber.abort("Count must be a non-negative integer.")
}
count =
if (count <= 0) count = 0
return
}
// 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()
}
}
Line 46 ⟶ 115:
/* 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.") }
Line 55 ⟶ 276:
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.
Line 121 ⟶ 396:
static indexOfAny(a, values) { indexOfAny(a, values, 0) }
//
static
isList_(a)
var
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.
Line 137 ⟶ 431:
// Returns true if 'a' contains ANY of the values, false otherwise.
static containsAny(a, values) { indexOfAny(a
// Returns true if 'a' contains NONE of the values, false otherwise.
static containsNone(a, values) { !
// Groups each individual element of a list by count and indices, preserving order.
Line 251 ⟶ 545:
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.
Line 277 ⟶ 599:
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
}
Line 286 ⟶ 623:
}
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
}
Line 335 ⟶ 732:
// 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
Line 360 ⟶ 772:
}
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
}
}
Line 426 ⟶ 919:
pop() {
var item = peek()
if (!(item
_stack.removeAt(-1)
}
Line 447 ⟶ 940:
}
/* 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(", ") + "]" }
}</syntaxhighlight>
| |||