Containers: The iterator object
jacob navia
I think it is important that the user code stays as abstract as
possible, without getting into the specifics of any container, as Mr
Becarisse said (if I remember correctly).
Well, this could be done as follows. Please tell me what do you think.
Thanks
--------
All containers should be able to support the "GetNext" and the
"GetPrevious" functions. A "Rewind" operation resets the
iterator object to be reused with the same container.
To iterate ANY container from your user code you do:
Iterator *it = Container->Vtable->StartIterator(Container);
then:
void *object;
for (object = it->GetNext();
object != NULL;
object = it->GetNext()) {
// use the object
}
The iterator object is as follows:
typedef struct tagIterator {
/* Public (Required) fields */
void *(*GetNext)(void);
void *(*GetPrevious)(void);
void (*Rewind)(void);
/* Private fields follow, specific to each container
Here implementations store a pointer to the container
being iterated, the current index, whatever they need
*/
} Iterator;
For a single linked list, GetPrevious can return always NULL
(performance is really bad if you have a long list) or it can
supply the previous by going through the list at all times.
Containers are good for some operations but bad for others.
For hash tables or trees, GetNext() returns the "next" object in
an unspecified sequence that is guaranteed however to visit all elements
and return NULL when all elements have been visited.
Beides, a new operation is added to all containers:
Container->Vtable->StoreCurrent(Iterator *it,void *element);
All this operations take always the container itself as the first
argument. In this case it is unnecessary since the iterator already
has this information.
I do not know if this incoherence is a good idea...
jacob
Willem
) In the last discussion we discussed how to do "GetNext" etc with containers.
)
) I think it is important that the user code stays as abstract as
) possible, without getting into the specifics of any container, as Mr
) Becarisse said (if I remember correctly).
)
) Well, this could be done as follows. Please tell me what do you think.
)
) Thanks
)
) --------
)
)
) All containers should be able to support the "GetNext" and the
) "GetPrevious" functions. A "Rewind" operation resets the
) iterator object to be reused with the same container.
)
) To iterate ANY container from your user code you do:
)
) Iterator *it = Container->Vtable->StartIterator(Container);
)
) then:
) void *object;
) for (object = it->GetNext();
) object != NULL;
) object = it->GetNext()) {
) // use the object
) }
Wouldn't the following be cleaner:
for (object = it->GetFirst(); object; object = it->GetNext()) {
/* ... */
}
GetFirst() would then take the place of Rewind().
By the way, your for loop is equivalent to:
while (object = it->GetNext()) {
/* ... */
}
Isn't it ?
I could work with that as well.
Both could work if GetFirst() was defined as ''Rewind(); GetNext();''
) For a single linked list, GetPrevious can return always NULL
) (performance is really bad if you have a long list) or it can
) supply the previous by going through the list at all times.
) Containers are good for some operations but bad for others.
You should have it go through the list at all times, I think.
Otherwise you have a function that works some of the time, which
I personally don't think is very appropriate for a generic interface.
) For hash tables or trees, GetNext() returns the "next" object in
) an unspecified sequence that is guaranteed however to visit all elements
) and return NULL when all elements have been visited.
This raises the question: what happens if an element is added or removed
while an iterator is in effect ? You could simply call it 'undefined
behaviour' unless it's the 'current' item. (Like an SQL cursor, or Perl).
) Beides, a new operation is added to all containers:
)
) Container->Vtable->StoreCurrent(Iterator *it,void *element);
In light of the above, a 'DeleteCurrent' would be advisable as well.
) All this operations take always the container itself as the first
) argument. In this case it is unnecessary since the iterator already
) has this information.
)
) I do not know if this incoherence is a good idea...
Incoherence ? You mean not passing the object as first parameter ?
I don't really think the iterator has this information, actually.
It does need a pointer to its own iterator struct, doesn't it ?
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Eric Sosman
> In the last discussion we discussed how to do "GetNext" etc with
> containers.
>
> I think it is important that the user code stays as abstract as
> possible, without getting into the specifics of any container, as Mr
> Becarisse said (if I remember correctly).
>
> Well, this could be done as follows. Please tell me what do you think.
Don't forget to describe what happens if the content of
the container changes while an iteration is in progress. Some
possibilities (by no means exhaustive):
- A content change implicitly rewinds all iterators (or
fast-forwards them to "The End").
- A content change puts all iterators into a "null state,"
where attempts to navigate forward or backward indicate
"nothing there."
- A content change puts all iterators into an "error state,"
where all navigation attempts report a failure condition.
(This is, more or less, how Java's iterators behave.)
- A content change puts all iterators into an undefined
state and wakes up the nasal demons.
Note that the policy of "Content changes don't disturb existing
iterators" runs into both practical and definitional difficulties.
For example, if an iterator returns item X and is then asked for
the next item, we'd like to say it returns X's successor -- but if
X has been removed in the meantime, "X's successor" becomes a bit
nebulous ...
To allow for "filtering" operations, where you iterate over
the contents and either keep or discard each item as you come to
it, Java's iterators have a "remove the most recently returned
item" operation that leaves things in a well-defined state. You
might want to consider something similar.
--
Eric Sosman
eso...@ieee-dot-org.invalid
jacob navia
[snip]
> GetFirst() would then take the place of Rewind().
>
That is a great idea. Thanks a lot. GetFirst() is just
Rewind().
> By the way, your for loop is equivalent to:
>
> while (object = it->GetNext()) {
> /* ... */
> }
>
> Isn't it ?
Yes.
> I could work with that as well.
> Both could work if GetFirst() was defined as ''Rewind(); GetNext();''
>
Yes. Let's agree that GetFirst() is rewind.
>
> ) For a single linked list, GetPrevious can return always NULL
> ) (performance is really bad if you have a long list) or it can
> ) supply the previous by going through the list at all times.
> ) Containers are good for some operations but bad for others.
>
> You should have it go through the list at all times, I think.
> Otherwise you have a function that works some of the time, which
> I personally don't think is very appropriate for a generic interface.
>
Yes. But that should be implementation defined. There *could* be some
container that just never supports GetPrevious() for whatever reasons.
> ) For hash tables or trees, GetNext() returns the "next" object in
> ) an unspecified sequence that is guaranteed however to visit all elements
> ) and return NULL when all elements have been visited.
>
> This raises the question: what happens if an element is added or removed
> while an iterator is in effect ? You could simply call it 'undefined
> behaviour' unless it's the 'current' item. (Like an SQL cursor, or Perl).
Each iterator should have the timestamp counter of the last modification
of its container. When it accesses its container, it reads the time
stamp. If it is bigger it means the container has been modified AFTER
the iterator was created and it stops iterating.
The "time stamp" is just a counter that gets incremented at each
modification.
>
> ) Beides, a new operation is added to all containers:
> )
> ) Container->Vtable->StoreCurrent(Iterator *it,void *element);
>
> In light of the above, a 'DeleteCurrent' would be advisable as well.
Probably yes.
>
> ) All this operations take always the container itself as the first
> ) argument. In this case it is unnecessary since the iterator already
> ) has this information.
> )
> ) I do not know if this incoherence is a good idea...
>
> Incoherence ? You mean not passing the object as first parameter ?
> I don't really think the iterator has this information, actually.
> It does need a pointer to its own iterator struct, doesn't it ?
Yes, this is a bug in the above specs (that you discovered) Of course it
needs a pointer to its own structure All those functions (GetNext()
aren't void but should take a pointer to the iterator structure.
Thanks a lot for your help.
>
>
> SaSW, Willem
Ian Collins
> On 3/20/2010 3:59 PM, jacob navia wrote:
>> In the last discussion we discussed how to do "GetNext" etc with
>> containers.
>>
>> I think it is important that the user code stays as abstract as
>> possible, without getting into the specifics of any container, as Mr
>> Becarisse said (if I remember correctly).
>>
>> Well, this could be done as follows. Please tell me what do you think.
>> [...]
>
> Don't forget to describe what happens if the content of
> the container changes while an iteration is in progress. Some
> possibilities (by no means exhaustive):
>
> - A content change implicitly rewinds all iterators (or
> fast-forwards them to "The End").
>
> - A content change puts all iterators into a "null state,"
> where attempts to navigate forward or backward indicate
> "nothing there."
>
> - A content change puts all iterators into an "error state,"
> where all navigation attempts report a failure condition.
> (This is, more or less, how Java's iterators behave.)
The first 3 are at best impractical due to the overheads they would
incur, or down right impossible. How do you tack copies of iterators?
> - A content change puts all iterators into an undefined
> state and wakes up the nasal demons.
Probably the only practical option!
> Note that the policy of "Content changes don't disturb existing
> iterators" runs into both practical and definitional difficulties.
> For example, if an iterator returns item X and is then asked for
> the next item, we'd like to say it returns X's successor -- but if
> X has been removed in the meantime, "X's successor" becomes a bit
> nebulous ...
A nasal demon?
--
Ian Collins
jacob navia
> On 3/20/2010 3:59 PM, jacob navia wrote:
>> In the last discussion we discussed how to do "GetNext" etc with
>> containers.
>>
>> I think it is important that the user code stays as abstract as
>> possible, without getting into the specifics of any container, as Mr
>> Becarisse said (if I remember correctly).
>>
>> Well, this could be done as follows. Please tell me what do you think.
>> [...]
>
> Don't forget to describe what happens if the content of
> the container changes while an iteration is in progress. Some
> possibilities (by no means exhaustive):
>
> - A content change implicitly rewinds all iterators (or
> fast-forwards them to "The End").
>
> - A content change puts all iterators into a "null state,"
> where attempts to navigate forward or backward indicate
> "nothing there."
>
Each container has a "modified" time stamp. When an iterator is created
this timestamp is copied into it. If when accessing the container the
iterator notices that the time stamps has increased it stops iterating.
Simple, economic and powerful.
Just C. The time stamp is just a counter of modifications done to
the iterator. To invalidate all iterators to an object you just
set that counter to zero.
> Note that the policy of "Content changes don't disturb existing
> iterators" runs into both practical and definitional difficulties.
> For example, if an iterator returns item X and is then asked for
> the next item, we'd like to say it returns X's successor -- but if
> X has been removed in the meantime, "X's successor" becomes a bit
> nebulous ...
>
> To allow for "filtering" operations, where you iterate over
> the contents and either keep or discard each item as you come to
> it, Java's iterators have a "remove the most recently returned
> item" operation that leaves things in a well-defined state. You
> might want to consider something similar.
>
Yes, that is useful. Thanks
Keith Thompson
> Eric Sosman a écrit :
[...]
>> Don't forget to describe what happens if the content of
>> the container changes while an iteration is in progress. Some
>> possibilities (by no means exhaustive):
>>
>> - A content change implicitly rewinds all iterators (or
>> fast-forwards them to "The End").
>>
>> - A content change puts all iterators into a "null state,"
>> where attempts to navigate forward or backward indicate
>> "nothing there."
>>
>
> Each container has a "modified" time stamp. When an iterator is created
> this timestamp is copied into it. If when accessing the container the
> iterator notices that the time stamps has increased it stops iterating.
So far, it sounds like you're depending on the ability to generate
timestamps sufficiently fine-grained that they're guaranteed to chgane
between operations on iterators. But ...
> Simple, economic and powerful.
>
> Just C. The time stamp is just a counter of modifications done to
> the iterator. To invalidate all iterators to an object you just
> set that counter to zero.
Then I wouldn't call it a time stamp.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
bartc
"Keith Thompson" <ks...@mib.org> wrote in message
news:ln634q5...@nuthaus.mib.org...
> jacob navia <ja...@jacob.remcomp.fr> writes:
>> Just C. The time stamp is just a counter of modifications done to
>> the iterator. To invalidate all iterators to an object you just
>> set that counter to zero.
>
> Then I wouldn't call it a time stamp.
A sequence or serial number.
But still, sounds like a solution to something that may not be a problem.
How often is this done on other data structures in C?
What happens if the container is completely destroyed between one iteration
and another? To solve all the problems, you have to turn it into a file
system almost.
--
Bartc
Ian Collins
>
> Each container has a "modified" time stamp. When an iterator is created
> this timestamp is copied into it. If when accessing the container the
> iterator notices that the time stamps has increased it stops iterating.
>
> Simple, economic and powerful.
>
> Just C. The time stamp is just a counter of modifications done to
> the iterator. To invalidate all iterators to an object you just
> set that counter to zero.
What happens if you copy an iterator?
--
Ian Collins
jacob navia
have the same time stamp, and if the object has changed it will detect
that.
But in general I haven't addressed the copy of containers yet. Ideally
you should have a Copy method that makes a deep copy and knows
the specific shape of each container
Eric Sosman
> On 03/21/10 10:31 AM, Eric Sosman wrote:
>> On 3/20/2010 3:59 PM, jacob navia wrote:
>>> In the last discussion we discussed how to do "GetNext" etc with
>>> containers.
>>>
>>> I think it is important that the user code stays as abstract as
>>> possible, without getting into the specifics of any container, as Mr
>>> Becarisse said (if I remember correctly).
>>>
>>> Well, this could be done as follows. Please tell me what do you think.
>>> [...]
>>
>> Don't forget to describe what happens if the content of
>> the container changes while an iteration is in progress. Some
>> possibilities (by no means exhaustive):
>>
>> - A content change implicitly rewinds all iterators (or
>> fast-forwards them to "The End").
>>
>> - A content change puts all iterators into a "null state,"
>> where attempts to navigate forward or backward indicate
>> "nothing there."
>>
>> - A content change puts all iterators into an "error state,"
>> where all navigation attempts report a failure condition.
>> (This is, more or less, how Java's iterators behave.)
>
> The first 3 are at best impractical due to the overheads they would
> incur, or down right impossible. How do you tack copies of iterators?
You don't, but you don't need to. Keep a "change counter"
in the collection, incremented each time something is inserted
or removed. Copy the counter into the iterator when the iterator
is created. Each time the iterator is used, compare its count
to the collection's count; a mismatch means Danger, Will Robinson!
(Of course, there's always counter overflow or wrap-around
to worry about. If somebody makes, say, exactly four gigachanges
to the collection between one use of an iterator and the next, it
might go undetected. Use umaxint_t if this is a concern; a CPU
with a teraHertz clock frequency would take seven months just to
count that high, never mind make that many insertions/removals.)
--
Eric Sosman
eso...@ieee-dot-org.invalid
Andrew Poelstra
I think the iterator object itself should have a Delete() method,
as well as InsertBefore() and InsertAfter().
I'm not sure what should be done to all the other iterators when
one of them modifies the container, though.
--
Andrew Poelstra
http://www.wpsoftware.net/andrew
jacob navia
>
> I think the iterator object itself should have a Delete() method,
> as well as InsertBefore() and InsertAfter().
Yes, they could be useful. Another method that was missing in my design
was:
container->Vtable->DisposeIterator(container,iterator);
that would free the iterator allocated with newIterator...
>
> I'm not sure what should be done to all the other iterators when
> one of them modifies the container, though.
>
All other iterators over the same container become invalid
instantaneusly and will always return NULL. As I proposed yesterday
a modification counter is established in all containers. When accessing
its container, an iterator tests if this counter is higher than
the value it got when created. If yes, then it returns NULL.
Ian Collins
> Andrew Poelstra a écrit :
>
>>
>> one of them modifies the container, though.
>
> All other iterators over the same container become invalid
> instantaneusly and will always return NULL. As I proposed yesterday
> a modification counter is established in all containers. When accessing
> its container, an iterator tests if this counter is higher than
> the value it got when created. If yes, then it returns NULL.
Won't that be a problem if an iterator is being used to scan a container
and remove selected elements? It would become invalid after the first
removal.
--
Ian Collins
Ian Collins
Potential danger, but in many case the iterator would still be valid.
Attempting to define and support those cases would be a nightmare. For
example the iterator would still be valid after items have been inserted
or removed in front of or behind it.
--
Ian Collins
jacob navia
Yes, that is why I will add the Remove() method to iterators.
I am not sure about InsertAfter/InsertBefore.
Of course that allows you to remove the object pointed to by the
current iterator. All OTHER iterators are invalid
jacob navia
The iterator is still "valid" but will always return NULL. It just
doesn't matter.
jacob
Ian Collins
> Ian Collins a écrit :
I though returning NULL indicated that the iterator is at the end of the
container?
How you you use an iterator to insert some values form one container
into another?
--
Ian Collins
jacob navia
You need two iterators for that. Each iterator points to its container.
I will add a replace/delete/ method that will use the current object
(the one pointed to by the iterator) to change it.
Phil Carmody
> "Keith Thompson" <ks...@mib.org> wrote in message
> news:ln634q5...@nuthaus.mib.org...
>> jacob navia <ja...@jacob.remcomp.fr> writes:
>
>>> Just C. The time stamp is just a counter of modifications done to
>>> the iterator. To invalidate all iterators to an object you just
>>> set that counter to zero.
>>
>> Then I wouldn't call it a time stamp.
>
> A sequence or serial number.
>
> But still, sounds like a solution to something that may not be a
> problem. How often is this done on other data structures in C?
How does strtok protect against you changing the string it's
working on? Not at all. The primitives are by design very
primitive - all bells and whistles are to be bolted on ad hoc.
> What happens if the container is completely destroyed between one
> iteration and another? To solve all the problems, you have to turn it
> into a file system almost.
Rather start client counting.
File systems are notorious for suffering from these problems too,
they don't necessarily solve the problem, merely move it into a
different domain.
Phil
--
I find the easiest thing to do is to k/f myself and just troll away
-- David Melville on r.a.s.f1
jacob navia
> On 03/22/10 10:19 AM, jacob navia wrote:
>> The iterator is still "valid" but will always return NULL. It just
>> doesn't matter.
>
> I though returning NULL indicated that the iterator is at the end of the
> container?
>
Actually it will call the currently defined error function with the
error "CONTAINER_ERROR_OBJECT_CHANGED". If that function returns (and
doesn't abort the program) the iterator returns NULL.
Ian Collins
Then I think that's wrong. It is one reason why I said it would be a
nightmare defining the operations that do and don't invalidate an iterator.
--
Ian Collins
jacob navia
> On 03/22/10 10:44 PM, jacob navia wrote:
>>> On 03/22/10 10:19 AM, jacob navia wrote:
>>>> The iterator is still "valid" but will always return NULL. It just
>>>> doesn't matter.
>>>
>>> I though returning NULL indicated that the iterator is at the end of
>>> the container?
>>>
>>
>> Actually it will call the currently defined error function with the
>> error "CONTAINER_ERROR_OBJECT_CHANGED". If that function returns (and
>> doesn't abort the program) the iterator returns NULL.
>
> Then I think that's wrong.
Of course! I am ALWAYS wrong :-)
But maybe you care to explain why?
Thanks
It is one reason why I said it would be a
> nightmare defining the operations that do and don't invalidate an iterator.
>
It is very simple. ALL operations that modify the container other
than through the iterator invalidate all iterators to that container.
When you use an iterator over a container, you are allowed to
o Read anything even from different iterators.
o Write through a single iterator. THAT iterator (the one you use
to modify the container) is NOT invalidated. ALL others are.
This is different to C++ where the rules go for pages and pages.
Eric Sosman
> On 03/22/10 03:07 AM, Eric Sosman wrote:
>> in the collection, incremented each time something is inserted
>> or removed. Copy the counter into the iterator when the iterator
>> is created. Each time the iterator is used, compare its count
>> to the collection's count; a mismatch means Danger, Will Robinson!
>
> Potential danger, but in many case the iterator would still be valid.
> Attempting to define and support those cases would be a nightmare. For
> example the iterator would still be valid after items have been inserted
> or removed in front of or behind it.
Perhaps I'm over-generalizing, but I assumed the notion of
"iterator" was intended to extend to all containers, not just
ordered containers. For example, if insertion or deletion causes
a hash table to reorganize while an iteration is in progress,
things get hairy.
--
Eric Sosman
eso...@ieee-dot-org.invalid
jacob navia
The rule is very easy
If you change the contents of a container, all iterators to it are invalid
and will call the error routine.
The only changes are allowed through the iterator you are using. You can delete
and replace items, or add before/after if it is a sequential container. If you
do this, any OTHER iterators are invalidatee of course, but not the iterator you use
to do the change.
Andrew Poelstra
I think that as far as modifying lists while iterators are active
goes, you are simply Not Supposed To Do That. Jacob is trying to
make sure that if you do, something consistent will happen, even
if that's something potentially confusing.
Eric Sosman
> Eric Sosman a écrit :
>> On 3/21/2010 5:01 PM, Ian Collins wrote:
>>> On 03/22/10 03:07 AM, Eric Sosman wrote:
>>>> [...] Keep a "change counter"
>>>> in the collection, incremented each time something is inserted
>>>> or removed. Copy the counter into the iterator when the iterator
>>>> is created. Each time the iterator is used, compare its count
>>>> to the collection's count; a mismatch means Danger, Will Robinson!
>>>
>>> Potential danger, but in many case the iterator would still be valid.
>>> Attempting to define and support those cases would be a nightmare. For
>>> example the iterator would still be valid after items have been inserted
>>> or removed in front of or behind it.
>>
>> Perhaps I'm over-generalizing, but I assumed the notion of
>> "iterator" was intended to extend to all containers, not just
>> ordered containers. For example, if insertion or deletion causes
>> a hash table to reorganize while an iteration is in progress,
>> things get hairy.
>>
>
> The rule is very easy
... though the implementation may not be.
> If you change the contents of a container, all iterators to it are invalid
> and will call the error routine.
That's the easy part.
> The only changes are allowed through the iterator you are using. You can
> delete
> and replace items, or add before/after if it is a sequential container.
> If you
> do this, any OTHER iterators are invalidatee of course, but not the
> iterator you use
> to do the change.
That's the hard part. FWIW, Java dodges the problem for hash
tables by (1) permitting only deletions during iteration, not
insertions, and (2) re-hashing only when a table grows, not when
items are removed. Thus, an iterator can be sure that the table
will not re-hash itself during iteration. If reorganizations could
occur, keeping the iteration sane would (it seems to me) be a good
deal more difficult.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Ian Collins
Fair enough.
--
Ian Collins
Andrew Poelstra
Having said that, I just realized that since doing this is
(maybe) a programming error, there should be a flag in the
iterator that can be checked with assert().
Ian Collins
> Ian Collins a écrit :
>> On 03/22/10 10:44 PM, jacob navia wrote:
>>>> On 03/22/10 10:19 AM, jacob navia wrote:
>>>>> The iterator is still "valid" but will always return NULL. It just
>>>>> doesn't matter.
>>>>
>>>> I though returning NULL indicated that the iterator is at the end of
>>>> the container?
>>>>
>>>
>>> Actually it will call the currently defined error function with the
>>> error "CONTAINER_ERROR_OBJECT_CHANGED". If that function returns (and
>>> doesn't abort the program) the iterator returns NULL.
>>
>> Then I think that's wrong.
>
> Of course! I am ALWAYS wrong :-)
Why do you always spit the dummy when someone disagrees with you?
> But maybe you care to explain why?
In this case, efficiency (remember this is C we a talking about). In
C++, the most commonly used container is std::vector. Anywhere you
would malloc an array of something in C, you can use std::vector in C++.
A vector<T> iterator can be as simple as a T*, so accessing items in a
vector through an iterator is just as efficient as accessing element in
an array through a pointer.
> It is one reason why I said it would be a
>> nightmare defining the operations that do and don't invalidate an
>> iterator.
>
> It is very simple. ALL operations that modify the container other
> than through the iterator invalidate all iterators to that container.
>
> When you use an iterator over a container, you are allowed to
>
> o Read anything even from different iterators.
>
> o Write through a single iterator. THAT iterator (the one you use
> to modify the container) is NOT invalidated. ALL others are.
>
> This is different to C++ where the rules go for pages and pages.
As I've said many times, the complexity of a problem is invariant. The
choice is where to put it!
--
Ian Collins
Flash Gordon
> Ian Collins a écrit :
>> On 03/22/10 10:44 PM, jacob navia wrote:
>>>> On 03/22/10 10:19 AM, jacob navia wrote:
>>>>> The iterator is still "valid" but will always return NULL. It just
>>>>> doesn't matter.
>>>>
>>>> I though returning NULL indicated that the iterator is at the end of
>>>> the container?
>>>>
>>>
>>> Actually it will call the currently defined error function with the
>>> error "CONTAINER_ERROR_OBJECT_CHANGED". If that function returns (and
>>> doesn't abort the program) the iterator returns NULL.
>>
>> Then I think that's wrong.
>
> Of course! I am ALWAYS wrong :-)
>
> But maybe you care to explain why?
I can.
> It is one reason why I said it would be a
>> nightmare defining the operations that do and don't invalidate an
>> iterator.
>>
>
> It is very simple. ALL operations that modify the container other
> than through the iterator invalidate all iterators to that container.
>
> When you use an iterator over a container, you are allowed to
>
> o Read anything even from different iterators.
>
> o Write through a single iterator. THAT iterator (the one you use
> to modify the container) is NOT invalidated. ALL others are.
>
> This is different to C++ where the rules go for pages and pages.
I don't know C++ rules for this kind of thing, but I'll describe a real
situation I've got. In my case it is implemented using a database, but
it could equally well be implemented with a list...
I have one job which is repeatedly starts at the beginning of the list,
goes through it sometimes changing state fields on some of the records,
sometimes deleting them, sometimes adding new items to the *end* of the
list (i.e. not the current node the iterator is on.
There is a logically separate task which could be interspersed with the
first task either by being a separate thread, or being a function which
is called between steps through the list described above. This iterates
through a second list, and under some conditions added entries to the
end of the first list.
For this particular program, restarting the iterator on the first list
when items are added to the end of the list would be completely the
*wrong* thing to do (but it's what would happen with your described
implementation), and in some situations could actually cause an
effective lockup preventing things from being done where my customer
actually gets fined if the job isn't done.
The first list I talked about was a list of jobs to be run. Sometimes
the jobs won't complete (and might continue to not complete for a long
time). Sometimes the jobs decide to submit more jobs to be run later.
The second list is a list of jobs to be scheduled at defined time
intervals (anything from once a minute to once a day).
--
Flash Gordon
Nick
> Eric Sosman a écrit :
>> On 3/21/2010 5:01 PM, Ian Collins wrote:
>>> On 03/22/10 03:07 AM, Eric Sosman wrote:
>>>> [...] Keep a "change counter"
>>>> in the collection, incremented each time something is inserted
>>>> or removed. Copy the counter into the iterator when the iterator
>>>> is created. Each time the iterator is used, compare its count
>>>> to the collection's count; a mismatch means Danger, Will Robinson!
>>>
>>> Potential danger, but in many case the iterator would still be valid.
>>> Attempting to define and support those cases would be a nightmare. For
>>> example the iterator would still be valid after items have been inserted
>>> or removed in front of or behind it.
>>
>> Perhaps I'm over-generalizing, but I assumed the notion of
>> "iterator" was intended to extend to all containers, not just
>> ordered containers. For example, if insertion or deletion causes
>> a hash table to reorganize while an iteration is in progress,
>> things get hairy.
>>
>
> The rule is very easy
>
> If you change the contents of a container, all iterators to it are invalid
> and will call the error routine.
But as Flash pointed out, that stops you using your container as a queue
- which seems a bit of a drastic limitation. There will be things that
can always blow up iteration (as someone else pointed out, running in
arbitrary order through a hash table is one) but adding items to the end
of a simple linked-list shouldn't prevent me reading the next item. Nor
from deleting from the front of the list.
If this container is to replace all the messy add-hoc structures we
cobble together, it has to be able to do the common things we do that
way.
I think you need to rethink this. Simplicity is now getting in the way
of usefulness.
--
Online waterways route planner | http://canalplan.eu
Plan trips, see photos, check facilities | http://canalplan.org.uk
jacob navia
> jacob navia <ja...@nospam.org> writes:
>
>> Eric Sosman a écrit :
>>> On 3/21/2010 5:01 PM, Ian Collins wrote:
>>>> On 03/22/10 03:07 AM, Eric Sosman wrote:
>>>>> [...] Keep a "change counter"
>>>>> in the collection, incremented each time something is inserted
>>>>> or removed. Copy the counter into the iterator when the iterator
>>>>> is created. Each time the iterator is used, compare its count
>>>>> to the collection's count; a mismatch means Danger, Will Robinson!
>>>> Potential danger, but in many case the iterator would still be valid.
>>>> Attempting to define and support those cases would be a nightmare. For
>>>> example the iterator would still be valid after items have been inserted
>>>> or removed in front of or behind it.
>>> Perhaps I'm over-generalizing, but I assumed the notion of
>>> "iterator" was intended to extend to all containers, not just
>>> ordered containers. For example, if insertion or deletion causes
>>> a hash table to reorganize while an iteration is in progress,
>>> things get hairy.
>>>
>> The rule is very easy
>>
>> If you change the contents of a container, all iterators to it are invalid
>> and will call the error routine.
>
> But as Flash pointed out, that stops you using your container as a queue
> - which seems a bit of a drastic limitation.
You misunderstand completely. I have implemented already queues using a
list container.
You use the list directly, i.e. using
for (list_element=List->First; list_element != NULL;
list_element = list_element->Next ) {
// Use list_element->data here
}
You see?
You can use the components of the containers directly and iterate them
WITHOUT using any iterators at all.
Iterators are useful for MOST uses, but not for ALL uses. But you are
NOT limited to using iterators. You can use the containers directly.
> There will be things that
> can always blow up iteration (as someone else pointed out, running in
> arbitrary order through a hash table is one) but adding items to the end
> of a simple linked-list shouldn't prevent me reading the next item. Nor
> from deleting from the front of the list.
>
That can be only done safely with lists. An abstract iterator through
ANY container can't do that. If not, you end up with MESSY rules like
in C++, where each container defines what is allowed and what is not
allowed. That is impossible to remember. Description of limitations for
the standard conntainers are QUITE lengthy.
> If this container is to replace all the messy add-hoc structures we
> cobble together, it has to be able to do the common things we do that
> way.
>
It does that. Iterators though, are an abstraction that is useful in
MOST cases but not in ALL cases.
> I think you need to rethink this. Simplicity is now getting in the way
> of usefulness.
No. This design offers simplicity AND usefulness. You can use simple
iterators OR you can access a container directly.
jacob navia
>
> But as Flash pointed out, that stops you using your container as a queue
> - which seems a bit of a drastic limitation.
In a std::deque, erasing and inserting objects in the middle will
invalidate all iterators and references. But inserting an element at
either end (through push_back(…) or push_front(…) or insert(c.end(),…)
or insert(c.begin(),…)) will not invalidate references, though it may
invalidate iterators.
Easy to remember isn't it?
And what is invalidated depends on the implementation. GREAT.
Now, remember that FOR EACH container you have to remember a similar
set of rules, regarding what is invalidated and what is not.
I think that simple rules are less error prone than baroque
specs. Obviously in special cases you will not use iterators
but use the container elements directly, iterating them for
a specific container. That allows you to erase at the same time
that you append, change whatever, you are on your own.
Yes, in C we can *improve* things to what already has been done.
jacob
Richard Heathfield
> Nick a écrit :
>>
>> But as Flash pointed out, that stops you using your container as a queue
>> - which seems a bit of a drastic limitation.
>
> In a std::deque, erasing and inserting objects in the middle will
> invalidate all iterators and references. But inserting an element at
> either end (through push_back(…) or push_front(…) or insert(c.end(),…)
> or insert(c.begin(),…)) will not invalidate references, though it may
> invalidate iterators.
>
> Easy to remember isn't it?
Yes, if you bear in mind that the whole point of a deque is that it's a
double-ended queue. If you need to insert items in the middle, a deque
isn't the obvious data structure to choose.
>
> And what is invalidated depends on the implementation. GREAT.
Your "GREAT" is presumably intended to be sarcastic, but in fact there's
really nothing to be sarcastic about. If you want to bang in a nail,
choose a hammer. If you choose a screwdriver handle instead, that's not
a good choice, but the particular problems you will encounter will
depend on the particular design of the screwdriver. Likewise, if you try
to bash an element into the middle of a deque, you may well be able to
do it, but things are likely to go wrong (or at least become awkward) in
ways that will indeed depend on the implementation of the deque.
> Now, remember that FOR EACH container you have to remember a similar
> set of rules, regarding what is invalidated and what is not.
Yes. Each data structure has its own strengths and weaknesses. The trick
is to choose one whose strengths you can exploit without being hamstrung
by the weaknesses of that choice. If those weaknesses get in the way,
the chances are good that you're using the wrong structure.
<snip>
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
jacob navia
Andrei Alexandrescu
This slides set critics some of the misfeatures of the C++ iterators
implementation.
There are sevearl sites wth the video of this presentation, for
instance:
Another interesting one is:
Iterators: Signs of Weakness in Object-Oriented Languages
Henry G. Baker
I have read his prose for some years, but this paper is heavy.
Essentially it is a critique of C and C++ where you can't define
anonymous functions and you need iterators...
Another one is:
http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf
This is theory heavy paper... I find it difficult to read, but I
will try to finish it when I have some time.
jacob navia
> jacob navia wrote:
>> Nick a écrit :
>>>
>>> But as Flash pointed out, that stops you using your container as a queue
>>> - which seems a bit of a drastic limitation.
>>
>> In a std::deque, erasing and inserting objects in the middle will
>> invalidate all iterators and references. But inserting an element at
>> either end (through push_back(…) or push_front(…) or insert(c.end(),…)
>> or insert(c.begin(),…)) will not invalidate references, though it may
>> invalidate iterators.
>>
>> Easy to remember isn't it?
>
> Yes, if you bear in mind that the whole point of a deque is that it's a
> double-ended queue. If you need to insert items in the middle, a deque
> isn't the obvious data structure to choose.
>
Then, it is obvious that using an iterator in a dequeue is not a good
idea.
My point was precisely what you say:
If you want an object that makes ABSTRACTION from any particular
container implementation (an iterator) then you MUST make
compromises.
If you leave OPEN the possibility of using the container object directly
then you have the best of both worlds.
That is what I am proposing.
(1) SIMPLE rules for iterators.
(2) Specific container access for going through all items for a
specific container.
[snip]
>
> Each data structure has its own strengths and weaknesses. The trick
> is to choose one whose strengths you can exploit without being hamstrung
> by the weaknesses of that choice. If those weaknesses get in the way,
> the chances are good that you're using the wrong structure.
>
Exactly. Then, if you want to make an abstract object valid for ANY
container (an iterator) you can't address any SPECIFIC characteristic
of a container. The iterator I proposed has that characteristc:
(1) Any write to the object other than through the iterator invalidates
all iterators to that object.
(2) You have limited write access to the container, being able to modify
only the current object.
Ian Collins
> Richard Heathfield a écrit :
>> jacob navia wrote:
>>> Nick a écrit :
>>>>
>>>> But as Flash pointed out, that stops you using your container as a
>>>> queue
>>>> - which seems a bit of a drastic limitation.
>>>
>>> In a std::deque, erasing and inserting objects in the middle will
>>> invalidate all iterators and references. But inserting an element at
>>> either end (through push_back(…) or push_front(…) or
>>> insert(c.end(),…) or insert(c.begin(),…)) will not invalidate
>>> references, though it may invalidate iterators.
>>>
>>> Easy to remember isn't it?
>>
>> Yes, if you bear in mind that the whole point of a deque is that it's
>> a double-ended queue. If you need to insert items in the middle, a
>> deque isn't the obvious data structure to choose.
>
> Then, it is obvious that using an iterator in a dequeue is not a good
> idea.
No it isn't. Iterators are the perfect tool for walking the container
(in either direction), of for passing to standard algorithms.
> My point was precisely what you say:
>
> If you want an object that makes ABSTRACTION from any particular
> container implementation (an iterator) then you MUST make
> compromises.
True.
> If you leave OPEN the possibility of using the container object directly
> then you have the best of both worlds.
Did anyone suggest otherwise?
> That is what I am proposing.
>
> (1) SIMPLE rules for iterators.
> (2) Specific container access for going through all items for a
> specific container.
There's nothing wrong with that, just don't let the rules get in the way
of efficiency.
>> Each data structure has its own strengths and weaknesses. The trick is
>> to choose one whose strengths you can exploit without being hamstrung
>> by the weaknesses of that choice. If those weaknesses get in the way,
>> the chances are good that you're using the wrong structure.
>>
>
> Exactly. Then, if you want to make an abstract object valid for ANY
> container (an iterator) you can't address any SPECIFIC characteristic
> of a container. The iterator I proposed has that characteristc:
I think I see where you are coming from now. C++ iterators are specific
to each container, but the algorithms that work with them are generic.
You are proposing a single iterator type and algorithms that work with it?
> (1) Any write to the object other than through the iterator invalidates
> all iterators to that object.
> (2) You have limited write access to the container, being able to modify
> only the current object.
How does 2 relate to iterators, assuming they only reference on object
in a container?
--
Ian Collins
Andrew Poelstra
> Nick a écrit :
>> jacob navia <ja...@nospam.org> writes:
>>
>>> The rule is very easy
>>>
>>> If you change the contents of a container, all iterators to it are invalid
>>> and will call the error routine.
>>
>> But as Flash pointed out, that stops you using your container as a queue
>> - which seems a bit of a drastic limitation.
>
> You misunderstand completely. I have implemented already queues using a
> list container.
>
> You use the list directly, i.e. using
> for (list_element=List->First; list_element != NULL;
> list_element = list_element->Next ) {
> // Use list_element->data here
> }
>
> You see?
>
> You can use the components of the containers directly and iterate them
> WITHOUT using any iterators at all.
>
> Iterators are useful for MOST uses, but not for ALL uses. But you are
> NOT limited to using iterators. You can use the containers directly.
>
I agree. It's Bad Polymorphism if you have an iterator that does
two different things (ie, what you want OR destroy itself, other
iterators and the list) depending on the specific data structure
you obtained it from.
Now, given that if you use one iterator's list-manipulation
functions, it will invalidate all other iterators, I think
you do need to have a concept of a "const" iterator, which
you pass to algorithms that guarantee they won't screw you
around.
Flash Gordon
If you can do that for any ordered container, then what need iterators?
If not, then for your containers to be generic you need to support the
kind of operation I was talking about.
> Iterators are useful for MOST uses, but not for ALL uses. But you are
> NOT limited to using iterators. You can use the containers directly.
So you get the overheads of generic containers with the work of using
the specific type of data structure you've selected directly. Sounds
like the worst of both worlds to me, at least in terms of the things I do.
Remember, trees are also often used for ordered data and have a nice
ordered access. If you think you can't do what I was talking about with
trees as well as linked lists, then consider that the database I'm
actually using for this uses btrees for the index, and I'm using an
iterator to traverse that tree whilst doing inserts and deletes.
>> There will be things that
>> can always blow up iteration (as someone else pointed out, running in
>> arbitrary order through a hash table is one) but adding items to the end
>> of a simple linked-list shouldn't prevent me reading the next item. Nor
>> from deleting from the front of the list.
>
> That can be only done safely with lists.
No, it can be done with trees as well. I'll agree you can't do it with a
hash (not easily anyway).
> An abstract iterator through
> ANY container can't do that. If not, you end up with MESSY rules like
> in C++, where each container defines what is allowed and what is not
> allowed. That is impossible to remember. Description of limitations for
> the standard conntainers are QUITE lengthy.
No, it's a simple rule you need (the ones in C++ might be complex). The
simple rule is that if it is an ordered container you can do it, if it
isn't you can't.
>> If this container is to replace all the messy add-hoc structures we
>> cobble together, it has to be able to do the common things we do that
>> way.
>
> It does that. Iterators though, are an abstraction that is useful in
> MOST cases but not in ALL cases.
Iterators are useful on trees as well as lists, and useful with the
ability to add/delete else where in the tree whilst iterating.
>> I think you need to rethink this. Simplicity is now getting in the way
>> of usefulness.
>
> No. This design offers simplicity AND usefulness. You can use simple
> iterators OR you can access a container directly.
They may be useful for some situations, but they are not generic enough
to be useful to me as a generic library, and not targeted enough for
when I don't want a generic library.
They may well be perfect for other people.
--
Flash Gordon
ng2010
"jacob navia" <ja...@spamsink.net> wrote in message
news:ho39f3$n55$1...@speranza.aioe.org...
> In the last discussion we discussed how to do "GetNext" etc with
> containers.
>
> I think it is important that the user code stays as abstract as
> possible, without getting into the specifics of any container, as Mr
> Becarisse said (if I remember correctly).
>
> Well, this could be done as follows. Please tell me what do you think.
>
> Thanks
>
> --------
>
>
> All containers should be able to support the "GetNext" and the
> "GetPrevious" functions.
That, of course, is false. It is only true to you, for you don't know any
better (apparently). So, before you start in on details, you better
discuss the alternative choices and why the above stated design is best.
(Aside: If this is a user group, it surely doesn't need first-time
library builders acting like they have definitive library designs.
"neophytes" WILL get sucked into the other neophyte's personal R&D, and
surely C is "well-evolved" and not a research project in real usage (?)).
(Aside 2: JN, if you think C is so great and good and readily usable, why
don't you go actually USE it instead of trying to extend/modify it? Your
actions say that C is not up to the task. And you are going on and on
about FOUNDATIONAL issues with the language. I was trying to be helpful
when I said don't waste your time.)
jacob navia
> "jacob navia" <ja...@spamsink.net> wrote in message
> news:ho39f3$n55$1...@speranza.aioe.org...
>> In the last discussion we discussed how to do "GetNext" etc with
>> containers.
>>
>> I think it is important that the user code stays as abstract as
>> possible, without getting into the specifics of any container, as Mr
>> Becarisse said (if I remember correctly).
>>
>> Well, this could be done as follows. Please tell me what do you think.
>>
>> Thanks
>>
>> --------
>>
>>
>> All containers should be able to support the "GetNext" and the
>> "GetPrevious" functions.
>
> That, of course, is false. It is only true to you, for you don't know any
> better (apparently).
That, of course, is true. It is only false to you, for you don't know
any better (apparently).
Anybody can say that. If you disagree with something I write, it is not
enough to say "That is false" but you have to explain why you consider
it false.
You are unable to propose any arguments apparently.
> So, before you start in on details, you better
> discuss the alternative choices and why the above stated design is best.
>
Because in non sequential containers GetNext and GetPrevious should
traverse the sequence in some unspecified order that only guarantees
that all elements will be eventually visited. I wrote that inmy proposal
but since you did not get past the first sentence you did not read it.
HINT:
Read the propositions to the end, THEN reply. Thanks.
> (Aside: If this is a user group, it surely doesn't need first-time
> library builders acting like they have definitive library designs.
> "neophytes" WILL get sucked into the other neophyte's personal R&D, and
> surely C is "well-evolved" and not a research project in real usage (?)).
>
You are free to have your opinion, this is Usenet. Since (again) you do
not put any argumentation to substantiate your views, it is better to
leave them as what they are. Your personal opinion.
> (Aside 2: JN, if you think C is so great and good and readily usable, why
> don't you go actually USE it instead of trying to extend/modify it?
I use C every day. What is comic in your attacks is that you do not know
anything about me but somehow you think you can make statements like
"Why don't you actually USE C".
> Your
> actions say that C is not up to the task. And you are going on and on
> about FOUNDATIONAL issues with the language.
And why should I refrain from doing that?
Ahh of course, I forgot, excuse me: Because you said so.
> I was trying to be helpful
> when I said don't waste your time.)
Great! Then, you could be even more helpful and *explain* your point
ofview instead of just stating "This is wrong"...
You see? If you "explain" your views, we can discuss about them.
If you just say: "This is wrong" there is no discussion possible.
Tim Rentsch
> On 2010-03-23, jacob navia <ja...@jacob.remcomp.fr> wrote:
>> Nick a <<C3>> <<83>> <<C2>> <<A9>> crit :
>>> jacob navia <ja...@nospam.org> writes:
>>>
>>>> The rule is very easy
>>>>
>>>> If you change the contents of a container, all iterators to it are invalid
>>>> and will call the error routine.
>>>
>>> But as Flash pointed out, that stops you using your container as a queue
>>> - which seems a bit of a drastic limitation.
>>
>> You misunderstand completely. I have implemented already queues using a
>> list container.
>>
>> You use the list directly, i.e. using
>> for (list_element=List->First; list_element != NULL;
>> list_element = list_element->Next ) {
>> // Use list_element->data here
>> }
>>
>> You see?
>>
>> You can use the components of the containers directly and iterate them
>> WITHOUT using any iterators at all.
>>
>> Iterators are useful for MOST uses, but not for ALL uses. But you are
>> NOT limited to using iterators. You can use the containers directly.
>>
>
> I agree. It's Bad Polymorphism if you have an iterator that does
> two different things (ie, what you want OR destroy itself, other
> iterators and the list) depending on the specific data structure
> you obtained it from. [snip]
Not "Bad Polymorphism". It may be (or may not be, depending on
specifics) bad interface design, or bad implementation choice, or
something else along those lines. The phrase "Bad Polymorphism"
just doesn't scan in this context.
Phil Carmody
> Andrew Poelstra <apoe...@localhost.localdomain> writes:
>> I agree. It's Bad Polymorphism if you have an iterator that does
>> two different things (ie, what you want OR destroy itself, other
>> iterators and the list) depending on the specific data structure
>> you obtained it from. [snip]
>
> Not "Bad Polymorphism". It may be (or may not be, depending on
> specifics) bad interface design, or bad implementation choice, or
> something else along those lines. The phrase "Bad Polymorphism"
> just doesn't scan in this context.
"Bad polymorphism" to me just implies "violates the LSP".
His example is one of a violation of the LSP.
Tim Rentsch
> Tim Rentsch <t...@x-alumni2.alumni.caltech.edu> writes:
>> Andrew Poelstra <apoe...@localhost.localdomain> writes:
>>> I agree. It's Bad Polymorphism if you have an iterator that does
>>> two different things (ie, what you want OR destroy itself, other
>>> iterators and the list) depending on the specific data structure
>>> you obtained it from. [snip]
>>
>> Not "Bad Polymorphism". It may be (or may not be, depending on
>> specifics) bad interface design, or bad implementation choice, or
>> something else along those lines. The phrase "Bad Polymorphism"
>> just doesn't scan in this context.
>
> "Bad polymorphism" to me just implies "violates the LSP".
> His example is one of a violation of the LSP.
Yes, I understood that he intended his comment to mean
that such an implementation would violate some design
principle. But he didn't say which design principle,
and no matter which design principle was meant, "Bad
Polymorphism" is a bad name for it.
ng2010
> ng2010 a écrit :
>> "jacob navia" <ja...@spamsink.net> wrote in message
>> news:ho39f3$n55$1...@speranza.aioe.org...
>>> In the last discussion we discussed how to do "GetNext" etc with
>>> containers.
>>>
>>> I think it is important that the user code stays as abstract as
>>> possible, without getting into the specifics of any container, as Mr
>>> Becarisse said (if I remember correctly).
>>>
>>> Well, this could be done as follows. Please tell me what do you
>>> think. Thanks
>>>
>>> --------
>>>
>>>
>>> All containers should be able to support the "GetNext" and the
>>> "GetPrevious" functions.
>>
>> That, of course, is false. It is only true to you, for you don't
>> know any better (apparently).
>
> That, of course, is true. It is only false to you, for you don't know
> any better (apparently).
>
> Anybody can say that. If you disagree with something I write, it is
> not enough to say "That is false" but you have to explain why you
> consider it false.
You are obviously wrong on that assertion. _I_ don't have to GIVE you
anything.
>
>
> You are unable to propose any arguments apparently.
Apparently you are ARGUING. I wouldn't want to get in-between anything.
>
>> So, before you start in on details, you better
>> discuss the alternative choices and why the above stated design is
>> best.
>
> Because
Well, see, go back and start again. I wasn't offering amnesty to continue
on in your immature and wasteful way. Your book report was bad. You need
to rewrite it and offer it again for regrading. There is no progression
to the next level until you meet the requirements of the preceding level.
> HINT:
>
> Read the propositions to the end, THEN reply. Thanks.
HINT:
Don't start selling snakeoil until you establish a market for it. (NOT a
recommendation to sell snakeoil!).
>
>
>> (Aside: If this is a user group, it surely doesn't need first-time
>> library builders acting like they have definitive library designs.
>> "neophytes" WILL get sucked into the other neophyte's personal R&D,
>> and surely C is "well-evolved" and not a research project in real
>> usage (?)).
>
> You are free to have your opinion, this is Usenet. Since (again) you
> do not put any argumentation to substantiate your views, it is better
> to leave them as what they are. Your personal opinion.
That is childishness on your part (I make some assumptions that follow
the immediately following list of your "wants").
1. This isn't a group to sell R&D projects to.
2. Your personal agenda is just that: personal.
3. If C is (still) useful, people will come in here and talk about it IN
USE, but if you FLOOD the room with your PROPOGANDA/AGENDA, ... I don't
think you want to be that.
4. Go talk in the standard C group if your intention is to "evolve" C.
Become a member of the C ISO group if that is your true intent, THEY own
C, you do not.
5. There is no "C" outside of the C standard unless you create your own
"fork"/tangent from it. Else, it is something else.
>
>> (Aside 2: JN, if you think C is so great and good and readily
>> usable, why don't you go actually USE it instead of trying to
>> extend/modify it?
>
> I use C every day. What is comic in your attacks is that you do not
> know anything about me but somehow you think you can make statements
> like "Why don't you actually USE C".
I'm going to let go that comment you made about "my attacks". Extending C
and using it are quite different. Because I know you don't use it. Your
mind is ENTIRELY occupied by "making it better", and I told you before,
stop "spinning your wheels", it's just a car. It's not alive, and it's
not your life. IT, takes your time though, and that's all you have.
>
>> Your
>> actions say that C is not up to the task. And you are going on and on
>> about FOUNDATIONAL issues with the language.
>
> And why should I refrain from doing that?
I don't think this is the group for your elementary R&D. I can tool up
and try to sell my next big stupid combobulated thing (and you're doing
it as a skunkwork) .... it's a circus. See a flea do something never
intended. Starting to sound like a crime.
Refrain from doing what? What were you doing?
jacob navia
> jacob navia wrote:
>>. If you disagree with something I write, it is
>> not enough to say "That is false" but you have to explain why you
>> consider it false.
>
> You are obviously wrong on that assertion. _I_ don't have to GIVE you
> anything.
>
(snip)
OK. This is Usenet, you can say whatever you feel like. Personally,
since you do not propose any arguments and just dismiss everything I say
without any arguments I will stop discussing with you.
Richard Heathfield
wrote:
> ng2010 a écrit :
<snip>
>> It is only false to you, for you don't
> know any better (apparently).
>
> Anybody can say that. If you disagree with something I write, it is
> not enough to say "That is false" but you have to explain why you
> consider it false.
Agreed. Neither is it sufficient to say "That is a lie" (which you
very often do say); you have to explain not only why you consider it
to be untrue but also why you think it is a *deliberate* untruth.
Nick Keighley
> jacob navia wrote:
> > ng2010 a écrit :
> >>news:ho39f3$n55$1...@speranza.aioe.org...
> >>> In the last discussion we discussed how to do "GetNext" etc with
> >>> containers.
>
> >>> I think it is important that the user code stays as abstract as
> >>> possible, without getting into the specifics of any container, as Mr
> >>> Becarisse said (if I remember correctly).
>
> >>> Well, this could be done as follows. Please tell me what do you
> >>> think. Thanks
>
> >>> All containers should be able to support the "GetNext" and the
> >>> "GetPrevious" functions.
this seems too prescriptive. A container could allow forward iteration
only.
> >> That, of course, is false. It is only true to you, for you don't
> >> know any better (apparently).
>
> > That, of course, is true. It is only false to you, for you don't know
> > any better (apparently).
>
> > Anybody can say that. If you disagree with something I write, it is
> > not enough to say "That is false" but you have to explain why you
> > consider it false.
>
> You are obviously wrong on that assertion. _I_ don't have to GIVE you
> anything.
and at this point you choose not have a technical debate. bye.
<snip>
jacob navia
> On 28 Mar, 05:35, "ng2010" <ng2...@att.invalid> wrote:
>> jacob navia wrote:
>>> ng2010 a écrit :
>>>> "jacob navia" <ja...@spamsink.net> wrote in message
>>>> news:ho39f3$n55$1...@speranza.aioe.org...
>
>
>>>>> In the last discussion we discussed how to do "GetNext" etc with
>>>>> containers.
>>>>> I think it is important that the user code stays as abstract as
>>>>> possible, without getting into the specifics of any container, as Mr
>>>>> Becarisse said (if I remember correctly).
>>>>> Well, this could be done as follows. Please tell me what do you
>>>>> think. Thanks
>>>>> All containers should be able to support the "GetNext" and the
>>>>> "GetPrevious" functions.
>
> this seems too prescriptive. A container could allow forward iteration
> only.
>
If a container doesn't support GetPrevious then its GetPrevious function
returns always NULL.
You would like that the container gives a compile error if somebody
uses GetPrevious with it.
Maybe your option is better. I have to think about it. Thanks for the
suggestion.
Ian Collins
> Nick Keighley a �crit :
>> On 28 Mar, 05:35, "ng2010" <ng2...@att.invalid> wrote:
>>> jacob navia wrote:
>>>>> "jacob navia" <ja...@spamsink.net> wrote in message
>>>>> news:ho39f3$n55$1...@speranza.aioe.org...
>>
>>
>>>>>> In the last discussion we discussed how to do "GetNext" etc with
>>>>>> containers.
>>>>>> I think it is important that the user code stays as abstract as
>>>>>> possible, without getting into the specifics of any container, as Mr
>>>>>> Becarisse said (if I remember correctly).
>>>>>> Well, this could be done as follows. Please tell me what do you
>>>>>> think. Thanks
>>>>>> All containers should be able to support the "GetNext" and the
>>>>>> "GetPrevious" functions.
>>
>> this seems too prescriptive. A container could allow forward iteration
>> only.
>>
>
> If a container doesn't support GetPrevious then its GetPrevious function
> returns always NULL.
Or you could support the concept of forward and reverse iterators. That
would give to symmetry for algorithms.
--
Ian Collins
jacob navia
> On 03/29/10 12:36 AM, jacob navia wrote:
>>> On 28 Mar, 05:35, "ng2010" <ng2...@att.invalid> wrote:
>>>> jacob navia wrote:
>>>>>> "jacob navia" <ja...@spamsink.net> wrote in message
>>>>>> news:ho39f3$n55$1...@speranza.aioe.org...
>>>
>>>
>>>>>>> In the last discussion we discussed how to do "GetNext" etc with
>>>>>>> containers.
>>>>>>> I think it is important that the user code stays as abstract as
>>>>>>> possible, without getting into the specifics of any container, as Mr
>>>>>>> Becarisse said (if I remember correctly).
>>>>>>> Well, this could be done as follows. Please tell me what do you
>>>>>>> think. Thanks
>>>>>>> All containers should be able to support the "GetNext" and the
>>>>>>> "GetPrevious" functions.
>>>
>>> this seems too prescriptive. A container could allow forward iteration
>>> only.
>>>
>>
>> If a container doesn't support GetPrevious then its GetPrevious function
>> returns always NULL.
>
> Or you could support the concept of forward and reverse iterators. That
> would give to symmetry for algorithms.
>
Precisely GetPrevious is the reverse iterator... I thought something like:
for (obj=GetLast(iterator); obj != NULL; obj = GetPrevious(iterator)) (
// do something with obj.
)
The only requirement is that the order is reversed, i.e. the order of
GetNext is the reverse of GetPrevious.
We always have:
GetPrevious of GetFirst() is NULL
GetNext of GetLast is NULL.
Keith Thompson
> Ian Collins a écrit :
>> On 03/29/10 12:36 AM, jacob navia wrote:
>>> If a container doesn't support GetPrevious then its GetPrevious function
>>> returns always NULL.
>>
>> Or you could support the concept of forward and reverse iterators.
>> That would give to symmetry for algorithms.
>>
>
> Precisely GetPrevious is the reverse iterator... I thought something like:
>
> for (obj=GetLast(iterator); obj != NULL; obj = GetPrevious(iterator)) (
> // do something with obj.
> )
>
> The only requirement is that the order is reversed, i.e. the order of
> GetNext is the reverse of GetPrevious.
>
> We always have:
>
> GetPrevious of GetFirst() is NULL
> GetNext of GetLast is NULL.
It looks more like GetPrevious is a function that takes an iterator
as an argument.
I think what Ian was suggesting was to have distinct types for forward
and reverse iterators (and probably for bidirectional iterators).
Then you just wouldn't define a GetPrevious function for forward
iterators.
Given C's lack of overloading/overriding, you could either give your
Get* functions distinct names (ugly), or you could refer to them via
pointer-to-function members of the iterator type. You could have
something like:
forward_iterator *iter = forward_iterator_init(...);
iter = iter->get_next(); /* ok */
or maybe
set_to_next(iter);
iter = iter->get_previous(); /* error, no such member */
Handling allocation and deallocation of iterator objects would be
tricky given C's lack of implicitly invoked destructors. It might
be better to declare and use iterator objects rather than pointers
to iterator objects.
I haven't really thought this through. Quite possibly there's
a cleaner approach that I haven't thought of.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Ian Collins
> jacob navia<ja...@nospam.org> writes:
>> Ian Collins a écrit :
>>> On 03/29/10 12:36 AM, jacob navia wrote:
> [...]
>>>> If a container doesn't support GetPrevious then its GetPrevious function
>>>> returns always NULL.
>>>
>>> Or you could support the concept of forward and reverse iterators.
>>> That would give to symmetry for algorithms.
>>>
>>
>> Precisely GetPrevious is the reverse iterator... I thought something like:
>>
>> for (obj=GetLast(iterator); obj != NULL; obj = GetPrevious(iterator)) (
>> // do something with obj.
>> )
>>
>> The only requirement is that the order is reversed, i.e. the order of
>> GetNext is the reverse of GetPrevious.
>>
>> We always have:
>>
>> GetPrevious of GetFirst() is NULL
>> GetNext of GetLast is NULL.
>
> It looks more like GetPrevious is a function that takes an iterator
> as an argument.
>
> I think what Ian was suggesting was to have distinct types for forward
> and reverse iterators (and probably for bidirectional iterators).
> Then you just wouldn't define a GetPrevious function for forward
> iterators.
Yes, I was.
> Given C's lack of overloading/overriding, you could either give your
> Get* functions distinct names (ugly), or you could refer to them via
> pointer-to-function members of the iterator type. You could have
> something like:
Indeed, this whole thing is starting to resemble forcing a square peg in
a round whole. The container/iterator idiom does not fix well with C.
--
Ian Collins