Re: AVL Tree Implementation

[mfeldman@seas.gwu.edu (Michael Feldman)]

In article <52pvit$gae@goanna.cs.rmit.edu.au>,
Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote:
>
>WITH Text_IO;
>PACKAGE My_Int_IO IS
>  NEW Text_IO.Integer_IO(Num => Integer);
>
>(I don't understand how this instantiates IO for Boolean types.)

Ah - when it was gnatchopped into 3 different files, the comment was
obsoleted. My_Int_IO is an Ada 83 artifice anyway; currently I use
Ada.Integer_Text_IO.:-)

I _think_ you are looking at a mixture of programs from Feldman/Koffman
_first edition_ (1991) and my _old_ data structures book (Prentice
Hall 1985, re-published by AW, 1993).
>
[snip]
>
>>Textbooks don;t (and shouldn't) provide everything in ready-to-run
>>form; the student has to learn how to create components by adapting
>>other components.
>
>The assumption here is that a data structures textbook is of value
>*only* to students, and more specifically only to students of data

Yes, I'd agree that this is the primary "market" I am targeting.

>I can't tell you how often I have cursed authors who have said
>"deletion from <xxx> left as an exercise for the reader" (Sedgewick
>is not the only offender, but he's on the list).

Well, if we publish every line of every subprogram of every package,
there will be nothing left - students have to learn _somewhere_ how
to _write_ these packages. 

I agree that there should be more books of the "numerical recipes" or 
"Booch components" variety, intended to provide "ready to run" components
to experienced users. OTOH, I've got my hands full with writing for my
chosen "customers", so others will have to write these.:-)

>Leaving out operations, or providing fragments that require nontrivial
>stitching, is a good way to ensure that this assumption will be *true*
>of a particular book.

Which assumption? That occasionally a user will curse the author?
Yeah, I guess I'll have to live with that.:-)

>One of the books I cherish on my crowded shelves, as a horrible example,
>is by some noted American academics who swear that their C book is not a
>rehash of a their previous Pascal book, but where one of the major
>components that is left for the reader to complete relies totally
>on nested functions, which C does not support.

I think I know the book you're referring to; that is, pure and simple,
an _error_. Occasionally a reused exercise will turn out to be too-
casually reused. I was bitten by this also, but not much...

I admire your very high standards for books; you and I have discussed
this publicly and privately before. I don;t think it's too realistic
for you to expect _perfection_, though. Nothing would _ever_ get out
to where people could use it if the standard were _that_ high...

>The reader is always left with the suspicion that the author didn't
>provide complete code because he _couldn't_ and that the data structure
>is of no real use.

<shrug> How do I respond to this one? ("Trust me! I know how to do it!")?

>One of the things I was proudest of in the Pascal code I provided to the
>students in the CS241 course when I taught it was that it was complete
>working generic (thanks to M4, sigh, and thank goodness for Ada) code
>that they could take away and _use_ in applications

Yep, we all write code like this. I'm reasonably proud of mine too, even
if some of it was stubbed out so students could fill it back in.

>>>If you were using Ada in a data structures course, which books, and which
>>>associated package libraries, would you use?

>>Well, for me, this is of course a loaded question.:-)

>>Oh, OK, I'll answer it. I use the Feldman book.:-)

>Well, if your publisher had seen fit to send us a review copy, it would
>have been a very strong contender here.  

I will make damn sure you get one. 'Course, you might curse me 'cause
some of my packages have stubbed-out methods in some of the packages.

>We _have_ got the old book, which
>explicitly said (on p207) that AVL trees were beyond its scope.

Correct. And that book came out originally with no software distribution
at all. I put one together, but it's not very good because I was already
busy working on the new edition (which took 5 years, interleaved with
my "day job").
>
>>ftp://ftp.gwu.edu/pub/ada/courses/cs2code.zip (8+3 filenames)
>>ftp://ftp.gwu.edu/pub/ada/courses/cs2code.tar.Z (long filenames)
>
>Thank you for this information.  I have followed it up right away.
>(Check the date and contents of the README file at ftp.gwu.edu.)

Will do.

>Could I suggest adding compilation instructions to cs2code/?
>"gcc -c *.adb" doesn't even come close to working, and there is
>no Makefile.  (For example, PrintPermutations is dangling in mid air.)

I'll think about this - I've tended to stay away from compiler-
specifics, but it's a good idea for the README.

>I must say that I find
>	IsIn(Set, Element)
>a very confusing order of arguments, given the name.  The English is
>"Element is in Set".
>	Has_Member(Set, Element)
>or	Is_In(Element, Set)
>would clash less with the way one says it in English.  

Yeah, good point.

>I also prefer
>code to follow the Ada Quality and Style guidelines.  I prefer this
>so much that since it was pointed out to me two weeks ago that the
>AQ&S recommends indenting by 3, I have abandoned my cross-language
>use of 4 and switched to 3 for the Ada code I'm working on.  So I am
>not terribly thrilled by keywords ALLINCAPS and RunOnWords.  I know
>these are superficial issues, but they _are_ highly visible, and it
>is hard enough trying to persuade the students to follow the guidelines
>without them saying "but Mike Feldman doesn't!".

But AQ&S is only a guide, not a law. We've been around this loop
before, publicly and privately. I am still a member of the (still large)
group of intro-course teachers (especially in Pascal circles) who believe 
that beginners learn code patterns better if the reserved words are
emphasized. We do that with upper case.

Since I'm writing for beginners, that's the lexical style
I choose. It's not worth fighting over. The important thing is
_consistent_ style (even AQ&S says this, and mine is consistent)
and _clear_ code (which I strive for, though this is not quite
so measurable). 

Underscores are a different story. Purely a matter of taste. YMMV.:-)

To summarize - we need more Ada 95 books for different "markets".

Who's going to write the one Richard needs?
(Basically, a software components book like the original Booch
components book.)

Mike Feldman