[Info-vax] DEC Basic and dynamic memory ?

[Arne Vajhøj]

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