sort_libraries

Sort Libraries is a library of sort-related procedures for working on lists.

The library is inspired by Scheme's SRFI 132, and uses the same procedure API. The library provides procedures to sort, merge and work with sorted lists, and is useful particularly in cases where records or other structures must be ordered with custom comparison procedures.

Links

statistics

Procedures

list_binary_search (is_lt, is_equal, lst, item, start_index, end_index)

Returns the index of given item in list, or fails if item is not in list. 

  list_binary_search("<", "=", [1,1,2,3], 2) # => 3

Parameters:

is_lt
a procedure of two arguments, succeeding if the first is "less than" the second
is_equal
a procedure of two arguments, succeeding if the first is "equal to" the second
lst
a list of items
item
to find in list
start_index
optional start index to search from (defaults to 1)
end_index
optional end index to search to (defaults to length of list)

list_delete_neighbour_dups (is_equal, lst)

Returns a new list without duplicate items from the given (sorted) list. 

  list_delete_neighbour_dups("=", [1,1,2,2,3]) # => [1,2,3]

Parameters:

is_equal
a procedure of two arguments, succeeding if the first is "equal to" the second
lst
a list of items

list_find_median (is_lt, lst, nil, compute_mean)

Returns the median element from given list. 

  list_find_median("<", [1,2,3,4,5], 0) # => 3
  list_find_median("<", [1,2,3,4], 0)   # => 2.5

Parameters:

is_lt
a procedure of two arguments, succeeding if the first is "less than" the second
lst
a list of items
nil
value to return for an empty list
compute_mean
optional procedure for computing mean of two middle elements, defaults to using `arithmetic_mean` from statistics.

list_is_sorted (is_lt, lst)

Succeeds if the given list is sorted. 

  list_is_sorted("<", [1,2,2,3])  # => succeeds

Parameters:

is_lt
a procedure of two arguments, succeeding if the first is "less than" the second
lst
a list of items

list_merge (is_lt, lst1, lst2)

Returns a new ordered list consisting of the items in the two given lists. 

  list_merge("<", [1,3,5], [2,4]) # => [1,2,3,4,5]

Parameters:

is_lt
a procedure of two arguments, succeeding if the first is "less than" the second
lst1
a list of items
lst2
a list of items

list_select (is_lt, lst, k)

Returns the kth smallest element. Fails if the list is smaller than k elements. 

  list_select("<", [4,1,2,5], 3) # => 4

Parameters:

is_lt
a procedure of two arguments, succeeding if the first is "less than" the second
lst
a list of items
k
order index of element to return

list_separate (is_lt, lst, k)

Destructively modifies the list to place the smallest k items at the front. 

  list_separate("<", [4,1,2,5], 2) # list changed to => [1,2,5,4]

Parameters:

is_lt
a procedure of two arguments, succeeding if the first is "less than" the second
lst
a list of items
k
number of elements to move

list_sort (is_lt, lst)

Destructively sorts the given list. 

  list_sort(">", [3,1,2]) # list changed to => [3,2,1]

Parameters:

is_lt
a procedure of two arguments, succeeding if the first is "less than" the second
lst
a list of items
Home