Although Julia has integrated support for various data structures (arrays, tuples, dictionaries, sets), it doesn’t exhaust the full gamut of options. More exotic structures (like queues and deques, stacks, counters, heaps, tries and variations on sets and dictionaries) are implemented in the DataStructures package.
As always we start by loading the required package.
julia> using DataStructures
I won’t attempt to illustrate all structures offered by the package (that would make for an absurdly dull post), but focus instead on queues and counters. The remaining types are self-explanatory and well illustrated in the package documentation.
Queue
Let’s start off with a queue. The data type being queued must be specified at instantiation. We’ll make a queue which can hold items of Any type. Can’t get more general than that.
queue = Queue(Any);
The rules of a queue are such that new items are always added to the back. Adding items is done with enqueue!().
enqueue!(queue, "First in.");
for n in [2:4]; enqueue!(queue, n); end
enqueue!(queue, "Last in.")
Queue{Deque{Any}}(Deque [{"First in.",2,3,4,"Last in."}])
length(queue)
5
The queue now holds five items. We can take a look at the items at the front and back of the queue using front() and back(). Note that indexing does not work on a queue (that would violate the principles of queuing!).
front(queue)
"First in."
back(queue)
"Last in."
Finally we can remove items from the front of the queue using dequeue!(). The queue implements FIFO.
dequeue!(queue)
"First in."
Counter
The counter() function returns an Accumulator object, which is used to assemble item counts.
cnt = counter(ASCIIString)
Accumulator{ASCIIString,Int64}(Dict{ASCIIString,Int64}())
Using a Noah’s Ark example we’ll count the instances of different types of domestic animals.
push!(cnt, "dog") # Add 1 dog
1
push!(cnt, "cat", 3) # Add 3 cats
3
push!(cnt, "cat") # Add another cat (returns current count)
4
push!(cnt, "mouse", 5) # Add 5 mice
5
Let’s see what the counter looks like now.
cnt
Accumulator{ASCIIString,Int64}(["mouse"=>5,"cat"=>4,"dog"=>1])
We can return (and remove) the count for a particular item using pop!().
pop!(cnt, "cat")
4
cnt["cat"] # How many cats do we have now? All gone.
0
And simply accessing the count for an item is done using [] indexing notation.
cnt["mouse"] # But we still have a handful of mice.
5
I’ve just finished reading through the second early access version of Julia in Action by Chris von Csefalvay. In the chapter on Strings the author present a nice example in which he counts the times each character speaks in Shakespeare’s Hamlet. I couldn’t help but think that this would’ve been even more elegant using an Accumulator.
Tomorrow we’ll take a look at an extremely useful data structure: a graph. Until then, feel free to check out the full code for today on GitHub.
