Containers: The iterator object

[jacob navia]

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
}

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]

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

 

[jacob navia]

Willem a écrit :
[snip]

GetFirst() would then take the place of Rewind().

Of course!

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.

 

[Ian Collins]

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?

 

[jacob navia]

Eric Sosman a écrit :

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.

 

[bartc]

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.

 

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

 

[jacob navia]

Ian Collins a écrit :

What happens if you copy an iterator?

Nothing. The copy has the same behavior as the original. It will
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]

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

 

[Andrew Poelstra]

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.

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.

 

[jacob navia]

Andrew Poelstra a écrit :

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 :


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]

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!

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.

 

[jacob navia]

Ian Collins a écrit :

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.

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]

Ian Collins a écrit :

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.

The iterator is still "valid" but will always return NULL. It just
doesn't matter.

jacob

 

[Ian Collins]

Ian Collins a écrit :

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?

How you you use an iterator to insert some values form one container
into another?

 

[jacob navia]

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?

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]

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