Re: OO Style with Ada Containers

On Nov 20, 9:11 am, Maciej Sobczak <see.my.homep...@xxxxxxxxx> wrote:
On 19 Lis, 23:16, Matthew Heaney <mhea...@xxxxxxx> 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.
.

Relevant Pages

  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Iterative subspace decomposition
    ... Subspace Tracking," IEEE Transactions on Signal Processing, vol. 43, ... the PASTd algorithm does not produce orthogonal ... it is not producing the eigendecomposition I ...
    (sci.math.num-analysis)
  • Re: rapidly converging rational sqrt
    ... Note that after iteration 6 we have ... > more than 100 significant digits. ... I don't wish to denigrate your algorithm unduly, but square root algorithms ...
    (sci.math.research)
  • Re: Encrypt with RijndaelManaged and decrypt with OpenSSL
    ... I forgot to add that yes this also produces the exact aes key ... you need to invoke the algorithm iteration 3 times to build ... that openssl enc does not provide an option to ...
    (microsoft.public.dotnet.security)
  • Re: smallest disk covering a set of points
    ... If there is a 4th point outside the second circle on ... iteration" when an algorithm is found to fail more often fails ... my intuition tells me that it will converge to ...
    (comp.programming)
Loading