#! /usr/bin/env python
#
def ui4_rank_gray ( gray ):

#*****************************************************************************80
#
## UI4_RANK_GRAY ranks a Gray code.
#
#  Discussion:
#
#    This routine is entirely arithmetical,
#    and does not require access to bit testing and setting routines.
#
#    Given the number GRAY, its ranking is the order in which it would be
#    visited in the Gray code ordering.  The Gray code ordering begins
#
#    Rank  Gray  Gray
#          (Dec) (Bin)
#
#       0     0  0000
#       1     1  0001
#       2     3  0011
#       3     2  0010
#       4     6  0110
#       5     7  0111
#       6     5  0101
#       7     4  0100
#       8    12  0110
#       etc
#
#   This routine is given a Gray code, and has to return the rank.
#
#  Example:
#
#    Gray  Gray  Rank
#    (Dec) (Bin)
#
#     0       0     0
#     1       1     1
#     2      10     3
#     3      11     2
#     4     100     7
#     5     101     6
#     6     110     4
#     7     111     5
#     8    1000    15
#     9    1001    14
#    10    1010    12
#    11    1011    13
#    12    1100     8
#    13    1101     9
#    14    1110    11
#    15    1111    10
#    16   10000    31
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    22 November 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer GRAY, the Gray code to be ranked.
#
#    Output, integer RANK, the rank of GRAY, and the integer
#    whose Gray code is GRAY.
#
  from sys import exit

  gray_copy = gray

  if ( gray_copy < 0 ):
    print ( '' )
    print ( 'UI4_RANK_GRAY - Fatal error!' )
    print ( '  Input value of GRAY < 0.' )
    exit ( 'UI4_RANK_GRAY - Fatal error!' )

  if ( gray_copy == 0 ):
    rank = 0
    return rank
#
#  Find TWO_K, the largest power of 2 less than or equal to GRAY.
#
  k = 0
  two_k = 1
  while ( 2 * two_k <= gray_copy ):
    two_k = two_k * 2
    k = k + 1

  rank = two_k
  last = True
  gray_copy = gray_copy - two_k

  while ( 0 < k ):

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

    next = ( two_k <= gray_copy and gray_copy < two_k * 2 )

    if ( next ):
      gray_copy = gray_copy - two_k

    if ( next != last ):
      rank = rank + two_k
      last = True
    else:
      last = False

  return rank

def ui4_rank_gray_test ( ):

#*****************************************************************************80
#
## UI4_RANK_GRAY_TEST tests UI4_RANK_GRAY.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    22 November 2015
#
#  Author:
#
#    John Burkardt
#
  import platform
  from ui4_to_ubvec import ui4_to_ubvec

  n = 5

  print ( '' )
  print ( 'UI4_RANK_GRAY_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  UI4_RANK_GRAY ranks a UI4 in the Gray ordering.' )
  print ( '' )
  print ( ' UI4  Rank  (binary)' )
  print ( '' )
 
  for ui4 in range ( 0, 32 ):
    rank = ui4_rank_gray ( ui4 )
    ubvec = ui4_to_ubvec ( ui4, n )
    print ( '  %2d    %2d  ' % ( ui4, rank ), end = '' )
    for j in range ( 0, n ):
      print ( '%2d' % ( ubvec[j] ), end = '' )
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'UI4_RANK_GRAY_TEST' )
  print ( '  Normal end of execution.' )
  return

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