Encoding Graphs

This tutorial show how to construct mappings for types that refer to themselves and can contain cycles. The mapping we will be focused on in this tutorial are standard.typeref which is located in the tier.standard submodule.

In the Encoding References tutorial we learned about reference mappings. Such mappings are the first part that is needed to encode tree and graph data structures that can contain cycles. The second thing that is needed is a way for mappings to be able to refer to either themselves or to have cross referencing between two or more structures. The standard.typeref mapping makes this self and cross referencing possible. The trick is to construct a mapping in two stages, first create a mapping with incomplete references, and then finalize that incomplete reference to be the desired type.

The case of constructing a type that refers to itself is practically a requirement when building trees or graphs and the api provides a special function for simplifying the process. The standard.selfref function.

API

local tier   = require"tier"
local standard  = tier.standard
local primitive = tier.primitive

local output = io.open("Graphs.dat", "wb")

--Creates a linked list mapping via the selfref method
local linked_list_mapping = standard.selfref(function(self_ref)
    return standard.object(standard.tuple
    {
        { key = "payload", mapping = primitive.double },
        { key = "next",    mapping = standard.optional(self_ref) }
    })
end)

--Creates an identical linked list mapping using the typeref api. 
local list_ref = standard.typeref()
local linked_list_mapping2 = standard.object(standard.tuple
{
   { key = "payload", mapping = primitive.double },
   { key = "next",    mapping = standard.optional(list_ref) }
})
list_ref:setref(linked_list_mapping2)

local linked_list = 
{
    payload = 2,
    next    = 
    {
        payload = 32,
        next = 
        {
            payload = 22
        }
    }
}

--Encodes a linked_list with the list mapping
tier.encode(output, linked_list, linked_list_mapping)
tier.encode(output, linked_list, linked_list_mapping2)

--We can also encode linked lists with references 
--Since we created them as reference mappings.
linked_list.next = linked_list
tier.encode(output, linked_list, linked_list_mapping)

--Creates a tree mapping
--A mapping where two of the sub mappings refer back to 
--the parent mapping.
local tree_node_mapping = standard.selfref(function(self_ref)
    return standard.tuple 
    {
        { key = "payload",   mapping = primitive.double },
        { key = "left",      mapping = standard.optional(self_ref) },
        { key = "right",     mapping = standard.optional(self_ref) }
    }
end)

--A simple tree mapping
local tree_mapping = standard.tuple
{
    { key = "num_nodes", mapping = primitive.varint },
    { key = "root",      mapping = tree_node_mapping }
}

local tree = 
{
   num_nodes = 5,
   root = 
   {
      payload = 3, 
      left = { payload = 2 },
      right = 
      {
          payload = 32,
          left = { payload = 65 },
          right = { payload = 22 }
      }
   } 
}

--Encode the tree
tier.encode(output, tree, tree_mapping)
output:close()

local input = io.open("Graphs.dat", "rb")
local list_a = tier.decode(input, list_mapping)
local list_b = tier.decode(input) --Dynamic decoding
local cyclic_list = tier.decode(input, list_mapping)
local tree_a = tier.decode(input, tree_mapping)
input:close()

Cross Reference Usage Examples

local tier  = require"tier"
local standard  = tier.standard
local primitive = tier.primitive

local bar_ref = standard.typeref()
local foo_mapping = standard.object(standard.tuple
{
   { key = "a_string", mapping = primitive.string }, 
   { key = "bar",      mapping = bar_ref }
})

local bar_mapping = standard.object(standard.tuple
{
   { key = "a_number", mapping = primitive.double },
   { key = "foo",      mapping = foo_mapping } 
})
bar_ref:setref(bar_mapping)

local output = io.open("CrossReferenceTypes.dat", "wb")

local foo = { a_string = "FizzBuzz" }
local bar = { a_number    = 52 , ["foo"] = foo }
foo.bar = bar

local tuple = standard.tuple 
{
    {mapping = foo_mapping},
    {mapping = bar_mapping}
}

tier.encode(output, {foo, bar}, tuple)
output:close()

local input = io.open("CrossReferenceTypes.dat", "rb")
local res     = tier.decode(input, tuple)
local foo_val = res[1]
local bar_val = res[2]

assert(foo_val == bar_val.foo)
assert(bar_val == foo_val.bar)

This marks the end of this tutorial and also the end of "The basics" tutorial series.