@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. @defunx 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}. @defunx 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 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