Category talk:Wren-sort: Difference between revisions
Content added Content deleted
(→Source code: Bug fix) |
(→Source code: Added SortedList class.) |
||
Line 482: | Line 482: | ||
return (c%2 == 1) ? [[a[hc]], 1, hc..hc] : [[a[hc-1], a[hc]], 2, hc-1..hc] |
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'. |
|||
prune() { |
|||
var c = _lst.count |
|||
if (c < 2) return |
|||
for (i in c-1..1) { |
|||
if (_lst[i-1] == _lst[i]) _lst.removeAt(i) |
|||
} |
|||
} |
|||
// 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. |
|||
resort(cmp) { |
|||
SortedList.isCmp_(cmp) |
|||
_cmp = cmp |
|||
SortedList.sortAll_(_lst, _cmp) |
|||
} |
|||
// Resort 'this' using the current comparison function. Not usually needed though see 'asList'. |
|||
resort() { |
|||
SortedList.sortAll_(_lst, _cmp) |
|||
} |
|||
// 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) } |
|||
// 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 } |
|||
}</lang> |
}</lang> |