ordering

Overview

A collection of utility functions and algorithms for working with ordered data.

This module contains several utilities for working with ordering functions. An ordering function is a binary function which returns the first argument if it is ordered before the second argument or if the two arguments are equal.

For example, the natural increasing order, ordering.INCREASING, is defined as:

function ordering.INCREASING(x,y)
   return x <= y and x or y
end

Instances of ordered collections in the Sano library (SkipMap, SkipSet, PairingHeap) can be constructed using any user-defined ordering function (by default they use ordering.INCREASING). For each of these collections, the ordering function is interpreted in the obvious way: the 'retrieval' order of the collection will be consistent with the order in which elements are returned by the ordering function:

> p = PairingHeap:new(ordering.DECREASING)
> p:addAll{3,2,1,6,5}; print(p:get())
6
> s = SkipSet:new(ordering.DECREASING)
> s:addAll{1,2,3,4,5,6}; print(s)
{6, 5, 4, 3, 2, 1}

ordering.DECREASING returns larger elements first, so the largest element is at the top of the heap, and at the start of the iteration order of the SkipSet (an ordered set implementation).

In addition, this module contains several algorithms for operating on ordered data. See for example: ordering.first, ordering.kth, ordering.sorted, and ordering.lexicographical

Summary

DECREASINGReturns x if x >= y and y otherwise.
INCREASINGReturns x if x <= y and y otherwise.
byKeyReturns a new ordering, obk, in which obk(x,y) == x iff x[key] <= y[key].
byTransformReturns a new ordering obt, in which obt(x,y) == x iff transform(x) <= transform(y).
chainedReturns a new ordering based on a chain of ordering functions.
equals...
firstReturns the first element that would appear if the elements of iterable were sorted by orderFn, which defaults to ordering.INCREASING.
greaterThan...
greaterThanOrEq...
heapsortedSorts the elements of iterable using a heap along with the specified ordering function.
isSortedTesting function which returns true if the iterable is sorted according to the specified ordering function.
keyOrderedReturns an iterator over the key-value pairs of mapIterable, ordered by key.
kthReturns the element that would appear at the kth index if the elements of iterable were sorted.
firstReturns the last element that would appear if the elements of iterable were sorted by orderFn, which defaults to ordering.INCREASING.
lessThan...
lessThanOrEq...
lexicographicalReturns -1, 0, or 1 indicating whether iterable1 is ordered lexicographically before, is equal to, or is ordered after iterable2.
ranked...
reverseReturns a new ordering which is the reverse of orderFn.
rsortedReturns a Sano Vector reverse sorted using the built-in Lua sort function and the ordering function specified (default ordering.INCREASING).
sortedReturns a Sano Vector sorted using the built in Lua sort function and the ordering specified (default ordering.INCREASING).

Detail

ordering.DECREASING(x,y)

Returns x if x >= y and y otherwise.

ordering.INCREASING(x,y)

Returns x if x <= y and y otherwise.

This ordering is the default ordering typically used in functions where an (optional) ordering function is left unspecified.

ordering.byKey(key [,orderFn])

Returns a new ordering, obk, in which obk(x,y) == x iff x[key] <= y[key].

For example, to sort a vector of tables, t, using the second element of each table as the sort criteria:

> v = vector({1,1},{1,2},{1,1.3},{1,1.4})
> sorted = ordering.sorted(v, ordering.byKey(2))
> for t in sorted:iter() do print(t[1],t[2]) end
1       1
1       1.3
1       1.4
1       2

ordering.byTransform(transform)

Returns a new ordering obt, in which obt(x,y) == x iff transform(x) <= transform(y).

ordering.chained(...)

Returns a new ordering based on a chain of ordering functions.

If the first ordering function in the chain determines the two input are equal, the second ordering function is consulted, and so on, until one of the orderings reveals a preference or the chain is exhausted. In effect, orderings later in the chain are used to 'break ties' between orderings earlier in the chain.

This is useful for sorting some data based on multiple criteria. For example, we might sort a list of Tuple objects storing names in the form (first, last) using the following code:

