;;; BENCHMARK SETS

; GALORE 2

(require (planet "set.ss" ("soegaard" "galore.plt" 2 0)))

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

;;; 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)

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

; The same intervals, but now as sets.

(define sets 
  (map (lambda (xs) (list->set integer-compare 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 integer-compare xs))
        lists-with-duplicates)
   'list->set))


;;; LIST OF SETS -> UNION 

(time
 (begin
   ; union of a list of sets
   (foldl union (empty integer-compare) 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
           (intersection (car sets) (cadr sets))
           (loop (cdr sets)))))))

; N=300, K=300

; cpu time: 1375 real time: 1390 gc time: 203
; list->set

; cpu time: 25141 real time: 25250 gc time: 10734
; union

; cpu time: 375 real time: 375 gc time: 234
; intersection