#lang racket

(require data/heap)
;(require "../plivastigoj.rkt")

(define (run-time)
  (* (current-inexact-milliseconds)
     #i1/1000))

(define (somma-semplice v)
  (let ((lim (vector-length v)))
    (let ancora ((i 0) (somma 0.0))
      (if (= i lim)
        somma
        (ancora (+ i 1) 
                (+ somma (vector-ref v i)))))))

(define (somma-posneg v)
  (let ((n (vector-length v)))
    (let sum ((i 0) (pos 0.0) (neg 0.0))
      (if (= i n)
        (+ pos neg)
        (let ((item (vector-ref v i)))
          (if (positive? item)
            (sum (+ i 1) (+ pos item) neg)
            (sum (+ i 1) pos (+ neg item))))))))

(define (ordinata sommatore v)
  (heap-sort! (λ (a b)
                (<= (abs a) (abs b)))
              v)
  (sommatore v))

(define (somma-posneg-ordinata v)
  (ordinata somma-posneg v))

(define (somma-esatta-0 v)
  (let ((lim (vector-length v)))
    (let ancora ((i 0) (somma 0))
      (if (= i lim)
        somma
        (ancora (+ i 1) 
                (+ somma (inexact->exact (vector-ref v i))))))))

(define (somma-esatta-1 v #:from (from 0) #:to (to (vector-length v)))
  (let sum ((from from) (to to))
    (case (- to from)
      ((0) 0)
      ((1) (inexact->exact (vector-ref v from)))
      ((2) (+ (inexact->exact (vector-ref v from))
              (inexact->exact (vector-ref v (+ from 1)))))
      (else
       (let ((middle (quotient (+ from to) 2)))
         (+ (sum from middle)
            (sum middle to)))))))

(define (somma-ricorsiva v #:from (from 0) #:to (to (vector-length v)))
  (let sum ((from from) (to to))
    (case (- to from)
      ((0) 0)
      ((1) (vector-ref v from))
      ((2) (+ (vector-ref v from)
              (vector-ref v (+ from 1))))
      ((3) (+ (vector-ref v from)
              (vector-ref v (+ from 1))
              (vector-ref v (+ from 2))))
      ((4) (+ (+ (vector-ref v from)
                 (vector-ref v (+ from 1)))
              (+ (vector-ref v (+ from 2))
                 (vector-ref v (+ from 3)))))
      (else
       (let ((middle (quotient (+ from to) 2)))
         (+ (sum from middle)
            (sum middle to)))))))

(define (somma-ricorsiva-ordinata v)
  (ordinata somma-ricorsiva v))

(define (pop! h)
  (begin0 (heap-min h)
    (heap-remove-min! h)))

(define (push! h v)
  (heap-add! h v)
  h)

(define (somma-un-heap h)
  (displayln "somma un heap inizio somma")
  (let ancora ((count (heap-count h)))
    (case count
      ((0) 0)
      ((1) (pop! h))
      (else
       (heap-add! h (+ (pop! h) (pop! h)))
       (ancora (- count 1))))))

(define (somma-heap v)
  (displayln "somma heap inizio separazione")
  (let ((lim (vector-length v)))
    (let ancora ((i 0)
                 (heap-pos (make-heap <=))
                 (heap-neg (make-heap >=)))
      (if (= i lim)
        (begin
          (displayln "somma heap fine separazione")
          (+ (somma-un-heap heap-pos)
             (somma-un-heap heap-neg)))
        (let ((q (vector-ref v i)))
          (if (positive? q)
            (ancora (+ i 1)
                    (push! heap-pos q)
                    heap-neg)
            (ancora (+ i 1)
                    heap-pos
                    (push! heap-neg q))))))))

(define (test sommatore nome v (somma-esatta #f))
  (let* ((v (vector-copy v))
         (t0 (run-time))
         (rispo (sommatore v))
         (t1 (run-time))
         (errore (if somma-esatta
                   (abs (/ (- rispo somma-esatta) somma-esatta))
                   #f)))
    (displayln (list nome (exact->inexact rispo) (- t1 t0) errore))
    rispo))

(define (fa n exp)
  (let ((v (make-vector n)))
    (for ((i (in-range n)))
      (vector-set! v i (let ((x (expt (random) exp)))
                         (if (zero? (random 2))
                           x
                           (- x)))))
    (let ((esatta (test somma-esatta-0 "esatta 0" v)))
      (test somma-esatta-1 "esatta 1" v)
      (test somma-semplice "semplice" v esatta)
      (test somma-posneg "posneg" v esatta)
      (test somma-posneg-ordinata "posneg ordinata" v esatta)
      (test somma-ricorsiva "ricorsiva" v esatta)
      (test somma-ricorsiva-ordinata "ricorsiva ordinata" v esatta)
      (test somma-heap "heap" v esatta)
      (values))))