[comp.sys.hp] HP Basic linked lists?

jeffp@phred.UUCP (02/18/87)

Does anyone out there have any clever ideas on how to get Basic 4.0
on series 200/300 machines to create and use linked lists?

I don't need to dynamically allocate and deallocate the records, but
would like to be able to have pointers associated with each one that
will point to the predecessor and successor.  In Pascal the list element
would be:

TYPE	link = ^list_element;
	datatype = {bunch of integers & booleans};

	list_element =	RECORD
			one_before : link; {points to element before this}
			data : datatype;
			one_after : link;  {points to next element}
			END;

The main goal is to be able to sort a bunch of such things in BASIC and be
able to store only as many as have been used (also in BASIC).

{seismo!nike!uw-beaver, ihnp4!allegra!fluke} !tikal!phred!jeffp {Jeff Parke}
Genie  : JEFFP
DELPHI : JEFFPARKE

baker@hpfcls.UUCP (02/20/87)

The obvious hack is to maintain  parallel  arrays of info (some strings,
some real, some integers.....)  and have one array which always contains
the index of the next record.  I suppose a "Head" variable  pointing the
first element would also be useful.  Records can then be sorted  without
moving data other than the "next" pointer.

Possibly more effcient (array  indexing time can add up) method might be
to implement the list  management  routines in Pascal on the 200/300 and
create a loadable binary that can be called from Basic.

Jim Baker
HP Ft. Collins Systems Division

rocky@hpfcms.UUCP (02/20/87)

> In Pascal the list element would be:

Have you considered using CSUBs (Compiled SUBroutines) ?  A CSUB is written
in the Pascal workstation environment, using Pascal and/or assembly.
The compiled module is processed by a utility which transforms it into
a LOADable BASIC subroutine.  Parameters can be passed, COM can be
accessed, etc.  There are also support routines for device and file IO
from the CSUB with BASIC revision 5.0.

I don't fully understand your requirements, but still suggest that you check out
the capability of CSUBs.

Rocky Craig
Hewlett-Packard, Fort Collins Colorado (the home of Rocky Mountain BASIC)
hplabs!hpfcla!rocky

gore@nucsrl.UUCP (02/23/87)

/ nucsrl:comp.sys.hp / jeffp@phred.UUCP (Jeff Parke) /  2:32 pm  Feb 18, 1987 /
> Does anyone out there have any clever ideas on how to get Basic 4.0
> on series 200/300 machines to create and use linked lists?
> 
> I don't need to dynamically allocate and deallocate the records, but
> would like to be able to have pointers associated with each one that
> will point to the predecessor and successor.

Have three parallel arrays (say, DATA, PREVIOUS, NEXT), with the following
semantics:

   For a link identified by index I:
	the data is stored in DATA(I)
	the index of the immediately preceeding link is stored in PREVIOUS(I)
	 "    "   "   "       "      following    "  "     "   "  NEXT(I)

Jacob Gore
Northwestern University, Computer Science Research Lab
{ihnp4,chinet}!nucsrl!gore

daver@hpsgpa.UUCP (02/23/87)

Back in the days when FORTRAN was the only alternative to COBOL and assembly
language we did linked lists by using three arrays, one for each pointer and
one for the data.  In (minimal) Basic you could define three arrays, D for 
the data, N for 'next_pointer' and P for 'previous_pointer' and step through
and array forward by:
                          J=N(J)
backward by:
			  J=P(J)
and add an element after element j by:
			  P(T)=J
			  N(T)=N(J)
			  D(T)=<data>
			  P(N(T))=T
			  N(J)=T
			  T=T+1
where T points to the first unused element in the arrays.  It would also be
simple to implement a second linked list of free elements in the array to 
provide efficient use of memory when elements are removed.

paull@hpcvck.UUCP (02/24/87)

If you decide to pursue a linked list implementation via CSUBs you
should be aware that the absolute address of objects in COM are subject
to relocation.  It would be unwise to keep POINTERs in your data
structures.  The offset of such pointers from the COM base address
will not change, but the base address (as reported from FIND_COM)
may.

steve@hpfcrj.UUCP (02/25/87)

) /:comp.sys.hp / jeffp@phred.UUCP (Jeff Parke) /  1:32 pm  Feb 18, 1987 /
) The main goal is to be able to sort a bunch of such things in BASIC and be
) able to store only as many as have been used (also in BASIC).
) ----------
	The usual way to do linked lists in BASIC is to have a two-dimensional
