Charles: missing vector iterators

Charles: missing vector iterators

[Victor Porton]

Why in Charles.Vectors iterators are missing even despite it is 
modelled after STL?

Iterators are good for many things, including reliability:

In enclosed loops:

for i in ... loop
  for j in ... loop
    ...
  end loop;
end loop;

personally I often mess I and J. Probability to mess iterators is 
lesser than to mess natural number indexes because iterators are more 
type-safe.

Please add these.

BTW, may be put Chrles on SourceForge or something that if e.g. I will 
want to submit a patch it would become simpler?

Re: Charles: missing vector iterators

[Preben Randhol]

Victor Porton wrote:
> personally I often mess I and J. 

Why don't you use propper variable names?

-- 
Preben Randhol ------------------------ http://www.pvv.org/~randhol/ --
�There are three things you can do to a woman. You can love her, suffer
 for her, or turn her into literature.�  - Justine, by Lawrence Durrell

Re: Charles: missing vector iterators

[Marc A. Criley]

Victor Porton wrote:
> 
> In enclosed loops:
> 
> for i in ... loop
>   for j in ... loop
>     ...
>   end loop;
> end loop;
> 
> personally I often mess I and J. Probability to mess iterators is
> lesser than to mess natural number indexes because iterators are more
> type-safe.

You can't mess with I and J inside a loop like this.  They're
effectively constants as far as the enclosed statements are concerned.

Marc A. Criley
Quadrus Corporation
www.quadruscorp.com

Re: Charles: missing vector iterators

[Preben Randhol]

Marc A. Criley wrote:
> You can't mess with I and J inside a loop like this.  They're
> effectively constants as far as the enclosed statements are concerned.

I think he meant writing : A (J,I) in stead of A (I,J)

-- 
Preben Randhol ------------------------ http://www.pvv.org/~randhol/ --
�There are three things you can do to a woman. You can love her, suffer
 for her, or turn her into literature.�  - Justine, by Lawrence Durrell

Re: Charles: missing vector iterators

[Matthew Heaney]

porton@ex-code.com (Victor Porton) wrote in message news:<3dd29387$0$303$bed64819@news.gradwell.net>...
> Why in Charles.Vectors iterators are missing even despite it is 
> modelled after STL?

Because iterators for vectors are too fragile.

An unbounded vector automatically grows as necessary during
insertions.  This works by deallocating the existing internal array,
reallocating a new (longer) array, and copying the existing elements
onto the new array.

The issue is that an iterator designates the old array, which gets
deallocated.  It's too easy for forget this fact, which means dangling
references occur.

The whole problem goes away by simply using the index subtype to refer
to elements in the vector, instead of an iterator.

Realize that the iterator exists in the STL because of the nature of
template expansion in C++.  In Ada, a separate iterator is not
necessary because the generic actual subprogram only needs to match
the signature of the generic formal, not its name (which is not the
case in C++).

Remember that Charles is *modelled* on the STL, but it is not a
literal port of the STL.  Charles is first and foremost an Ada
library, and it takes advantage of specific features of the Ada
language, specifically nested subprograms.


> Iterators are good for many things, including reliability:

Just the opposite.  A vector iterator is very UNreliable.
 
>Probability to mess iterators is 
> lesser than to mess natural number indexes because iterators are more 
> type-safe.

Wrong for vectors.  I don't know what would ever motivate you to think
this, when iteration over a scalar range is so high level in Ada:

for I in I_Subtype loop
   for J in J_Subtype loop
     ...

This is hard to get wrong.

 
> Please add these.

Your suggestion is noted, and rejected.

 
> BTW, may be put Chrles on SourceForge or something that if e.g. I will 
> want to submit a patch it would become simpler?

You can get more immediate feedback by sending me email directly.  CLA
is probably not the most suitable forum for discussing Charles
features.

mheaney at on2 dot com

Re: Charles: missing vector iterators

[Victor Porton]

In article <slrnat7gbr.473.randhol+news@kiuk0152.chembio.ntnu.no>,
	Preben Randhol <randhol+news@pvv.org> writes:
> Marc A. Criley wrote:
>> You can't mess with I and J inside a loop like this.  They're
>> effectively constants as far as the enclosed statements are concerned.
> 
> I think he meant writing : A (J,I) in stead of A (I,J)> 

I meant A(j) messed with A(i).

Re: Charles: missing vector iterators

[Preben Randhol]

Victor Porton wrote:
> I meant A(j) messed with A(i).

Thought so. So they you rather call them Outer and Inner. Using i and
j like this is considered error-prone.

-- 
Preben Randhol ------------------------ http://www.pvv.org/~randhol/ --
�There are three things you can do to a woman. You can love her, suffer
 for her, or turn her into literature.�  - Justine, by Lawrence Durrell

Re: Charles: missing vector iterators

[Preben Randhol]

Victor Porton wrote:
> I meant A(j) messed with A(i).

Thought so. Call them Outer and Inner in stead. Using i and
j like this is considered error-prone.

-- 
Preben Randhol ------------------------ http://www.pvv.org/~randhol/ --
�There are three things you can do to a woman. You can love her, suffer
 for her, or turn her into literature.�  - Justine, by Lawrence Durrell

Re: Charles: missing vector iterators

[Victor Porton]

In article <1ec946d1.0211140804.42621077@posting.google.com>,
	mheaney@on2.com (Matthew Heaney) writes:
> porton@ex-code.com (Victor Porton) wrote in message news:<3dd29387$0$303$bed64819@news.gradwell.net>...
>> Why in Charles.Vectors iterators are missing even despite it is 
>> modelled after STL?
> 
> Because iterators for vectors are too fragile.
> 
> An unbounded vector automatically grows as necessary during
> insertions.  This works by deallocating the existing internal array,
> reallocating a new (longer) array, and copying the existing elements
> onto the new array.
> 
> The issue is that an iterator designates the old array, which gets
> deallocated.  It's too easy for forget this fact, which means dangling
> references occur.

type Iterator_Type is private;

...

type Iterator_Type is
    record
        Contaner: Container_Access;
        Index: Index_Type;
    end record;

It is probably space inefficient but otherwise good.

With a good compiler we seemingly can even live without space 
inefficiency using my previously posted to c.l.a idea of per
container instance iterators:

type Iterator_Type(Contaner: Container_Access) is
    record
        Index: Index_Type;
    end record;

Now we can introduce a space efficient Range_Type (if compiler well 
optimized records with discriminants for space):

type Range_Type(Contaner: Container_Access) is
    record
        First, Last: Iterator_Type(Container);
    end record;

With a good compiler (if these exist) here it will be optimized to keep 
only one value of Container_Access for Range_Type variables.

Well, may be someday I will write my own containers library with 
features like this container-specific Range_Type.

BTW, for conveniency ranges should be transfered not as two separate
values, but as records with two components.

> The whole problem goes away by simply using the index subtype to refer
> to elements in the vector, instead of an iterator.

[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".]
 

Re: Charles: missing vector iterators

[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.