Programming Praxis: Cyclic Sorted List

Today's problem is to insert an element into the correct place in a cyclic sorted list. A cyclic sorted list is an ordered list whose last element points to the first element. One thing to keep in mind is that you may be given any node in the list to start with. The problem doesn't say it but I'm going to assume that this list is singly linked.

The first thing I need to figure out is how to represent a cyclic sorted list in Clojure. I've decided to represent the list as a series of nodes. Each node is an atom that points to a two element vector. The first element is the value of the node and the second element is a function that returns the next node. I tried to make the second element an atom but this gave me a stack overflow error.

After that I just need functions to find the insert spot and to insert the value.

;;cyclic list insertion

(def start-node (atom [1 (fn [] start-node)]))

(defn insert-after [node val]
  (let [new-node (atom [val (last @node)])]
    (swap! node (fn [n] [(first n) (fn [] new-node)])))) 

(defn find-insert-spot [node val]
  (loop [cnode node
         ctr 0]
    (let [next-node ((last @cnode))
          cval (first @cnode)
          nval (first @next-node)]
      (if (= next-node node)
        cnode
        (if (or (<= cval val nval)
                (and (> cval nval) (or (>= val cval)
                                       (<= val nval))))
          cnode
          (recur next-node (inc ctr)))))))

(defn insert-val [node val]
  (insert-after (find-insert-spot node val) val))

(defn get-nth-after [start cnt]
  (loop [cnode start i cnt]
    (if (= i 0)
      cnode
      (recur ((last @cnode)) (dec i)))))

(defn ring-vals [start]
  (loop [cnode start
         acc []]
    (let [next-node ((last @cnode))
          cval (first @cnode)]
      (if (= next-node start)
        (conj acc cval)
        (recur next-node (conj acc cval))))))

gist