Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uunet!willett!ForthNet
From: ForthNet@willett.UUCP (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: Data Structures
Message-ID: <676.UUL1.3#5129@willett.UUCP>
Date: 19 Mar 90 02:52:29 GMT
Organization: Latest link in the ForthNet chain.  (Pgh, PA)
Lines: 48


 Date: 03-15-90 (04:41)              Number: 3038 (Echo)
   To: ALL                           Refer#: NONE
 From: JONAH THOMAS                    Read: (N/A)
 Subj: B-TREES                       Status: PUBLIC MESSAGE

    This is simpler than the recursive form to put together, but it
 takes more typing to actually make the tree.  What the recursive
 defining words give you is the chance to take all those 'subs' out of
 the tree set-up.  But then you can only use the tree words with
 specialized tree-reading words, in post-fix notation.  I haven't
 actually used it all enough to see whether this is a disadvantage.
    The B-Tree was almost as easy:

 : B-SIDE 2 + ;
 : B-DOWN 4 + ;
 : B-LINK-UP ( here addr | here 0  -- ) 
           DUP IF   B-DOWN DUP @ , !   ELSE  , DROP   THEN ;
 : SUBS ( addr -- ) CREATE HERE SWAP DUP , B-LINK-UP 0 , ;

    Three fields, the 1st looks back, the 2nd looks sideways, and the 3rd
 looks forward.  B-LINK-UP copies the parent's down-address into the
 child's side-address, and the child's address into the parent's
 down-address, so the 1st child defined (the last one in the list) at
 each level has a 0 in its side-address.

 VARIABLE B-LEVEL ( used for indenting while printing )
 : SAME-LEVEL 2 + @ ;
 : DOWN-ONE   4 + @ ;
 : .TREE ( addr -- ) RECURSIVE   CR B-LEVEL @ SPACES DUP .NAMER DUP
     DOWN-ONE ?DUP IF  1 B-LEVEL +!  .TREE   -1 B-LEVEL +!  THEN
     SAME-LEVEL ?DUP   IF .TREE THEN ;

     A non-recursive form of .TREE was more complicated because it had to
 keep track of what it was doing, and know when to quit.  Recursion does
 all that on the return stack automatically.  
     Recursive defining words ought to be really useful, but they don't
 look that useful to me yet.  Maybe with some special state variables, so
 they're part-time recursive defining words.  But it looks really
 complicated.

 ---
  * Via ProDoor 3.1 

 NET/Mail : The MATRIX (5 Nodes/1.2 Gig) Birmingham, AL (205) 323-2016  
-----
This message came from GEnie via willett through a semi-automated process.
Report problems to: 'uunet!willett!dwp' or 'willett!dwp@gateway.sei.cmu.edu'