Re: AVL Tree Implementation

[ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe)]

mfeldman@seas.gwu.edu (Michael Feldman) writes:
>>	feldman		-- nothing
>Hmmm - which distribution are you looking at? This is in mine:
>(Feldman, Software Construction and Data Structures with Ada 95, AW 1996)

The one where
y% ls | wc -l		=>     166			(files)
y% cat * | wc		=>    9922   36596  283729
and where my_int_io.ads says
-- pre-instantiations of IO for numeric and boolean types

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.)

>[Five AVL operation packages listed]

>These are subunits intended to be incorporated into a modification of
>the generic BST package:

>[Seven binary search tree files listed]

I guess what we have must be from an earlier book, or incomplete.

>No, I don't provide a complete AVL package; the intention is that
>the student will just modify the ordinary BST package with the new
>AVL operators.

>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
structures.  Now I am not a student, and haven't been for some time,
but I have *often* turned to data structures textbooks (all of which
I purchased _after_ my undergraduate years) for something to actually
use.  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).

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.

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.

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.

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

>>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.  We _have_ got the old book, which
explicitly said (on p207) that AVL trees were beyond its scope.

>The home page for this book is at

>http://heg-school.aw.com/cseng/authors/feldman/cs2-ada/cs2-ada.html

>The program library is online there and also here at GW at

>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.)

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 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.  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!".

In fact, this bothered me so much that I revised my Ada->HTML converter
(which can also generate plain text), adding options
  -bi		% Breaks: Insert between <lower><upper>
  -bd		% Breaks: Delete between <lower><upper>
  -rM/N		% Reindent: q*M+r leading spaces => q*N+r


-- 
Australian citizen since 14 August 1996.  *Now* I can vote the xxxs out!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.