Bijections
A Bijection
data type for Julia.
A Dict
in Julia is not one-to-one. Two different keys might have the same value. A Bijection
data structure behaves just like a Dict
except it prevents assigning the same value to two different keys.
Getting Started
After using Bijections
we create a new Bijection
in one of the following ways:
b = Bijection()
: This gives a newBijection
in which the keys
and values are of Any
type.
b = Bijection{S,T}()
: This gives a newBijection
in which the keys are of typeS
and the values are of typeT
.b = Bijection(x,y)
: This gives a newBijection
in which the keys are typetypeof(x)
, the values are typetypeof(y)
and the key-value pair(x,y)
is inserted into theBijection
.b = Bijection(dict::AbstractDict{S, T})
: This gives a newBijection
in which the keys are typeS
, the values are typeT
and all key-value pairs indict
are inserted into theBijection
.b = Bijection(pair_list::Vector{Pair{S, T}})
: Create a newBijection
using a list of pairs.
Adding and Deleting Pairs
Once a Bijection
, b
, is created, we add a new key-value pair in the same manner as with a Dict
:
julia> b[1] = "hello"
"hello"
julia> b[2] = "bye"
"bye"
Notice, however, that if we add a new key with a value that already exists in the Bijection
an error ensues:
julia> b = Bijection{Int, String}()
Bijection Dict{Int64, String}()
julia> b[3] = "hello"
ERROR: One of x or y already in this Bijection
Likewise, if a key already has a value it cannot be changed by giving it a new value:
julia> b[1] = "ciao"
ERROR: One of x or y already in this Bijection
If we wish to change the value associated with a given key, the pair must first be deleted using delete!
:
julia> delete!(b,1)
Bijection Dict{Int64, String} with 1 entry:
2 => "bye"
julia> b[1] = "ciao"
"ciao"
Using a Bijection
To access a value associated with a given key, we use the same syntax as for a Dict
:
julia> b[1]
"ciao"
julia> b[2]
"bye"
If the key is not in the Bijection
an error is raised:
julia> b[3]
ERROR: KeyError: 3 not found
Since the values in a Bijection
must be distinct, we can give a value as an input and retrieve its associate key. The function inverse(b,y)
finds the value x
such that b[x]==y
. However, we provide the handy short cut b(y)
:
julia> b("bye")
2
julia> b("ciao")
1
Naturally, if the requested value is not in the Bijection
an error is raised:
julia> b("hello")
ERROR: KeyError: hello not found
Creating an Inverse Bijection
There are two functions that take a Bijection
and return a new Bijection
that is the functional inverse of the original: inv
and active_inv
.
Independent inverse: inv
Given a Bijection
b
, calling inv(b)
creates a new Bijection
that is the inverse of b
. The new Bijection
is completely independent of the original, b
. Changes to one do not affect the other:
julia> b = Bijection{Int,String}()
Bijection Dict{Int64, String}()
julia> b[1] = "alpha"
"alpha"
julia> b[2] = "beta"
"beta"
julia> bb = inv(b)
Bijection Dict{String, Int64} with 2 entries:
"alpha" => 1
"beta" => 2
julia> bb["alpha"]
1
julia> bb["alpha"]
1
julia> b[3] = "gamma"
"gamma"
julia> bb["gamma"]
ERROR: KeyError: key "gamma" not found
Active inverse: active_inv
The active_inv
function also creates an inverse Bijection
, but in this case the original and the inverse are actively tied together. That is, modification of one immediately affects the other. The two Bijection
s remain inverses no matter how either is modified.
julia> b = Bijection{Int,String}()
Bijection Dict{Int64, String}()
julia> b[1] = "alpha"
"alpha"
julia> b[2] = "beta"
"beta"
julia> bb = active_inv(b)
Bijection Dict{String, Int64} with 2 entries:
"alpha" => 1
"beta" => 2
julia> b[3] = "gamma"
"gamma"
julia> bb["gamma"]
3
Iteration
Bijection
s can be used in a for
statement just like Julia dictionaries:
julia> for (x,y) in b; println("$x --> $y"); end
2 --> beta
3 --> gamma
1 --> alpha
Inspection
Thinking of a Bijection
as a mapping between finite sets, we provide the functions domain
and image
. These return, respectively, the set of keys and the set of values of the Bijection
.
julia> domain(b)
Set(Any[2,1])
julia> image(b)
Set(Any["bye","ciao"])
The collect
function returns the Bijection
as an array of key-value pairs:
julia> collect(b)
2-element Array{Tuple{Any,Any},1}:
(2,"bye")
(1,"ciao")
The length
function returns the number of key-value pairs:
julia> length(b)
2
The isempty
function returns true
exactly when the Bijection
contains no pairs:
julia> isempty(b)
false
Composition
Given two Bijection
s a
and b
, their composition c = a*b
is a new Bijection
with the property that c[x] = a[b[x]]
for all x
in the domain of b
.
julia> a = Bijection{Int,Int}(); a[1] = 10; a[2] = 20;
julia> b = Bijection{String,Int}(); b["hi"] = 1; b["bye"] = 2;
julia> c = a * b;
julia> c["hi"]
10