Re: Charles: missing vector iterators

[mheaney@on2.com (Matthew Heaney)]

porton@ex-code.com (Victor Porton) wrote in message news:<3dd4baae$0$304$bed64819@news.gradwell.net>...
> 
> type Iterator_Type is
>     record
>         Contaner: Container_Access;
>         Index: Index_Type;
>     end record;
> 
> It is probably space inefficient but otherwise good.

Well that is the whole point.

A vector iterator doesn't add any power to the abstraction, it merely
changes the syntax of vector manipulation.

It would be simple enough for a user to add an "iterator layer" on top
of the existing vector, or add another package, e.g.

with Charles.Vectors.Unbounded;
generic
   with package Vector_Types is new Charles.Vectors.Unbounded (<>);
package Generic_Vector_Iterators is
   type Iterator_Type is private;  

   function First (V : Vector_Subtype) return Iterator_Type;
...
end Generic_Vector_Iterators;


> [Skipped because we define the term "iterator" differently:
>  I mean fat iterators (which can be dereferenced without
>  supplying containers; while Matthew Heaney means
>  "something based on pointers".]

I use the term "fat" per the GNAT user's guide (or was it the
reference manual?).  It means whether the representation of the
iterator object requires one pointer or two pointers.  (In GNAT, an
access type that designates an unconstrained array is by default
implemented as a pair of pointers, hence the term "fat.")

All iterators can always be dereferenced without also supplying a
container.  That's practically the meaning of "iterator."  It's not
clear why you think I meant otherwise.

An early version of the library did in fact have vector iterators,
implemented as:

type Iterator_Type is
   record
      Elements : Element_Array_Access;
      Index    : Index_Subtype'Base;
   end record;

The problem with your implementation, like this:

type Iterator_Type is
   record
      Container : Container_Access;
      Index     : Index_Subtype'Base;
   end record;

is that you either have to

1) pay a syntactic penalty to stay in safe RM territory; or
2) avoid the syntactic penalty by playing Chap13 tricks.

In the first case, you would need to implement operations this way:

  function First (Container : access Container_Type) 
    return Iterator_Type;

and then declare vector container objects as aliased:

  Vector : aliased Vector_Subtype;
  ...
  Iterator : Iterator_Type := First (Vector'Access);

This will cause further headaches if you only have a constant view of
the vector, ie

procedure Print (V : Vector_Subtype) is
   Iterator : Iterator_Type := First (V'Access); --won't compile
begin

There are ways around this, but they involve Chap13 tricks.

In the second case, you have a similar problem:

   function First (Container : Container_Type) 
      return Iterator_Type is

      Result : Iterator_Type;
   begin
      Result.Container := Container'Access; --won't compile

To work around this you have to play the same Chap13 tricks.

Note also that your implementation won't work with a swap.  If I do
this:

   V1 : Vector_Subtype;
   Iter : Iterator_Type := First (V1);

   V2 : Vector_Subtype;

   Swap (V1, V2);

   E := Element (Iter);

This *should* return the element that was in V1, and is now in V2. 
(Iterators always designate elements, not containers.)  But in your
formulation Iter designates some element in V1.  This is incorrect. 
This error is especially pernicious, because V1 and V2 may have
different lengths and sizes, which means you'll end up deferencing
garbage.

I personally find it much simpler to implement the iterator as a
pointer to the internal array, rather than the container.  This works,
but the problem is that that iterator is very fragile, and is very
susceptable to dangling reference problems because of automatic
reallocation.

All of these problems go away if you simply don't have a vector
iterator.  You have random access, so just use an index, which does
the job equally well.  If this syntax offends you:

  E : Element_Type := Element (Vector, Iterator);

then you can just write a local subprogram to take out the vector
param:

  V : Vector_Subtype;
 ...
  function Element (Iterator : Iterator_Type) return Element_Type is
  begin
    return Element (V, Iterator);
  end;

and now all is well.

Your suggestion is noted, and rejected.