Category talk:Wren-sort: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎Source code: Made several methods 'chaining' friendly.)
(→‎Source code: Added Find.nearest and SortedList.nearestIndexOf methods.)
Line 370: Line 370:
return (t[1] > 0) ? t[2].to : -1
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.
// Finds the lowest value in an unsorted list according to 'cmp' but without sorting.
Line 470: Line 474:


// Convenience versions of the above which use default values for the 'cmp' parameter.
// Convenience versions of the above which use default values for the 'cmp' parameter.
static all(a, value) { all(a, value, false) }
static all(a, value) { all(a, value, false) }
static first(a, value) { first(a, value, false) }
static first(a, value) { first(a, value, false) }
static last(a, value) { last(a, value, false) }
static last(a, value) { last(a, value, false) }
static lowest(a) { lowest(a, false) }
static nearest(a, value) { nearest(a, value, false) }
static highest(a) { highest(a, false) }
static lowest(a) { lowest(a, false) }
static quick(a, k) { quick(a, k, false) }
static highest(a) { highest(a, false) }
static quick(a, k) { quick(a, k, false) }


// Finds the median element(s) of a sorted list.
// Finds the median element(s) of a sorted list.
Line 695: Line 700:
// in the sorted list. Returns -1 if not found.
// in the sorted list. Returns -1 if not found.
lastIndexOf(value) { Find.last(_lst, value, _cmp) }
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.
// Iterator protocol methods.

Revision as of 18:33, 12 June 2022

Source code

<lang ecmascript>/* 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)  }
   // Reverses a list in place and returns it.
   static reverse(a) {
       var c = a.count
       if (c < 2) return a
       var i = 0
       var j = a.count - 1
       while (i < j) {
           var t = a[i]
           a[i] = a[j]
           a[j] = t
           i = i + 1
           j = j - 1
       }
       return a
   }

}

/*

   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 }

}</lang>