@code{(require 'hilbert-fill)}
@ftindex hilbert-fill

@noindent
@cindex Hilbert
@cindex Space-Filling
The @dfn{Hilbert Space-Filling Curve} is a one-to-one mapping
@cindex Hilbert Space-Filling Curve
between a unit line segment and an @var{n}-dimensional unit cube.
This implementation treats the nonnegative integers either as
fractional bits of a given width or as nonnegative integers.

@noindent
The integer procedures map the non-negative integers to an
arbitrarily large @var{n}-dimensional cube with its corner at the
origin and all coordinates are non-negative.

@noindent
For any exact nonnegative integer @var{scalar} and exact integer
@var{rank} > 2,

@example
(= @var{scalar} (hilbert-coordinates->integer
           (integer->hilbert-coordinates @var{scalar} @var{rank})))
                                       @result{} #t
@end example

When treating integers as @var{k} fractional bits,

@example
(= @var{scalar} (hilbert-coordinates->integer
           (integer->hilbert-coordinates @var{scalar} @var{rank} @var{k})) @var{k})
                                       @result{} #t
@end example


@defun integer->hilbert-coordinates scalar rank

Returns a list of @var{rank} integer coordinates corresponding to exact
non-negative integer @var{scalar}.  The lists returned by @code{integer->hilbert-coordinates} for @var{scalar} arguments
0 and 1 will differ in the first element.


@end defun
@defun integer->hilbert-coordinates scalar rank k

@var{scalar} must be a nonnegative integer of no more than
@code{@var{rank}*@var{k}} bits.

@code{integer->hilbert-coordinates} Returns a list of @var{rank} @var{k}-bit nonnegative integer
coordinates corresponding to exact non-negative integer @var{scalar}.  The
curves generated by @code{integer->hilbert-coordinates} have the same alignment independent of
@var{k}.
@end defun


@defun hilbert-coordinates->integer coords


@defunx hilbert-coordinates->integer coords k
Returns an exact non-negative integer corresponding to @var{coords}, a list
of non-negative integer coordinates.
@end defun

@subsubsection Gray code

@cindex Gray code
@noindent
A @dfn{Gray code} is an ordering of non-negative integers in which
@cindex Gray code
exactly one bit differs between each pair of successive elements.  There
are multiple Gray codings.  An n-bit Gray code corresponds to a
Hamiltonian cycle on an n-dimensional hypercube.

@noindent
Gray codes find use communicating incrementally changing values between
asynchronous agents.  De-laminated Gray codes comprise the coordinates
of Hilbert space-filling curves.


@defun integer->gray-code k
Converts @var{k} to a Gray code of the same @code{integer-length} as
@var{k}.
@end defun

@defun gray-code->integer k
Converts the Gray code @var{k} to an integer of the same
@code{integer-length} as @var{k}.

For any non-negative integer @var{k},
@example
(eqv? k (gray-code->integer (integer->gray-code k)))
@end example
@end defun

@defun = k1 k2
@defunx gray-code<? k1 k2
@defunx gray-code>? k1 k2
@defunx gray-code<=? k1 k2
@defunx gray-code>=? k1 k2
These procedures return #t if their Gray code arguments are
(respectively): equal, monotonically increasing, monotonically
decreasing, monotonically nondecreasing, or monotonically nonincreasing.

For any non-negative integers @var{k1} and @var{k2}, the Gray code
predicate of @code{(integer->gray-code k1)} and
@code{(integer->gray-code k2)} will return the same value as the
corresponding predicate of @var{k1} and @var{k2}.
@end defun

@subsubsection Bitwise Lamination
@cindex lamination


@defun delaminate-list count ks


Returns a list of @var{count} integers comprised of the @var{j}th
bit of the integers @var{ks} where @var{j} ranges from @var{count}-1
to 0.

@example
(map (lambda (k) (number->string k 2))
     (delaminate-list 4 '(7 6 5 4 0 0 0 0)))
    @result{} ("0" "11110000" "11000000" "10100000")
@end example

@code{delaminate-list} is its own inverse:
@example
(delaminate-list 8 (delaminate-list 4 '(7 6 5 4 0 0 0 0)))
    @result{} (7 6 5 4 0 0 0 0)
@end example
@end defun