Only in v5: .copied
diff rc v4/Makefile v5/Makefile
*** v4/Makefile Tue Nov 11 08:06:26 2008
 v5/Makefile Tue Nov 11 09:24:59 2008
***************
*** 1,11 ****
! all: Pub/Done
! PUBFILES=index.html makeindex.php.txt hilbert.py hilbert_test.py \
! hilbert_thumb.gif
! Pub/Done: ${PUBFILES}
cp ${PUBFILES} Pub
! touch Pub/Done
index.html: makeindex.php.txt
rm f index.html
 1,18 
! all: Pub/.copied
! SOURCES=makeindex.php.txt hilbert.py hilbert_test.py Makefile
! PUBFILES=${SOURCES} index.html hilbert_thumb.gif v4_v5_diff.txt
! v4_v5_diff.txt: old/v5/.copied
! (cd old; diff rc v4 v5 >../v4_v5_diff.txt; true)
!
! old/v5/.copied: ${SOURCES}
! cp ${SOURCES} old/v5
! touch old/v5/.copied
!
! Pub/.copied: ${PUBFILES}
cp ${PUBFILES} Pub
! touch Pub/.copied
index.html: makeindex.php.txt
rm f index.html
diff rc v4/hilbert.py v5/hilbert.py
*** v4/hilbert.py Sat Nov 8 16:19:26 2008
 v5/hilbert.py Tue Nov 11 09:24:59 2008
***************
*** 39,62 ****
def initial_start_end( nChunks, nD ):
# This orients the largest cube so that
# the first step is along the x axis, regardless of nD and nChunks:
return 0, 2**( ( nChunks  1 ) % nD ) # in Python 0 <= a % b < b.
# Unpacking arguments and packing results of int <> Hilbert functions.
# nD == # of dimensions.
! # A "chunk" is an nDbit int (or Python long, i.e. bignum).
! # Arrays of chunks are highestorder first.
# Bits within "coord chunks" are x highestorder, y next, etc.,
# i.e., the same order as coordinates input to Hilbert_to_int()
# and output from int_to_Hilbert().
! ## unpack_index( int, nD ) > array of index chunks.
#
def unpack_index( i, nD ):
! p = 2**nD # Chunks are digits mod 2**nD.
! nChunks = max( 1, int( ceil( log( i + 1, p ) ) ) ) # # of digits
chunks = [ 0 ] * nChunks
for j in range( nChunks  1, 1, 1 ):
chunks[ j ] = i % p
 39,63 
def initial_start_end( nChunks, nD ):
# This orients the largest cube so that
+ # its start is the origin (0 corner), and
# the first step is along the x axis, regardless of nD and nChunks:
return 0, 2**( ( nChunks  1 ) % nD ) # in Python 0 <= a % b < b.
# Unpacking arguments and packing results of int <> Hilbert functions.
# nD == # of dimensions.
! # A "chunk" is an nDbit int (or Python long, aka bignum).
! # Lists of chunks are highestorder first.
# Bits within "coord chunks" are x highestorder, y next, etc.,
# i.e., the same order as coordinates input to Hilbert_to_int()
# and output from int_to_Hilbert().
! ## unpack_index( int index, nD ) > list of index chunks.
#
def unpack_index( i, nD ):
! p = 2**nD # Chunks are like digits in base 2**nD.
! nChunks = max( 1, int( ceil( log( i + 1, p ) ) ) ) # # of digits
chunks = [ 0 ] * nChunks
for j in range( nChunks  1, 1, 1 ):
chunks[ j ] = i % p
***************
*** 68,74 ****
return reduce( lambda n, chunk: n * p + chunk, chunks )
! ## unpack_coords( array of nD coords ) > array of coord chunks each nD bits.
def unpack_coords( coords ):
nD = len( coords )
biggest = reduce( max, coords ) # the max of all coords
 69,75 
return reduce( lambda n, chunk: n * p + chunk, chunks )
! ## unpack_coords( list of nD coords ) > list of coord chunks each nD bits.
def unpack_coords( coords ):
nD = len( coords )
biggest = reduce( max, coords ) # the max of all coords
***************
*** 79,89 ****
return transpose_bits( chunks, nD )
! ## transpose_bits  Given nSrcs source ints each nDests bits long,
! # return nDests ints each nSrcs bits long.
! # Like a matrix transpose where ints are rows and bits are columns.
! # Earlier srcs become higher bits in dests;
! # earlier dests come from higher bits of srcs.
def transpose_bits( srcs, nDests ):
srcs = list( srcs ) # Make a copy we can modify safely.
nSrcs = len( srcs )
 80,91 
