blob: 62b1bae38c135fb563f23f3663d83dc3107547c5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
@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
@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
|
