/** This file contains routines for generating Gray codes with different
    algorithms.  Gray codes are sequences in which at most one element of the
    sequence changes at a time.

    See:
    "Generalized Gray Codes with Applications", Dah-Jyh GUAN
    https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.1344

    Savage, Carla Diane (1997). "A Survey of Combinatorial Gray Codes". SIAM Review. Society for Industrial and Applied Mathematics (SIAM). 39 (4): 605–629. CiteSeerX 10.1.1.39.1924. doi:10.1137/S0036144595295272. JSTOR 2132693.
    http://www4.ncsu.edu/~savage/AVAILABLE_FOR_MAILING/survey.ps
*/

/** This implements the Guan algorithm (see citation above) for calculating a
    finite "(n, k)-Gray code" where n is the number of states for each element
    and k is the number of elements.  For example, the binary Gray code with k
    elements is a "(2,k)-Gray code".

    This creates a finite-length series with n^k elements.
*/
grayCode[N, K] :=
{
   n = new array[[K+1], N]  // The maximum for each digit
   g = new array[[K+1], 0]  // The Gray code; element 0 is LSB
   u = new array[[K+1], 1]

   while (g@K == 0)
   {
      // Print the current state
      for j = K-1 to 0 step -1
         print[" " + g@j]

      println[]

      // enumerate next Gray code
      i = 0
      k = g@0 + u@0
      while ((k >= n@i) or (k<0))
      {
         u@i = -u@i
         i = i+1
         k = g@i + u@i
      }
      g@i = k
   }
}


/** This implements a modification of the Guan algorithm (see citation above)
    for calculating an infinite "(n, infinity)-Gray code"
    where n is the number of states for each element and a potentially
    infinite length. 

    This creates a infinite-length series.
*/
grayCode[N] :=
{
   g = new array[[1], 0]  // The Gray code; element 0 is LSB
   u = new array[[1], 1]

   while true
   {
      // Print the current state
      for j = length[g]-1 to 0 step -1
         print[" " + g@j]

      println[]

      // enumerate next Gray code
      i = 0
      k = g@0 + u@0
      while ((k >= N) or (k<0))
      {
         u@i = -u@i
         i = i+1
         if i >= length[g]
         {
            // Extend arrays
            g@i = 0     
            u@i = 1
         }
         k = g@i + u@i
      }
      g@i = k
   }
}


/** This implements the Guan algorithm (see citation above) for calculating a
    finite Gray code where each element can have a different number of states.
    The states are specified in the states array, which contains the possible
    values that each state can have.  Element 0 in the array is the least
    significant value.  Each state can be any Frink expression.

    For example:
       args = [array[5 to 7], array[3 to 4]]
       grayCodeStates[args]
*/
grayCodeStates[states is array] :=
{
   n = deepCopy[states]
   K = length[states]
   g = new array[[K+1], 0]  // The Gray code; element 0 is LSB
   u = new array[[K+1], 1]

   while (g@K == 0)
   {
      // Print the current state
      for j = K-1 to 0 step -1
         print[" " + n@j@(g@j)]

      println[]

      // enumerate next Gray code
      i = 0
      k = g@0 + u@0
      while ((k >= length[n@i]) or (k<0))
      {
         u@i = -u@i
         i = i+1
         if i >= K
            return
         k = g@i + u@i
      }
      g@i = k
   }
}