Re: OO Style with Ada Containers

[Matthew Heaney <mheaney@on2.com>]

On Nov 20, 9:11 am, Maciej Sobczak <see.my.homep...@gmail.com> wrote:
> On 19 Lis, 23:16, Matthew Heaney <mhea...@on2.com> wrote:
>
> 1.
> The most important part of STL is the notion of range-based iteration.
> Every single algorithm that iterates over something gets a pair of
> iterators denoting the range to be visited.
>
> sort(v.begin(), v.end());

But there's nothing that precludes that in Ada:

generic
  type Cursor is private;
  ...
procedure Generic_Algorithm (First, Back : Cursor);

You'd instantiate as follows:

procedure Op (V : Integer_Vectors.Vector) is
  procedure Algorithm is
    new Generic_Algorithm (Integer_Vectors.Cursor, ...);

  C1 : Cursor := ...;
  C2 : Cursor := ...;
begin
  Algorithm (First => C1, Back => C2);
end Op;

Here the algorithm begins at C1, and terminates when the cursor equals
C2.  You can use any cursor you like as the "back" cursor value (one
off-the-end of the sequence).

If you want to iterate over the entire range, use V.First as the First
cursor and Integer_Vectors.No_Element as the Back cursor.

However, I find that it's easier to just say:

generic
  type Cursor is private;
  function Has_Element (C : Cursor) return Boolean is <>;
  ...
procedure Generic_Algorithm (First : Cursor);

So if we want to iterate over all of the elements, we accept the
default for Has_Element (which is declared in the package itself):

procedure Op (V : Integer_Vectors.Vector) is
  procedure Algorithm is
    new Generic_Algorithm (Integer_Vectors.Cursor);

  C1 : Cursor := ...;
begin
  Algorithm (C1);
end Op;

If you want to iterate over a range you can say:

procedure Op (V : Integer_Vectors.Vector) is
  C2 : constant Cursor := ...;

  function Has_Element (C : Cursor) return Boolean is
  begin
     return C /= C2;  -- or whatever
  end;
  procedure Algorithm is
    new Generic_Algorithm (Integer_Vectors.Cursor);

  C1 : Cursor := ...;
begin
  Algorithm (C1);
end Op;

Here the locally declared Has_Element becomes the default, so the
iteration terminates when the cursor equals C2.

You don't have to do it that way; you could say:

procedure Op (V : Integer_Vectors.Vector) is
  function Predicate (C : Cursor) return Boolean is ...;
  procedure Algorithm is
    new Generic_Algorithm
   (Integer_Vectors.Cursor,
    Has_Element => Predicate);

  C1 : Cursor := ...;
begin
  Algorithm (C1);
end Op;


> But why not:
>
> vector<int>::iterator middle = v.begin() +
>                                (v.end() - v.begin()) / 2;
>
> sort(v.begin(), middle);
> sort(middle, v.end());
>
> And then why not doing it in paraller... ;-)

Unfortunately, the vector container in the Ada library doesn't have
arithmetic operators.  (I lobbied for them, but wasn't able to
convince the ARG of their necessity.)  However, you can synthesize
such operators using the vector operations To_Cursor and To_Index.  So
we can write your example in Ada like this:


procedure Op (V : in out Integer_Vectors.Vector) is
  I : Extended_Index := V.First_Index + Count_Type'Pos (V.Length / 2);
  Middle : Cursor := To_Cursor (V, I);

begin
  Sort(V.First, Middle);
  Sort(Middle, No_Element);
end Op;


> Sorting only the first N elements?
> (let's assume there are at least N)
>
> sort(v.begin(), v.begin() + N);
>
> And so on.

procedure Op (V : in out Integer_Vectors.Vector) is
  I : Extended_Index := V.First + N;
  C : Cursor := To_Cursor (V, I);
begin
  Sort (V.First, C);
end Op;


> Ada.Containers does not support anything like this. The only available
> algorithms work on whole containers.

Well, there are no "available" algorithms in the standard library
(excepting array-based sorting), but assuming you have your own
algorithms you can do it as I describe above.


> This is more similar to Java approach, which has a sort method for
> sorting whole lists (however, users can have a list-like view on the
> part of the container, but this is not a range-based iteration, rather
> smart application of view-like containers - in any case, the focus is
> on containers, not on ranges).

For a range of elements, you can use the two-cursor approach (which
describe a half-open range), or pass the termination condition as a
generic formal predicate operation.


> 2.
> Another important part of STL is the notion of iterator category.
> Depending on the category, the iterator can support different sets of
> operations. The most powerful is RandomAccessIterator, which allows to
> arbitrarily jump around the sequence in constant time.

Right, but in Ada the category is described in the generic formal
region:

generic
  type IT is <>;  -- means any integer type
  type DT is (<>);  -- means any discrete type
  type FT is digits <>;  -- means any floating pt type
  ... -- etc

A "random-access cursor" would be described like this:


generic
  type Cursor is private;
  with function "+" (L : Cursor; R : Count_Type'Base)
    return Cursor is <>;
  with function "-" (L, R : Cursor)
    return Count_Type'Base is <>;
  ...
procedure Generic_Algorithm (...);


> Iterator to the vector is a random access iterator, because vector
> itself is inherently random-accessible.
> This is why I was able to do
> the above arithmetics to initialize the iterator to the middle of the
> vector.

As you can in Ada.


> I would not be able to do it in the same way with linked
> lists.

Right.


> Categories also allow the algorithms to automatically select the most
> optimal implementation, depending on the abilities of the given
> iterators.

Well, you're comparing apples and oranges.  In Ada, if a generic
algorithm requires a random-access cursor, it imports the requisite
operations as generic formal parameters.


> Nothing like this exists in Ada, where cursors just resemble this:

False; see the examples above.


> In STL-like library I would expect range-based algorithms and
> iterators that benefit from abilities of the underlying sequence.

As would I; see above for a few ideas.