;a specialised hash-table to store a set of integer values.
;linear probing and keys only - no values.
;i would like to find out why "set-include?" is so slow - 18x slower than guile hash-tables.

(import (srfi srfi-1))
(define (hash-function hash-table value) (modulo value (- (vector-length hash-table) 1)))

(define (set-add! a value)
  (let ((target-index-start (hash-function a value)) (a-length (vector-length a)))
    ;the first loop searches to the end of the vector, loop-2 searches from index 0 to the collision index
    (let loop ((target-index target-index-start))
      (if (vector-ref a target-index)
        (if (< target-index a-length) (loop (+ 1 target-index))
          (let loop-2 ((target-index 0))
            (if (< target-index target-index-start)
              (if (vector-ref a target-index) (loop-2 (+ 1 target-index-start))
                (vector-set! a target-index value))
              #f)))
        (vector-set! a target-index value)))))

(define (set-include? a value)
  (let ((target-index-start (hash-function a value)) (a-length (vector-length a)))
    ;nearly the same search as in "set-add!"
    (let loop ((target-index target-index-start))
      (let ((e (vector-ref a target-index)))
        (if e
          (if (eqv? value e) #t
            (if (< target-index a-length) (loop (+ 1 target-index))
              (let loop-2 ((target-index 0))
                (if (< target-index target-index-start)
                  (let ((e (vector-ref a target-index)))
                    (if e (if (eqv? value e) #t (loop-2 (+ 1 target-index-start))) #f))
                  #f))))
          #f)))))

(define (set-create . values)
  (let ((r (make-vector (+ 1 (* 2 (length values))) #f)))
    (for-each (lambda (e) (set-add! r e)) values) r))

(let ((set (set-create 14 98 56 97 345 906 1 53 451)))
  (display
    (if
      (and (every (lambda (e) (set-include? set e)) (list 53 98 56 345 97 1))
        (not (any (lambda (e) (set-include? set e)) (list 99 54 330 2 0))))
      "success" "failure"))
  (newline))