SortedQueue in Ruby

I've started working on the solver class for my ES project. I'm essentially implementing Dijkstra's algorithm where the graph nodes are the different board states and the edges are the turns. It's a little different as I'm generating the graph while traversing it instead of starting with a known graph.

One of the data structures required for implementing Dijkstra's algo is a priority queue. A strict priority queue won't quite work for me, as that requires numeric values for the priority, which I don't have. Instead I've defined a compare function for my nodes and want the queue to simply be sorted based on that.



Sadly Ruby doesn't have any built-in data structures for this. Arrays can be sorted and I could use that, but it would be incredibly inefficient as I would have to re-sort before every pop.

Thanks to the suggestion of jspcal on stackoverflow I found a couple libraries that implement sorted trees (Red-Black trees to be specific). Building a sorted queue on top of this was fairly easy.

Here's what I have so far. Eventually this will be checked into my github repository for ES, but for now I've posted the class as a gist, embedded below for convenience (I think I might have to switch to gists for all code embedding in my blog):



The only requirement for using the sorted queue is that the objects are Comparable.

---

Sorted queue based off of a red-black tree for Ruby.