CVS difference for ai05s/ai05-0136-1.txt

Differences between 1.16 and version 1.17
Log of other versions for file ai05s/ai05-0136-1.txt

--- ai05s/ai05-0136-1.txt	2011/02/08 08:21:05	1.16
+++ ai05s/ai05-0136-1.txt	2011/04/09 06:04:38	1.17
@@ -3990,3 +3990,240 @@
 forcing copying everything at every step.
 
 ****************************************************************
+
+From: Martin Dowie
+Sent: Thursday, April  7, 2011  3:47 AM
+
+Am I right in thinking that it is up to the user of the tree to balance the
+children/siblings in the arrangement they want?
+
+If so, this seems to deminish the usefulness of this container (well, the
+unbounded form anyway).
+
+Would it be too late to add an operation:
+
+   procedure Balance (Container : in out Tree; N : in Count_Type);  -- N => 0, would do nothing
+
+?
+
+****************************************************************
+
+From: Simon Wright
+Sent: Thursday, April  7, 2011  5:31 PM
+
+The whole point of a multiway tree is to let the user store the
+children/siblings in the way they want. Balancing only applies to (binary) trees
+where you don't care about the internal representation, just the ordering.
+
+What would Balance do to a tree that held an XML document?
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, April  7, 2011  7:47 PM
+
+Right. The ways that I've used multiway trees in practice include things like
+the compiler symbol table, Ada expression trees, HTML/XML parse trees, MIME
+e-mail description (each section is a child of the whole), and the like. In all
+of these, the ordering of nodes is important, and equally importantly, there can
+be many siblings. (Think about the tree representing a subprogram call; the
+parameters are a sibling list, and it can be as long as necessary.)
+
+Balanced trees come up primarily for indexing applications; but here it is
+better to use the indexed containers (Maps and Sets) rather than raw
+roll-your-own trees. (The ordered map and set containers are exactly a wrapper
+around a balanced tree.) [I've never used a balanced tree in my code in 30 years
+of programming; the ordered map and set will be the very first time.]
+
+I don't even know what "Balance" would actually do; all of the algorithms I know
+of do that around keys of some sort, and the multiway tree has no such concept.
+
+If there is enough demand, it might make sense to define a separate balanced
+binary tree container, but I don't think it has all that much in common with the
+multiway tree. (Other than that you can use a multiway tree to create a binary
+tree; the reverse is obviously impossible.)
+
+****************************************************************
+
+From: Martin Dowie
+Sent: Friday, April  8, 2011  1:54 AM
+
+Even now, longer after my college days, my first port of call is often Wirth,
+'Algorithms + Data Structures = Programs'. In section 4.5 (of my dusty old
+volume) he describes such a balanced Multiway Tree. I see there is now a online
+.pdf version where this has moved to 4.7
+(http://www-old.oberon.ethz.ch/WirthPubl/AD.pdf).
+
+I just wanted to be clear on what the AI is specifying and I'm not claiming this
+would be useful for XML et al parsing. Adding a 'Balance' subprogram would be a
+simple method of adding the facility and gives the user the option to balance or
+not (and when to do it!). Maybe another package
+(Ada.Containers.Multiway_B_Trees) would be a more appropriate option.
+
+I have used such a tree once when we had (a lot of) pages of data on an external
+store and limited memory.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, April  8, 2011  2:37 AM
+
+...
+> Even now, longer after my college days, my first port of call is often
+> Wirth, 'Algorithms + Data Structures = Programs'. In section 4.5 (of
+> my dusty old volume) he describes such a balanced Multiway Tree.
+
+Funny. Wirth's book was my college data structures textbook. The edition we used
+(this was in 1978 or so) was so riddled with errors that no one could figure out
+how the examples were supposed to work. (This clearly was not helped by a rookie
+professor.) I didn't learn much in that class or from that book!! That's clear,
+because most of my old Computer Science textbooks are on the bookshelves here in
+the office, and that one is not -- it is either at home or in a landfill. (I
+believe that later versions were better, but of course, once burned by a
+product, you rarely try it again.)
+
+I learned more about data structures from Isaac's textbook when I was helping
+him with his homework (he was my roommate at the time, and he took the class
+about a year after I did) than I ever did from Wirth's book. Ike's textbook is
+still on the bookshelf here.
+
+Interestingly, it does not mention multiway trees at all (it has a lot of text
+on binary trees and B-Trees). I also checked several volumes of Knuth (our other
+main reference here), and I didn't find any references to that term there
+either.
+
+Which probably explains why I didn't even know the *name* of this data structure
+when I went to create this container. I had always called it a
+parent-child-sibling tree; I looked that up on the internet and found the term
+"multiway tree", which seemed like a much better name. Thus the container has
+it.
+
+In any case, it was designed to hold XML parses and expression trees, not to do
+anything where ordering is insignificant.
+
+> I see there is now a online .pdf
+> version where this has moved to 4.7
+> (http://www-old.oberon.ethz.ch/WirthPubl/AD.pdf).
+>
+> I just wanted to be clear on what the AI is specifying and I'm not
+> claiming this would be useful for XML et al parsing.
+> Adding a 'Balance' subprogram would be a simple method of adding the
+> facility and gives the user the option to balance or not (and when to
+> do it!). Maybe another package
+> (Ada.Containers.Multiway_B_Trees) would be a more appropriate option.
+
+I don't think defining "Balance" would be simple! We wouldn't want to require a
+particular algorithm, and I don't know how you could define it abstractly. And
+if we didn't require an algorithm, it's use probably would not be portable
+enough to use.
+
+Did you have some sort of definition in mind? You only showed a specification,
+and I have no idea what the second parameter is supposed to be for, for
+instance.
+
+> I have used such a tree once when we had (a lot of) pages of data on
+> an external store and limited memory.
+
+That sounds like the classic B-Tree and especially B+ Tree algorithms. They
+depended on fixed size pages (i.e. disk blocks); you only "rebalanced" (split)
+when the pages were full. Commonly used in database indexes in the 1980's.
+
+But those wouldn't make much sense for one of the abstract containers - there is
+no counterpart of the fixed size page. But I don't think that is what you were
+proposing anyway.
+
+The interesting thing is although I wrote a lot of code that put data structures
+on disk, I always kept the indexes in main memory -- so I never needed that kind
+of tree. (And usually those indexes where -- yup, you guessed it -- a multiway
+tree.)
+
+Anyway, I suspect that there are lots of niche data structures that could be
+defined, and probably more than a few that ought to be defined. Gotta have
+something to do for Ada 2020. :-)
+
+****************************************************************
+
+From: Jeff Cousins
+Sent: Friday, April  8, 2011  6:52 AM
+
+> That sounds like the classic B-Tree and especially B+ Tree algorithms.
+> They depended on fixed size pages (i.e. disk blocks); you only "rebalanced"
+> (split) when the pages were full. Commonly used in database indexes in the
+> 1980's.
+
+We still use B+ Trees massively in my part of BAE Systems, I'd kind of assumed
+that's what the new Container would use.  The fixed page size is not just useful
+for back up on hard disk but also for distribution via LAN packets (to both
+users of the data wanting their own copy for faster access, and to hot
+standbys).
+
+****************************************************************
+
+From: Martin Dowie
+Sent: Friday, April  8, 2011  8:17 AM
+
+Well, that was 2 of us wondering about that then. :-)
+
+I don't mind if this isn't what this container is going to do - I'm sure there
+are plenty uses for it - but perhaps it could be made clearer?
+
+****************************************************************
+
+From: Florian Weimer
+Sent: Friday, April  8, 2011  4:52 PM
+
+> Even now, longer after my college days, my first port of call is often
+> Wirth, 'Algorithms + Data Structures = Programs'. In section
+> 4.5 (of my dusty old volume) he describes such a balanced Multiway
+> Tree.
+
+Red-black trees are balanced 2,3,4 trees in disguise.  Sedgewick went even so
+far to suggest that it's beneficial to make the correspondence explicit (perhaps
+restricting both to 2,3 trees or equivalents), in the form of left-leaning
+red-black trees.  It surely helps code density.
+
+I think general B trees with variable-length records are not quite sound from a
+theoretical perspective, so you cannot use a stock balancing operation and get
+useful bounds.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, April  8, 2011  4:58 PM
+
+...
+> I don't mind if this isn't what this container is going to do
+> - I'm sure there are plenty uses for it - but perhaps it could be made
+> clearer?
+
+The implementation of the container, as with all containers, is not given. I had
+imagined a list of lists implementation, but obviously there are a lot of other
+options. So if someone wants to use fixed pages for sibling lists, that's fine.
+
+Part of the idea here is that this could be a building block, that provides
+memory management and checking, for more complex structures. One of the reasons
+that we have the various Splice routines is so that you can build a fairly
+efficient balancing scheme on top if that makes sense.
+
+I have not idea how to "make it clearer". There is nothing anywhere that
+promises "balanced" or B-Tree or anything like that. I realize that omissions
+aren't as obvious as inclusions, but this is just a basic multiway tree that
+makes no promises beyond providing a basic structure. If you had a "Binary_Tree"
+container, you'd have the same sort of issue, as that too promises nothing.
+
+I suppose we could add an AARM Note: "This tree just provides a basic structure,
+and make no promises about balancing or other automatic organization. Rather, it
+provides a building block on which to construct more complex and more
+specialized tree containers."
+
+If some such derived container proves to be widely used, it would make sense to
+consider standardizing it next time.
+
+****************************************************************
+
+From: Martin Dowie
+Sent: Friday, April  8, 2011  5:09 PM
+
+I think this sums it up nicely.
+
+****************************************************************

Questions? Ask the ACAA Technical Agent