Only in v6: .copied
diff -rc v4/Makefile v6/Makefile
*** v4/Makefile	Tue Nov 11 08:06:26 2008
--- v6/Makefile	Sun Nov 16 19:27:53 2008
***************
*** 1,14 ****
! 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
  	touch datefile
  	php makeindex.php.txt >index.html
  	chmod a-w index.html
--- 1,33 ----
! all:	Pub/.copied
  
! VER=v6
  
! SOURCES=makeindex.php.txt hilbert.py hilbert_test.py hilbert_pic.py \
! 	Makefile
! 
! DIFFS=v4_${VER}_diff.txt v5_${VER}_diff.txt 
! 
! PUBFILES=${SOURCES} ${DIFFS} index.html hilbert_thumb.gif hilbert_pic.pdf
! 
! v4_${VER}_diff.txt:	old/${VER}/.copied
! 	(cd old; diff -rc v4 ${VER} >../v4_${VER}_diff.txt; true)
! 
! v5_${VER}_diff.txt:	old/${VER}/.copied
! 	(cd old; diff -rc v5 ${VER} >../v5_${VER}_diff.txt; true)
! 
! old/${VER}/.copied:	${SOURCES}
! 	cp ${SOURCES} old/${VER}
! 	touch old/${VER}/.copied
! 
! Pub/.copied:	${PUBFILES}
  	cp ${PUBFILES} Pub
! 	touch Pub/.copied
  
! index.html:	${SOURCES} ${DIFFS}
  	rm -f index.html
  	touch datefile
  	php makeindex.php.txt >index.html
  	chmod a-w index.html
+ 
+ hilbert_pic.pdf:	hilbert.py hilbert_pic.py
+ 	hilbert_pic.py >hilbert_pic.pdf
diff -rc v4/hilbert.py v6/hilbert.py
*** v4/hilbert.py	Sat Nov  8 16:19:26 2008
--- v6/hilbert.py	Sun Nov 16 19:27:53 2008
***************
*** 4,9 ****
--- 4,11 ----
  #        int_to_Hilbert( 0, nD ) ==> ( 0, 0, 0, ... 0 ) Start at origin.
  #        int_to_Hilbert( 1, nD ) ==> ( 1, 0, 0, ... 0 ) 1st step is along x.
  #    Hilbert_to_int( ( x, y, z ) ) ==> i
+ # Steve Witham ess doubleyou at tiac remove-this dot net.
+ # http://www.tiac.net/~sw/2008/10/Hilbert
  
  
  from sys import argv
***************
*** 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 nD-bit int (or Python long, i.e. bignum).
! # Arrays of chunks are highest-order first.
  # Bits within "coord chunks" are x highest-order, 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
--- 41,65 ----
  
  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 nD-bit int (or Python long, aka bignum).
! # Lists of chunks are highest-order first.
  # Bits within "coord chunks" are x highest-order, 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
--- 71,77 ----
      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 )
--- 82,93 ----
      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 )
Only in v6: hilbert_pic.py
diff -rc v4/hilbert_test.py v6/hilbert_test.py
*** v4/hilbert_test.py	Sat Nov  8 16:19:27 2008
--- v6/hilbert_test.py	Sun Nov 16 19:27:53 2008
***************
*** 117,153 ****
          child_start_end_test( nbits )
  
  
! def check_visited( visited, prefix, size, nD ):
      if nD > 0:
!         for i in range( size ):
!             check_visited( visited, prefix + [i], size, nD - 1 )
      else:
          if not tuple( prefix ) in visited:
              print "missing", prefix
  
  
! def int_to_Hilbert_test( n, nD ):
!     ld = int( n ** (1./nD) )
!     assert ld ** nD == n
      visited = {}        
      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,
!         if i > 0:
              nDiffs = sum( [ pt[k] != prev_pt[k] for k in range( nD ) ] )
              if nDiffs != 1:
                  print "BZZT, different along", nDiffs, "dimensions",
              maxDiff = max( [ abs(pt[k] - prev_pt[k]) for k in range( nD ) ] )
              if maxDiff != 1:
                  print "BZZT, max difference is", maxDiff,
          prev_pt = pt
!         if ( i + 1 ) % 8 == 0:
!             print
!     check_visited( visited, [], ld, nD )
  
  
  if argv[0].endswith( "/hilbert_test.py" ) or argv[0] == "hilbert.py":
--- 117,173 ----
          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 number of
! # dimensions.  "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, linear_size, nD ):
      if nD > 0:
!         for i in range( linear_size ):
!             check_visited( visited, prefix + [i], linear_size, nD - 1 )
      else:
          if not tuple( prefix ) in visited:
              print "missing", prefix
  
  
! def tuple_print_width( n ):  # tuple with n 1-digit numbers and trailing sp
!     if n == 0:  return 3   # ()_
!     if n == 1:  return 5   # (1,)_  special case
!     else:       return n * 3 + 1
! 
! 
! def int_to_Hilbert_test( n, nD, doPrint=True ):
!     tups_per_line = 2**( int( log( 80 / tuple_print_width( nD ), 2 ) ) )
!     linear_size = int( ( n + .5 ) ** (1./nD) )
!     isCube = linear_size ** nD == n
!     if not isCube:
!         print "(This is not a complete cube:)"
      visited = {}        
      for i in range( n ):
          pt = tuple( int_to_Hilbert( i, nD ) )
