Missing in Booch: range operations

Missing in Booch: range operations

[Victor Porton]

Range operations (deleting the range between two iterators, inserting 
content of a container or its subrange into a position of another 
container etc.) are missing in current Booch. Just to make sure that 
these are not forgotten.

BTW, these should throw an exception if the begin and the end of the 
range are from different containers.

Re: Missing in Booch: range operations

[Stephen Leake]

porton@ex-code.com (Victor Porton) writes:

> Range operations (deleting the range between two iterators, inserting 
> content of a container or its subrange into a position of another 
> container etc.) are missing in current Booch. Just to make sure that 
> these are not forgotten.

By analogy with the corresponding String operators, I think these
would more properly be called "slice" operations.

-- 
-- Stephe

Re: Missing in Booch: range operations

[Matthew Heaney]

porton@ex-code.com (Victor Porton) wrote in message news:<3dcb8eec$0$307$bed64819@news.gradwell.net>...
> Range operations (deleting the range between two iterators, inserting 
> content of a container or its subrange into a position of another 
> container etc.) are missing in current Booch. Just to make sure that 
> these are not forgotten.

They were not forgotten in Charles:

  procedure Delete 
    (Container   : in out Container_Type;
     First, Back : Iterator_Type);

The list has splice operations, which are efficient because it only
swaps pointers -- there is no copying of elements:

   procedure Splice
     (Container : in out Container_Type;
      Before    : in     Iterator_Type;
      Source    : in out Container_Type);

   procedure Splice
     (Container : in out Container_Type;
      Before    : in     Iterator_Type;
      Source    : in out Container_Type;
      Iterator  : in     Iterator_Type);

   procedure Splice
     (Container : in out Container_Type;
      Before    : in     Iterator_Type;
      Source    : in out Container_Type;
      First     : in     Iterator_Type;
      Back      : in     Iterator_Type);

In the case of a vector, you can insert a single element:

   procedure Insert
     (Container : in out Container_Type;
      Before    : in     Index_Type;
      New_Item  : in     Element_Type);

If you want to copy the contents of another container into the middle
of a vector, you should first open up a "hole" in the vector:
     
   procedure Insert_N
     (Container : in out Container_Type;
      Before    : in     Index_Type'Base;
      Count     : in     Length_Subtype);

and then copy the items from the source into the newly-inserted range
(the empty hole) of the vector.

http://home.earthlink.net/~matthewjheaney/charles/index.html

There is online documention for vector which delves into some of these
issues in greater detail:

http://home.earthlink.net/~matthewjheaney/charles/charles-vectors-unbounded.html

 
> BTW, these should throw an exception if the begin and the end of the 
> range are from different containers.

The problem is that iterators only know about elements -- they don't
know anything about containers.  Neither Charles nor the STL attempts
to detect this error.

Re: Missing in Booch: range operations

[Simon Wright]

mheaney@on2.com (Matthew Heaney) writes:

> The problem is that iterators only know about elements -- they don't
> know anything about containers.  Neither Charles nor the STL attempts
> to detect this error.

Matt, you say this as though it were a law of nature! There is nothing
in the notion of iterator that prevents them knowing about the
container. Indeed (being pedantic) the very name iterator indicates
that there is a container involved (otherwise, what would you be
iterating over?)

dictionary.com says:

   iterator

   <programming> An object or routine for accessing items from a list,
   array or stream one at a time.

   By extension, the term can be used for an object or routine for
   accesing items from any data structure that can be viewed as a
   list. For example, a traverser is an iterator for tree-shaped data
   structures.

Re: Missing in Booch: range operations

[Matthew Heaney]

Simon Wright <simon@pushface.org> wrote in message news:<x7vznsizw0n.fsf@smaug.pushface.org>...
> mheaney@on2.com (Matthew Heaney) writes:
> 
> > The problem is that iterators only know about elements -- they don't
> > know anything about containers.  Neither Charles nor the STL attempts
> > to detect this error.
> 
> Matt, you say this as though it were a law of nature! There is nothing
> in the notion of iterator that prevents them knowing about the
> container. Indeed (being pedantic) the very name iterator indicates
> that there is a container involved (otherwise, what would you be
> iterating over?)

When I speak of an iterator, I am refering to what STL and Charles do.
 In that model, iterators don't know about containers.

Charles iterators are modelled on iteration thru a linked list, for
example:

  List : List_Type;

  declare
    Node : Node_Access := List.Head;
  begin
    while Node /= null loop
      <do something with Node.Element>
      Node := Node.Next;
    end loop;
  end;

