Re: Wanted: Ada STL. Reward: Ada's Future

[Matthew Heaney <matthew_heaney@acm.org>]

Stephen Leake <Stephen.Leake@gsfc.nasa.gov> writes:

> I thought Matthew just did that, but you haven't answered the question
> "why does the STL allow iteration past the end of the array". This
> bugs me too. Is there a real reason here, or is it an accident of the
> implementation?

To terminate an iteration, you always have to "fall off the end" of the
thing you're iterating over.  This is true of array iteration, loop
iteration, stream iteration, etc:

  for (i = 0; i < len; i++ { 
    ... a [i] ...
  }

The iteration terminates when i falls off the end the array.

  declare
     Node : Node_Access := List;
  begin
     while Node /= null loop
        <process Node.Item>
        Node := Node.Next;
     end loop;
  end;

This loop terminates when Node falls off the end of the list.

  loop
     Get (N);
     exit when N = 0;
     <process N>
  end loop;


This loop terminates when N falls off the end of the stream (eos being
indicated by a sentinal, the value 0).

Now what Ada does, is do this falling off the end behind the scenes, so
that you the programmer don't have to worry about whether your index has
an extra value.  However, you can use the low level approach (necessary
once in a while), by using the technique I showed in my earlier post.

I do this in the implementation of an iterator over a bounded data
structure implemented as an array:

type Stack_Iterator is
  record
    Index : Natural;  -- note that this is Natural, not Positive
    Stack : Stack_Access;
  end record;

function Initialize 
  (Stack : Stack_Type) return Stack_Iterator is
begin
  return (Index => Stack.Top, Stack => Stack'Access);
end;

function Is_Done (Iterator : Stack_Iterator) return Boolean is
begin
   return Iterator.Index = 0;  
   -- the value 0 is outside range of index subtype (Positive)
end;

procedure Advance (Iterator : Stack_Iterator) is
begin
  Iterator.Index := Iterator.Index - 1;
  -- this might case Index to fall off the end of the array
end;


Iteration would look like this:

declare
   Iter : Stack_Iterator := Initialize (Stack);
begin
   while not Is_Done (Iterator) loop
     <process Get_Item (Iter)>
     Advance (Iter);
   end loop;
end;


This loop terminates because Iter.Index falls of the end of the array
(in this case, the beginning of the array).

Iteration past the end of the array isn't an STL "problem," it is just
the nature of iteration, irrespective of language.  (Although in Ada's
case, this falling off the end is often hidden from the programmer.)