Re: c++ vs ada results

[uvaarpa!software.org!smithd@mcnc.org (Doug Smith)]

In article <1991Aug15.154021.24043@cats.com> andy@cats.com (Andy Davidson) writ
es:
> In article <1991Aug14.182554.16576@software.org> smithd@software.org (Doug Sm
ith) writes:
> >
> >It is possible to take an algorithmic approach to building these
> >utilities.  This creates a smaller library of generics that provide the

> What exactly do you mean by an "algorithmic approach"? Do you mean a
> structured design approch?? Can you elaborate on your statement
> 
(I don't think this is structured design, you be the judge...)

Since several people have asked for more information...

There is a published work that you can reference:

    The Ada Generic Library
        Linear List Processing Packages
    Musser & Stepanov
    Springer-Verlag 1989

An example that comes to mind is the usual sort generic:

    generic
        type Element is private;
        type Index is (<>);
        type Arrays is array (Index range <>) of Element;
        with function "<" (Left, Right : Element)
                           return        Boolean;
    procedure Sort (Arr : in out Arrays);

I consider this the usual data structure oriented approach.  Which is
a conventient form, but should be built on top of a more general
sorting algorithm:

    generic
        type Element is limited private;
        type Index is (<>);
        type Arrays is array (Index range <>) of Element;
        with function "<" (Left, Right : Element)
                           return        Boolean;
        with procedure Swap (Left, Right : in out Element);
    procedure Sort (Arr : in out Arrays);

Which could be built on another, even more general sorting algorithm:

    generic
        type Index   is (<>);
        with function Element_Is_Less_Than
                          (Left, Right : Index)
                           return        Boolean;
        with procedure Swap (Left, Right : in     Index);
    procedure Sort (From, To : in     Index);

And then I would even try to make Index limited private, but that
gets messy, and you get the idea.  When you get down to the actual
algorithm, you will have declared the assumptions that the algorithm
makes as part of the declaration.

So if you can describe the Quick_Sort algorithm using only limited
private types, and for a binary tree you have a way of partitioning
the tree, moving elements, comparing elements, etc.--then you have
an efficient sort that works both on arrays and binary trees.