In other words, the "iterator" Node_Access doesn't know anything about
the list object.  It only knows about the nodes in the list (and nodes
in the list don't know anything about the list, either).

Of course, it is possible to implement an iterator type as a "fat"
pointer, comprising a pointer to the internal node, and another
pointer to the container.  But this is not necessary in order to have
a working iterator, and it does incur a space penalty.

Charles has been optimized for flexibility and efficiency, and it is
general enough that such a layer (comprising a "fat" iterator) on top
of the existing infrastructure can be implemented quite easily.  As
much as possible I prefer to defer issues as this ("thin" vs. "fat"
iterators) to the library user.

Re: Missing in Booch: range operations

[Matthew Heaney]

porton@ex-code.com (Victor Porton) wrote in message news:<3dcb8eec$0$307$bed64819@news.gradwell.net>...
> 
> BTW, these should throw an exception if the begin and the end of the 
> range are from different containers.

Here's an analogy.  Suppose we have this:

   type T1 is access Integer;
   for T1'Storage_Pool use P1;

   type T2 is access Integer;
   for T2'Storage_Pool use P2;

   function Free2 is 
     new Unchecked_Deallocation (Integer, T2);

and now we do this:

   declare
     O1 : T1 := new Integer;
     O2 : T2 := T2 (O1);
   begin
     Free2 (O2);
   end;

Here, we allocate an object from the storage pool (P1) associated with
access type T1, but we deallocate that some object to the storage pool
(P2) associated with access type T2.

What should happen?

If your answer is "The behavior isn't defined by the language,
therefore you shouldn't do it.", then that same argument should apply
to iterator types (which are simply access types in disguise).

Re: Missing in Booch: range operations

[Victor Porton]

In article <1ec946d1.0211081307.24a6c05c@posting.google.com>,
	mheaney@on2.com (Matthew Heaney) writes:
> porton@ex-code.com (Victor Porton) wrote in message news:<3dcb8eec$0$307$bed64819@news.gradwell.net>...

>> BTW, these should throw an exception if the begin and the end of the 
>> range are from different containers.
> 
> The problem is that iterators only know about elements -- they don't
> know anything about containers.  Neither Charles nor the STL attempts
> to detect this error.

For some classes of containers e.g. for linked lists it is
possible: throw an exception if te end of list reached
(actually Ada compilers will throw these "automagically").

A good thing to have a debug version where iterators "know"
about containers.

See www.STLport.org for an C++ STL with extensive debugging.

Re: Missing in Booch: range operations

[Matthew Heaney]

porton@ex-code.com (Victor Porton) wrote in message news:<3dcccf4d$0$308$bed64819@news.gradwell.net>...
> 
> For some classes of containers e.g. for linked lists it is
> possible: throw an exception if te end of list reached
> (actually Ada compilers will throw these "automagically").

Yes, that's true, but the problem is that you don't always iterate to
the back of the container, ie

   I : Iterator_Type := Find_X (First (C), Back (C));
   J : Iterator_Type := Find_Not_X (I, Back (C));
begin
   while I /= J loop 

In this example iterator J probably does *not* designate the end of
the container.

 
> A good thing to have a debug version where iterators "know"
> about containers.

If there's interest, I could always supply checked versions, that
implement the iterators and the containers with whatever extra state
is necessary to check that the iterators are being used properly.


> See www.STLport.org for an C++ STL with extensive debugging.

Yes, I am familiar with this implementation.  Perhaps we could use
this as a model to build a debug version of Charles.

Re: Missing in Booch: range operations

[Stephen Leake]

mheaney@on2.com (Matthew Heaney) writes:

> If there's interest, I could always supply checked versions, that
> implement the iterators and the containers with whatever extra state
> is necessary to check that the iterators are being used properly.

That was one of the requirements for Grace lists; it turned out to be
hard to implement (at least for me :). Building it on the current
Charles list package would be a good idea, since it ended up requiring
a couple of internal lists to keep track of everything.

-- 
-- Stephe

Re: Missing in Booch: range operations

[Victor Porton]

In article <1ec946d1.0211081335.6b2ac730@posting.google.com>,
	mheaney@on2.com (Matthew Heaney) writes:
> porton@ex-code.com (Victor Porton) wrote in message news:<3dcb8eec$0$307$bed64819@news.gradwell.net>...
> Here's an analogy.  Suppose we have this:

Analogously to pool specific access types we can create container 
_instance_ specific iterators! It may be useful against mistakes.

generic
  For_Container: in out Containers_Library.Container_Type;
package Container_Instance is
  Container: Containers_Library.Container_Type renames For_Container;
  type Iterator is new Containers_Library.Iterator;
  function New_Iterator return Iterator;
end;

generic
  Container: in out Containers_Library.Container_Type;
package body Container_Instance is
  function New_Iterator return Iterator is
  begin
    return Containers_Library.New_Iterator(Container);
  end;
end;

I suggest you to put something such in your libraries:
at least no harm from it.

Well, Simon and Charles, are you likely to accept my
possible patches like this?

Re: Missing in Booch: range operations

[Simon Wright]

porton@ex-code.com (Victor Porton) writes:

> generic
>   For_Container: in out Containers_Library.Container_Type;
> package Container_Instance is
>   Container: Containers_Library.Container_Type renames For_Container;
>   type Iterator is new Containers_Library.Iterator;
>   function New_Iterator return Iterator;
> end;

I don't at first see how to do this in the BCs, where the
Container_Type and Iterator (BTW, if you are going to say
Container_Type, eew, why not Iterator_Type?) are abstract ..

but there would be no point anyway unless I make the major change of
supporting the STL/Charles view of iteration, and the likelihood of
that is minimal.

Re: Missing in Booch: range operations

[Simon Wright]

porton@ex-code.com (Victor Porton) writes:

> Range operations (deleting the range between two iterators, inserting 
> content of a container or its subrange into a position of another 
> container etc.) are missing in current Booch. Just to make sure that 
> these are not forgotten.

They are missing from the BCs because they were not in the C++ BCs of
which the Ada BCs are a translation. (I am on somewhat weak ground
here, because the C++ iterators were defined in the concrete
containers, somewhat like Charles).

I don't think you can rely even on "=" being meaningfully defined for
present BC iterators -- indeed, having more than one iterator over a
container is odd, and dangerous if you use Delete_Item_At.

> BTW, these should throw an exception if the begin and the end of the 
> range are from different containers.

Now that I can agree with, though there are arguments the other way.

Re: Missing in Booch: range operations

[Victor Porton]

In article <x7vr8duzvba.fsf@smaug.pushface.org>,
	Simon Wright <simon@pushface.org> writes:
> porton@ex-code.com (Victor Porton) writes:
> 
>> generic
>>   For_Container: in out Containers_Library.Container_Type;
>> package Container_Instance is
>>   Container: Containers_Library.Container_Type renames For_Container;
>>   type Iterator is new Containers_Library.Iterator;
>>   function New_Iterator return Iterator;
>> end;
> 
> I don't at first see how to do this in the BCs, where the
> Container_Type and Iterator (BTW, if you are going to say
> Container_Type, eew, why not Iterator_Type?) are abstract ..
> 
> but there would be no point anyway unless I make the major change of
> supporting the STL/Charles view of iteration, and the likelihood of
> that is minimal.

I don't understand what is "the STL/Charles view of iteration" and
why you don't want add my code.

In the first letter I've written just a rough template (for both
Booch and Charles) which is something like Booch, but not Booch.
Now the code for Booch (not checked for errors!):

