;; Numeri di Fibonacci:

(define fib
  (lambda (n)    ; n naturale
    (if (< n 2)
        1
        (+ (fib (- n 2)) (fib (- n 1)))
        )
    ))


;; Applicazione della tecnica di memoization

(define fibonacci
  (lambda (n)
    (memoization-fib n (make-vector (+ n 1) 0))
    ))

(define memoization-fib
  (lambda (n history)
    (if (= (vector-ref history n) 0)
        (vector-set! history n
                     (if (< n 2)
                         1
                         (+ (memoization-fib (- n 2) history)
                            (memoization-fib (- n 1) history))
                         ))
        )
    (vector-ref history n)
    ))


;; Percorsi di Manhattan:

(define manh
  (lambda (i j)
    (if (or (= i 0) (= j 0))
        1
        (+ (manh (- i 1) j) (manh i (- j 1)))
        )
    ))


;; Applicazione della tecnica di memoization


;; Dato astratto "Matrice bidimensionale"
;; 
;; Operazioni:
;;
;;   (make-matrix <hgt> <wdt> <itm>)        :  naturale x naturale
;;                                               x elemento -> matrice
;;
;;   (matrix-ref <mat> <row> <col>)         :  matrice
;;                                               x indice x indice -> elemento
;;
;;   (matrix-set! <mat> <row> <col> <itm>)  :  matrice x indice x indice
;;                                               x elemento -> matrice

(define manhattan
  (lambda (i j)
    (memoization-manh i j (make-matrix (+ i 1) (+ j 1) 0))
    ))

(define memoization-manh
  (lambda (i j history)
    (if (= (matrix-ref history i j) 0)
        (matrix-set! history i j
                     (if (or (= i 0) (= j 0))
                         1
                         (+ (memoization-manh (- i 1) j history)
                            (memoization-manh i (- j 1) history))
                         ))
        )
    (matrix-ref history i j)
    ))


;; Realizzazione della Struttura Dati "Matrice"

(define make-matrix
  (lambda (m n default)
    (let ((matrix (make-vector m))
          )
      (set-rows! matrix (- m 1) n default)
      matrix
      )
    ))

;; Perche' non semplicemente cosi'? :
;;
;; (define make-matrix
;;   (lambda (m n default)
;;     (make-vector m (make-vector n default))
;;     ))


(define set-rows!
  (lambda (matrix k n default)
    (if (>= k 0)
        (begin
          (vector-set! matrix k (make-vector n default))
          (set-rows! matrix (- k 1) n default)
          ))
    ))


(define matrix-ref
  (lambda (matrix i j)
    (vector-ref (vector-ref matrix i) j)
    ))


(define matrix-set!
  (lambda (matrix i j x)
    (vector-set! (vector-ref matrix i) j x)
    ))