#! /usr/bin/env python
#
def ui4_unrank_gray ( rank ):

#*****************************************************************************80
#
## UI4_UNRANK_GRAY unranks a Gray code.
#
#  Discussion:
#
#    This routine is entirely arithmetical,
#    and does not require access to bit testing and setting routines.
#
#    The binary values of the Gray codes of successive integers differ in
#    just one bit.
#
#    The sequence of Gray codes for 0 to (2^N)-1 can be interpreted as a
#    Hamiltonian cycle on a graph of the cube in N dimensions.
#
#  Example:
#
#    Rank  Gray  Gray
#          (Dec) (Bin)
#
#     0     0       0
#     1     1       1
#     2     3      11
#     3     2      10
#     4     6     110
#     5     7     111
#     6     5     101
#     7     4     100
#     8    12    1100
#     9    14    1001
#    10    12    1010
#    11    13    1011
#    12     8    1100
#    13     9    1101
#    14    11    1110
#    15    10    1111
#    16    31   10000
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    22 November 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer RANK, the integer whose Gray code is desired.
#
#    Output, integer GRAY, the Gray code of the given rank.
#
  if ( rank <= 0 ):
    gray = 0
    return gray

  rank_copy = rank
  k = 0
  two_k = 1
  while ( 2 * two_k <= rank_copy ):
    two_k = two_k * 2
    k = k + 1

  gray = two_k
  rank_copy = rank_copy - two_k
  next = True

  while ( 0 < k ):

    two_k = ( two_k // 2 )
    k = k - 1

    last = next
    next = ( two_k <= rank_copy and rank_copy <= two_k * 2 )

    if ( next != last ):
      gray = gray + two_k

    if ( next ):
      rank_copy = rank_copy - two_k

  return gray

def ui4_unrank_gray_test ( ):

#*****************************************************************************80
#
#% UI4_UNRANK_GRAY_TEST tests UI4_UNRANK_GRAY.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    19 November 2015
#
#  Author:
#
#    John Burkardt
#
  import platform
  from ui4_to_ubvec import ui4_to_ubvec

  n = 5

  print ( '' )
  print ( 'UI4_UNRANK_GRAY_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  UI4_UNRANK_GRAY unranks a Gray code.' )
  print ( '' )
  print ( '  Rank   I  (binary)' )
  print ( '' )
 
  for rank in range ( 0, 32 ):
    ui4 = ui4_unrank_gray ( rank )
    ubvec = ui4_to_ubvec ( ui4, n )
    print ( '  %2d    %2d  ' % ( rank, ui4 ), end = '' )
    for j in range ( 0, n ):
      print ( '%2d' % ( ubvec[j] ), end = '' )
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'UI4_UNRANK_GRAY_TEST' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  ui4_unrank_gray_test ( )
  timestamp ( )