Category talk:Wren-sort: Difference between revisions
m
→Source code: Now uses Wren S/H lexer.
(→Source code: Added SortedList class.) |
m (→Source code: Now uses Wren S/H lexer.) |
||
| (5 intermediate revisions by the same user not shown) | |||
Line 1:
===Source code===
<
import "./trait" for Comparable
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)
}
Line 157 ⟶ 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 173 ⟶ 175:
siftDown_(a, 0, end, cmp)
}
}
Line 196 ⟶ 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 208 ⟶ 211:
a[j+1] = v
}
}
Line 214 ⟶ 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 229 ⟶ 233:
}
}
}
Line 235 ⟶ 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 252 ⟶ 257:
}
}
}
Line 292 ⟶ 298:
static isSorted(a) { isSorted(a, false) }
static isSortedDesc(a) { isSorted(a, true) }
▲ var c = a.count
▲ var i = 0
▲ a[i] = a[j]
▲ a[j] = t
▲ }
}
Line 363 ⟶ 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 463 ⟶ 458:
// 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
static quick(a, k) { quick(a, k, false) }
// Finds the median element(s) of a sorted list.
Line 611 ⟶ 607:
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
}
Line 650 ⟶ 647:
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
// Not usually needed though see 'asList'.
resort() {
SortedList.sortAll_(_lst, _cmp)
return this
}
Line 684:
// 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.
Line 707 ⟶ 712:
// Returns the string representation of 'this'.
toString { _lst.toString }
}</
| |||