return transpose_bits( chunks, nD )
! ## transpose_bits 
! # Given nSrcs source ints each nDests bits long,
! # return nDests ints each nSrcs bits long.
! # Like a matrix transpose where ints are rows and bits are columns.
! # Earlier srcs become higher bits in dests;
! # earlier dests come from higher bits of srcs.
def transpose_bits( srcs, nDests ):
srcs = list( srcs ) # Make a copy we can modify safely.
nSrcs = len( srcs )
diff rc v4/hilbert_test.py v5/hilbert_test.py
*** v4/hilbert_test.py Sat Nov 8 16:19:27 2008
 v5/hilbert_test.py Tue Nov 11 09:24:59 2008
***************
*** 117,122 ****
 117,129 
child_start_end_test( nbits )
+ ## check_visited  Check that every point in the cube was visited.
+ #
+ # visited is a dictionary (or "hash" or associative array) whose key
+ # is a tuple representing the point coordinates. Prefix is a list
+ # of coordinates that's built up by recursion to the right size.
+ # "tuple(prefix) in visited" converts the list to a tuple
+ # and asks whether an entry with that key is in the dictionary.
def check_visited( visited, prefix, size, nD ):
if nD > 0:
for i in range( size ):
***************
*** 133,139 ****
for i in range( n ):
pt = tuple( int_to_Hilbert( i, nD ) )
print pt,
! visited[ pt ] = True
j = Hilbert_to_int( pt )
if j != i:
print "BZZT, decodes to", j,
 140,146 
for i in range( n ):
pt = tuple( int_to_Hilbert( i, nD ) )
print pt,
! visited[ pt ] = True # Add pt to visited dictionary.
j = Hilbert_to_int( pt )
if j != i:
print "BZZT, decodes to", j,
diff rc v4/makeindex.php.txt v5/makeindex.php.txt
*** v4/makeindex.php.txt Sat Nov 8 16:19:28 2008
 v5/makeindex.php.txt Tue Nov 11 09:24:59 2008
***************
*** 24,30 ****
Hilbert Curves in More (or fewer) than Two Dimensions
! version 0.4
Let's develop Python functions to map between a point on a
 24,30 
Hilbert Curves in More (or fewer) than Two Dimensions
! version 0.5
Let's develop Python functions to map between a point on a
***************
*** 77,87 ****
most significant bit x, the next (if any) y, and so forth
(punting on what the bits after z are called).
In this walk,
! 12
!  
! 0 3
! the first step is along the y axis, but we'll say the walk
! as a whole travels along the x axis.
"Travel," here, means the difference between
the beginning and end of the walk of a cube (here a 2cube).
When D>1, the travel of a unit Dcube walk is always along a different
 77,87 
most significant bit x, the next (if any) y, and so forth
(punting on what the bits after z are called).
In this walk,! 32
! 
! 01
! the first step is along the x axis, but we'll say the walk
! as a whole travels along the y axis.
"Travel," here, means the difference between
the beginning and end of the walk of a cube (here a 2cube).
When D>1, the travel of a unit Dcube walk is always along a different
***************
*** 126,134 ****
For D=2 (and D=1), there is only one Gray code for a given travel,
and only one way to orient the subsquares within the larger walk.
! For D>2, there are many
! possible walks of a unit cube, and many combinations of subcube
! orientations that are compatible with a given parent walk.
We won't go into all these possibilities except to point out that
the code being described here effectively represents a set of
arbitrary choices about the shape of the walk.
 126,134 
For D=2 (and D=1), there is only one Gray code for a given travel,
and only one way to orient the subsquares within the larger walk.
! For D>2, there is more than one
! possible walk of a unit cube, and some (all?) parent walks are compatible
! with multiple combinations of subcube orientations.
We won't go into all these possibilities except to point out that
the code being described here effectively represents a set of
arbitrary choices about the shape of the walk.
***************
*** 154,174 ****
coordinates:
!  "Unpack" the index into a list of h Dbit ints.
!  h is the number of levels of
recursion (in our case the number of times to loop); from this
calculate the orientation of the overall cube.
! Then, for each number in the list, starting at the most
significant,
!  Use a modified Gray code to convert the D bits of index into
! a Dbit output int with one bit destined for each of the D
! coordinates,
 Calculate the start and end corners for the child cube
