(module floyd-cycle-detection mzscheme
  ;; Implementation of Floyd's "tortoise-and-hare" cycle detection.
  
  (require (lib "contract.ss"))
  
  (provide/contract [floyd 
                     (((any/c . -> . any)
                       any/c
                       (any/c any/c . -> . boolean?))
                      . ->* .
                      (any/c number?))]

                    [find-cycle-length
                     ((any/c . -> . any)
                      any/c
                      (any/c any/c . -> . boolean?)
                      . -> . 
                      number?)])
  
  
  ;; floyd: (X -> X) X (X X -> boolean) -> (values X number)
  ;; Floyd's cycle-detection algorithm.
  ;; Assumption: a cycle must exist, or else this function will
  ;; diverge.
  (define (floyd f x0 =?)    
    (let ([t (initial-race f x0 =?)])
      (find-first-repetition f x0 t =?)))

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;; Helpers for floyd:
  
  ;; initial-race: (X -> X) X (X X -> boolean) -> X
  ;; Returns the first place where the tortoise and hare first
  ;; meet up if they race.
  (define (initial-race f x0 =?)
    (let loop ([t (f x0)]
               [h (f (f x0))])
      (cond
        [(=? t h)
         t]
        [else
         (loop (f t) (f (f h)))])))
  
  ;; find-first-repetition: (X -> X) X X (X X -> boolean) -> (values X number)
  ;; Returns the first element that begins the cycle, 
  ;; and the length of the path to that beginning element.
  (define (find-first-repetition f x0 t =?)
    (let loop ([t x0]
               [h t]
               [length 0])
      (cond
        [(=? t h)
         (values h length)]
        [else
         (loop (f t) (f h) (add1 length))])))
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  
  
  
  
  
  ;; find-cycle-length: (X -> X) X (X X -> boolean) -> number
  ;; Returns the length of the cycle.  Precondition: t must be already 
  ;; somewhere in the cycle.  If not, this function will diverge.
  (define (find-cycle-length f t =?)
    (let loop ([h (f t)]
               [length 1])
      (cond [(=? h t)
             length]
            [else
             (loop (f h)
                   (add1 length))])))
  
  
  
  
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;; The following is a small exercise of Floyd's algorithm.
  
  ;; exercise: -> boolean
  ;; Should return true if the exercise is working correctly.
  (define (exercise)
    (define graph '((a b)
                    (b c)
                    (c d)
                    (d b)))
    (define (f sym)
      (cadr (assq sym graph)))
    ;; we expect to see that we get back (values b 1) out of this.
    (let-values ([(start-of-cycle distance-to-cycle)
                  (floyd f 'a eq?)])
      (and (equal? start-of-cycle 'b)
           (equal? distance-to-cycle 1)
           (equal? (find-cycle-length f start-of-cycle eq?) 
                   3))))
  
  
  ;; How good is the current-pseudo-random-generator?  Let's see.
  (define (exercise-2)
    (define x0 (pseudo-random-generator->vector
                (current-pseudo-random-generator)))
    (define (f x)
      (parameterize ([current-pseudo-random-generator
                      (vector->pseudo-random-generator x)])
        (random)
        (pseudo-random-generator->vector
         (current-pseudo-random-generator))))
    
    (floyd f x0 equal?))
  
  
  
  (define (exercise-3)
    ;; playing with posix.1.2001 random implementation
    (define (myrand x)
      (modulo (+ (* x 1103515245) 12345)
              (expt 2 32)))
    (floyd myrand 1 =)))