[Info-vax] DEC Basic and dynamic memory ?

[Dave Froble]

On 1/28/2022 8:33 PM, Arne Vajhøj wrote:
> On 1/28/2022 2:57 PM, Simon Clubley wrote:
>> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
>> a custom data structure in dynamic memory and then walk the tree
>> either depth-first or breadth-first ?
>>
>> I've had a quick look at the dynamic storage section of the DEC Basic user
>> manual, but I don't see how you link a set of nodes together into a tree.
>> However, as mentioned previously, I don't know DEC Basic and searching
>> for the word pointer didn't reveal anything appropriate, so I assume
>> it's another keyword I am not aware of.
>>
>> In addition, how easy is this to do if the nodes are not all of the
>> same record type, but have a common tag at the start of each record
>> to say what kind of record it actually is ? I see you have variant
>> records in DEC Basic. Do they also work in a dynamic memory based
>> tree structure ?
>
> Basic is different than C and Pascal. You do not call a dynamic
> allocation function and get back a machine address that you need
> to free later.
>
> But you can do a tree by using a dynamic sized array and indexes
> into that as "pointers".
>
> And Basic map dynamic is similar to C union.
>
> Example code (maybe not super elegant - either because
> it is not the right language for the task or because my Basic
> skills are very limited - but it seems to work):
>
> $ typ tree.bas
> record treenoderec
>    long v
>    long styp
>    string s = 512
>    long pnode
>    long lnode
>    long rnode
> end record
>
> declare integer constant STRING_TYP = 1
> declare integer constant INTEGER_TYP = 2
> declare integer constant DECIMAL_TYP = 3
> $ typ dyn.bas
> program dyn
>
> %include "tree.bas"
>
> external sub tree_insert(treenoderec dim(), long, long, long, string)
> external sub tree_print(treenoderec dim())
> external sub tree_dump(treenoderec dim(), long)
>
> declare long top
> declare long capacity
> top = 0
> capacity = 1
> dim treenoderec tree (1 to capacity)
> map (u) string sv = 512
> map dynamic (u) long iv
> map dynamic (u) decimal zv
>
> declare long i, j
>
> for i = 1 to 10
>     sv = "Nothing"
>     call tree_insert(tree(), top, rnd * 1000, STRING_TYP, sv)
>     if top = capacity then
>         gosub extend_tree_array
>     end if
> next i
> iv = 123
> call tree_insert(tree(), top, 499, INTEGER_TYP, sv)
> zv = 123.45
> call tree_insert(tree(), top, 501, DECIMAL_TYP, sv)
> call tree_dump(tree(), top)
> call tree_print(tree())
> exit program
>
> extend_tree_array:
> dim treenoderec temp(1 to capacity)
> for j = 1 to capacity
>     temp(j) = tree(j)
> next j
> capacity = 2 * capacity
> dim treenoderec tree (1 to capacity)
> for j = 1 to capacity / 2
>     tree(j) = temp(j)
> next j
> return
>
> end program
> !
> sub tree_update(treenoderec tree(), long top, long ix)
>
> %include "tree.bas"
>
> if tree(top)::v < tree(ix)::v then
>     if tree(ix)::lnode = 0 then
>         tree(ix)::lnode = top
>         tree(top)::pnode = ix
>     else
>         call tree_update(tree(), top, tree(ix)::lnode)
>     end if
> else
>     if tree(ix)::rnode = 0 then
>         tree(ix)::rnode = top
>         tree(top)::pnode = ix
>     else
>         call tree_update(tree(), top, tree(ix)::rnode)
>     end if
> end if
>
> end sub
> !
> sub tree_insert(treenoderec tree(), long top, long v, long styp, string s)
>
> %include "tree.bas"
>
> external sub tree_update(treenoderec dim(), long, long)
>
> declare long ix
>
> top = top + 1
> tree(top)::v = v
> tree(top)::styp = styp
> tree(top)::s = s
> tree(top)::lnode = 0
> tree(top)::rnode = 0
> if top = 1 then
>     tree(top)::pnode = 0
> else
>    call tree_update(tree(), top, 1)
> end if
>
> end sub
> !
> sub tree_print_part(treenoderec tree(), long ix)
>
> %include "tree.bas"
>
> map (u) string sv = 512
> map dynamic (u) long iv
> map dynamic (u) decimal zv
>
> if tree(ix)::lnode > 0 then
>     call tree_print_part(tree(), tree(ix)::lnode)
> end if
> sv = tree(ix)::s
> if tree(ix)::styp = STRING_TYP then
>     print tree(ix)::v, trm$(sv)
> end if
> if tree(ix)::styp = INTEGER_TYP then
>     print tree(ix)::v, iv
> end if
> if tree(ix)::styp = DECIMAL_TYP then
>     print tree(ix)::v, zv
> end if
> if tree(ix)::rnode > 0 then
>     call tree_print_part(tree(), tree(ix)::rnode)
> end if
>
> end sub
> !
> sub tree_print(treenoderec tree())
>
> %include "tree.bas"
>
> external sub tree_print_part(treenoderec dim(), long)
>
> call tree_print_part(tree(), 1)
>
> end sub
> !
> sub tree_dump(treenoderec tree(), long top)
>
> %include "tree.bas"
>
> declare long i
>
> for i = 1 to top
>     print i,tree(i)::v,tree(i)::styp,tree(i)::pnode,tree(i)::lnode,tree(i)::rnode
> next i
>
> end sub
> $ bas dyn
> $ lin dyn
> $ run dyn
>  1             763           1             0             2             3
>  2             179           1             1             0             5
>  3             902           1             1             4             0
>  4             889           1             3             7             0
>  5             387           1             2             8             6
>  6             475           1             5             0             9
>  7             882           1             4             0             0
>  8             185           1             5             0             10
>  9             638           1             6             11            0
>  10            269           1             8             0             0
>  11            499           2             9             0             12
>  12            501           3             11            0             0
>  179          Nothing
>  185          Nothing
>  269          Nothing
>  387          Nothing
>  475          Nothing
>  499           123
>  501           123.44
>  638          Nothing
>  763          Nothing
>  882          Nothing
>  889          Nothing
>  902          Nothing
>
> Arne
>

Arne, I have difficulty following your code examples.  Is it me, or you?

-- 
David Froble                       Tel: 724-529-0450
Dave Froble Enterprises, Inc.      E-Mail: davef at tsoft-inc.com
DFE Ultralights, Inc.
170 Grimplin Road
Vanderbilt, PA  15486