*Function* **EXTREMUM, EXTREMA, N-MOST-EXTREME**

**Syntax:**

**extremum** *sequence predicate &key key (start 0) end* =>

**extrema** *sequence predicate &key key (start 0) end* =>

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

**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

**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.

Manual Index