Function EXTREMUM, EXTREMA, N-MOST-EXTREME

Syntax:

extremum sequence predicate &key key (start 0) end => morally-smallest-element

extrema sequence predicate &key key (start 0) end => morally-smallest-elements

n-most-extreme n sequence predicate &key key (start 0) end => n-smallest-elements

Arguments and Values:

sequence---a proper sequence.

predicate---a designator for a function of two arguments that returns a generalized boolean.

key---a designator for a function of one argument, or nil.

start, end---bounding index designators of sequence. The defaults for start and end are 0 and nil, respectively.

morally-smallest-element---the element of sequence that would appear first if the sequence were ordered according to sort using predicate and key

morally-smallest-elements---the identical elements of sequence that would appear first if the sequence were ordered according to sort using predicate and key. If predicate states that neither of two objects is before the other, they are considered identical. n---a positive integer

n-smallest-elements---the n elements of sequence that would appear first if the sequence were ordered according to sort using predicate and key

Description:

extremum returns the element of sequence that would appear first if the subsequence of sequence specified by start and end were ordered according to sort using predicate and key.

extremum determines the relationship between two elements by giving keys extracted from the elements to the predicate. The first argument to the predicate function is the part of one element of sequence extracted by the key function (if supplied); the second argument is the part of another element of sequence extracted by the key function (if supplied). Predicate should return true if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the predicate should return false.

The argument to the key function is the sequence element. The return value of the key function becomes an argument to predicate. If key is not supplied or nil, the sequence element itself is used. There is no guarantee on the number of times the key will be called.

If the key and predicate always return, then the operation will always terminate. This is guaranteed even if the predicate does not really consistently represent a total order (in which case the answer may be wrong). If the key consistently returns meaningful keys, and the predicate does reflect some total ordering criterion on those keys, then the answer will be right

The predicate is assumed to consider two elements x and y to be equal if (funcall predicate x y) and (funcall predicate y x) are both false.

The return value of (extremum predicate sequence :key key) can be defined as (elt (sort predicate (subseq sequence start end) :key key) 0) except when sequence is empty (see Exceptional Situations), but may use faster (less asymptotically complex) algorithms to find this answer.

extrema is similar to extremum, but it returns a list of values. There can be more than one extremum, as determined by predicate, and with extremum the choice of which extremum to return is arbitrary. extrema returns all the possible values which predicate determines to be equal.

n-most-extreme returns a list of n values without testing for equality. It orders sequence in the same way as extremum and extrema, then returns the first n elements of the sorted sequence.

Exceptional situations:

If sequence is empty, then the error no-extremum is signalled. Invoking the continue restart will cause extremum to return nil.

Should be prepared to signal an error of type type-error if sequence is not a proper sequence.

If there are fewer than n values in the part of sequence that n-most-extreme may operate on, it returns all the values it can in sorted order and signals the warning n-most-extreme-not-enough-elements. This warning stores the given values for n and the relevant subsequence, and they may be accessed with n-most-extreme-not-enough-elements-n and n-most-extreme-not-enough-elements-subsequence, respectively.

Implementation notes:

There are two implementations of this function included in cl-utilities, which should only concern you if you want to squeeze out more efficiency, since the versions perform differently on different inputs.

The function extremum-fastkey is used exactly like extremum, but it calls key fewer times. If key is fast, extremum-fastkey is slower than regular extremum, but if key is hard to compute you can get significant gains in speed. The extremum-fastkey function is more complicated than extremum, and therefore may be more likely to contain bugs. That said, it doesn't seem buggy.

Don't worry about the performance of passing #'identity as key. This is optimized by a compiler macro.