;
; super-test creates n trees, inserts k random items and deletes them in random order
; checking the correctness of the tree after every deletion  
;


(defparameter *test-list-array* nil)

(defun prepare-test-lists (n k)

  (let ((lis nil))
    (setf *test-list-array* (make-array n :initial-element nil))
    (dotimes (i n)
      (do ((rnd (random (* 10 k)) (random (* 10 k))))
          ((= (length lis) k) lis)
        (setf lis (adjoin rnd lis)))
      (setf (aref *test-list-array* i) lis))))
    
  

(defun test-tree (lis)

  (let ((tt (rbt:make-red-black-tree)))

    (dolist (elem lis)
      (rbt:insert elem tt))

    tt))


(defun super-test (n k)

  (dotimes (i n)

    (let* ((len k)
           (extra-time 0)
           (lis nil)
           (root nil))

      (if (zerop (mod i 50)) (format t "i = ~A~%" i))
      
      (setf lis (aref *test-list-array* i))

      (setf root (test-tree lis))

;      (if (null (check-rbt root))
;        (error "RBT-property not fulfilled"))

      (setf lis (loop for j from 0 to (- k 2) collect (rbt:select j root)))
      (print lis)
      (setf lis (butlast lis 5))

      (loop with it = nil

            while (not (null lis))
            do

            (setf it (nth (random (length lis)) lis))
            (setf lis (remove it lis))
            (rbt:delete-by-key it root)))))
            
;            (when (null (check-rbt root))

;              (setf err-tree root)
;              (error "Mistake in delete-function")))

;      (gapp:graph-app (tree-list root))

;            (format nil "Len lis = ~A ~%" (length (item-list root)))))))