generic
  For_Container: in out BC.Containers.Container'Class;
package BC.Containers.Container_Instance is
  Container: BC.Containers.Container'Class renames For_Container;
  type Iterator is new BC.Containers.Iterator;
  function New_Iterator return Iterator'Class;
end;

generic
  For_Container: in out BC.Containers.Container'Class;
package body BC.Containers.Container_Instance is
  function New_Iterator return Iterator'Class is
  begin
    return Iterator'Class(BC.Containers.New_Iterator(Container));
  end;
end;

Re: Missing in Booch: range operations

[Simon Wright]

porton@ex-code.com (Victor Porton) writes:

> I don't understand what is "the STL/Charles view of iteration" and

I meant, the idea that two iterators designate a range within a
container over which some algorithm is to be applied.

> why you don't want add my code.

It would help if it compiled ..

> In the first letter I've written just a rough template (for both
> Booch and Charles) which is something like Booch, but not Booch.
> Now the code for Booch (not checked for errors!):
> 
> generic
>   For_Container: in out BC.Containers.Container'Class;
> package BC.Containers.Container_Instance is
>   Container: BC.Containers.Container'Class renames For_Container;
>   type Iterator is new BC.Containers.Iterator;
>   function New_Iterator return Iterator'Class;
> end;
> 
> generic
>   For_Container: in out BC.Containers.Container'Class;
> package body BC.Containers.Container_Instance is
>   function New_Iterator return Iterator'Class is
>   begin
>     return Iterator'Class(BC.Containers.New_Iterator(Container));
>   end;
> end;

The first 2 lines of the package body are clearly wrong.

This modified code nearly compiles:

   with BC.Containers;
   generic
      with package Containers_Base is new BC.Containers (<>);
      For_Container : in out Containers_Base.Container'Class;
   package BC.Containers.Container_Instance is
      Container : Containers_Base.Container'Class renames For_Container;
      type Iterator is new Containers_Base.Iterator with private;
      function New_Iterator return Iterator'Class;
   private
      type Iterator is new Containers_Base.Iterator with null record;
   end BC.Containers.Container_Instance;

   package body BC.Containers.Container_Instance is
      function New_Iterator return Iterator'Class is
      begin
         return Iterator'Class (Containers_Base.New_Iterator (Container));
      end;
   end BC.Containers.Container_Instance;

