Category talk:Wren-sort: Difference between revisions
→Source code: Added SortedList class.
(→Source code: Bug fix) |
(→Source code: Added SortedList class.) |
||
Line 482:
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>
| |||