2
\$\begingroup\$

This is a follow up to my last review request.

I made three major changes:

  • I had it fully implement ISeq and IPersistentStack, meaning it's now compatible with all of the core sequence functions.

  • The queue now stores a custom comparator so it can be treated as a min queue, a max queue, or any other sorting method needed.

  • Because records can't implement ISeq (because they already do as an associative structure), I had to use deftype for the first time. This created some complications, and I ended up moving the linked list structure to another file and treating it as a separate entity. The queue is now basically just a wrapper over the linked list.

Example:

(-> (new-minimum-priority-queue) ; Lower priorities first
    (conj [2 :b] ; Conj takes [priority element] pairs
          [1 :a])
    (push-queue 3 :c) ; Or you can just fall back to the base functions
    (seq))
=> ([1 :a] [2 :b] [3 :c])

I'm looking for any feedback, although I have a few main concerns:

  • This is my first time ever using deftype. Any critique regarding its usage would be appreciated.

  • This is my first time implementing the entirety of ISeq. Any critique here would be appreciated as well.

  • It's relatively slow. For head insertions (the fastest operation possible for the queue), it's 10x slower than conjoining onto a vector or list. For "tail" insertions that require iterating the entire list, it's 33,000x slower than conjoining onto a vector!


(ns priority-queue.node-list)

(defrecord Node [priority bucket child])

(defn new-node [priority value]
  (->Node priority [value] nil))

(defn- add-value-to-node [node value]
  (update node :bucket conj value))

(defn- set-child-of-node [node child]
  (assoc node :child child))

; TODO Add equality-f as well?
(defn push-new-node [root priority value priority-comparator]
  (let [node (new-node priority value)]
    ((fn rec [{n-pri :priority, n-child :child :as cur-node}]
       (cond
         (nil? cur-node) node
         (priority-comparator priority n-pri) (set-child-of-node node cur-node)
         (= priority n-pri) (add-value-to-node cur-node value)
         :else (set-child-of-node cur-node (rec n-child))))
     root)))

(defn- has-n-values? [node n]
  (>= (count (:bucket node)) n))

(defn remove-priority [root]
  (if (has-n-values? root 2)
    (update root :bucket subvec 1)
    (:child root)))

(defn peek-root
  "Returns a pair of [priority highest-priority-item], or nil if the node has no values."
  [root]
  (when (has-n-values? root 1)
    (let [{:keys [bucket priority]} root]
      [priority (first bucket)])))

(ns priority-queue.priority-queue
  (:require [priority-queue.node-list :as nl]
            [criterium.core :as c])
  (:import [clojure.lang IPersistentStack ISeq]))

(declare new-priority-queue seq-queue push-queue peek-priority? pop-priority?
         equiv)

(deftype Priority-Queue [root size priority-comparator]
  ISeq
  (seq [q] (seq-queue q))

  (empty [q] (new-priority-queue priority-comparator))
  (count [q] size)
  (cons [q [p e :as priority-element-pair]] (push-queue q p e))
  (equiv [q1 q2] (equiv q1 q2))

  (first [q] (peek-priority? q))
  (next [q] (second (pop-priority? q)))
  (more [q] (or (next q)
                (empty q)))

  IPersistentStack
  (peek [q] (peek-priority? q))
  (pop [q] (or (next q)
               (throw (IllegalStateException. "Can't pop empty priority queue using pop. Use peek-priority? to
               return nil when peeking an empty queue.")))))

(defn new-priority-queue [priority-comparator]
  (->Priority-Queue nil 0 priority-comparator))

(defn new-minimum-priority-queue []
  (new-priority-queue <))

(defn new-maximum-priority-queue []
  (new-priority-queue >))

(defn queue-empty? [^Priority-Queue queue]
  (nil? (.root queue)))

; TODO: Find a way to generalize
(defn- alter-size [^Priority-Queue queue, f]
  (->Priority-Queue (.root queue) (f (.size queue)) (.priority_comparator queue)))

(defn- alter-root [^Priority-Queue queue, f]
  (->Priority-Queue (f (.root queue)) (.size queue) (.priority_comparator queue)))

(defn push-queue
  "Pushes the value with a given priority into the queue."
  [^Priority-Queue queue, priority, value]
  (when-not value
    (throw (RuntimeException. (str "Pushed values must be truthy!: " (pr-str value)))))

  (-> queue
      (alter-root #(nl/push-new-node % priority value (.priority_comparator queue)))
      (alter-size inc)))

(defn peek-priority?
  "Returns either a pair of [priority highest-priority-item], or nil if the queue is empty.
  If multiple items have the same priority, the first pushed item is returned."
  [^Priority-Queue queue]
  (when-not (queue-empty? queue)
    (nl/peek-root (.root queue))))

(defn pop-priority?
  "Returns either a pair of [highest-priority rest-queue], or nil if the queue is empty."
  [^Priority-Queue queue]
  (when-let [popped (peek-priority? queue)]
    [popped
     (-> queue
         (alter-root nl/remove-priority)
         (alter-size dec))]))

(defn seq-queue [^Priority-Queue queue]
  (when (and queue (not (queue-empty? queue)))
    (loop [rest-queue queue
           acc []]
      (if-let [[popped remaining] (pop-priority? rest-queue)]
        (recur remaining (conj acc popped))
        (seq acc)))))

(defn equiv [^Priority-Queue q1, ^Priority-Queue q2]
  (and (= (.size q1) (.size q2))
       (= (.root q1) (.root q2))))
\$\endgroup\$
  • \$\begingroup\$ Seems like a lot of work. Is this just an exercise? Have you considered writing a wrapper to java.util.PriorityQueue<E>? docs.oracle.com/javase/10/docs/api/java/util/PriorityQueue.html \$\endgroup\$ – Alan Thompson May 31 '18 at 20:23
  • \$\begingroup\$ @AlanThompson This was an exercise. I had never written a priority queue before, used deftype, or fully implemented ISeq from scratch. I also didn't have a project going, and this ended up being a lot of fun. \$\endgroup\$ – Carcigenicate May 31 '18 at 20:35
  • \$\begingroup\$ I had to implement a Heap priority queue once, that was also a good exercise. en.wikipedia.org/wiki/Binary_heap \$\endgroup\$ – Alan Thompson May 31 '18 at 22:36
  • \$\begingroup\$ @AlanThompson I was thinking about trying that. I ended up starting to write a BST implementation for kicks. I think I'm going to just try making a bunch of structures. \$\endgroup\$ – Carcigenicate Jun 1 '18 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.