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 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
--- 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 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
--- 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 ****
  <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
--- 24,30 ----
  <BODY>
  
  <h3>Hilbert Curves in More (or fewer) than Two Dimensions</h3>
! <font size="-1">version 0.5</font>
  <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
--- 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>
!   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.
--- 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 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>
  
--- 154,176 ----
  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>
  
--- 178,185 ----
  
  <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
--- 323,331 ----
  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 ****
--- 340,346 ----
  
  <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 );
--- 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 "<table>\n";
! exec( "/bin/ls -ld hilbert.py hilbert_test.py makeindex.php.txt *diff.txt", $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 )
--- 394,402 ----
  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>
--- 409,419 ----
      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>
--- 421,429 ----
      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>