Version: 5.2
3 Orders and Ordered Dictionaries
This library defines orders and the ordered
dictionary generic interface.
Contract for orderings, represented by the symbols '=,
'<, and '>.
Struct-type property for defining new ordered dictionary types. The
value associated with
prop:ordered-dict should be an
immutable vector of six procedures, two “extrema” procedures and
four “search” procedures. The extrema procedures must satisfy
e/c and the search procedures must satisfy
s/c:
The procedures are implementations of the following generic functions:
A struct type that implements prop:ordered-dict must also
implement prop:dict.
Returns the position of the least (greatest) key in the ordered
dictionary dict. If dict is empty, #f is
returned.
Returns the position of the least key greater than key, the
least key greater than or equal to key, the greatest key less
than key, and the greatest key less than or equal to
key, respectively. If no key satisfies the criterion,
#f is returned.
Produces a named order object encapsulating a domain contract and a
comparator function. If a single procedure is given, it is used
directly as the comparator. If two or three procedures are given, they
are used to construct the comparator.
The domain-contract is not applied to the comparison
function; rather, clients of the order are advised to incorporate the
domain contracts into their own contracts. For example, when a
splay-tree (see data/splay-tree) is constructed with
an order, it applies the domain-contract to its keys. Thus the
contract is checked once per dictionary procedure call, rather than on
every comparison.
An order object is applicable as a procedure; it behaves as its
comparator.
Examples: |
| > (define string-order (order 'string-order string? string=? string<?)) | | > (string-order "abc" "acdc") | '< | | > (string-order "x" 12) | string=?: expects type <string> as 2nd argument, given: 12; | other arguments were: "x" |
|
Returns #t if x is an order object, #f
otherwise.
Extracts the comparator function from an order object.
Extracts the domain contract from an order object.
Returns a procedure representing the order’s equality relation or
less-than relation, respectively.
The order of the real numbers. The domain of
real-order
excludes
+nan.0 but includes
+inf.0 and
-inf.0. The standard numeric comparisons (
=,
<) are used; exact
1 is equal to inexact
1.0.
An ad hoc order that encompasses many built-in Racket data types. The
datum-order comparator orders values of the same data type
according to the data type’s natural order:
string=?,
string<? for strings, for example (but see the warning about
numbers below). Different data types are ordered arbitrarily but
contiguously; for example, all strings sort before all vectors, or
vice versa. Programs should not rely on the ordering of different data
types.
The order is designed so that lists, vectors, and prefab structs are
ordered lexicographically.
Warning! The datum-order is not compatible with the
standard numeric order; all exact numbers are ordered before all
inexact numbers. This allows 1 to be considered distinct from
1.0, for example.
The following built-in data types are currently supported: numbers,
strings, bytes, keywords, symbols, booleans, characters, null, pairs,
vectors, boxes, and prefab structs.