!         if doPrint: print pt,
!         visited[ pt ] = True      # Add pt to "visited" dictionary.
          j = Hilbert_to_int( pt )
          if j != i:
              print "BZZT, decodes to", j,
! 
!         if i > 0:  # Check that we have stepped one unit, along one dim:
              nDiffs = sum( [ pt[k] != prev_pt[k] for k in range( nD ) ] )
              if nDiffs != 1:
                  print "BZZT, different along", nDiffs, "dimensions",
              maxDiff = max( [ abs(pt[k] - prev_pt[k]) for k in range( nD ) ] )
              if maxDiff != 1:
                  print "BZZT, max difference is", maxDiff,
+ 
          prev_pt = pt
!         if ( i + 1 ) % tups_per_line == 0:
!             if doPrint: print
! 
!     if isCube:
!         check_visited( visited, [], linear_size, nD )
  
  
  if argv[0].endswith( "/hilbert_test.py" ) or argv[0] == "hilbert.py":
***************
*** 159,168 ****
      print
      int_to_Hilbert_test( 64, 3 )
      print
      for nD in [ 2, 3, 4, 5 ]:
          pt = [ 0 ] * nD
!         pt[0] = 1000000
          x = Hilbert_to_int( pt )
          print x, log( x, 10 )
!         print int_to_Hilbert( 1000000, nD )
  
--- 179,205 ----
      print
      int_to_Hilbert_test( 64, 3 )
      print
+     int_to_Hilbert_test( 4096, 3, doPrint=False ) # nChunks > nD
+     print
+     int_to_Hilbert_test( 4096, 4, doPrint=False )
+     print
+     k = 10**12  # definitely a long
      for nD in [ 2, 3, 4, 5 ]:
+         # Decode point ( k, 0, 0... ) to an int...how many digits?:
          pt = [ 0 ] * nD
!         pt[0] = k
          x = Hilbert_to_int( pt )
          print x, log( x, 10 )
!         # Double-check:
!         pt2 = list( int_to_Hilbert( x, nD ) )
!         if pt2 != pt:
!             print "BZZT!  Encodes to ", pt2
! 
!         # Encode k to an nD point:
!         pt = int_to_Hilbert( k, nD )
!         print pt
!         # Double-check:
!         y = Hilbert_to_int( pt )
!         if y != k:
!             print "BZZT!  Decodes to", y
  
diff -rc v4/makeindex.php.txt v6/makeindex.php.txt
*** v4/makeindex.php.txt	Sat Nov  8 16:19:28 2008
--- v6/makeindex.php.txt	Sun Nov 16 19:27:53 2008
***************
*** 23,30 ****
  </HEAD>
  <BODY>
  
  <h3>Hilbert Curves in More (or fewer) than Two Dimensions</h3>
! <font size="-1">version 0.4</font>
  <p>
  
  Let's develop Python functions to map between a point on a
--- 23,42 ----
  </HEAD>
  <BODY>
  
+ 
+ <table width="100%" border="0">
+   <tr>
+     <td width="129" align="center">
+       <img src="http://www.mac-guyver.com/switham/thumbnails/hilbert_thumb4.gif" 
+                                     width="109"></td>
+     <td valign="top"> 
+ <p>
  <h3>Hilbert Curves in More (or fewer) than Two Dimensions</h3>
! <font size="-1">version 0.6</font>
!     </td>
!   </tr>
! </table>
! 
  <p>
  
  Let's develop Python functions to map between a point on a
***************
*** 77,87 ****
  most significant bit <i>x</i>, the next (if any) <i>y</i>, and so forth
  (punting on what the bits after <i>z</i> are called).
  In this walk,<pre>
!   1---2
!   |   |
!   0   3</pre>
! the first <i>step</i> is along the <i>y</i> axis, but we'll say the walk
! as a whole <i>travels</i> along the <i>x</i> axis.
  "Travel," here, means the difference between
  the beginning and end of the walk of a cube (here a 2-cube).
  When <i>D</i>>1, the travel of a unit <i>D</i>-cube walk is always along a different
--- 89,99 ----
  most significant bit <i>x</i>, the next (if any) <i>y</i>, and so forth
  (punting on what the bits after <i>z</i> are called).
  In this walk,<pre>
!   3---2
!       |
!   0---1</pre>
! the first <i>step</i> is along the <i>x</i> axis, but we'll say the walk
! as a whole <i>travels</i> along the <i>y</i> axis.
  "Travel," here, means the difference between
  the beginning and end of the walk of a cube (here a 2-cube).
  When <i>D</i>>1, the travel of a unit <i>D</i>-cube walk is always along a different
***************
*** 126,134 ****
  
  For <i>D</i>=2 (and <i>D</i>=1), there is only one Gray code for a given travel,
  and only one way to orient the subsquares within the larger walk.
! For <i>D</i>>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.
--- 138,146 ----
  
  For <i>D</i>=2 (and <i>D</i>=1), there is only one Gray code for a given travel,
  and only one way to orient the subsquares within the larger walk.
! For <i>D</i>>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:
  
  <ul>
!   <li>"Unpack" the index into a list of <i>h</i> <i>D</i>-bit ints.</li>
!   <li><i>h</i> 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.
    </li>
  </ul>
  
! Then, for each number in the list, starting at the most-
  significant,
  <ul>
!   <li>Use a modified Gray code to convert the <i>D</i> bits of index into
!   a <i>D</i>-bit output int with one bit destined for each of the <i>D</i>
!   coordinates,</li>
    <li>Calculate the start and end corners for the child cube
!   to which the indexed point belongs,</li>
    <li>Loop to do the child cube.</li>
  </ul>
  
--- 166,188 ----
  coordinates:
  
  <ul>
!   <li>"Unpack" the index into a list of <i>h</i> <i>D</i>-bit ints
!       (called "index chunks").</li>
!   <li><i>h</i> 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.
    </li>
  </ul>
  
! Then, for each index chunk, starting at the most-
  significant,
  <ul>
!   <li>Use a modified Gray code to convert the index chunk into
!   a <i>D</i>-bit "coordinate chunk" with one bit destined for each of 
!   the <i>D</i>
!   coordinates;</li>
    <li>Calculate the start and end corners for the child cube
!   to which the indexed point belongs;</li>
    <li>Loop to do the child cube.</li>
  </ul>
  
***************
*** 176,182 ****
  
  <ul>
    <li>"Pack" the output coordinates by redistributing the <i>D</i> bits from
!       each of <i>h</i> output ints into <i>D</i> ints, each with <i>h</i> bits.
    </li>
  </ul>
  
--- 190,197 ----
  
  <ul>
    <li>"Pack" the output coordinates by redistributing the <i>D</i> bits from
!       each of <i>h</i> coordinate chunks into <i>D</i> ints,
!       each with <i>h</i> bits.
    </li>
  </ul>
  
***************
*** 320,328 ****
  the bottom-level cube at the origin has a fixed orientation.
  <p>
  
! 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
  <i>travels</i> the y dimension.
  Our child- orientation method always makes the first child of a parent
--- 335,343 ----
  the bottom-level cube at the origin has a fixed orientation.
  <p>
  
! 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
  <i>travels</i> the y dimension.
  Our child- orientation method always makes the first child of a parent
***************
*** 337,342 ****
--- 352,358 ----
  
  <pre><font size="-1">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.
  </font></pre>
***************
*** 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 "<table>\n";
! exec( "/bin/ls -ld hilbert.py hilbert_test.py *.php.txt", $lines );
  foreach( $lines as $line ) {
     echo "<tr>\n";
     $parts=explode( " ", $line );
--- 363,378 ----
  $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).",
! "hilbert_pic.pdf" => "Exploded views of 3D Hilbert walks.",
! "hilbert_pic.py" => "Python/pdfgen code that generates hilbert_pic.pdf"
  );
  
  $subst_url = array(
  );
  
  echo "<table>\n";
! exec( "/bin/ls -ld hilbert.py hilbert_test.py makeindex.php.txt *diff.txt hilbert_pic.py hilbert_pic.pdf", $lines );
  foreach( $lines as $line ) {
     echo "<tr>\n";
     $parts=explode( " ", $line );
***************
*** 390,398 ****
  Python tuples, like
  <pre>     ( x, y, z )
  </pre>
! 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.
  <pre>
      point = ( x, y, z )
--- 408,416 ----
  Python tuples, like
  <pre>     ( x, y, z )
  </pre>
! 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.
  <pre>
      point = ( x, y, z )
***************
*** 405,412 ****
      x, y, z = f( point )
      x = point[ 0 ]
      number_of_dimensions = len( point )
- 
  </pre>
  "Lists" in Python are actually one-dimensional packed arrays.
  They are like tuples, but modifiable, so,
  <pre>
--- 423,433 ----
      x, y, z = f( point )
      x = point[ 0 ]
      number_of_dimensions = len( point )
  </pre>
+ I use tuples for points where I can here just because they
+ <i>look</i> like points.
+ <p>
+ 
  "Lists" in Python are actually one-dimensional packed arrays.
  They are like tuples, but modifiable, so,
  <pre>
***************
*** 414,421 ****
      a[ 1 ] = a[ 0 ] + a[ 1]
      x, y = a
  </pre>
! I use tuples for points where I can here just because they
! <i>look</i> like points.
  <p>
  
  In Python, the bitwise operations on ints and longs are:<pre>
--- 435,443 ----
      a[ 1 ] = a[ 0 ] + a[ 1]
      x, y = a
  </pre>
! 
! The expression "[0] * n" means <i>n</i> copies of a list of one zero,
! concatenated together-- in other words a list of <i>n</i> zeroes.
  <p>
  
  In Python, the bitwise operations on ints and longs are:<pre>