! to which the indexed point belongs,
 Loop to do the child cube.
 154,176 
coordinates:
!  "Unpack" the index into a list of h Dbit ints
! (called "index chunks").
!  h will be the number of levels of
recursion (in our case the number of times to loop); from this
calculate the orientation of the overall cube.
! Then, for each index chunk, starting at the most
significant,
!  Use a modified Gray code to convert the index chunk into
! a Dbit "coordinate chunk" with one bit destined for each of
! the D
! coordinates;
 Calculate the start and end corners for the child cube
! to which the indexed point belongs;
 Loop to do the child cube.
***************
*** 176,182 ****
 "Pack" the output coordinates by redistributing the D bits from
! each of h output ints into D ints, each with h bits.
 178,185 
 "Pack" the output coordinates by redistributing the D bits from
! each of h coordinate chunks into D ints,
! each with h bits.
***************
*** 320,328 ****
the bottomlevel cube at the origin has a fixed orientation.
! We pin the problem down by saying that the point with index zero is
the origin point,
! and that the first step is in the x direction.
With our modified Gray code, that means the first level zero unit cube
travels the y dimension.
Our child orientation method always makes the first child of a parent
 323,331 
the bottomlevel cube at the origin has a fixed orientation.
! We decree that the point with index zero is
the origin point,
! and that the first step shall be in the x direction.
With our modified Gray code, that means the first level zero unit cube
travels the y dimension.
Our child orientation method always makes the first child of a parent
***************
*** 337,342 ****
 340,346 
def initial_start_end( nChunks, nD ):
# This orients the largest cube so that
+ # it's start is the origin (0 corner), and
# the first step is along the x axis, regardless of nD and nChunks:
return 0, 2**( ( nChunks  1 ) % nD ) # in Python 0 <= a % b < b.
***************
*** 347,360 ****
$cmt = array(
"hilbert.py" => "index <==> Hilbert and support functions.",
"hilbert_test.py" => "Tests hilbert.py functions for 1 to 3 dimensions.",
! "makeindex.php.txt" => "PHP script that inserts this listing."
);
$subst_url = array(
);
echo "\n";
! exec( "/bin/ls ld hilbert.py hilbert_test.py *.php.txt", $lines );
foreach( $lines as $line ) {
echo "\n";
$parts=explode( " ", $line );
 351,364 
$cmt = array(
"hilbert.py" => "index <==> Hilbert and support functions.",
"hilbert_test.py" => "Tests hilbert.py functions for 1 to 3 dimensions.",
! "makeindex.php.txt" => "PHP source for this page (inserts this listing)."
);
$subst_url = array(
);
echo "\n";
! exec( "/bin/ls ld hilbert.py hilbert_test.py makeindex.php.txt *diff.txt", $lines );
foreach( $lines as $line ) {
echo "\n";
$parts=explode( " ", $line );
***************
*** 390,398 ****
Python tuples, like
( x, y, z )
! are arrays that can't be modified once created. They can be
passed as arguments, returned from functions, and indexed like
! arrays. They are sometimes implicit in the syntax for multiple
assignment or returning multiple values from functions. E.g.
point = ( x, y, z )
 394,402 
Python tuples, like
( x, y, z )
! are lists that can't be modified once created. They can be
passed as arguments, returned from functions, and indexed like
! lists. They are sometimes implicit in the syntax for multiple
assignment or returning multiple values from functions. E.g.
point = ( x, y, z )
***************
*** 405,412 ****
x, y, z = f( point )
x = point[ 0 ]
number_of_dimensions = len( point )

"Lists" in Python are actually onedimensional packed arrays.
They are like tuples, but modifiable, so,
 409,419 
x, y, z = f( point )
x = point[ 0 ]
number_of_dimensions = len( point )
+ I use tuples for points where I can here just because they
+ look like points.
+
+
"Lists" in Python are actually onedimensional packed arrays.
They are like tuples, but modifiable, so,
***************
*** 414,421 ****
a[ 1 ] = a[ 0 ] + a[ 1]
x, y = a
! I use tuples for points where I can here just because they
! look like points.
In Python, the bitwise operations on ints and longs are:
 421,429 
a[ 1 ] = a[ 0 ] + a[ 1]
x, y = a
!
! The expression "[0] * n" means n copies of a list of one zero,
! concatenated together in other words a list of n zeroes.
In Python, the bitwise operations on ints and longs are: