Category talk:Wren-sort: Difference between revisions
m
→Source code: Now uses Wren S/H lexer.
m (→Source code: Tweak.) |
m (→Source code: Now uses Wren S/H lexer.) |
||
| (9 intermediate revisions by the same user not shown) | |||
Line 1:
===Source code===
<
import "./trait" for Comparable
/*
Line 24:
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) {
Line 77:
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 {
Line 87 ⟶ 88:
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
}
Line 112 ⟶ 113:
}
}
quick_(a, s, r, cmp)
quick_(a, l, e, cmp)
Line 159:
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])
Line 175:
siftDown_(a, 0, end, cmp)
}
return a
}
Line 198 ⟶ 199:
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])
Line 210 ⟶ 211:
a[j+1] = v
}
return a
}
Line 216 ⟶ 218:
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])
Line 231 ⟶ 233:
}
}
return a
}
Line 237 ⟶ 240:
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])
Line 254 ⟶ 257:
}
}
return a
}
Line 294 ⟶ 298:
static isSorted(a) { isSorted(a, false) }
static isSortedDesc(a) { isSorted(a, true) }
}
Line 365 ⟶ 354:
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.
Line 412 ⟶ 405:
}
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
static
static highest(a) { highest(a, false) }
static quick(a, k) { quick(a, k, false) }
// Finds the median element(s) of a sorted list.
Line 435 ⟶ 480:
}
/*
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 }
}</syntaxhighlight>
| |||