#! /usr/bin/env python
#
def thue_binary_next ( n, thue ):

#*****************************************************************************80
#
## THUE_BINARY_NEXT returns the next element in a binary Thue sequence.
#
#  Discussion:
#
#    Thue demonstrated that arbitrarily long sequences of 0's and
#    1's could be generated which had the "cubefree" property.  In
#    other words, for a given string S, there was no substring W
#    such that S contained "WWW".  In fact, a stronger result holds:
#    if "a" is the first letter of W, it is never the case that S
#    contains the substring "WWa".
#
#    In this example, the digits allowed are binary, that is, just
#    "0" and "1".  The replacement rules are:
#
#    "0" -> "01"
#    "1" -> "10"
#
#    This routine produces the next binary Thue sequence in a given series.
#    However, the input sequence must be a Thue sequence in order for
#    us to guarantee that the output sequence will also have the
#    cubic nonrepetition property.
#
#    Also, enough space must be set aside in THUE to hold the
#    output sequence.  This will always be twice the input
#    value of N.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    17 May 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer N, the length of the input sequence.
#
#    Input, integer THUE(N), the initial Thue sequence.
#
#    Output, integer N, the length of the output sequence.
#
#    Output, integer THUE(N), the result of applying the substitution rules once.
#
  import numpy as np
  from sys import exit

  n2 = 2 * n
  thue2 = np.zeros ( n2, dtype = np.int32 )

  i2 = 0
  for i in range ( 0, n ):

    if ( thue[i] == 0 ):
      thue2[i2] = 0
      i2 = i2 + 1
      thue2[i2] = 1
      i2 = i2 + 1
    elif ( thue[i] == 1 ):
      thue2[i2] = 1
      i2 = i2 + 1
      thue2[i2] = 0
      i2 = i2 + 1
    else:
      print ( '' )
      print ( 'THUE_BINARY_NEXT - Fatal error!' )
      print ( '  The input sequence contains a non-binary digit' )
      print ( '  THUE[%d] = %d' % ( i, thue[i] ) )
      exit ( 'THUE_BINARY_NEXT - Fatal error!' )
 
  return n2, thue2

def thue_binary_next_test ( ):

#*****************************************************************************80
#
## THUE_BINARY_NEXT_TEST tests THUE_BINARY_NEXT.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    17 May 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'THUE_BINARY_NEXT_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  THUE_BINARY_NEXT returns the next Thue binary sequence.' )
  print ( '' )

  n = 1
  thue = np.zeros ( n, dtype = np.int32 )
  thue[0] = 0

  print ( '  %2d:  ' % ( n ) ),
  for i in range ( 0, n ):
    print ( '%d' % ( thue[i] ) ),
  print ( '' )

  for i in range ( 0, 6 ): 

    n, thue = thue_binary_next ( n, thue )

    print ( '  %2d:  ' % ( n ) ),
    for i in range ( 0, n ):
      print ( '%d' % ( thue[i] ) ),
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'THUE_BINARY_NEXT_TEST:' )
  print ( '  Normal end of execution.' )
  return

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