From: Greg Menke
Subject: Tree or Hash?
Date: 
Message-ID: <pv6seg11.fsf@erols.com>
I've been working on a little program which requires an index to a
relatively large array.  Essentially its, a btree where each node branches
to 2 child nodes, to a depth of 15 from a single root node.  It is
created dynamically as the program executes.

I was thinking of creating the index as a list, starting out as:

(nil nil)

add a node to the first branch:

((nil nil) nil)

then another:

((nil (nil nil)) nil)

etc..., so the index grows downwards.  My technique is to implement a
search function which recurses down the tree in accordance with a key,
and adds nodes as required to get to the bottom of the tree where the
final entry cooresponding to that key resides.  To create the nodes, I
use rplaca and rplacd to replace the appropriate 'nil's with a new list
'(nil nil) which represents a new node.  I traverse the tree by
passing the car/cadr of the "current" node to the next level of
recursion- so the rplaca/d always operate on a simple list: (nil nil)
which is contained in the caller's simple list, such as 
((nil nil) nil).

I've been running into trouble generating, (I think), a
circular list, causing the interpreter to go into an infinite loop
after just a couple additions.

Hopefully I explained this coherently.. as to my question, is the
rplaca/rplacd approach a "good" way to tack new parts onto a recursive
list structure?  I more than half suspect my code is the problem, but
I don't know enough about the nuances of conses yet to quite
understand whats happening.

I think a hash table will be a better approach for this, but I'm
curious about the list technique.

Thanks,

Gregm.
From: Hrvoje Niksic
Subject: Re: Tree or Hash?
Date: 
Message-ID: <87g17out1c.fsf@pc-hrvoje.srce.hr>
Greg Menke <ยทยทยท@erols.com> writes:

> I've been working on a little program which requires an index to a
> relatively large array.  Essentially its, a btree where each node
> branches to 2 child nodes, to a depth of 15 from a single root node.

By "btree" you mean "binary tree", not "balanced tree", right?

> It is created dynamically as the program executes.
> 
> I was thinking of creating the index as a list, starting out as:
> 
> (nil nil)

You will save a cons cell per tree node if you use a dotted pair
instead.  Then you would start out with:

    (nil . nil)

...and have (car node) be the left element, and (cdr node) the right
element (in your scheme the right element would be (cadr node)).  Then
you can define convenience functions that access the tree:

    (defun tree-left (node)
      (car node))

    (defun tree-right (node)
      (cdr node))

For additional clarity, you can define setf methods for modifying the
tree:

    (defsetf tree-left (x) (p) `(progn (rplaca ,x ,p) ,p))

    (defsetf tree-right (x) (p) `(progn (rplacd ,x ,p) ,p))

Now, (tree-left NODE) and (tree-right NODE) will access the NODE
elements, whereas (setf (tree-left NODE) VALUE) and
(setf (tree-right NODE) VALUE) will modify them destructively.

You can create a new node using `(cons nil nil)', but you can as well
define a function whose name will describe what you're doing.

> I've been running into trouble generating, (I think), a circular
> list, causing the interpreter to go into an infinite loop after just
> a couple additions.

Set *print-circle* to t.  This should help debugging the circular list 
problem.

> Hopefully I explained this coherently.. as to my question, is the
> rplaca/rplacd approach a "good" way to tack new parts onto a
> recursive list structure?

Yes, I think it is.