* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
@ 2002-11-08 15:01 ` Stephen Leake
2002-11-08 21:07 ` Matthew Heaney
` (7 subsequent siblings)
8 siblings, 0 replies; 19+ messages in thread
From: Stephen Leake @ 2002-11-08 15:01 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
2002-11-08 15:01 ` Stephen Leake
@ 2002-11-08 21:07 ` Matthew Heaney
2002-11-09 13:56 ` Simon Wright
2002-11-08 21:35 ` Matthew Heaney
` (6 subsequent siblings)
8 siblings, 1 reply; 19+ messages in thread
From: Matthew Heaney @ 2002-11-08 21:07 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 21:07 ` Matthew Heaney
@ 2002-11-09 13:56 ` Simon Wright
2002-11-13 20:17 ` Matthew Heaney
0 siblings, 1 reply; 19+ messages in thread
From: Simon Wright @ 2002-11-09 13:56 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-09 13:56 ` Simon Wright
@ 2002-11-13 20:17 ` Matthew Heaney
0 siblings, 0 replies; 19+ messages in thread
From: Matthew Heaney @ 2002-11-13 20:17 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
2002-11-08 15:01 ` Stephen Leake
2002-11-08 21:07 ` Matthew Heaney
@ 2002-11-08 21:35 ` Matthew Heaney
2002-11-09 8:24 ` Victor Porton
` (5 subsequent siblings)
8 siblings, 0 replies; 19+ messages in thread
From: Matthew Heaney @ 2002-11-08 21:35 UTC (permalink / raw)
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).
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
` (2 preceding siblings ...)
2002-11-08 21:35 ` Matthew Heaney
@ 2002-11-09 8:24 ` Victor Porton
2002-11-13 20:22 ` Matthew Heaney
2002-11-09 8:46 ` Victor Porton
` (4 subsequent siblings)
8 siblings, 1 reply; 19+ messages in thread
From: Victor Porton @ 2002-11-09 8:24 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-09 8:24 ` Victor Porton
@ 2002-11-13 20:22 ` Matthew Heaney
2002-11-13 22:28 ` Stephen Leake
0 siblings, 1 reply; 19+ messages in thread
From: Matthew Heaney @ 2002-11-13 20:22 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-13 20:22 ` Matthew Heaney
@ 2002-11-13 22:28 ` Stephen Leake
0 siblings, 0 replies; 19+ messages in thread
From: Stephen Leake @ 2002-11-13 22:28 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
` (3 preceding siblings ...)
2002-11-09 8:24 ` Victor Porton
@ 2002-11-09 8:46 ` Victor Porton
2002-11-09 14:12 ` Simon Wright
2002-11-09 14:04 ` Simon Wright
` (3 subsequent siblings)
8 siblings, 1 reply; 19+ messages in thread
From: Victor Porton @ 2002-11-09 8:46 UTC (permalink / raw)
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?
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-09 8:46 ` Victor Porton
@ 2002-11-09 14:12 ` Simon Wright
0 siblings, 0 replies; 19+ messages in thread
From: Simon Wright @ 2002-11-09 14:12 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
` (4 preceding siblings ...)
2002-11-09 8:46 ` Victor Porton
@ 2002-11-09 14:04 ` Simon Wright
2002-11-09 16:12 ` Victor Porton
` (2 subsequent siblings)
8 siblings, 0 replies; 19+ messages in thread
From: Simon Wright @ 2002-11-09 14:04 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
` (5 preceding siblings ...)
2002-11-09 14:04 ` Simon Wright
@ 2002-11-09 16:12 ` Victor Porton
2002-11-09 20:00 ` Simon Wright
2002-11-11 5:41 ` Victor Porton
2002-11-11 7:50 ` Victor Porton
8 siblings, 1 reply; 19+ messages in thread
From: Victor Porton @ 2002-11-09 16:12 UTC (permalink / raw)
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;
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-09 16:12 ` Victor Porton
@ 2002-11-09 20:00 ` Simon Wright
0 siblings, 0 replies; 19+ messages in thread
From: Simon Wright @ 2002-11-09 20:00 UTC (permalink / raw)
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 ..
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
` (6 preceding siblings ...)
2002-11-09 16:12 ` Victor Porton
@ 2002-11-11 5:41 ` Victor Porton
2002-11-11 6:39 ` Simon Wright
2002-11-11 7:50 ` Victor Porton
8 siblings, 1 reply; 19+ messages in thread
From: Victor Porton @ 2002-11-11 5:41 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-11 5:41 ` Victor Porton
@ 2002-11-11 6:39 ` Simon Wright
0 siblings, 0 replies; 19+ messages in thread
From: Simon Wright @ 2002-11-11 6:39 UTC (permalink / raw)
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).
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Missing in Booch: range operations
2002-11-08 10:09 Missing in Booch: range operations Victor Porton
` (7 preceding siblings ...)
2002-11-11 5:41 ` Victor Porton
@ 2002-11-11 7:50 ` Victor Porton
2002-11-13 20:26 ` Matthew Heaney
8 siblings, 1 reply; 19+ messages in thread
From: Victor Porton @ 2002-11-11 7:50 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 19+ messages in thread