(module collatz mzscheme
  
  ;; By Paulo Jorge Matos
  ;; During a very dark saturday night where there was nothing more to do than
  ;; to program in Scheme (IT WOULD BE A GREAT NIGHT THEN!!!)...
  
  (require (lib "plot.ss" "plot")
           (lib "class.ss")
           (lib "plot-extend.ss" "plot")) ;; To create the plots
  
  ;; Collatz Function (optimized)
  ;; =================
  ;; F(n) = [(3n+1) / 2] if n is odd
  ;; F(n) = n/2 if n is even
 
  ;; Background Vocabulary
  ;; =====================
  ;;
  ;; Collatz Number:  The positive integer which is passed as an argument to the collatz function.
  ;; Hailstone Sequence: The sequence generated by the continuous iteration of the collatz function.
  ;; Hailstone Number: A number belonging to a HailStone Sequence.

;                                
;                                
;                                
;   ;   ; ;;;;; ;;;;; ;      ;;; 
;   ;   ;   ;     ;   ;     ;   ;
;   ;   ;   ;     ;   ;     ;    
;   ;   ;   ;     ;   ;      ;;; 
;   ;   ;   ;     ;   ;         ;
;   ;   ;   ;     ;   ;     ;   ;
;    ;;;    ;   ;;;;; ;;;;;  ;;; 
;                                
;                                
;                                
                                                            
  ;; We're defining a database for the peaks and sizes of hailstone sequences and another one for the hailstone sequences themselves.
  (define collatzdb (make-hash-table))
  (define seqdb (make-hash-table))
  
  ;; add-collatzdb : k1 x pair -> void
  ;; Adds to the database of size/peak values the value of the size and peak in a pair of the
  ;; collatz sequence of k1.
  (define (add-collatzdb k1 p)
    (hash-table-put! collatzdb k1 p))
  
  ;; check-collatzdb : k -> pair | #f
  ;; Given a k, verifies the database of size/peak values and if there is no information
  ;; about the hailstone sequence of k there, returns #f, else returns the saved information.
  (define (check-collatzdb k)
    (hash-table-get collatzdb k (lambda () #f)))
  
  ;; add-seqdb : k1 x list -> void
  ;; Adds to the database of hailstone sequences the sequence for k1.
  (define (add-seqdb k1 l)
    (hash-table-put! seqdb k1 l))
  
  ;; check-seqdb : k -> l | #f
  ;; Given a collatz number k, verifies the hailstone sequence database to know if there is any 
  ;; collatz number k in database, if there is returns its hailstone sequence, else returns #f.
  (define (check-seqdb k)
    (hash-table-get seqdb k (lambda () #f)))
  
  ;; collatz : k -> pair
  ;; Given k, returns a pair with the length of the HailStone Sequence and the 
  ;; sequence peak. Saves in a database the sequence until it reaches 1.
  (define (collatz k)
    (define (collatz-aux n size peak seq) 
      (cond ((= n 1)
             (if (not (check-seqdb k)) 
                 (add-seqdb k (reverse! (cons 1 seq))))  ;; adds sequence to sequence database
             (cons (+ 1 size) peak))
            ((even? n)
             (collatz-aux (/ n 2)
                          (+ size 1)
                          (max n peak)
                          (cons n seq)))
            ((odd? n)
             (collatz-aux (/ (+ (* 3 n) 1) 2)
                          (+ size 1)
                          (max n peak)
                          (cons n seq)))
            (else #f)))
    (let* ((val-init (check-collatzdb k))
           (val-final (if val-init 
                          val-init 
                          (collatz-aux k 0 k null)))) ;; Only executes auxiliar procedure once!
      (if (not val-init)
          (add-collatzdb k val-final)) ;; Adds to database is there's nothing there.
      val-final))
  
  ;; iota : init x end x step -> list
  ;; Returns a list with first element init, last element end and with 
  ;; step between list values.
  (define (iota init end step)
    (define (iota-aux i l)
      (if (> i end)
          (reverse! l)
          (iota-aux (+ i step) (cons i l))))
    (iota-aux init null))
  
  ;; collatz-peaks : init x end x step -> list
  ;; Given an initial value, final value and a step, returns a list with the peaks of
  ;; the collatz sequence of each value in the list.
  (define (collatz-peaks init end step)
    (map (lambda (k)
           (cdr (collatz k)))
         (iota init end step)))
  
  ;; collatz-size : init x end x step -> list
  ;; Given an initial value, final value and a step, returns a list with the sizes of the
  ;; collatz sequence of each value in the list.
  (define (collatz-size init end step)
    (map (lambda (k)
           (car (collatz k)))
         (iota init end step)))
  
  ;; average : list -> k
  ;; Given a list of numbers, returns its average.
  (define (average l)
    (/ (apply + l)
       (length l)))
                                            

;                                
;                                
;                                
;   ;;;;  ;      ;;;  ;;;;;  ;;; 
;   ;   ; ;     ;   ;   ;   ;   ;
;   ;   ; ;     ;   ;   ;   ;    
;   ;;;;  ;     ;   ;   ;    ;;; 
;   ;     ;     ;   ;   ;       ;
;   ;     ;     ;   ;   ;   ;   ;
;   ;     ;;;;;  ;;;    ;    ;;; 
;                                
;                                
;                                

  
  
  ;; New plot type
  (define point-syms
    '((square 16) (odot 9) (bullet 17) (circle 4)))
  
  (define-plot-type pline
                    data 2dplotview (x-min x-max) ((color 'red) (width 1) (sym 'square))
                    (send* 2dplotview 
                      (set-line-color color) 
                      (set-line-width width)
                      (plot-line data)
                      (plot-points data 
                                   (cond [(assq sym point-syms) => cadr]
                                         [else (error "Symbol not found in table!")]))))
  
  ;; collatz-plot-peaks : init x end x step -> plot
  ;; Given an initial value, a final value and a step it generates a plot of the various peaks
  ;; of sequence values.
  (define (collatz-plot-peaks init end step)
    (let ([peaks-val (collatz-peaks init end step)])
      (plot (pline (map vector
                        (iota init end step)
                        peaks-val) 
                   (color 'green))
            (x-min init)
            (x-max end)
            (y-min 0)
            (y-max (apply max peaks-val))
            (x-label "Collatz Values")
            (y-label "Sequence Length")
            (title (format "Collatz : initial ~a, end ~a, step ~a."
                           init end step)))))
  
  ;; collatz-plot-size : init x end x step -> plot
  ;; Given an initial value, final and a step, generates a plot of the various sizes of the
  ;; sequence for the range of values.
  (define (collatz-plot-size init end step)
    (let ([size-val (collatz-size init end step)])
      (plot (pline (map vector
                        (iota init end step)
                        size-val)
                   (color 'red))
            (x-min init)
            (x-max end)
            (y-min 0)
            (y-max (apply max size-val))
            (x-label "HailStone Numbers")
            (y-label "Sequence Size")
            (title (format "Size of Collatz with init ~a, end ~a and step ~a."
                           init end step)))))
  
  ;; collatz-plot-seq : k -> plot
  ;; Plots a collatz sequence for a given value.
  (define (collatz-plot-seq k)
    (let* ([val (check-seqdb k)]
           [seq (if (not val)
                    (begin 
                      (collatz k)
                      (check-seqdb k))
                    val)])
      (plot (pline (map vector
                        (iota 0 (- (length seq) 1) 1)
                        seq))
            (x-min 0)
            (x-max (length seq))
            (y-min 0)
            (y-max (apply max seq))
            (x-label "Sequence Values")
            (y-label "Sequence Iterations")
            (title (format "HailStone Sequence for ~a~n" k)))))
                   
      
  

;                                            
;                                            
;                                            
;   ;;;;  ;;;;; ;;;;   ;;;  ;;;;  ;;;;;  ;;; 
;   ;   ; ;     ;   ; ;   ; ;   ;   ;   ;   ;
;   ;   ; ;     ;   ; ;   ; ;   ;   ;   ;    
;   ;;;;  ;;;;; ;;;;  ;   ; ;;;;    ;    ;;; 
;   ;  ;; ;     ;     ;   ; ;  ;;   ;       ;
;   ;   ; ;     ;     ;   ; ;   ;   ;   ;   ;
;   ;     ;;;;; ;      ;;;  ;       ;    ;;; 
;                                            
;                                            
;                                            
                                                     

  ;; report-value : k -> void
  ;; Function that given a collatz number prints to the interaction window a report on that number.
  (define (report-value k)
    (let* ([stats-valor (collatz k)]
           [seq (check-seqdb k)])
      (printf "Value : ~a~n===========================~n" k)
      (printf "Sequence :~n~a~n" seq)
      (printf "Size : ~a ~n" (car stats-valor))
      (printf "Peak : ~a ~n" (cdr stats-valor))
      (printf "Average : ~a ~n" (exact->inexact (average seq)))
      (printf "Plot of HailStone Sequence:~n~a~n" (collatz-plot-seq k))))
                           
  
  
  ;; report-seq : init end step -> void
  ;; Function that given an initial value init, an end value and a step value prints
  ;; to the interaction window the report for each sequence of {init, init+step, init+2*step, ..., end}.
  (define (report-seq init end step)
    (let ([vals-seq (iota init end step)])
      (printf "Values of Sequence : ~a~n" vals-seq)
      (printf "Plot of HailStone Sequence Peaks :~n~a~n" (collatz-plot-peaks init end step))
      (printf "Plot of HailStone Sequence Sizes :~n~a~n" (collatz-plot-size init end step))))
  
  (provide (all-defined))
  )