> -- names = [('J','Jones'),('A','Jones'),('A','Smith'),('B','Smith')]
> -- sort by last name, then use first name to break ties
> names:sort(ordering.chained(ordering.byKey(2), ordering.byKey(1)))
> print(names)
[("A", "Jones"), ("J", "Jones"), ("A", "Smith"), ("B", "Smith")]

equals

ordering.first(iterable [,orderFn])

Returns the first element that would appear if the elements of iterable were sorted by orderFn, which defaults to ordering.INCREASING.

greaterThan

greaterThanOrEq

ordering.heapsorted(iterable, orderFn)

Sorts the elements of iterable using a heap along with the specified ordering function.

ordering.isSorted(iterable [,orderFn])

Testing function which returns true if the iterable is sorted according to the specified ordering function.

ordering.keyOrdered(mapIterable, orderFn)

Returns an iterator over the key-value pairs of mapIterable, ordered by key.

mapIterable may be a Lua table or any two element iterable. See iter.mapIter for more information on the map-iterable contract.

Examples:

> keys, vals = "edcba", iter.count(5,1,-1)
> for k,v in ordering.keyOrdered(iter.zip(keys,vals)) do print(k,v) end
a       1
b       2
c       3
d       4
e       5
> -- equivalently:
> m = {a=1,b=2,c=3,d=4,e=5}
> for k,v in ordering.keyOrdered(m) do print(k,v)
a       1
b       2
c       3
d       4
e       5

ordering.kth(iterable, k, orderFn)

Returns the element that would appear at the kth index if the elements of iterable were sorted.

This method also returns as a second value a sano.Vector, v in which:

For example:

> v = vector(iter.count(1,10)); v:shuffle(); print(v)
[4, 3, 9, 2, 6, 8, 5, 1, 10, 7]
> print(ordering.kth(v,6))
6       [1, 2, 3, 5, 4, 6, 7, 9, 10, 8]

The element 6 is in the 6th position and is the first value returned. The second value returned is the Vector used for partitioning. Notice that the set of elements which appear before 6 in the Vector are the same that would appear if the entire Vector were sorted; likewise for the set of elements which appear after 6.

The time complexity is expected O(size(iterable)). See http://en.wikipedia.org/wiki/Median_algorithm for more information on the algorithm used.

If iterable is a Vector, the operation is done IN PLACE; otherwise, the elements of iterable are added to a new Vector. In either case, the Vector (new or otherwise) is returned as the second value.

param k: must be positive and <= the number of elements in iterable

ordering.first(iterable [,orderFn])

Returns the last element that would appear if the elements of iterable were sorted by orderFn, which defaults to ordering.INCREASING.

lessThan

lessThanOrEq

ordering.lexicographical(iterable1, iterable2 [,orderFn])

Returns -1, 0, or 1 indicating whether iterable1 is ordered lexicographically before, is equal to, or is ordered after iterable2.

The ordering on strings is a lexicographical ordering based on the ordering of individual letters - if the two strings have a different first letter, the string which starts with the alphabetically first letter is ordered first. If the two strings have the same first letter, then second letter is examined, and so on, until one or both of the strings run out of letters or pairwise comparisons reveal an ordering.

More generally, in a lexicographical ordering:

If a = a1, a2, ..., aN and b = b1, b2, ..., bN, then a < b iff:
b1 > a1
OR
b1 == a1, b2 == a2, ..., bK == aK, bK+1 > aK+1 (b is greater than a)

If a and b have different sizes, the smaller will be ordered before the larger if pairwise comparisons do not reveal an ordering.

Examples: (1,1) <= (1,1), () <= (1), (1,2,1) <= (1,3)

The evaluation is 'short-circuit' and halts as soon as there is enough information to determine the ordering.

returns -1 if iterable1 is ordered before iterable2, 0 if the two iterables are equal, 1 if iterable2 is ordered after iterable2

ranked

ordering.reverse(orderFn)

Returns a new ordering which is the reverse of orderFn.

ordering.rsorted(iterable [,orderFn])

Returns a Sano Vector reverse sorted using the built-in Lua sort function and the ordering function specified (default ordering.INCREASING).

If orderFn is left unspecified, the order of the returned Vector will be max first.

ordering.sorted(iterable [,orderFn])

Returns a Sano Vector sorted using the built in Lua sort function and the ordering specified (default ordering.INCREASING).

ordering.test

unit test