/* Module "sort.wren" */
import "./trait" for Comparable
/*
Cmp provides standard comparison methods for use with the Sort and Find classes.
All comparison methods return a function, which take two parameters p1 & p2 say and
returns -1, 0, or +1 depending on whether p1 < p2, p1 == p2 or p1 > p2 respectively.
*/
class Cmp {
static bool { Fn.new { |b1, b2| (b1 == b2) ? 0 : (b1) ? 1 : -1 } } // false < true
static boolDesc { Fn.new { |b1, b2| (b1 == b2) ? 0 : (b1) ? -1 : 1 } } // false > true
static num { Fn.new { |n1, n2| (n1-n2).sign } } // numerical order
static numDesc { Fn.new { |n1, n2| (n2-n1).sign } } // reverse numerical order
// For other objects which define the comparison operators.
static comparable { Fn.new { |c1, c2| (c1 == c2) ? 0 : (c1 < c2) ? -1 : 1 } }
static comparableDesc { Fn.new { |c1, c2| (c1 == c2) ? 0 : (c1 < c2) ? 1 : -1 } }
// Lexicographical order of codepoints.
static string {
return Fn.new { |s1, s2|
if (s1 == s2) return 0
var cp1 = s1.codePoints.toList
var cp2 = s2.codePoints.toList
var len = (cp1.count <= cp2.count) ? cp1.count : cp2.count
for (i in 0...len) {
if (cp1[i] < cp2[i]) return -1
if (cp1[i] > cp2[i]) return 1
}
return (cp1.count < cp2.count) ? -1 : 1
}
}
// Reverse lexicographical order of codepoints.
static stringDesc { Fn.new { |s1, s2| -string.call(s1, s2) } }
// Private helper function to enable case insensitivity.
static lower_(s) {
if (s == "") return s
var cps = s.codePoints.toList
for (i in 0...cps.count) {
var c = cps[i]
if (c >= 65 && c <= 90) cps[i] = c + 32
}
return cps.reduce("") { |acc, c| acc + String.fromCodePoint(c) }
}
// As 'string' or 'stringDesc' but ignoring case.
static insensitive { Fn.new { |s1, s2| string.call(lower_(s1), lower_(s2)) } }
static insensitiveDesc { Fn.new { |s1, s2| stringDesc.call(lower_(s1), lower_(s2)) } }
// As 'string' or 'stringDesc' using the object's string representation.
static general { Fn.new { |g1, g2| string.call(g1.toString, g2.toString) } }
static generalDesc { Fn.new { |g1, g2| stringDesc.call(g1.toString, g2.toString) } }
// Provides a default comparison function depending on the type of 'v'.
static default(v) {
return (v is Num) ? Cmp.num :
(v is String) ? Cmp.string :
(v is Bool) ? Cmp.bool :
(v is Comparable) ? Cmp.comparable : Cmp.general
}
// Provides a default descending comparison function depending on the type of 'v'.
static defaultDesc(v) {
return (v is Num) ? Cmp.numDesc :
(v is String) ? Cmp.stringDesc :
(v is Bool) ? Cmp.boolDesc :
(v is Comparable) ? Cmp.comparableDesc : Cmp.generalDesc
}
}
/*
Sort contains various sorting methods which may be useful in different scenarios.
As it would be too expensive to check that all elements of a large list are of the
same type or compatible types, errors are left to emerge naturally. In place sorting
methods return the original list after sorting.
*/
class Sort {
// Private helper function 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.") }
// In place quicksort. Unstable.
static quick(a, s, e, cmp) {
isList_(a)
var c = a.count
if (c < 2 || s < 0 || s >= c || e <= s || e >= c) return a
if (!e) e = c - 1
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
quick_(a, s, e, cmp)
return a
}
// Private worker method for quicksort.
static quick_(a, s, e, cmp) {
if (e <= s) return
var p = a[((s+e)/2).floor]
var l = s
var r = e
while (l <= r) {
while (cmp.call(a[l], p) < 0) l = l + 1
while (cmp.call(a[r], p) > 0) r = r - 1
if (l <= r) {
var t = a[l]
a[l] = a[r]
a[r] = t
l = l + 1
r = r - 1
}
}
quick_(a, s, r, cmp)
quick_(a, l, e, cmp)
}
// Out of place merge sort. Stable.
static merge(m, cmp) {
isList_(m)
var len = m.count
if (len < 2) return m
if (cmp == true) cmp = Cmp.defaultDesc(m[0])
if (!cmp) cmp = Cmp.default(m[0])
return merge_(m, cmp)
}
// Private worker function for merge sort.
static merge_(m, cmp) {
var len = m.count
if (len < 2) return m
var middle = (len/2).floor
var left = m[0...middle]
var right = m[middle..-1]
left = merge_(left, cmp)
right = merge_(right, cmp)
if (cmp.call(left[-1], right[0]) <= 0) {
left.addAll(right)
return left
}
var result = []
while (left.count > 0 && right.count > 0) {
if (cmp.call(left[0], right[0]) <= 0) {
result.add(left[0])
left = left[1..-1]
} else {
result.add(right[0])
right = right[1..-1]
}
}
if (left.count > 0) result.addAll(left)
if (right.count > 0) result.addAll(right)
return result
}
// In place heap sort. Unstable.
static heap(a, cmp) {
isList_(a)
var count = a.count
if (count < 2) return a
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
var start = ((count - 2)/2).floor
while (start >= 0) {
siftDown_(a, start, count - 1, cmp)
start = start - 1
}
var end = count - 1
while (end > 0) {
var t = a[end]
a[end] = a[0]
a[0] = t
end = end - 1
siftDown_(a, 0, end, cmp)
}
return a
}
// Private helper function for heap sort.
static siftDown_(a, start, end, cmp) {
var root = start
while (root*2 + 1 <= end) {
var child = root*2 + 1
if (child + 1 <= end && cmp.call(a[child], a[child+1]) < 0) child = child + 1
if (cmp.call(a[root], a[child]) < 0) {
var t = a[root]
a[root] = a[child]
a[child] = t
root = child
} else {
return
}
}
}
// In place insertion sort. Stable.
static insertion(a, cmp) {
isList_(a)
var c = a.count
if (c < 2) return a
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
for (i in 1..c-1) {
var v = a[i]
var j = i - 1
while (j >= 0 && cmp.call(a[j], v) > 0) {
a[j+1] = a[j]
j = j - 1
}
a[j+1] = v
}
return a
}
// In place selection sort. Unstable.
static selection(a, cmp) {
isList_(a)
var c = a.count
if (c < 2) return a
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
var last = c - 1
for (i in 0...last) {
var iMin = i
for (j in i+1..last) {
if (cmp.call(a[j], a[iMin]) < 0) iMin = j
}
if (iMin != i) {
var t = a[i]
a[i] = a[iMin]
a[iMin] = t
}
}
return a
}
// In place shell sort. Unstable.
static shell(a, cmp) {
isList_(a)
var n = a.count
if (n < 2) return a
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
var gaps = [701, 301, 132, 57, 23, 10, 4, 1]
for (gap in gaps) {
if (gap < n) {
for (i in gap...n) {
var t = a[i]
var j = i
while (j >= gap && cmp.call(a[j-gap], t) > 0) {
a[j] = a[j - gap]
j = j - gap
}
a[j] = t
}
}
}
return a
}
// Convenience methods which sort the whole of a list using a particular sorting
// method with default parameters. 'false' indicates a default ascending sort.
static quick(a) { quick(a, 0, a.count-1, false) }
static merge(a) { merge(a, false) }
static heap(a) { heap(a, false) }
static insertion(a) { insertion(a, false) }
static selection(a) { selection(a, false) }
static shell(a) { shell(a, false) }
// As above but sort in descending order.
static quickDesc(a) { quick(a, 0, a.count-1, true) }
static mergeDesc(a) { merge(a, true) }
static heapDesc(a) { heap(a, true) }
static insertionDesc(a) { insertion(a, true) }
static selectionDesc(a) { selection(a, true) }
static shellDesc(a) { shell(a, true) }
// Convenience methods which sort the whole of a list of strings ignoring case
// using quicksort with the appropriate comparison function.
static insensitive(a) { quick(a, 0, a.count-1, Cmp.insensitive) }
static insensitiveDesc(a) { quick(a, 0, a.count-1, Cmp.insensitiveDesc) }
// Checks whether a list is already sorted.
static isSorted(a, cmp) {
isList_(a)
var c = a.count
if (c < 2) return true
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
for (i in 1...c) {
if (cmp.call(a[i-1], a[i]) > 0) return false
}
return true
}
// Convenience versions of the above.
static isSorted(a) { isSorted(a, false) }
static isSortedDesc(a) { isSorted(a, true) }
}
/*
Find contains methods to search for values in lists where a comparison function is needed.
As it would be too expensive to check that all elements of a large list are of the same
or compatible types and are already sorted, errors are left to emerge naturally.
*/
class Find {
// Searches a sorted list for all instances of a particular value
// using the binary search algorithm and the comparison function
// by which it was (hopefully) sorted in the first place.
// 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 the range of indices at which the value was found or, if not found,
// the index at which it would need to be inserted.
static all(a, value, cmp) {
Sort.isList_(a)
var count = a.count
if (count == 0) return [false, 0, 0..0]
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
var low = 0
var high = count - 1
while (low <= high) {
var mid = ((low + high)/2).floor
if (cmp.call(a[mid], value) >= 0) {
high = mid - 1
} else {
low = mid + 1
}
}
var found = (low < count && a[low] == value)
if (!found) return [false, 0, low..low]
if (low == a.count - 1) return [true, 1, low..low]
var last = low + 1
while (last < a.count) {
if (a[last] != value) break
last = last + 1
}
return [true, last-low, low..last-1]
}
// Works similarly to 'all' but only returns the index of the first match
// or -1 if there were no matches at all.
static first(a, value, cmp) {
var t = all(a, value, cmp)
return (t[1] > 0) ? t[2].from : -1
}
// Works similarly to 'all' but only returns the index of the last match
// or -1 if there were no matches at all.
static last(a, value, cmp) {
var t = all(a, value, cmp)
return (t[1] > 0) ? t[2].to : -1
}
// Works similarly to 'all' but only returns the index of the first match
// or the index at which it would need to be inserted if there were no matches at all.
static nearest(a, value, cmp) { all(a, value, cmp)[2].from }
// Finds the lowest value in an unsorted list according to 'cmp' but without sorting.
// Returns a list of three items:
// The first item is the lowest value.
// The second item is the number of times the lowest value was found.
// The third item is a list of indices at which the lowest value was found.
static lowest(a, cmp) {
Sort.isList_(a)
var count = a.count
if (count == 0) Fiber.abort("An empty list does not have a lowest element.")
if (count == 1) return [a[0], 1, [0]]
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
var min = a[0]
var iMin = [0]
for (i in 1...count) {
var m = cmp.call(a[i], min)
if (m < 0) {
min = a[i]
iMin = [i]
} else if (m == 0) {
iMin.add(i)
}
}
return [min, iMin.count, iMin]
}
// As 'lowest' but finds the highest value of the list according to 'cmp'
static highest(a, cmp) {
Sort.isList_(a)
var count = a.count
if (count == 0) Fiber.abort("An empty list does not have a lowest element.")
if (count == 1) return [a[0], 1, [0]]
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
var max = a[0]
var iMax = [0]
for (i in 1...count) {
var m = cmp.call(a[i], max)
if (m > 0) {
max = a[i]
iMax = [i]
} else if (m == 0) {
iMax.add(i)
}
}
return [max, iMax.count, iMax]
}
// Private helper function for 'quick' method.
static partition_(a, left, right, pivotIndex, cmp) {
var pivotValue = a[pivotIndex]
a[pivotIndex] = a[right]
a[right] = pivotValue
var storeIndex = left
var i = left
while (i < right) {
if (cmp.call(a[i], pivotValue) < 0) {
var t = a[storeIndex]
a[storeIndex] = a[i]
a[i] = t
storeIndex = storeIndex + 1
}
i = i + 1
}
var temp = a[right]
a[right] = a[storeIndex]
a[storeIndex] = temp
return storeIndex
}
// Finds the 'k'th smallest element of an unsorted list according to 'cmp'
// using the 'quickselect' algorithm. 'k' is zero based.
static quick(a, k, cmp) {
Sort.isList_(a)
if (k.type != Num || !k.isInteger || k < 0) {
Fiber.abort("'k' must be a non-negative integer")
}
var count = a.count
if (count <= k) Fiber.abort("The list is too small.")
if (count == 1) return a[0]
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
var left = 0
var right = count - 1
while (true) {
if (left == right) return a[left]
var pivotIndex = ((left + right)/2).floor
pivotIndex = partition_(a, left, right, pivotIndex, cmp)
if (k == pivotIndex) {
return a[k]
} else if (k < pivotIndex) {
right = pivotIndex - 1
} else {
left = pivotIndex + 1
}
}
}
// Convenience versions of the above which use default values for the 'cmp' parameter.
static all(a, value) { all(a, value, false) }
static first(a, value) { first(a, value, false) }
static last(a, value) { last(a, value, false) }
static nearest(a, value) { nearest(a, value, false) }
static lowest(a) { lowest(a, false) }
static highest(a) { highest(a, false) }
static quick(a, k) { quick(a, k, false) }
// Finds the median element(s) of a sorted list.
// Returns a list of three items:
// The first item is a list of the median element(s).
// The second item is the number of median element(s).
// The third item is the range of indices at which the median element(s) occur.
static median(a) {
Sort.isList_(a)
var c = a.count
if (c == 0) Fiber.abort("An empty list does not have a median element.")
var hc = (c/2).floor
return (c%2 == 1) ? [[a[hc]], 1, hc..hc] : [[a[hc-1], a[hc]], 2, hc-1..hc]
}
}
/*
SortedList represents a list which is always sorted with respect to some comparison function.
This means that lookups are much faster for large lists as we can use binary search.
When the entire list needs to be sorted (as opposed to a single element 'insertion' sort) and
has at least 10 elements, the 'quicksort' algorithm is used and so the sort is unstable.
If a stable sort is required, add items one by one, never in bulk.
For methods which require an index to be passed, negative indices are supported.
*/
class SortedList is Sequence {
// Private helper function to check that 'a' is a sequence and throw an error otherwise.
static isSeq_(a) { (a is Sequence) ? true : Fiber.abort("Argument must be a sequence.") }
// Private helper function to check that 'cmp' is a suitable comparison function
// and throw an error otherwise.
static isCmp_(cmp) {
if ((cmp is Fn) && cmp.arity == 2) return true
Fiber.abort("Argument must be a comparison function which takes 2 arguments.")
}
// Private helper method to sort 'lst' in place using 'cmp' and a suitable algorithm.
static sortAll_(lst, cmp) {
if (lst.count < 10) {
Sort.insertion(lst, cmp)
} else {
Sort.quick(lst, 0, lst.count - 1, cmp)
}
}
// Creates a new empty SortedList using a comparer 'cmp'.
construct new(cmp) {
SortedList.isCmp_(cmp)
_lst = []
_cmp = cmp
}
// Private constructor to create a new empty SortedList
// from a list a which is already sorted using 'cmp'.
construct new_(a, cmp) {
_lst = a
_cmp = cmp
}
// Creates a new SortedList from a sequence 'a' and comparer 'cmp'.
construct fromSeq(a, cmp) {
SortedList.isSeq_(a)
SortedList.isCmp_(cmp)
_lst = a.toList
_cmp = cmp
SortedList.sortAll_(_lst, _cmp)
}
// Creates a new SortedList from a sequence 'a'
// using the default comparer for its first element's type.
construct fromSeq(a) {
SortedList.isSeq_(a)
if (a.count == 0) {
Fiber.abort("Sequence must have at least one element to deduce the comparer.")
}
_lst = a.toList
if ((a is List) || (a is SortedList)) {
_cmp = Cmp.default(_lst[0])
} else {
_cmp = Cmp.default(_lst.take(1).toList[0])
}
SortedList.sortAll_(_lst, _cmp)
}
// Creates a new SortedList from a single value 's'
// using a comparer 'cmp'.
construct fromOne(s, cmp) {
SortedList.isCmp_(cmp)
_lst = [s]
_cmp = cmp
}
// Creates a new SortedList from a single value 's'
// using the default comparer for its type.
construct fromOne(s) {
_lst = [s]
_cmp = Cmp.default(s)
}
// Returns the number of elements in the sorted list.
count { _lst.count }
// Returns whether or not the sorted list is empty.
isEmpty { count == 0 }
// Removes all elements from the sorted list.
clear() { _lst.clear() }
// Adds 'item' to the sorted list and returns it.
add(item) {
_lst.add(item)
Sort.insertion(_lst, _cmp)
return item
}
// Adds each element of a sequence 'other' to the sorted list
// and returns the added items.
addAll(other) {
SortedList.isSeq_(other)
_lst.addAll(other)
SortedList.sortAll_(_lst, _cmp)
return other
}
// Removes the first element in the sorted list that matches 'e'.
// and returns it or returns null if not found.
remove(e) {
var ix = indexOf(e)
if (ix == -1) return null
return _lst.removeAt(ix)
}
// Removes all elements in the sorted list that match 'e'
// Returns 'value' if there were any removals, otherwise 'null'.
removeAll(e) {
var ix = indexOf(e)
if (ix == -1) return null
while (ix < _lst.count && _lst[ix] == e) _lst.removeAt(ix)
return e
}
// Removes the element at index 'i' and returns it.
removeAt(i) { _lst.removeAt(i) }
// Removes all duplicates from 'this' and returns the result.
prune() {
var c = _lst.count
if (c < 2) return this
for (i in c-1..1) {
if (_lst[i-1] == _lst[i]) _lst.removeAt(i)
}
return this
}
// Returns a new Sorted list consisting only of distinct elements of 'this'.
distinct {
var sl = copy()
sl.prune()
return sl
}
// Replaces all occurrences of 'old' by 'swap' in the sorted list and returns ['old', 'swap'].
replace(old, swap) {
var ix = indexOf(old)
if (ix >= 0) {
while (ix < _lst.count && _lst[ix] == old) {
_lst[ix] = swap
ix = ix + 1
}
SortedList.sortAll_(_lst, _cmp)
}
return [old, swap]
}
// Returns a copy of this.
copy() { SortedList.new_(_lst.toList, _cmp) }
// Converts 'this' to an 'ordinary' list and returns the result.
toList { _lst.toList }
// Returns the internal list for use with List methods which don't mutate it.
// If they do, re-sort 'this' afterwards.
asList { _lst }
// Resort 'this' using a (different) comparison function and returns the result.
resort(cmp) {
SortedList.isCmp_(cmp)
_cmp = cmp
SortedList.sortAll_(_lst, _cmp)
return this
}
// Resort 'this' using the current comparison function and returns the result.
// Not usually needed though see 'asList'.
resort() {
SortedList.sortAll_(_lst, _cmp)
return this
}
// Returns the element (or a copy of the range of elements)
// at index 'i' within the sorted list.
[index] {
if (!(index is Range)) {
return _lst[index]
}
return SortedList.new_(_lst[index], _cmp)
}
// Replaces the element at 'index' in the sorted list with 'item'.
[index]=(item) {
_lst[index] = item
Sort.insertion(_lst, _cmp)
}
// Uses binary search to find the index of the first occurence of 'value'
// in the sorted list. Returns -1 if not found.
indexOf(value) { Find.first(_lst, value, _cmp) }
// Uses binary search to find the index of the last occurence of 'value'
// in the sorted list. Returns -1 if not found.
lastIndexOf(value) { Find.last(_lst, value, _cmp) }
// Uses binary search to find the index of the first occurence of 'value'
// in the sorted list. Returns the index at which it would need to be inserted
// if not found.
nearestIndexOf(value) { Find.nearest(_lst, value, _cmp) }
// Iterator protocol methods.
iterate(iterator) { _lst.iterate(iterator) }
iteratorValue(iterator) { _lst.iteratorValue(iterator) }
// Creates a new sorted list by adding the elements of a sequence 'other'
// to the elements of 'this' and using the same comparer to sort them.
+(other) {
var res = _lst + other
SortedList.sortAll_(res, _cmp)
return SortedList.new_(res, _cmp)
}
// Creates a new sorted list by repeating the present one 'count' times
// and then sorting it.
*(count) {
var res = _lst * count
SortedList.sortAll_(res, _cmp)
return SortedList.new_(res, _cmp)
}
// Returns the string representation of 'this'.
toString { _lst.toString }
}
