Trees in Julia

question

#1

Hi Guys!
I am new to Julia and am trying to learn by writing some code. So I was trying to implement a tree and get the sum of node of all the elements in the sub-tree given a particular node.
Selection_028
Here is my work:

struct element
    name::String
    data::Int64
    loe
end


F1 = element("F1", 1, nothing)
F2 = element("F2", 2, nothing)
F3 = element("F3", 3, nothing)
D4 = element("D4", 0, [F1, F2])
D5 = element("D5", 0, [F3])
D6 = element("D6", 0, [D4, D5])


function sum_data_loe(loe)
    if loe == nothing
        0
    else
        (length(loe)>1)?(sum_data_element(loe[1]) + sum_data_loe[2:end]):sum_data_element(loe[1])
    end
end


function sum_data_element(e)
    if e.data == 0
        sum_data_loe(e.loe)
    else
        e.data
    end
end


@test sum_data_element(F1) == 1 #Test Passed
@test sum_data_loe(nothing) == 0 #Test Passed
@test sum_data_element(D5) == 3 #Test Passed
@test sum_data_element(D4) == 3 #Failed
@test sum_data_element(D6) == 6 #Failed

Error:

Error During Test
Test threw an exception of type MethodError
Expression: sum_data_element(D4) == 3
MethodError: no method matching endof(::#sum_data_loe)
Closest candidates are:
endof(::SimpleVector) at essentials.jl:257
endof(::Char) at char.jl:18
endof(::String) at strings/string.jl:153

Stacktrace:
[1] sum_data_loe(::Array{element,1}) at ./In[9]:5
[2] sum_data_element(::element) at ./In[10]:3
[3] include_string(::String, ::String) at ./loading.jl:522
[4] execute_request(::ZMQ.Socket, ::IJulia.Msg) at /home/subhankar/.julia/v0.6/IJulia/src/execute_request.jl:158
[5] (::Compat.#inner#18{Array{Any,1},IJulia.#execute_request,Tuple{ZMQ.Socket,IJulia.Msg}})() at /home/subhankar/.julia/v0.6/Compat/src/Compat.jl:378
[6] eventloop(::ZMQ.Socket) at /home/subhankar/.julia/v0.6/IJulia/src/eventloop.jl:8
[7] (::IJulia.##14#17)() at ./task.jl:335
There was an error during testing
Stacktrace:
[1] record(::Base.Test.FallbackTestSet, ::Base.Test.Error) at ./test.jl:533
[2] do_test(::Base.Test.Threw, ::Expr) at ./test.jl:352


#2

It looks like you tried to index into a function in the else part of sum_data_loe. All of the tests pass for me if I replace sum_data_loe[2:end] with sum_data_loe(loe[2:end])).


#3

Thanks a lot!!!


#4

A bit nitpicking maybe, but element is a type and should begin with a capital letter. See here for the conventions: https://docs.julialang.org/en/latest/manual/variables/#Stylistic-Conventions-1. Of course you are free to do what you want :wink:

[Edit]: ah, and the variables F1, F2, … D6 should be in lower case, i.e. f1, f2, … d6.


#5

As you might know already, there are Julia packages for data structures such as
https://github.com/Keno/AbstractTrees.jl https://github.com/JuliaCollections/DataStructures.jl

Try this in Julia 0.7

struct Element
    name::String
    data::Int64
    loe
end

F1 = Element("F1", 1, nothing)
F2 = Element("F2", 2, nothing)
F3 = Element("F3", 3, nothing)
D4 = Element("D4", 0, [F1, F2])
D5 = Element("D5", 0, [F3])
D6 = Element("D6", 0, [D4, D5])


import AbstractTrees: children, printnode, print_tree, Leaves
children(el::Element) = something(el.loe, [])

sum_data_element(el::Element) = sum(map(x->x.data, Leaves(el)))

using Test
@test sum_data_element(F1) == 1
@test sum_data_element(D5) == 3
@test sum_data_element(D4) == 3
@test sum_data_element(D6) == 6


printnode(io::IO, el::Element) = print(io, el.name, ' ', el.data)
print_tree(D6)