Visualizing Bubble Sort

So I finally finished my rubbish sort visualization. It was more about learning a bit of Clojure interacting with Swing.

The code certainly isn't the prettiest, but it is very concise compared how it'd look in Java. The canvas does the drawing, using proxy to provide implementations of the paintComponent and listen to tick events from the timer.

The bubble-sort function returns a list which represents each intermediate stage of the bubble sort algorithm (well, it's not quite perfect as it includes all the swaps, not one at a time).

An atom is used to represent the mutable state (in this case, a counter which moves between 0 and the number of items in the list).

The full code is available in my Git repository here.

Mutants!

Part of the rationale of Clojure is to get rid of free-for-all mutation: "for the concurrent programming future, pervasive, unmoderated mutation simply has to go."

Atoms are a way of performing mutation in a safe way, free from any potential race conditions.

An atom is associated with a Clojure value, in this case an integer.

  (def position (atom 0))

If you want to observe the value, use deref or the @ notation.

  user> (prn @position)
  0
  nil
  user> (prn position)
  #
  nil
  user> (prn (deref position))
  0
  nil

So how do you actually change the value inside the atom? swap! and compare-and-set! change the values of atoms. Both have the ! (bang) suffix to indicate that they are destructive operations.

swap! takes two arguments, the atom itself and a function to apply to the value and swap with the current value of the atom. For example:

  user> (swap! position inc)
  1
  user> (swap! position inc)
  2

compare-and-set! (CAS)is a lower level function which sets the value of an atom given the original value and the new. The value is only changed if it is observed first to be equal to the original value. A Boolean return value indicates whether the atom was changed.

  user> (swap! position (fn [x] 0))
  0
  user> (compare-and-set! position 0 1)
  true
  user> (compare-and-set! position 0 2)
  false

I'll use atoms to change state when animating my little sorting visualization.

Clojure short-hand

After reading through some Clojure code and talking to people on IRC, I found a few ways of making code a bit more concise.

#(+ %1 %2) is short hand for (fn [x y] (+ x y)). For example, this is valid:

  user> (map #(+ %1 %2) (range 0 4 ) (range 0 4))
  (0 2 4 6)

Documentation for this is squirreled away on the Clojure Reader page.

Another useful function I didn't know was into which allows you to create a new data structure from an existing one. When you create literal sets, the reader creates hash types (i.e. unordered).

  user> #{1 2 3 4 5 6 7 98 100}
  #{1 2 98 3 4 100 5 6 7} ;; look the ordering has changed.

Using into, I can change that:

  user> (into (sorted-set) #{1 2 3 4 5 6 7 98 100})
  #{1 2 3 4 5 6 7 98 100}

Going back to my sort app, based on the Snake game code previously mentioned, it seems to get a drawing panel I should subclass a JPanel and override the paint method to get a canvas to draw on.

(def maxval 100)

(def model (take 100 (repeatedly (fn [] (rand-int maxval)))))

(def canvas (proxy [JPanel ActionListener] []
  (paintComponent [g]
    (proxy-super paintComponent g)
    (.setColor g Color/RED)
    (let [width (.getWidth this) height (.getHeight this) barHeight (/ height (inc (count model))) barWidthPerVal (/ width maxval)]
      (prn width height)
      (doseq [val (into (sorted-map) (zipmap (range 0 (count model)) model))] 
 (let [y (int (* (first val) barHeight)) barWidth (int (* (second val) barWidthPerVal))]
   (.fillRect g 0 y barWidth barHeight)))))
  (actionPerformed [e] (prn "Doing something"))))

this is still a keyword in Clojure, which is something that took me a while to work out, I guess I was hoping that I could do (.getHeight) and the this would be explicit?

proxy (as I've briefly mentioned before) allows you to override methods and implement interfaces. In this case I've overridden the painComponent method of JPanel and replaced it with some gubbins to draw the list I'm trying to sort.

I've also overridden the actionPerformed method which is where I'll mutate the model with one iteration of the chosen sort method. I've decided (again based on the Snake Clojure code) to use a Swing Timer to fire events to signal when to redraw.

On a side note, encapsulating an object behind functions is nice and simple. In the style of SICP we use a local let expression to hide x from the outside world.

(let [x (Timer. 1000 canvas)]
  (defn stop-timer [] (.stop x))
  (defn start-timer [] (.start x))
  (defn is-running [] (.isRunning x)))

Now all I need to write in my daft demo app is a way of generating all the intermediate steps for sorting algorithms. For my implementation of bubble-sort this is simple (it generates a list of the intermediate bits and pieces), but for quick sort it's little bit harder.