Dictionaries, sets, and others

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

Dictionaries

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

Let us look at a simple datatype to hold a user's credentials: ID, password, e-mail, and so on. We will not include a username as this will be the key to a credential datatype. In practice this would not be a great idea, as users often forget their usernames as well as their passwords!

To implement this we use a simple module. This includes a type and some functions which operate on that type. Note the inclusion of the export statement which makes the type UserCreds and the functions visible.

moduleAuth

typeUserCreds
   uid::Int
   password::ASCIIString
  fullname::ASCIIString
  email::ASCIIString
  admin::Bool
end

function matchPwds(_mc::Dict{ASCIIString,UserCreds}, _name::ASCIIString, _pwd::ASCIIString)
    return (_mc[_name].password == base64(_pwd) ? true : false)
end

isAdmin(_mc::Dict{ASCIIString,UserCreds}, _name::ASCIIString) = _mc[_name].admin;
exportUserCreds, matchPwds, isAdmin;

end

We can use this to create an empty authentication array (AA) and add an entry for myself. We will be discussing security and encryption later, so at present we'll just use the base64() function to scramble the password:

julia> using Auth
julia> AA = Dict{ASCIIString,UserCreds}();
julia> AA["malcolm"] = UserCreds(101,base64("Pa55word"),"Malcolm Sherrington","malcolm@myemail.org",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 default constructor UserCreds() 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.

The using Auth statement looks for auth.jl in directories on the LOAD_PATH but will also include the current directory. On a Linux system where v"0.3" is installed on /opt typically would be:

julia>println(LOAD_PATH)
Union(UTF8String,ASCIIString)
["/opt/julia//usr/local/share/julia/site/v0.3","/opt/julia/usr/share/julia/site/v0.3"]

We can add to the LOAD_PATH with push!:

Julia>push!(LOAD_PATH, "/home/malcolm/jlmodules); # => if we add this statement to the startup file .juliarc.jlit will happen whenever Julia starts up.

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

julia> BB = ["malcolm" =>UserCreds(101,base64("Pa55word"),
"Malcolm Sherrington","malcolm@myemail.org",true)];

So the values can be referenced via the key:

julia> me = BB["malcolm"]
UserCreds(101,"UGE1NXdvcmQ=",
"Malcolm Sherrington","malcolm@myemail.org",true)

The . notation is used to reference the fields:

julia>me.fullname # => "Malcolm Sherrington"

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

Attempting to retrieve a value with a key 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 the try / catch / finally syntax.

So the isAdmin function in auth.jl could be rewritten as:

function isAdmin2(_mc::Dict{ASCIIString,UserCreds}, _name::ASCIIString)
    check_admin::Bool = false;
    try
        check_admin = _mc[_name].admin
    catch
        check_admin = false
    finally
        return check_admin
   end
end

Sets

A set is a collection of distinct objects and the "Bulls and Cows" example earlier could have been implemented using sets rather than strings. Julia implements its support for sets in Base.Set (file: set.jl) and the underlying data structure is an associative array.

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

julia> S0 = Set(); # => Set{Any}()
julia> S1 = Set(1,2,4,2); # => Set{Int64}(4,2,1)

Elements can be added to a set using the push!() function; recall ! implies that the data structure is altered:

julia> push!(S0,"Malcolm"); push!(S0,21); # => Set{Any}("Malcolm",21)
julia> push!(S1,"Malcolm"); # =>MethodError(convert,(Int64,"Malcolm") , since set elements need to be type {Int64}

The usual set operations apply such as union, intersection, difference (setdiff()) and complement. It is possible to test for subset, note that:

julia> S0 = Set(1.0,2.5,4.0); S1 = Set(1.0); issubset(S1,S0) # => true
julia> S0 = Set(1.0,2.5,4.0); S1 = Set(1); issubset(S1,S0) # => false

When dealing with integers there is a special type of set IntSet which produces an ordered set:

julia> K = IntSet(2,2,3,1,5,13,7,3,11) # =>IntSet(1, 2, 3, 5, 7, 11, 13)

Normal sets of type {Int} can be mixed with an {IntSet} and the result is a regular set not an IntSet:

julia> L = Set(3,1,11)
julia>setdiff(K,L) # => 5-element Array{Int64,1}: (2, 3, 7, 11, 13)

Other data structures

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

The Deque type is a double-ended queue with allows 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 FILO and FIFO access respectively. Deques expose the push!(), pop!(), shift!(), and unshift!() functions.

A stack will use push!() and pop!() to add and retrieve data, a queue will use push!() and unshift!(). Queues encapsulate these processes as enqueue!() and dequeue!().

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

julia> usingDataStructures
julia> S = Stack(Char,100); # => Stack{Deque{Char}}(Deque [])
julia> Q = Queue(Char,100); # => Queue{Deque{Char}}(Deque [])
julia> greet = "Here's looking at you kid!";
julia> for i = 1:endof(greet)
 push!(S,greet[i]) enqueue!(Q,greet[i])end
julia> for i = 1:endof(greet) print(pop!(S)) end
!dikuoy ta gnikools'ereH
julia> for i = 1:endof(greet) print(dequeue!(Q)) end

Here's looking at you kid!