summaryrefslogtreecommitdiffstats
path: root/phil-spc.txi
diff options
context:
space:
mode:
authorThomas Bushnell, BSG <tb@debian.org>2005-11-02 14:55:21 -0800
committerBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:32 -0800
commit34c54a22ff7818bb8b38ef4d9c87dbbcb221ba73 (patch)
tree1189d06a81277bcf8539b0260a69a19f6038effb /phil-spc.txi
parent611b3db17894e5fdc0db3d49eaf6743d27b44233 (diff)
parent5145dd3aa0c02c9fc496d1432fc4410674206e1d (diff)
downloadslib-34c54a22ff7818bb8b38ef4d9c87dbbcb221ba73.tar.gz
slib-34c54a22ff7818bb8b38ef4d9c87dbbcb221ba73.zip
Import Debian changes 3a2-1debian/3a2-1
slib (3a2-1) unstable; urgency=low * New upstream release. * Acknowledge NMU. (Closes: #281809) * Makefile: Don't hack Makefile; use rules instead. * debian/rules: Set on make invocations: prefix, htmldir, TEXI2HTML. * debian/rules (clean): Clean more stuff here. * Makefile: Comment out old rule for $(htmldir)slib_toc.html. Instead, specify directly that the texi2html invocation produces that file. * debian/rules (binary-indep): Find web files in slib subdir. * debian/control (Build-Depends-Indep): Go back to using scm.
Diffstat (limited to 'phil-spc.txi')
-rw-r--r--phil-spc.txi130
1 files changed, 126 insertions, 4 deletions
diff --git a/phil-spc.txi b/phil-spc.txi
index 1193c6c..ac1743c 100644
--- a/phil-spc.txi
+++ b/phil-spc.txi
@@ -2,12 +2,13 @@
@ftindex hilbert-fill
@noindent
-@cindex Peano
@cindex Hilbert
@cindex Space-Filling
-The @dfn{Peano-Hilbert Space-Filling Curve} is a one-to-one mapping
-@cindex Peano-Hilbert Space-Filling Curve
+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
@@ -15,7 +16,8 @@ arbitrarily large @var{n}-dimensional cube with its corner at the
origin and all coordinates are non-negative.
@noindent
-For any exact nonnegative integers @var{scalar} and @var{rank},
+For any exact nonnegative integer @var{scalar} and exact integer
+@var{rank} > 2,
@example
(= @var{scalar} (hilbert-coordinates->integer
@@ -23,16 +25,136 @@ For any exact nonnegative integers @var{scalar} and @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 bitwise-laminate k1 @dots{}
+@defunx bitwise-delaminate count k
+
+Returns an integer composed of the bits of @var{k1} @dots{} interlaced
+in argument order. Given @var{k1}, @dots{} @var{kn}, the n low-order
+bits of the returned value will be the lowest-order bit of each
+argument.
+
+
+@defunx bitwise-laminate count k
+Returns a list of @var{count} integers comprised of every @var{count}h
+bit of the integer @var{k}.
+
+@example
+(map (lambda (k) (number->string k 2))
+ (bitwise-delaminate 4 #x7654))
+ @result{} ("0" "1111" "1100" "1010")
+(number->string (bitwise-laminate 0 #b1111 #b1100 #b1010) 16)
+ @result{} "7654"
+@end example
+
+For any non-negative integers @var{k} and @var{count}:
+@example
+(eqv? k (bitwise-laminate (bitwise-delaminate count k)))
+@end example
+@end defun
+
+
+@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
+