[Gambas-user] Data Structures like C++

[Bruce]

On Wed, 2012-05-23 at 17:19 +0200, tobi wrote:
> On Thu, 24 May 2012, Bruce wrote:
> > On Mon, 2012-05-21 at 22:25 +0200, Benoît Minisini wrote:
> > 
> > > * Tree
> > > * Graph
> > > 
> > > Native implementation of that would be interesting.
> > > 
> > > Any volunteer? :-)
> > > 
> > I think trees are easily implemented directly in gambas using Emil's
> > suggestions regarding object references as a general n-tree can be
> > implemented as a B-tree using something like
> >  
> >     Class CNode
> >         public data as Variant
> >         public left as CNode
> >         public right as CNode
> >     Public Sub PreOrder() as Variant[]
> >         blah blah ... etc  according to Mr Knuth
> >     End
> > 
> > where "left" is the first child and "right" is the first sibling.  Read
> > Knuth Vol 3 for the truth (I had to go searching through the attic to
> > find my copy.)
> > 
> >         Now Graphs are   M U C H   more interesting!  
> >         
> >         Someone said that they couldn't think of a use for them.  Well
> >         here's one, UML diagrams are all directed graphs. In fact much
> >         of OO thinking is actually (mathematically) directed graphs.
> >         Nodes and edges. From use cases through structural models,
> >         component models, in fact the whole she-bang.
> > 
> > 
> > Getting back to trees. The funny thing is that I had a real need to
> > construct a n-tree this week to solve a problem I had with populating a
> > gambas treeview from a persistence store where the nodes where out of
> > order, i.e. the parents were later in the storage than the children (the
> > code is a hack and I choose not to share it.)  Suffice to say that
> > Demosthenes original post prompted me to go searching through the attic.
> > 
> > .. found some interesting stuff, by the way .. (No, lets not go there.)
> > 
> > Getting back to the point, I think a gb.datastructures component is an
> > excellent idea.  I can't help much on the dev side as I'm pretty poor at
> > C/C++ (can "read only") and am totally lost with Benoit's macros but I'd
> > be willing to put in much effort at testing and proving. Ah! Linked
> > lists, how many times have I needed them and built them from scratch.
> > 
> > Bruce
> > 
> > 
> > 
> > ------------------------------------------------------------------------------
> > Live Security Virtual Conference
> > Exclusive live event will cover all the ways today's security and 
> > threat landscape has changed and how IT managers can respond. Discussions 
> > will include endpoint security, mobile security and the latest in malware 
> > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> > _______________________________________________
> > Gambas-user mailing list
> > Gambas-user at lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/gambas-user
> 
> Hi,
> 
> so what syntax did you desire for an n-tree then? You presented a b-tree above, this appears generic
> to me... I certainly lack theory on those things.
> 
> But shouldn't it be less annoying to get to level 3 than "Root.left.left.left" ?
> There are a lot of purposes and designs of trees (graphs), right? To implement a certain idea would
> not be too difficult but instead to implement only one of those as a generic tree (graph) which is
> then able to be inherited and specialised, maybe in gambas, - that's what I find difficult (no
> wonder without theory).
> 
> Regards,
> Tobi
Hi Tobi,

I probably didn't make it clear.

"Any n-tree can be transformed into a b-tree where the left branch is
the first child and the right branch is the first sibling."  To be more
correct I should have said "Any k-ary tree can be represented as a
binary tree where the left branch is the first child and the right
branch is the next sibling".  The theory is in wikipedia here:
http://en.wikipedia.org/wiki/Binary_tree#Encoding_general_trees_as_binary_trees.

These binary trees have well known (Knuth and others) algrorithms for
different actions to be used on the binary tree, insertions, deletions,
(graft and prune), traversals in particular orders, searches, sorts etc
etc.

The application of a binary tree structure to suit a particular problem
is a different matter.  This is what you can use the tree for or how to
apply the tree "structure" to solve a particular problem.

In my case, which was a set of rows in a database containing a "data"
component and a "parent" value that I was trying to populate a treeview
with (1800 records) where the rows were out of order with respect to
building the treeview.  It was an n-level "table of contents" thing.

Rather than try to traverse the database several times and resolve
getting each toc level resolved, I just read the whole thing as a single
db.result and created a binary tree of the above type, creating dummy
parent nodes as soon as I had a need for them and setting their "data"
to a placebo value.  When I later located the real parent row in the
db.result iteration all I had to do was replace the placebo value with
the nodes real data.

At the end of the db.result iteration, the treeview could be populated
via a pre-order traversal of that tree. Bingo.

Regarding your "root,left,left,left" annoyance.  No that is the way you
need to get to the first node at a particular level of the tree.  But
once you're there there is an algorithm for traversing the tree at that
level,  an in-order traverse.  In fact I could have used the in-order
traversal equally well to solve my problem.

What I am saying regarding "it would be nice to have" these things in a
gb.component is they could provide the structure and the fundamental
algorithms.  The application of those things to the problem at hand
still requires an understanding of how such structures and methods can
be used to solve that problem, but at least the underlying
infrastructure would be there.

Every time one of these problems pops up in my life I have to go find
which gambas project it was where I created the structures and
algorithms.  The trouble is I only ever do the minimum necessary in a
particular project.  So if, for problem "x" I reckon that a binary tree
in-order search is needed then which *^%$@ project did I use that last
in, etc. etc.  and then get wrapped up in the code for the tree itself
rather than its' application to the problem at hand.

I think that the binary tree structure only requires two classes, say
"bintree" and "bintreenode".  The bintree class contains the root node
and all the basic algorithms.  The bintreenode class is a dumb data and
reference holder. Unlike what I inferred in my first post it has no
algorithm methods, it is just a structure. 

I'd also hazard a guess that much of the code needed is already
somewhere in gambas hiding in the Collection indexing code, all it needs
is exposing!

Bruce