array, treat one dimension as addresses of records, with the fields across the
other dimension.  Since your data is all numeric, this should be no problem.
Thus:
     Array(Ptr,Next)    would be the link to the next record,
     Array(Ptr,Prev)      "   "   "   "   "   "  previous record, and
     Array(Ptr,Datum)     "   "   a typical data field.
If the Array was dimensioned, say, Array(1:1000,0:5) then you could use 0 as
a null pointer value (convenient since the Array would be initialized all
zeros).  Here you could have Next=0, Prev=1, and Datum=2 thru 5.
	However, since your data is all of one type (numeric), and in view of
the goal stated above, let me suggest an alternate approach.  This will work if
the main data values by which you plan to sort have a bound such that an
outlying value can be used to indicate unused records. If not, just add a field
to the array which acts as a flag for unused records.  Thus:
     Array(Index,Valid)    is the flag field, and
     Array(Index,Datum)    is a typical data field.
Assume we use 1 for 'in use' and 0 for 'not used'.  This allows you to sort the
data by using the
	MAT SORT Array(*,Valid) DES,(*,Key_data)
statement.  The first key forces all the unused records to the end, and the
second one sorts the valid data items according to the order of the Key_data
field.  The next step is to determine the amount of data in use.  I generally
do this with a simple loop, such as
	WHILE Array(Index,Valid)
	  Index=Index+1
	END WHILE
If it's possible to completely fill the array, you'll also want to check for
the maximum value of Index or use an ON ERROR to trap the subscript error at
the top.  A binary search could also be used.  Now that we know how much of
the array is in use, and since the sort statement has compacted the items to
the beginning,
	REDIM Array(1:Index-1,<other subscript range>)
will tell the system to ignore the unused entries.  For this to work, Index
must be the first subscript and <other subscript range> must not change.
	If you were able to use the sort key as a valid indicator as well, you
can just do
	OUTPUT @File;Array(*)
at this point.  If you have to use a separate field for a valid flag and don't
want to store it, there's always FOR-NEXT loops (don't need the REDIM in this
case, should be as fast as chasing down the linked lists).  Or, use two arrays,
one for the valid flag and one for the data items.  When you're ready to sort,
use
	MAT SORT Valid_flags DES TO Temp
then
	MAT REORDER Data_array BY Temp
This assumes Valid_flags and Temp are one-dimensional and Data_array is
subscripted as (Index,Data_field).  Now find the top by
	WHILE Valid_flags(Temp(Index))
	  Index=Index+1
	END WHILE
and do the
	REDIM Data_array(1:Index-1,<other subscript range>)
Since Data_array now has only valid data, just
	MAT SORT Data_array(*,Key_data).
And now you're ready for the
	OUTPUT @File;Data_array(*)
Hope this is some help.  		Regards,
        y-s-t---w   t-i			Steve Taylor
       /   / \   \ /   \		[hpfcla!steve-t]
      S-O-f   e-r-a     o-n
         \  /  \   \
          p     m-s r-e

<<Not an official statement of the Hewlett-Packard Company.>>

steve@hpfcrj.HP.COM (Steve Taylor) (03/03/87)

One additional note:  If you want to use MAT SORT to compact the data for
output, but wish to use linked lists for updating the data, you can combine
the two methods.  The main problem would be all the links becoming invalid
when the data is moved by the sort.  While it would be possible to fix-up the
links from the REORDER vector, it might be simpler to just put the array back
the way it was after the OUTPUT.  (I'll assume the pointers are in a separate
array and the primary sort field has a bound that can be used to flush unused
entries to the end.)
	First, MAT SORT Data_array <sort keys> TO R_vector
	then   MAT REORDER Data_array BY R_vector
Next determine the valid size, REDIM, OUTPUT, REDIM to original size, and now
to recover:    FOR I=1 TO Upper_bound
		 Restore_vector(R_vector(I))=I
	       NEXT I
	       MAT REORDER Data_array BY Restore_vector
and everything should be back where it was.  I'm assuming (also) that you'll
set up the links from scratch when you read the data back in from the file.
Good luck with your application.  	Regards,
        y-s-t---w   t-i			Steve Taylor
       /   / \   \ /   \		[hpfcla!steve-t]
      S-O-f   e-r-a     o-n
         \  /  \   \
          p     m-s r-e

<<Not an official statement of the Hewlett-Packard Company.>>