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):
    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 ) : 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.
Floyd s Cycle Detector .