/** This is a library to detect cycles in a sequence.

    See:
    https://en.wikipedia.org/wiki/Cycle_detection

    Hacker's Delight:
    https://web.archive.org/web/20160414011322/http://hackersdelight.org/hdcodetxt/loopdet.c.txt

    Rosetta code:
    https://rosettacode.org/wiki/Cycle_detection
*/

/** Detect a cycle in a function using Brent's method.

    args: [f, x0]
      where
    f:  a function that returns the successor value to f[x]
    x0: the starting value passed to the function.

    returns:
       [cycleStartIndex, cycleLength, cycleStartValue]
*/
detectCycleBrentFunction[f, x0] :=
{
   cycleLength = undef
   hare = x0

   power = 1

   // Main phase:  search successive powers of two.
   FOUND:
   while true
   {
      tortoise = hare
      for i = 1 to power-1
      {
         hare = f[hare]
         if (tortoise == hare)
         {
            cycleLength = i
            break FOUND
         }
      }

      power = power * 2
   }

   // Find the position of the first repetition of cycleLength
   tortoise = hare = x0
   for i = 1 to cycleLength
      hare = f[hare]

   // Distance between tortoise and hare is now cycleLength
   // Now the hare and tortoise move at the same speed until they agree
   cycleStartIndex = 0
   while tortoise != hare
   {
      cycleStartIndex = cycleStartIndex + 1
      tortoise = f[tortoise]
      hare = f[hare]
   }

   // tortoise contains cycle start value.
   return [cycleStartIndex, cycleLength, tortoise]
}

/** Helper function to regenerate the cycle from a function,
    original starting value, starting index, and cycleLength */
makeCycle[f, x0, cycleStartIndex, cycleLength] :=
{
   result = new array
   val = x0
   for i = 1 to cycleStartIndex
      val = f[val]

   result.push[val]
   for j = 1 to cycleLength-1
   {
      val = f[val]
      result.push[val]
   }

   return result
}



// Sample test
f = {|x| (x^2 + 1) mod 255}
x0 = 3
[cycleStartIndex, cycleLength, startValue] = detectCycleBrentFunction[f, x0]
cycle = makeCycle[f, startValue, 0, cycleLength]
println["Cycle start index: $cycleStartIndex"]
println["Cycle length:      $cycleLength"]
println["Cycle start value: $startValue"]
println["Cycle: $cycle"]