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.>>