;=======================================================
; quick sort


(deftemplate qsplit
  (multislot in)
  (slot pivot)
  (multislot left)
  (multislot right)
  (multislot tmp))

(deftemplate qsol
  (multislot in)
  (multislot out))

(deftemplate qsort_sol
  (multislot in)
  (multislot out))

(deftemplate qtree
 (multislot fat)
 (slot pivot)
 (multislot left)
 (multislot right))

(defrule q1
  (qsort $?Z)
  =>
  (if (empty $?Z) then (assert (qsort_sol (in $?Z) (out $?Z)))
   else (assert (qsplit (in $?Z) (pivot (nth$ 1 $?Z)) (tmp (rest$ $?Z)) (left) (right)))))

(defrule q2
  ?I<- (qsplit (in $?Z) (tmp $?W) (pivot ?P) (left $?A) (right $?B))
  =>
  (retract ?I)
  (if (empty $?W) then (assert (qgoal $?A) (qgoal $?B) (qtree (fat $?Z)
                                                              (pivot ?P)
                                                              (left $?A )
                                                              (right $?B)))
  else (if (< (nth$ 1 $?W) ?P) then (assert (qsplit (in $?Z)
                                                     (tmp (rest$ $?W))
                                                     (pivot ?P)
                                                     (left $?A (nth$ 1 $?W))
                                                     (right $?B)))
                                else (assert (qsplit (in $?Z)
                                                     (tmp (rest$ $?W))
                                                     (pivot ?P)
                                                     (left $?A)
                                                     (right $?B (nth$ 1 $?W))))
)))

(defrule q3
  ?I<-(qgoal $?Z)
  =>
  (retract ?I)
  (if (empty $?Z) then (assert (qsol (in $?Z) (out $?Z)))
   else (assert (qsplit (in $?Z) (pivot (nth$ 1 $?Z)) (tmp (rest$ $?Z)) (left) (right)))))

;potialto som rozpajal pole

(defrule q4
  ?I<-(qtree (fat $?Z) (pivot ?P) (left $?A) (right $?B))
  (qsol (in $?A) (out $?VA))
  (qsol (in $?B) (out $?VB))
  =>
  (retract ?I)
  (assert (qsol (in $?Z) (out $?VA ?P $?VB))))

(defrule q5
 (qsort $?Z)
 (qsol (in $?Z) (out $?VZ))
=>
 (assert (qsort_sol (in $?Z) (out $?VZ))))

(defrule q6 (declare (salience -1))
 ?I<-(qsol)
 =>
(retract ?I))