Re: [Sooc-devel] SMap Comments

[Mike R. <mik...@gm...>]

On Fri, Aug 1, 2008 at 12:56 AM, Daniel Reinish <sta...@gm...> wrote:
> Second: It's interesting that the node class is defined and
> implemented in the same files as the map class.  I actually didn't
> realize you could do that in sooc, but due to C's procedural nature,
> I guess that makes sense (and of course it's legal in other OO
> languages).

In fact, declaring multiple classes in one header is simple enough.
However, defining multiple classes in one implementation file is a
rather non-trivial aspect of Sooc.  When we went from

	s_class { ... };

to

	s_class (x,y) { ... };

there were *major* changes required to ensure that all the code in the
implementation would know what was the current class (I can't believe
it all actually *works*!).  But now, the bottom line for coding
classes is that after the first class implementation in a .c file, you
must do

	#undef	SCurrentType #define	SCurrentType TheSecondClass

before all subsequent class implementations (the #undef is technically
not necessary but it suppresses redefinition warnings).  It's ok, but
not required, to #define SCurrentType The FirstClass before the first
class implementation for consistency.

>  I suppose it was done this way because SBSTreeNode is integral to
>  the functionality of SMap.  It deserves pointing out, though, that
>  SBinaryNode, which is integral to the functionality of SLinkedList,
>  has its own file.  So this leads me to two questions: (1) Would
>  SBSTreeNode ever be useful to classes other than SMap, meaning
>  things might be more clear if it had its own file? (2) Could
>  SBSTreeNode have benefited from being a subclass of SBinaryNode (or
>  vice versa) since they do seem to share some ideas conceptually?

I was admittedly in a bit of a rush to code SMap.  As a result, I
didn't take much time to consider the design of SBSTreeNode.  However,
it is possible that it should be a subclass of SBinaryNode
(specifically, one with a "parent" pointer that runs back up the
tree).  I need to review SBinaryNode, but I think it does some memory
management stuff essential to the workings of SLinkedListIter.  Maybe
that functionality will come in handy for SMapIter at some point.

In any case, as the status of SBSTreeNode is not yet clear, I've moved
the whole thing into s-map.c so that it's not publicly exposed.  When
the design is settled, it can be refactored as necessary.

> Regarding the latter question, I see that the biggest difference
> regarding the way binary nodes and binary search tree nodes are
> linked in sooc is that SBinaryNode uses a public data member whereas
> SBSTreeNode uses a method that retrieves a private data member.
> Presumably the public data member is faster since it doesn't require
> whatever overhead occurs in calling a sooc method.  On the other
> hand, this might be an inconsistency, but I'm not sure.

I definitely think these things should be done in a consistent way.
In general, we are sticking to the get/set paradigm.  I can't think of
any reason to do SBSTreeNode differently, off the top of my head.

> Third: I see that data2 (I think) is what holds the actual data that
> is tied to the given key.  What does the plain "data" member do?  I
> was having some trouble following the code that uses it.

Because I wasn't sure how general SBSTreeNode should be, I tried to
make it "somewhat general".  In reality, it's map specific -- it needs
to have a key and some data.  As it stands, this thing should be
SMapNode, and data should be key, and data2 should be data.  It's a
little sloppy.

> On a related note, could you possibly explain in "laymen's terms"
> how your binary search tree and map implementation works?  I have a
> general idea from the code, but it would be helpful to get the full
> picture, so to speak.

An important feature of keys is that they are of types implementing
SComparable.  Given one and another, you can always tell if they are
equal, or if they are given in left-to-right order or right-to-left
order.  (So 1,2 would be left-to-right and 5,-3 would be
right-to-left.)

Start with the current node being the root node and with some given
key.  Compare the current node's key and the given key.  If they
match, you're there -- now you can get/set the corresponding data.  If
they are left-to-right order, run the same routine on root->right.  If
they are right-to-left order, run the same routine on root->left.
This is generally much faster than, for example, traversing a list
linearly in search of the key.  Anyway, for a node, node->left =
node->right = NULL at initialization.  This way you can find the
"leaves" in the tree.  If you are trying to add a new key and some
data, you can create a new node and affix it to an existing node's
left or right.

> Fourth: Related to the question above, I am unclear as to the
> purpose of the "up" member of SBSTreeNode.  From what I can tell,
> only "left" and "right" are used to build a map (which makes sense).
> I'm guessing "up" is intended for branching purposes.  The name
> SBSTreeNode implies that these nodes can be used to build a tree
> with multiple nodes attached to one root, rather than simply being a
> very fancy linear linked list.  SMap clearly is not intended to have
> this functionality, so it doesn't make use of the "up" link.  If my
> understanding is correct, might this be another reason for
> SBSTreeNode to be its own file, since it might be used by more
> complex collections later down the line?

The idea is that just as you can recursively descend into the tree,
you can recursively ascend it as well.  Nonetheless, I've begun to
think that only traversing functions, and not the structure itself,
would ever need to keep track of the path back "up".  I think I'll
remove that member.

> Fifth: How come set_up does not feature all the releasing and
> retaining that takes place in set_left and set_right?  Is this an
> oversight or intentional?  If intentional, could you explain the
> rationale?

In general, objects should not retain each other.  If they did, they
would become permanent!  Therefore, while a parent node should retain
its children, child nodes should not retain their parents.  This
probably won't matter though, since the "up" member will probably be
scrapped in the absence of a strong argument for "retaining" it ;)



Glad to see someone's poking around my code -- it helps keep me on my
toes!

Happy Soocing,

-Mike