(defpackage :cp/test/succinct-bit-vector
  (:use :cl :fiveam :cp/succinct-bit-vector :cp/displace)
  (:import-from :cp/test/base #:base-suite)
  (:import-from :cp/succinct-bit-vector #:+chunk-width+))
(in-package :cp/test/succinct-bit-vector)
(in-suite base-suite)

(test succinct-bit-vector
  (let ((state (sb-ext:seed-random-state 0)))
    (let ((sucbv (make-sucbv! #*101101)))
      (is (= 0 (sucbv-rank sucbv 0)))
      (is (= 1 (sucbv-rank sucbv 1)))
      (is (= 1 (sucbv-rank sucbv 2)))
      (is (= 2 (sucbv-rank sucbv 3)))
      (is (= 3 (sucbv-rank sucbv 4)))
      (is (= 3 (sucbv-rank sucbv 5)))
      (is (= 4 (sucbv-rank sucbv 6)))
  ( signals error ( sucbv - rank sucbv 7 ) )
      (is (= 0 (sucbv-select sucbv 0)))
      (is (= 0 (sucbv-select sucbv 1)))
      (is (= 2 (sucbv-select sucbv 2)))
      (is (= 3 (sucbv-select sucbv 3)))
      (is (= 5 (sucbv-select sucbv 4)))
      (signals error (sucbv-select sucbv 5)))
    
    ;; null case
    (let ((sucbv (make-sucbv! #*)))
      (is (= 0 (sucbv-rank sucbv 0)))
      (is (= 0 (sucbv-select sucbv 0))))

    ;; random case (non-multiple of +chunk-width+)
    (let* ((vec (let ((tmp (make-array 10000 :element-type 'bit)))
                  (dotimes (i (length tmp) tmp)
                    (setf (aref tmp i) (random 2 state)))))
           (sucbv (make-sucbv! vec))
           (sum 0))
      (is (zerop (sucbv-select sucbv 0)))
      (finishes
        (dotimes (i (length vec))
          (assert (= sum (sucbv-rank sucbv i)))
          (when (= 1 (aref vec i))
            (incf sum)
            (assert (= i (sucbv-select sucbv sum)))))))
    
    ;; random case (multiple of +chunk-width+)
    (let* ((vec (let ((tmp (make-array +chunk-width+ :element-type 'bit)))
                  (dotimes (i (length tmp) tmp)
                    (setf (aref tmp i) (random 2 state)))))
           (sucbv (make-sucbv! vec))
           (sum 0))
      (is (zerop (sucbv-select sucbv 0)))
      (finishes
        (dotimes (i (length vec))
          (assert (= sum (sucbv-rank sucbv i)))
          (when (= 1 (aref vec i))
            (incf sum)
            (assert (= i (sucbv-select sucbv sum)))))))))

 null case
 random case (non-multiple of +chunk-width+)
 random case (multiple of +chunk-width+)
(defpackage :cp/test/succinct-bit-vector
  (:use :cl :fiveam :cp/succinct-bit-vector :cp/displace)
  (:import-from :cp/test/base #:base-suite)
  (:import-from :cp/succinct-bit-vector #:+chunk-width+))
(in-package :cp/test/succinct-bit-vector)
(in-suite base-suite)

(test succinct-bit-vector
  (let ((state (sb-ext:seed-random-state 0)))
    (let ((sucbv (make-sucbv! #*101101)))
      (is (= 0 (sucbv-rank sucbv 0)))
      (is (= 1 (sucbv-rank sucbv 1)))
      (is (= 1 (sucbv-rank sucbv 2)))
      (is (= 2 (sucbv-rank sucbv 3)))
      (is (= 3 (sucbv-rank sucbv 4)))
      (is (= 3 (sucbv-rank sucbv 5)))
      (is (= 4 (sucbv-rank sucbv 6)))
  ( signals error ( sucbv - rank sucbv 7 ) )
      (is (= 0 (sucbv-select sucbv 0)))
      (is (= 0 (sucbv-select sucbv 1)))
      (is (= 2 (sucbv-select sucbv 2)))
      (is (= 3 (sucbv-select sucbv 3)))
      (is (= 5 (sucbv-select sucbv 4)))
      (signals error (sucbv-select sucbv 5)))
    
    (let ((sucbv (make-sucbv! #*)))
      (is (= 0 (sucbv-rank sucbv 0)))
      (is (= 0 (sucbv-select sucbv 0))))

    (let* ((vec (let ((tmp (make-array 10000 :element-type 'bit)))
                  (dotimes (i (length tmp) tmp)
                    (setf (aref tmp i) (random 2 state)))))
           (sucbv (make-sucbv! vec))
           (sum 0))
      (is (zerop (sucbv-select sucbv 0)))
      (finishes
        (dotimes (i (length vec))
          (assert (= sum (sucbv-rank sucbv i)))
          (when (= 1 (aref vec i))
            (incf sum)
            (assert (= i (sucbv-select sucbv sum)))))))
    
    (let* ((vec (let ((tmp (make-array +chunk-width+ :element-type 'bit)))
                  (dotimes (i (length tmp) tmp)
                    (setf (aref tmp i) (random 2 state)))))
           (sucbv (make-sucbv! vec))
           (sum 0))
      (is (zerop (sucbv-select sucbv 0)))
      (finishes
        (dotimes (i (length vec))
          (assert (= sum (sucbv-rank sucbv i)))
          (when (= 1 (aref vec i))
            (incf sum)
            (assert (= i (sucbv-select sucbv sum)))))))))
