OpenEuphoria

2. Re: dynamic allocation

• Posted by Jeffrey Fielding <JJProg at CYBERBURY.NET> Dec 24, 2000
• 358 views

On Sun, 24 Dec 2000, George Henry wrote:

> Dynamic allocation and pointers may be the only way to go to meet my current
> needs.
>
> Perhaps what Tone Koda mean when he wrote that sequences aren't flexible
> enough, is that they aren't dynamic enough for a lot of applications. As I
> just pointed out (prev. msg.), there is no decent way to access and modify
> deeply nested data and structures. (Is there?)
>
> Maybe all that's needed is an attitude adjustment. At first I thought, "Oh
> great, here is a language that lets you avoid pointers," but if that's not
> entirely true, so what? I worked with dynamic allocation and pointers pretty
> effectively for quite a few years, and am willing to do so again, if that's
> what it takes to get the job done.
>
> George
> _________________________________________________________________
> Get your FREE download of MSN Explorer at http://explorer.msn.com
>

It is possible to implement a tree with nested sequences - you just have
to use a recursive function to dynamically change a node. It's probably
much faster to emulate pointers with indices into a sequence. Here's a set
of tree routines I wrote for my pre-processor that uses such a method.

Jeff Fielding

-- Tree.e 1.0 by Jeffrey Fielding (JJProg at cyberbury.net)
sequence nodes
constant NODE_DATA = 1,
         NODE_PARENT = 2,
         NODE_CHILDREN = 3
global constant ROOT_NODE = 0
nodes = {}
global type tree_node(object x)
    if integer(x) then
        if x > ROOT_NODE then
            return x <= length(nodes) and sequence(nodes[x])
        else
            return x = ROOT_NODE
        end if
    end if
    return 0
end type
type tree_subnode(object x)
    if integer(x) then
        return x > 0 and x <= length(nodes) and sequence(nodes[x])
    end if
    return 0
end type
procedure disown_node(tree_node parent, tree_subnode node)
    integer i
    sequence s
    if parent then
        s = nodes[parent][NODE_CHILDREN]
        i = find(node,s)
        if i then
            nodes[parent][NODE_CHILDREN] = s[1..i-1] & s[i+1..length(s)]
        end if
    end if
end procedure
global procedure own_node(tree_node parent, tree_subnode node)
    disown_node(nodes[node][NODE_PARENT],node)
    nodes[node][NODE_PARENT] = parent
    if parent then
        nodes[parent][NODE_CHILDREN] &= node
    end if
end procedure
global function alloc_node(tree_node parent)
    integer i
    i = find(-1,nodes)
    if i then
        nodes[i] = {0,0,{}}
        own_node(parent,i)
        return i
    else
        nodes = append(nodes,{0,0,{}})
        own_node(parent,length(nodes))
        return length(nodes)
    end if
end function
global procedure free_node(tree_subnode node)
    while length(nodes[node][NODE_CHILDREN]) do
        free_node(nodes[node][NODE_CHILDREN][1])
    end while
    disown_node(nodes[node][NODE_PARENT],node)
    nodes[node] = -1
end procedure
global function parent_node(tree_subnode node)
    return nodes[node][NODE_PARENT]
end function
global function node_children(tree_subnode node)
    return nodes[node][NODE_CHILDREN]
end function
global function node_data(tree_subnode node)
    return nodes[node][NODE_DATA]
end function
global procedure node_set(tree_subnode node, object data)
    nodes[node][NODE_DATA] = data
end procedure
global function copy_tree(tree_subnode parent, tree_subnode node)
    tree_subnode new_node, t
    sequence s
    new_node = alloc_node(parent)
    node_set(new_node,node_data(node))
    s = node_children(node)
    for i = 1 to length(s) do
        t = copy_tree(new_node,s[i])
    end for
    return new_node
end function