Scala Priority Queue
This Scala class implements a flexible priority queue using a min-heap. The code is based on the Scala collection PriorityQueue.scala, but the advantage here is that all the operations are implemented so the min-heap paradigm stays true at all times. This means whatever operation you do on this priority queue the output will always keep / yield the elements of the queue ordered by priority, which is not the case in the default Scala implementation.
One of the main applications for this is to manage physical user queues. As such a few extra utility functions that you would not find in a regular priority queue implementation were thrown in for good measure (remove, getAllByPriority, etc).
The library has been released to Maven Central so you can use it by simply listing it as a dependency in your build.sbt:
"com.github.paulporu" %% "flexible-user-queue" % "1.2"
You can also have a look at this Play application for an example of how to use this priority queue in your own project.
Import the class in your code:
The following functions are now available.
val emptyQueue = new PriorityQueue[Int] // Returns true emptyQueue.isEmpty var queue = PriorityQueue(1) // Returns 1, queue remains unchanged queue.head // Returns 1, queue is now empty queue.dequeue() // Adds 3 to the queue queue += 3 // Adds the elements of the List to the queue while keeping the min priority of the heap, so now queue = PriorityQueue(1, 3, 12, 5) val elements = List(5,12,1) queue ++= elements // Returns the element with index 2 and deletes it from the queue queue.remove(2) // Returns a List containing all elements of the queue sorted ascendingly by priority queue.getAllByPriority() // Prints the queue as a String queue.toString() // Empties the queue queue.clear()
Scalatest was used in combination with the scoverage SBT plugin for unit testing. Scalastyle was used because it's always good to follow some guidelines. The Sonatype SBT plugin was used to release the library to the Maven Central repository.
Scoverage shows on the current version of this library (v1.2) a statement coverage of 89.16 % and a branch coverage of 78.57 %.