but fails with

   bc-containers-container_instance.ads:10:09: type must be declared
   abstract or "RESET" overridden

and when you think about it it's hard to see how this type Iterator
could be of any use (the concrete iterators in BCs are derived from
BC.Containers.Iterator, not from this new one).

I suppose it could contain a record with an actual iterator .. but
then that would have to be a Containers_Base.Iterator'Class, and we
know that won't work ..

Re: Missing in Booch: range operations

[Victor Porton]

In article <x7vd6pe344s.fsf@smaug.pushface.org>,
	Simon Wright <simon@pushface.org> writes:
> porton@ex-code.com (Victor Porton) writes:
> 
>> I don't understand what is "the STL/Charles view of iteration" and
> 
> I meant, the idea that two iterators designate a range within a
> container over which some algorithm is to be applied.

You cause me to wonder that you don't want accept this!

Programmers often need to deal with a range of elements of
a container. I now deal with exactly this (modifying a
HTML stream I consider parts of a HTML element as ranges in
the buffer to which I read from a file).

In any case I use this range, but now I just designate it by
natural numbers instead of iterators.

Well, e.g. many sorting algorithms deal with ranges.

Why?!!

> This modified code nearly compiles:
> 
>    with BC.Containers;
>    generic
>       with package Containers_Base is new BC.Containers (<>);
>       For_Container : in out Containers_Base.Container'Class;
>    package BC.Containers.Container_Instance is
>       Container : Containers_Base.Container'Class renames For_Container;
>       type Iterator is new Containers_Base.Iterator with private;
>       function New_Iterator return Iterator'Class;
>    private
>       type Iterator is new Containers_Base.Iterator with null record;
>    end BC.Containers.Container_Instance;
> 
>    package body BC.Containers.Container_Instance is
>       function New_Iterator return Iterator'Class is
>       begin
>          return Iterator'Class (Containers_Base.New_Iterator (Container));
>       end;
>    end BC.Containers.Container_Instance;
> 
> but fails with
> 
>    bc-containers-container_instance.ads:10:09: type must be declared
>    abstract or "RESET" overridden
> 
> and when you think about it it's hard to see how this type Iterator
> could be of any use (the concrete iterators in BCs are derived from
> BC.Containers.Iterator, not from this new one).

I don't see your point about how this scheme of derivation would 
disturb its use.

P.S. I want iterator ranges. May be I will even create modified
version of Booch at SourceForge. I think this split would not
cause any harm to the community as in any case we now only in the
process of standartization of Ada Standard Containers.

Re: Missing in Booch: range operations

[Simon Wright]

porton@ex-code.com (Victor Porton) writes:

> P.S. I want iterator ranges. May be I will even create modified
> version of Booch at SourceForge. I think this split would not cause
> any harm to the community as in any case we now only in the process
> of standartization of Ada Standard Containers.

If you want iterator ranges, why don't you try Charles which already
has them? (of course you are free to fork the BCs if you wish).

Re: Missing in Booch: range operations

[Victor Porton]

In article <x7vvg34zk1v.fsf@smaug.pushface.org>,
	Simon Wright <simon@pushface.org> writes:
> porton@ex-code.com (Victor Porton) writes:
> 
> If you want iterator ranges, why don't you try Charles which already
> has them? (of course you are free to fork the BCs if you wish).

The main problem with Charles now is missing documentation.

Re: Missing in Booch: range operations

[Matthew Heaney]

porton@ex-code.com (Victor Porton) wrote in message news:<3dcf6534$0$299$bed64819@news.gradwell.net>...
> 
> The main problem with Charles now is missing documentation.

There is online documentation for the vector:

http://home.earthlink.net/~matthewjheaney/charles/
charles-vectors-unbounded.html

I am actively working on documenting existing containers, and
implementing new ones.

For now, you can either extrapolate from the vector docs, or read an
STL book, or visit the SGI website.

Re: Missing in Booch: range operations

[Stephen Leake]

mheaney@on2.com (Matthew Heaney) writes:

> porton@ex-code.com (Victor Porton) wrote in message
> news:<3dcf6534$0$299$bed64819@news.gradwell.net>... 
> > 
> > The main problem with Charles now is missing documentation.
> 
> For now, you can either extrapolate from the vector docs, or read an
> STL book, or visit the SGI website.

Or write some documentation!

-- 
-- Stephe