minstack.clj

(ns super-sratch.minstack)

(defprotocol Stack (push [this x]) (peek [this]) (pop [this]))
(defprotocol FindMin (find-min [this]))
(defprotocol FindMax (find-max [this]))

(defrecord fmm-stack [stack minstack maxstack]
  Stack
  (push [this x]
    (merge this {:stack (vec (conj stack x))}
           (when (<= x (or (last minstack) Integer/MAX_VALUE))
             {:minstack (vec (conj minstack x))})
           (when (>= x (or (last maxstack) Integer/MIN_VALUE))
             {:maxstack (vec (conj maxstack x))})))
  (peek [this] (last stack))
  (pop [this]
    (let [[new popped] ((juxt drop-last last) stack)
          new (vec new)]
      (merge this {:stack new}
             (when (= popped (last minstack))
               {:minstack (vec (drop-last minstack))})
             (when (= popped (last maxstack))
               {:maxstack (vec (drop-last maxstack))}))))
  FindMin
  (find-min [this] (last minstack))
  FindMax
  (find-max [this] (last maxstack)))

(defn find-stack
  ([& ns]
   (let [fs (atom (->fmm-stack [] [] []))]
     (doseq [n ns]
       (swap! fs push n))
     @fs)))

(find-min (pop (find-stack 1 2 10 -5)))