(ns heapsort)

(set! *warn-on-reflection* true)

;; (def ^:const arr-size 12)
(def ^:const arr-size 100000)

(def ^:const Mu 1235523)
(def ^:const Mo 2012345678)

(def array (int-array arr-size))

(defn init-array! [^long first]
  (loop [i 0 val (unchecked-inc-int first)]
    (if (= i arr-size)
      nil
      (do (aset ^ints array i val)
          (recur (unchecked-inc-int i)
                 (unchecked-remainder-int
                  (unchecked-multiply-int val Mu) Mo))))))

(defn swap! [^long i1 ^long i2]
  (let [array (ints array) tmp (aget ^ints array i1)]
    (aset array i1 (aget array i2))
    (aset array i2 tmp)))

(defn move-up! [^long pos]
  (let [array (ints array)]
    (loop [pos pos ppos (unchecked-divide-int pos 2)]
      (if (or (= pos 0)
              (>= (aget array ppos) (aget array pos)))
        nil
        (do
          ;; TEMP: commented out
          ;;(swap! array ppos pos)
          (recur ppos (unchecked-divide-int ppos 2)))))))

(defn move-down! [^long cur-size]
  (let [array (ints array)]
    (loop [ppos 0]
      (let [pos (unchecked-multiply-int ppos 2)
            ;; set pos to the bigger child or -1
            pos (if (>= pos cur-size)
                  (int -1)
                  (if (and (< (unchecked-inc-int pos) cur-size)
                           (> (aget array (unchecked-inc-int pos)) (aget array pos)))
                    (unchecked-inc-int pos)
                    pos))
            ]
        (if (or (= pos -1)
                (>= (aget array ppos) (aget array pos)))
          nil
          (do (swap! ppos pos)
              (recur pos)))))))

(defn sort-array! []
  ;; create the heap (inlined)
  (let [array (ints array)]
    (loop [i 1]
      (if (= i arr-size)
        nil
        (do
          ;; move-up! inlined
          (loop [pos i ppos (unchecked-divide-int pos 2)]
            (if (or (= pos 0)
                    (>= (aget array ppos) (aget array pos)))
              nil
              (do ;(swap! array ppos pos)
                (recur ppos (unchecked-divide-int ppos 2)))))
          
          (recur (unchecked-inc-int i))))))

  ;; create the heap (NOT inlined)
  ;; (loop [i 1]
  ;;   (if (= i arr-size)
  ;;     nil
  ;;     (do (move-up! i)
  ;;         (recur (unchecked-inc-int i)))))


  ;; TEMP: commented out
  ;; repeatedely move heap top to the end and adjust the heap
  ;; (loop [i (unchecked-dec-int arr-size)]
  ;;   (if (= 0 i)
  ;;     nil
  ;;     (do (swap! 0 i)
  ;;         (move-down! i)
  ;;         (recur (unchecked-dec-int i)))))
  )


(defn run-sort []
  ;; (let [array (int-array arr-size)]
    (dotimes [i (long 200)] ;200
      (init-array! i)
      (sort-array!)
      )
    ;; (prn (seq array))
    
    )