From: Matthew Heaney <matthewjheaney@earthlink.net>
Subject: Re: GCC 4.0 Ada.Containers Cursor danger.
Date: Wed, 13 Jul 2005 02:46:07 GMT
Date: 2005-07-13T02:46:07+00:00 [thread overview]
Message-ID: <ubr57juds.fsf@earthlink.net> (raw)
In-Reply-To: 42d46b51$0$18005$9b4e6d93@newsread4.arcor-online.net
Georg Bauhaus <bauhaus@futureapps.de> writes:
> Here is a silly example demonstrating a subprogram that is
> independent of any specific container. That is, you can choose
> any instance in place of My_Container.
> As arguments to the following function, use cursors
> returned by Floor and Ceiling (to mark a range of
> associations in a map.) Use First and Last of a set to express
> forall. Do the same using a vector.
>
>
> with My_Container;
> -- some instance of some Ada.Container ("abstract" if you wish)
But you can make a generic algorithm that is, um, generic:
generic
type Element_Type (<>) is limited private;
type Cursor (<>) is private;
with function Element (Pos : Cursor) return ET is <>;
with procedure Next (Pos : in out Cursor) is <>;
with function "=" (L, R : ET) return Boolean is <>;
function Generic_Find
(Start, Stop : in Cursor;
Item : in Element_Type) return Cursor;
Start denotes the (inclusive) beginning of the range of items to be
tested.
Stop denotes the (exclusive) one-beyond-the-end-of-the-range of items to
be tested.
If the item isn't found, then Generic_Find returns Stop. Otherwise it
returns the earliest cursor in the sequence that matches Item.
> function gen_find
> (first,
> last: My_Container.Cursor;
> item: My_Container.Cursor) return My_Container.Cursor
This requires care, since if First and Last are both inclusive members
of the range, then there's no way to designate an empty range.
You always need a way to specify an empty range. Discrete subtypes work
that way, as do array types. In those cases, if T'Last < T'First, that
means the range is empty. But you can't do that for a cursor, so you
have to use the one-off-the-end technique instead.
> -- The first cursor of the sequence from `first` to `last` that designates
> -- an elemenent equal to the element designated by `item`.
> -- `No_Element` if not found.
> is
> use My_Container;
>
> p: Cursor := first;
> off: constant Cursor := Next(last);
> begin
> loop
> exit when p = off or else Element(p) = Element(item);
> next(p);
> end loop;
>
> if p = off then
> return No_Element;
> else
> return p;
> end if;
>
> end gen_find;
I prefer to say:
function Generic_Find
(Start, Stop : in Cursor;
Item : in Element_Type) return Cursor is
C : Cursor := Start;
begin
while C /= Stop then
if Element (C) = Item then
return C;
end if;
Next (C);
end loop;
return Stop;
end Generic_Find;
To make this a little more general, and possibly more efficient (you
have to be careful with value-returning functions), you could say:
generic
type Element_Type (<>) is limited private;
type Cursor (<>) is private;
with function Is_Equal (C : Cursor; E : ET) return Boolean is <>;
with procedure Next (Pos : in out Cursor) is <>;
function Generic_Find
(Start, Stop : in Cursor;
Item : in Element_Type) return Cursor;
Which you can implement as:
function Generic_Find
(Start, Stop : in Cursor;
Item : in Element_Type) return Cursor is
C : Cursor := Start;
begin
while C /= Stop then
if Is_Equal (C, Item) then
return C;
end if;
Next (C);
end loop;
return Stop;
end Generic_Find;
In fact, we could generalize this even more, to abstract-away the
element type:
generic
type Cursor (<>) is private;
with function Found (C : Cursor) return Boolean is <>;
with procedure Next (Pos : in out Cursor) is <>;
function Generic_Find
(Start, Stop : in Cursor) return Cursor;
So now you can say:
function Generic_Find
(Start, Stop : in Cursor) return Cursor is
C : Cursor := Start;
begin
while C /= Stop then
if Found (C) then
return C;
end if;
Next (C);
end loop;
return Stop;
end Generic_Find;
In any event, what should be noticed is that the container isn't part of
the generic algorithm. And that is the key to understanding iterators
(um, I mean cursors...), since they abstract-away the container. A
generic algorithm is a "generic algorithm" precisely because it's
container-independent.
You can use the algorithm to perform a linear search of a hashed
container (using those "dangerous" map cursors), e.g.
procedure Op (M : String_Integer_Maps.Map) is
procedure Find is
new Generic_Find (Integer, Cursor); -- accept defaults
C : constant Cursor := Find (M.First, No_Element);
begin
if Has_Element (C) then ...;
end;
next prev parent reply other threads:[~2005-07-13 2:46 UTC|newest]
Thread overview: 195+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-07-04 11:01 GCC 4.0 Ada.Containers Cursor danger Dmitriy Anisimkov
2005-07-04 18:56 ` Georg Bauhaus
2005-07-04 19:07 ` Georg Bauhaus
2005-07-05 4:27 ` Dmitriy Anisimkov
2005-07-05 15:01 ` Matthew Heaney
2005-07-06 9:10 ` Maxim Reznik
2005-07-06 10:45 ` Georg Bauhaus
2005-07-06 13:57 ` Maxim Reznik
2005-07-06 14:53 ` Georg Bauhaus
2005-07-06 15:09 ` Matthew Heaney
2005-07-06 16:37 ` Dmitriy Anisimkov
2005-07-06 16:43 ` Matthew Heaney
2005-07-06 22:24 ` Randy Brukardt
2005-07-07 10:23 ` Alex R. Mosteo
2005-07-06 12:41 ` Matthew Heaney
2005-07-06 15:37 ` Matthew Heaney
2005-07-06 21:51 ` Randy Brukardt
2005-07-05 14:51 ` Matthew Heaney
2005-07-05 17:11 ` Dmitriy Anisimkov
2005-07-05 18:02 ` Matthew Heaney
2005-07-05 19:08 ` Dmitriy Anisimkov
2005-07-05 19:26 ` Matthew Heaney
2005-07-05 19:44 ` Dmitriy Anisimkov
2005-07-05 20:06 ` Matthew Heaney
2005-07-06 2:10 ` Dmitriy Anisimkov
2005-07-06 22:44 ` Randy Brukardt
2005-07-07 3:41 ` Dmitriy Anisimkov
2005-07-07 19:18 ` Randy Brukardt
2005-07-08 3:01 ` Dmitriy Anisimkov
2005-07-09 6:17 ` Simon Wright
2005-07-11 2:24 ` Dmitriy Anisimkov
2005-07-11 2:24 ` Dmitriy Anisimkov
2005-07-06 5:52 ` Martin Dowie
2005-07-06 7:02 ` Dmitriy Anisimkov
2005-07-06 8:02 ` Georg Bauhaus
2005-07-06 8:37 ` Dmitriy Anisimkov
2005-07-06 9:06 ` Pascal Obry
2005-07-06 12:14 ` Georg Bauhaus
2005-07-06 7:53 ` Pascal Obry
2005-07-06 8:44 ` Dmitriy Anisimkov
2005-07-06 9:03 ` Pascal Obry
2005-07-06 9:34 ` Dmitriy Anisimkov
2005-07-06 9:42 ` Pascal Obry
2005-07-06 9:45 ` Dmitriy Anisimkov
2005-07-06 10:40 ` Georg Bauhaus
2005-07-06 16:22 ` Dmitriy Anisimkov
2005-07-06 16:42 ` Matthew Heaney
2005-07-06 16:59 ` Dmitriy Anisimkov
2005-07-06 17:12 ` Matthew Heaney
2005-07-06 18:12 ` Georg Bauhaus
2005-07-07 12:29 ` Dmitriy Anisimkov
2005-07-07 12:46 ` Matthew Heaney
2005-07-07 13:01 ` Dmitriy Anisimkov
2005-07-07 13:20 ` Matthew Heaney
2005-07-07 13:54 ` Georg Bauhaus
2005-07-07 17:56 ` Dmitriy Anisimkov
2005-07-07 22:12 ` Georg Bauhaus
2005-07-15 18:03 ` Dmitriy Anisimkov
2005-07-16 1:45 ` Matthew Heaney
2005-07-17 3:55 ` Dmitriy Anisimkov
2005-07-17 4:29 ` Matthew Heaney
2005-07-07 19:29 ` Randy Brukardt
2005-07-08 2:41 ` Dmitriy Anisimkov
2005-07-06 22:56 ` Randy Brukardt
2005-07-06 22:51 ` Randy Brukardt
2005-07-07 0:24 ` Matthew Heaney
2005-07-07 3:20 ` Randy Brukardt
2005-07-06 7:30 ` Dmitry A. Kazakov
2005-07-06 7:50 ` Georg Bauhaus
2005-07-06 8:11 ` Dmitriy Anisimkov
2005-07-06 11:36 ` Dmitry A. Kazakov
2005-07-06 12:14 ` Georg Bauhaus
2005-07-06 23:07 ` Randy Brukardt
2005-07-07 8:01 ` Dmitry A. Kazakov
2005-07-07 10:38 ` Georg Bauhaus
2005-07-07 13:00 ` Dmitry A. Kazakov
2005-07-07 13:41 ` Matthew Heaney
2005-07-07 22:12 ` Georg Bauhaus
2005-07-08 8:48 ` Dmitry A. Kazakov
2005-07-08 10:41 ` Georg Bauhaus
2005-07-08 13:03 ` Dmitry A. Kazakov
2005-07-08 13:31 ` Matthew Heaney
2005-07-10 2:12 ` Randy Brukardt
2005-07-10 8:52 ` Dmitry A. Kazakov
2005-07-11 10:58 ` Georg Bauhaus
2005-07-11 12:18 ` Dmitry A. Kazakov
2005-07-11 13:50 ` Georg Bauhaus
2005-07-11 18:38 ` Randy Brukardt
2005-07-12 8:44 ` Dmitry A. Kazakov
2005-07-12 10:33 ` Georg Bauhaus
2005-07-12 20:38 ` Randy Brukardt
2005-07-08 13:15 ` Matthew Heaney
2005-07-08 14:02 ` Dmitry A. Kazakov
2005-07-08 14:52 ` Matthew Heaney
2005-07-11 14:57 ` MMM
2005-07-11 18:36 ` Georg Bauhaus
2005-07-12 2:11 ` MMM
2005-07-12 21:47 ` Randy Brukardt
2005-07-13 4:31 ` MMM
2005-07-13 1:15 ` Georg Bauhaus
2005-07-13 2:46 ` Matthew Heaney [this message]
2005-07-14 4:11 ` Mikhail Terekhov
2005-07-14 12:44 ` Matthew Heaney
2005-07-19 1:38 ` Mikhail Terekhov
2005-07-19 3:21 ` Matthew Heaney
2005-07-14 23:03 ` Georg Bauhaus
2005-07-15 8:36 ` Dmitry A. Kazakov
2005-07-15 10:39 ` Georg Bauhaus
2005-07-15 14:10 ` Dmitry A. Kazakov
2005-07-15 12:10 ` Matthew Heaney
2005-07-19 3:51 ` Mikhail Terekhov
2005-07-19 11:35 ` Matthew Heaney
2005-07-19 3:11 ` Mikhail Terekhov
2005-07-19 12:44 ` Matthew Heaney
2005-07-20 5:20 ` Simon Wright
2005-07-21 2:39 ` Matthew Heaney
2005-07-21 3:23 ` Randy Brukardt
2005-07-19 23:51 ` Randy Brukardt
2005-07-20 15:33 ` Robert A Duff
2005-07-11 14:56 ` MMM
2005-07-11 23:24 ` Matthew Heaney
2005-07-12 3:05 ` MMM
2005-07-12 5:32 ` Simon Wright
2005-07-13 2:41 ` MMM
2005-07-12 11:16 ` Georg Bauhaus
2005-07-16 22:28 ` Robert A Duff
2005-07-12 13:32 ` Marc A. Criley
2005-07-12 14:51 ` MMM
2005-07-12 15:35 ` Matthew Heaney
2005-07-12 18:40 ` MMM
2005-07-12 19:12 ` Matthew Heaney
2005-07-12 19:42 ` MMM
2005-07-12 20:02 ` Georg Bauhaus
2005-07-13 3:52 ` MMM
2005-07-12 20:13 ` Matthew Heaney
2005-07-12 21:38 ` Simon Wright
2005-07-12 17:44 ` Marc A. Criley
2005-07-12 18:51 ` MMM
2005-07-12 19:15 ` Matthew Heaney
2005-07-12 19:47 ` Georg Bauhaus
2005-07-13 2:20 ` Matthew Heaney
2005-07-12 20:00 ` MMM
2005-07-12 20:09 ` Georg Bauhaus
2005-07-12 20:15 ` Matthew Heaney
2005-07-12 21:01 ` Randy Brukardt
2005-07-13 4:16 ` MMM
2005-07-19 23:58 ` Randy Brukardt
2005-07-12 21:59 ` Simon Wright
2005-07-12 20:56 ` Randy Brukardt
2005-07-14 5:01 ` Mikhail Terekhov
2005-07-20 0:10 ` Randy Brukardt
2005-07-07 12:36 ` Matthew Heaney
2005-07-07 12:52 ` Dmitriy Anisimkov
2005-07-07 13:52 ` Georg Bauhaus
2005-07-07 17:49 ` Dmitriy Anisimkov
2005-07-07 18:35 ` Matthew Heaney
2005-07-08 17:52 ` Craig Carey
2005-07-07 17:50 ` Dmitriy Anisimkov
2005-07-07 19:47 ` Randy Brukardt
2005-07-08 2:28 ` Dmitriy Anisimkov
2005-07-09 14:20 ` Matthew Heaney
2005-07-10 1:51 ` Randy Brukardt
2005-07-10 5:46 ` Craig Carey
2005-07-10 6:13 ` Craig Carey
2005-07-11 17:33 ` OT: Greg and Colin? (was Re: GCC 4.0 Ada.Containers Cursor danger.) Marc A. Criley
2005-07-06 22:34 ` GCC 4.0 Ada.Containers Cursor danger Randy Brukardt
2005-07-07 0:22 ` Matthew Heaney
2005-07-07 3:17 ` Randy Brukardt
2005-07-08 5:34 ` Jeffrey Carter
2005-07-10 1:53 ` Randy Brukardt
2005-07-10 19:32 ` Jeffrey Carter
2005-07-07 3:24 ` Randy Brukardt
2005-07-16 23:24 ` Matthew Heaney
2005-07-17 4:04 ` Dmitriy Anisimkov
2005-07-17 5:01 ` Matthew Heaney
2005-07-17 17:13 ` Dmitriy Anisimkov
2005-07-17 17:36 ` Matthew Heaney
2005-07-17 17:49 ` Dmitriy Anisimkov
2005-07-17 18:12 ` Matthew Heaney
2005-07-17 17:40 ` Dmitriy Anisimkov
2005-07-17 17:50 ` Dmitriy Anisimkov
2005-07-17 18:08 ` Matthew Heaney
2005-07-19 4:36 ` Mikhail Terekhov
2005-07-20 1:59 ` Matthew Heaney
2005-07-20 14:00 ` Pascal Obry
2005-07-20 14:34 ` Matthew Heaney
2005-07-20 16:51 ` Pascal Obry
2005-07-20 16:53 ` Pascal Obry
2005-07-21 3:18 ` Randy Brukardt
2005-07-20 2:37 ` Robert I. Eachus
2005-08-02 16:59 ` Craig Carey
2005-08-02 20:55 ` Simon Wright
2005-07-20 7:20 ` Georg Bauhaus
2005-07-17 9:28 ` Georg Bauhaus
2005-07-17 14:26 ` Matthew Heaney
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox