;;; BENCHMARK SETS

; AVL

(require (planet "sets.scm" ("oesterholt" "datastructs.plt" 1 0)))

;;; DATA CONSTRUCTION (to prepare for the benchmark)

; Create a list of overlapping intervals
; (0 2 ... 2N-1) (N ... 3N-1) ... ((K-1)N ... (K+1)N-1)
(define N 300)
(define K 300)

(require (lib "42.ss" "srfi"))

(define intervals (list-ec (: k K)
                           (list-ec (: n  (* k N) (* (+ k 2) N))
                                    n)))

; The same intervals, but now as sets.

(define (list->set xs)
  (let loop ([s (set = <)]
             [xs xs])
    (if (null? xs)
        s
        (loop (set+ s (car xs)) (cdr xs)))))

(define sets 
  (map (lambda (xs) (list->set xs))
       intervals))


;;; LIST -> SET

(define lists-with-duplicates
  (map (lambda (l) (append l l))
       intervals))

(time
 (begin
   ; conversion from list to set
   (map (lambda (xs) (list->set xs))
        lists-with-duplicates)
   'list->set))


;;; LIST OF SETS -> UNION 

(time
 (begin
   ; union of a list of sets
   (foldl set-union (set = <) sets)
   'union))

;;; LIST OF SETS -> INTERSECTION

; intersection between sets with overlap

(time
 (begin
   (let loop ([sets sets])
     (if (or (null? sets) (null? (cdr sets)))
         'intersection
         (begin
           (set-intersection (car sets) (cadr sets))
           (loop (cdr sets)))))))


; N=300, K=300

; cpu time: 1141 real time: 1141 gc time: 0
; list->set

; cpu time: 114781 real time: 115094 gc time: 13824
; union

; cpu time: 672 real time: 672 gc time: 157
; intersection