cycle_detector.py
def floyd(seqs, f=None, start=None, key=lambda x: x):
    """Floyd's Cycle Detector.

    See help(cycle_detector) for more context.

    Args:

      *args: Two iterators issueing the exact same sequence:
      -or-
      f, start: Function and starting state for finite state machine

    Yields: 

      Values yielded by sequence_a if it terminates, undefined if a
      cycle is found.

    Raises:

      CycleFound if exception is found; if called with f and `start`,
      the parametres `first` and `period` will be defined indicating
      the offset of start of the cycle and the cycle's period.
    """

    tortise, hare = seqs

    yield hare.next()
    tortise_value = tortise.next()
    hare_value = hare.next()
    while hare_value != tortise_value:
        yield hare_value
        yield hare.next()
        hare_value = hare.next()
        tortise_value = tortise.next()

    if f is None:
        raise CycleDetected()

    hare_value = f(hare_value)
    first = 0
    tortise_value = start
    while key(tortise_value) != key(hare_value):
        tortise_value = f(tortise_value)
        hare_value = f(hare_value)
        first += 1

    period = 1
    hare_value = f(tortise_value)
    while key(tortise_value) != key(hare_value):
        hare_value = f(hare_value)
        period += 1

    raise CycleDetected(period=period, first=first)
def floyd(seqs, f=None, start=None, key=lambda x: x):
    """Floyd's Cycle Detector.

    See help(cycle_detector) for more context.

    Args:

      *args: Two iterators issueing the exact same sequence:
      -or-
      f, start: Function and starting state for finite state machine

    Yields: 

      Values yielded by sequence_a if it terminates, undefined if a
      cycle is found.

    Raises:

      CycleFound if exception is found; if called with f and `start`,
      the parametres `first` and `period` will be defined indicating
      the offset of start of the cycle and the cycle's period.
    """

    tortise, hare = seqs

    yield hare.next()
    tortise_value = tortise.next()
    hare_value = hare.next()
    while hare_value != tortise_value:
        yield hare_value
        yield hare.next()
        hare_value = hare.next()
        tortise_value = tortise.next()

    if f is None:
        raise CycleDetected()

    hare_value = f(hare_value)
    first = 0
    tortise_value = start
    while key(tortise_value) != key(hare_value):
        tortise_value = f(tortise_value)
        hare_value = f(hare_value)
        first += 1

    period = 1
    hare_value = f(tortise_value)
    while key(tortise_value) != key(hare_value):
        hare_value = f(hare_value)
        period += 1

    raise CycleDetected(period=period, first=first)
Floyd's Cycle Detector.

    See help(cycle_detector) for more context.

    Args:

      *args: Two iterators issueing the exact same sequence:
      -or-
      f, start: Function and starting state for finite state machine

    Yields: 

      Values yielded by sequence_a if it terminates, undefined if a
      cycle is found.

    Raises:

      CycleFound if exception is found; if called with f and `start`,
      the parametres `first` and `period` will be defined indicating
      the offset of start of the cycle and the cycle's period.