Dictionaries, sets, stacks, and queues

In addition to arrays, Julia supports associative arrays, sets, and many other data structures. In this section, we will introduce dictionaries, sets, and a couple of others.

Dictionaries

Associative arrays consist of collections of key-values pairs. In Julia, associative arrays are called dictionaries (dicts).

Let us look at a simple data type to hold user credentials: ID, password, email, and so on. We will not include a username as this will be the key to a credential data type. In practice, this would not be a great idea as users often forget their username as well as their password!

This includes a type (struct) and some functions that operate on that type, as follows:

using Base64
struct UserCreds
  uid::Int
  password::String
  fullname::String
  email::String
  admin::Bool
end
function matchPwds(
  uc::Dict{String,UserCreds}, uname::String, pwd::String)
  return (uc[uname].password == base64encode(pwd) ? true : false)
end
isAdmin(uc::Dict{String,UserCreds},fname::String) = uc[fname].admin;

We can use this to create an empty authentication array (AA) and add an entry for myself.

For now, we will just use the base64() function to scramble the password, although, in practice, a better coding scheme would be used:

julia> AA = Dict{String,UserCreds}();
julia> AA["malcolm"] = UserCreds(101,
          base64encode("Pa55word"),
          "Malcolm Sherrington",
          "[e-mail]", true)
julia> println(matchPwds(AA,"malcolm","Pa55word") ? "OK" : "No, 
sorry")
OK

Adding the user requires the scrambling of the password by the user; otherwise, matchPwds() will fail.

To overcome this, we can override the UserCreds() default constructor by adding an internal constructor inside the type definition—this is an exception to the rule that type definitions can’t contain functions, since clearly it does not conflict with the requirement for multiple dispatch.

An alternative way to define the dictionary is by adding some initial values.

The values can be referenced via the key, as follows:

julia> me = AA["malcolm"]
UserCreds(101, "UGE1NXdvcmQ=", "Malcolm Sherrington",
          "[e-mail]", true)

The '.' notation is used to reference the fields:

julia> me.fullname
"Malcolm Sherrington"

Alternatively, it is possible to iterate over all the keys:

julia> for who in keys(AA)
         println(AA[who].fullname)
       end
"Malcolm Sherrington"

Attempting to retrieve a value with a key that does not exist, such as AA["james"], will produce an error.

We need to trap this in the module routines such as matchPwds() and isAdmin() using try/catch/finally syntax, like so:

# isAdmin function could be rewritten as:
function isAdmin2(uc::Dict{String,UserCreds},uname::String)
  check_admin::Bool = false;
  try
    check_admin = uc[uname].admin
  catch
    check_admin = false
  finally
    return check_admin
  end
end
julia> isAdmin(AA,"james")
ERROR: KeyError: key "james" not found
julia> isAdmin2(AA,"james")
false

Sets

A set is a collection of distinct unordered objects.

The basic constructor creates a set with elements of type Any; supplying arguments will determine (restrict) the set type:

julia> S0 = Set()
Set{Any}()

Alternatively, we can create a set of specific types of elements by supplying a list, like so:

julia> S1 = Set([1,2,3,1])
Set([2, 3, 1])
julia> typeof(S1)
Set{Int64}
julia> S2 = Set([2,4,6])
Set([4, 2, 6])

The “usual” functions of union and intersection can be applied to S1 and S2, as follows:

julia> S3 = union(S1, S2)
Set([4, 2, 3, 6, 1])
julia> S4 = intersect(S1, S2)
Set([2])

We can check whether one set is a subset of a second by executing the following code:

julia> issubset(S3,S4)
false
julia> issubset(S4,S3)
true

Elements can be added to a set using the push!() function.

Recall that ! implies that the data structure is altered, even though it is constructed as immutable:

# This works
julia> push!(S0,"Malcolm")
Set(Any["Malcolm"])
# But this does NOT
julia> push!(S1,"Malcolm")
ERROR: MethodError: Cannot `convert` an object of type String to an 
object of type Int64

It is possible to push mixed data types onto the S0 set, as this was defined as the Any type:

julia> push!(S0,21)
Set{Any} with 2 elements:
  "Malcolm"
  21

Because the set has no duplicate items, repeated ones are removed, and notice the order in the set is not the same as that in the list:

julia> S4 = Set([1, 1, 2, 3, 3, 5, 8])
Set{Int64} with 5 elements:
  5
  2
  8
  3
  1
julia> pop!(S4)
5

The pop()! function works on a Set but the order in which items are returned is random, corresponding to the arbitrary order created when the set was created.

Stacks and queues

The DataStructures package implements a rich bag of data structures, including deques, queues, stacks, heaps, ordered sets, linked lists, digital trees, and so on.

For a full discussion of ALL of these, see the following URL: https://github.com/JuliaCollections.

As an illustration, let’s look at the stack and deque data structures.

This is a double-ended queues that allows the insertion and removal of elements at both ends of a sequence.

The Stack and Queue types are based on the Deque type and provide interfaces for first in, last out (FILO) and first in, first out (FIFO) access respectively. Deques expose push!(), pop!(), shift!(), and unshift!() functions.

Consider the following simple example to illustrate using stacks and queues:

julia> using DataStructures
julia> S = Stack{Char}(100); typeof(S)
Stack{Char}
julia> Q = Queue{Char}(100); typeof(Q)
Queue{Char}

A stack will use push!() and pop!() to add and retrieve data, while a queue will use shift!() and unshift!().

Queues also encapsulate the latter two processes as enqueue!() and dequeue!().

Stacks are FILOs, while queues are FIFOs, as the following code snippet demonstrates:

julia> greet = "Here's looking at you kid!";
julia> for i = 1:lastindex(greet)
         push!(S,greet[i])
         enqueue!(Q,greet[i])
       end
julia> for i = 1:lastindex(greet) print(pop!(S)) end
!dik uoy ta gnikool s'ereH
julia> for i = 1:lastindex(greet) print(dequeue!(Q)) end
Here's looking at you kid!