▼Data:   Data Structures
On this page:
ordering/  c
gen:  ordered-dict
prop:  ordered-dict
ordered-dict?
dict-iterate-least
dict-iterate-greatest
dict-iterate-least/  >?
dict-iterate-least/  >=?
dict-iterate-greatest/  <?
dict-iterate-greatest/  <=?
order
order?
order-comparator
order-domain-contract
order-=?
order-<?
real-order
datum-order
8.6
  top  contents  ← prev  up  next → 

3 Orders and Ordered Dictionaries

Ryan Culpepper <ryanc@racket-lang.org>

 (require data/order) package: data-lib

This library defines orders and the ordered dictionary generic interface.

value

ordering/c : flat-contract?

Contract for orderings, represented by the symbols '=, '<, and '>.

value

gen:ordered-dict : any/c

A generic interface for defining new ordered dictionary types. Methods can be attached to the gen:ordered-dict interface using the #:methods keyword in a structure type definition. Two “extrema” methods and four “search” methods should be implemented. The extrema methods must satisfy e/c and the search methods must satisfy s/c:

e/c = (->i ([d ordered-dict?])
           [_ (d) (or/c #f (dict-iter-contract d))])
s/c = (->i ([d ordered-dict?]
            [k (d) (dict-key-contract d)])
            [_ (d) (or/c #f (dict-iter-contract d))])

The methods are implementations of the following generic functions:

A struct type that implements gen:ordered-dict must also implement gen:dict.

value

prop:ordered-dict : 
(struct-type-property/c
 (vectorof e/c e/c s/c s/c s/c s/c))
A deprecated structure type property used to defined custom ordered dictionaries. Use gen:ordered-dict instead. Accepts a vector of 6 procedures with the same arguments as the methods of gen:ordered-dict.

procedure

(ordered-dict? x) → boolean?

  x : any/c
Returns #t if x is an instance of a struct implementing the ordered dictionary interface (via gen:ordered-dict).

procedure

(dict-iterate-least dict) → (or/c (dict-iter-contract dict) #f)

  dict : ordered-dict?

procedure

(dict-iterate-greatest dict)

 → (or/c (dict-iter-contract dict) #f)
  dict : ordered-dict?
Returns the position of the least (greatest) key in the ordered dictionary dict. If dict is empty, #f is returned.

procedure

(dict-iterate-least/>? dict key)

 → (or/c (dict-iter-contract dict) #f)
  dict : ordered-dict?
  key : any/c

procedure

(dict-iterate-least/>=? dict key)

 → (or/c (dict-iter-contract dict) #f)
  dict : ordered-dict?
  key : any/c

procedure

(dict-iterate-greatest/<? dict key)

 → (or/c (dict-iter-contract dict) #f)
  dict : ordered-dict?
  key : any/c

procedure

(dict-iterate-greatest/<=? dict key)

 → (or/c (dict-iter-contract dict) #f)
  dict : ordered-dict?
  key : any/c
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.

procedure

(order name domain-contract comparator)

 → (and/c order? procedure?)
  name : symbol?
  domain-contract : contract?
  comparator : (-> any/c any/c ordering/c)
(order name domain-contract =? <? [>?]) → (and/c order? procedure?)
  name : symbol?
  domain-contract : contract?
  =? : (-> any/c any/c boolean?)
  <? : (-> any/c any/c boolean?)
  >? : (-> any/c any/c boolean?) = (lambda (x y) (<? y x))
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=?: contract violation

  expected: string?

  given: 12

procedure

(order? x) → boolean?

  x : any/c
Returns #t if x is an order object, #f otherwise.

procedure

(order-comparator ord) → (-> any/c any/c ordering/c)

  ord : order?
Extracts the comparator function from an order object.

procedure

(order-domain-contract ord) → contract?

  ord : order?
Extracts the domain contract from an order object.

procedure

(order-=? ord) → (-> any/c any/c boolean?)

  ord : order?

procedure

(order-<? ord) → (-> any/c any/c boolean?)

  ord : order?
Returns a procedure representing the order’s equality relation or less-than relation, respectively.

value

real-order : order?

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.

Examples:
> (real-order 1.0 1)

'=

> (real-order 5 7)

'<

> (real-order 9.0 3.4)

'>

> (real-order 1 +inf.0)

'<

> (real-order 5 -inf.0)

'>

value

datum-order : order?

An ad hoc order that encompasses many built-in Racket data types as well as prefab structs and fully-transparent structs. 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. Prefab and fully-transparent structs are ordered according to their most specific struct type, and prefab structs are ordered first by their prefab struct keys. The ordering of struct types is independent of the struct type hierarchy; a struct type may sort before one of its subtypes but after another.

Programs should not rely on the ordering of different data types, since it may change in future versions of Racket to improve comparison performance. The ordering of non-prefab struct types may change between one execution of a program and the next.

The order is guaranteed, however, to lexicographically sort proper lists, vectors, prefab structs, and fully-transparent structs. Improper lists sort lexicographically considered as pairs, but the ordering of an improper list and its proper prefix, such as '(a b . c) and '(a b), is not specified.

The datum-order comparator does not perform cycle-detection; comparisons involving cyclic data may diverge.

Warning: datum-order is not compatible with the standard numeric order; all exact numbers are ordered separately from all inexact numbers. Thus 1 is considered distinct from 1.0, for example.

The following data types are currently supported: numbers, strings, bytes, keywords, symbols, booleans, characters, paths, null, pairs, vectors, boxes, prefab structs, and fully-transparent structs.

The following example comparisons are specified to return the results shown:
> (datum-order 1 2)

'<

> (datum-order 8.0 5.0)

'>

> (datum-order 'apple 'candy)

'<

> (datum-order '(a #:b c) '(a #:c d c))

'<

> (datum-order '(5 . 4) '(3 2 1))

'>

> (datum-order '(a b . c) '(a b . z))

'<

> (datum-order "apricot" "apple")

'>

> (datum-order '#(1 2 3) '#(1 2))

'>

> (datum-order '#(1 2 3) '#(1 3))

'<

> (datum-order (box 'car) (box 'candy))

'>

> (datum-order '#s(point a 1) '#s(point b 0))

'<

> (datum-order '#s(A 1 2) '#s(Z 3 4 5))

'<

> (struct fish (name) #:transparent)
> (datum-order (fish 'alewife) (fish 'sockeye))

'<

The following example comparisons are unspecified but consistent within all executions of a single version of Racket:
(datum-order 1 2.0)
(datum-order 3+5i 3+2i)
(datum-order 'apple "zucchini")
(datum-order '(a b) '(a b . c))
(datum-order 0 'zero)

The following example comparison is unspecified but consistent within a single execution of a program:
(struct fowl (name) #:transparent)
(datum-order (fish 'alewife) (fowl 'dodo))

  top  contents  ← prev  up  next →