Avoiding failsafe behaviour of iterators

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi group,

I want to iterate over a set, remove the current element, then inside
the iteration iterate over the set again, such that I consider all
possible pairs with the first element, then remove the second element
from the set too if it meets certain constraints. In the end I will end
up with an empty set. Of course I am not interested in the deletion
process, but I build a new set (equivalence relation) on the way. Now
if I understand correctly, the process I describe will cause the first
iterator to fail, because it notices elements have been deleted. In my
scenario though, this is not a problem; I don?t want to consider pairs
in which one of the elements has been deleted. That?s what I deleted
them for in the first place.

So two questions:
- can I get around this failsafe behaviour of java.util.Set?
- Does anybody see a better way to implement this?

Some code to illustrate the problem (not tested or compiled, still in
the process of pseudocoding):
(note: no foreach, as I need Iterator.remove)

Equivalence<State> equivalence = new Equivalence<State>(allStates);
// allStates is the domain of the equivalence
for (Iterator<State> inner = allStates.iterator(); inner.hasNext(); ) {
State q = inner.next();
Set<State> equivClass = new HashSet<State>();
equivClass.add(q);
inner.remove();
for (Iterator<State> outer = allStates.iterator(); outer.hasNext(){
State qPrime = outer.next();
// do a lot of computation to see whether q and q' are equivalent
if (equivalent){
equivClass.add(qPrime);
outer.remove();
}
}
equivalence.add(equivClass);
}

TIA, H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD80X9e+7xMGD3itQRAlHeAJ4m10HOPaYz4ls79Rw1CPu18/YLcQCcDl7T
SU+kdWKd9BsbwkQLEsDPKCY=
=9f4i
-----END PGP SIGNATURE-----

 

[tom fredriksen]

- Does anybody see a better way to implement this?

If you could explain what it is you are trying to achieve (instead of
what you technically want to do), it might be easier to understand the
problem and suggest other ways of solving the problem.

/tom

 

[Adam Maass]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi group,

I want to iterate over a set, remove the current element, then inside
the iteration iterate over the set again, such that I consider all
possible pairs with the first element, then remove the second element
from the set too if it meets certain constraints. In the end I will end
up with an empty set. Of course I am not interested in the deletion
process, but I build a new set (equivalence relation) on the way. Now
if I understand correctly, the process I describe will cause the first
iterator to fail, because it notices elements have been deleted. In my
scenario though, this is not a problem; I don?t want to consider pairs
in which one of the elements has been deleted. That?s what I deleted
them for in the first place.

So two questions:
- can I get around this failsafe behaviour of java.util.Set?
- Does anybody see a better way to implement this?

Some code to illustrate the problem (not tested or compiled, still in
the process of pseudocoding):
(note: no foreach, as I need Iterator.remove)

Equivalence<State> equivalence = new Equivalence<State>(allStates);
// allStates is the domain of the equivalence
for (Iterator<State> inner = allStates.iterator(); inner.hasNext(); ) {
State q = inner.next();
Set<State> equivClass = new HashSet<State>();
equivClass.add(q);
inner.remove();
for (Iterator<State> outer = allStates.iterator(); outer.hasNext(){
State qPrime = outer.next();
// do a lot of computation to see whether q and q' are equivalent
if (equivalent){
equivClass.add(qPrime);
outer.remove();
}
}
equivalence.add(equivClass);
}

As you know, the second Iterator will cause the first to fail.

Is it possible to use a second Set that is identical in content to the
first?

Is it possible to avoid Iterator.remove()? (As I understand your
requirement, it is to build up a result; you shouldn't have to modify the
input sets to do that.)

 

[Chris Uppal]

I want to iterate over a set, remove the current element, then inside
the iteration iterate over the set again, such that I consider all
possible pairs with the first element, then remove the second element
from the set too if it meets certain constraints.

Can't you just do (pseudo-code):

while (set isn't empty)
{
elem1 = remove arbitrary element from set;
for (elem2 in set) // uses iterator
{
if ( blahBlahBlah(elem1, elem2) )
remove elem2; // via iterator
}
}

You only use one iterator at a time. The key as that the implementation of
"remove arbitrary element" can be done with a temporary iterator which you
discard as soon as it has removed the first element.

-- chris

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

tom fredriksen schreef:

If you could explain what it is you are trying to achieve (instead of
what you technically want to do), it might be easier to understand the
problem and suggest other ways of solving the problem.

Well, I tried, but obviously not hard enough. Well, to be precise, I am
trying to implement the minimisation of a tree automaton, as described
in TATA, on page 35 of chapter one, which can be found here:
http://www.grappa.univ-lille3.fr/tata/; in short:
/* I am following the algorithm in TATA, p. 35.
* Minimization Algorithm MIN
* input: complete and reduced DFTA A = (Q,F,Qf,d)
* begin
* Set P to {Qf,Q\Qf} // P is the initial equivalence relation
* repeat
* P' = P
* //Refine equivalence P in P'
* qP'q' if
* qPq' and
* forall f in ?Fn forall q1, ..., qi-??1, qi+1, ..., qn in?? Q
* d(f(q1,...,qi-1,q,qi+1,...,qn))Pd(f(q1,...,qi-??1,q',qi+1,...,qn))
* until P' = P
* Set Qmin to the set of equivalence classes of P
* // we denote by [q] the equivalence class of state q w.r.t.P
* Set dmin to {(f, [q1], . . . , [qn]) ->?? [f(q1, . . . , qn)]}
* Set Qminf to {[q] | q in Qf }
* output: DFTA Amin = (Qmin,F,Qminf,dmin)
* end
*/

The crucial part is the computation of the equivalence classes.

To do this, I hav a method which more or less does what I wrote in the
original mail. So what I have to do inside the loop above is loop over
all states in Q, for each state compute its equivalence class, and add
that class to the equivalence-under-construction.
To compute this equivalence class, I have to loop over all other states,
and check whether those two conditions are met (which involves even more
looping over all function symbols in the signature of the automaton).

The crucial thing to note is that it is useless to compute the
equivalence class of a state that already has been found equivalent to a
state whose equivalence class I computed in a previous loop, as it will
give the same result. So I thought: if I delete a state from the set I
still have to consider once I put it in some equivalence class, I avoid
doing unnecessary loops.

Perhaps a better approach would be to take one arbitrary element,
compute its equivalence class, remove this class from the set of states,
then repeat until the set is empty. Hm, seems better, I guess I can do
it this way.

Sometimes it helps to spell out your problems.

Still open for other suggestions.

Thanks for taking the time, H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD81H3e+7xMGD3itQRAnWQAJ9IQQEy1JzINPwQ3T2cKA6vPBb8xwCggUsE
L4gshZCpgN9aEi+yRIKdBv0=
=5cqa
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Adam Maass schreef:

As you know, the second Iterator will cause the first to fail.
Indeed.

Is it possible to use a second Set that is identical in content to the
first?

No, as the point of removing the states is to avoid iterating over them.

Is it possible to avoid Iterator.remove()? (As I understand your
requirement, it is to build up a result; you shouldn't have to modify the
input sets to do that.)

Yes. See my other post for a first idea of a solution.

Thanks, H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD81I/e+7xMGD3itQRAvpUAJ48z7oL9e5Jo57ku/KC36oRcifQxQCdFkDl
wks58opVpPjI7+Lib1yCo1k=
=GQFJ
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Chris Uppal schreef:

Can't you just do (pseudo-code):

while (set isn't empty)
{
elem1 = remove arbitrary element from set;
for (elem2 in set) // uses iterator
{
if ( blahBlahBlah(elem1, elem2) )
remove elem2; // via iterator
}
}

Indeed, this is a nice approach, I thought about it later, too.

You only use one iterator at a time. The key as that the implementation of
"remove arbitrary element" can be done with a temporary iterator which you
discard as soon as it has removed the first element.

Hm, seems pity to me to have to create an iterator just to get one
element, but the interface of Set does not allow to get an arbitrary
element, so I guess that is the only way...

Thanks, H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD81Nme+7xMGD3itQRAmOuAJ4kXDCE6OKEuLJifviz1ZGlKQW+5gCcCriT
Fw3s1auCxoRtlQZvrk92j3A=
=oIkM
-----END PGP SIGNATURE-----

 

[Dimitri Maziuk]

Hendrik Maryns sez:
....

Hm, seems pity to me to have to create an iterator just to get one
element, but the interface of Set does not allow to get an arbitrary
element, so I guess that is the only way...

Last I looked concurrent modification exception (or whatever
it's called) was thrown only if the number of elements has changed.
If your set allows null elements, you could try setting deleted
ones to null instead of actually deleting them. (But check the
implementation in src.zip first.)

Dima

 

[Thomas Hawtin]

Is it possible to use a second Set that is identical in content to the
first?

Or just copy the data into a List. Use indexes/ListIterator on the copy.

Tom Hawtin

 

[P.Hill]

The crucial thing to note is that it is useless to compute the
equivalence class of a state that already has been found equivalent to a
state whose equivalence class I computed in a previous loop, as it will
give the same result. So I thought: if I delete a state from the set I
still have to consider once I put it in some equivalence class, I avoid
doing unnecessary loops.

Forget the silly mathematic set notation and think like a software
engineer or computer scientist. To find oens you already have what
data structure would you need? I would have some type of map which
allows me to avoids multiple passes over the data. Right off without
spending time to study the problem I'm not sure of the key to my
suggested map (equivalenceclass and state?), but your sentences above
seem to be nearly talking about looking something up.
The map can link back to the "natural" representation of the set,
be it array or other data structure.

-Paul

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

P.Hill schreef:

Forget the silly mathematic set notation and think like a software
engineer or computer scientist.

Unfortunately, I am a mathematician with minor cs education, working as
a programmer.

To find oens

? ones?

you already have what
data structure would you need? I would have some type of map which
allows me to avoids multiple passes over the data. Right off without
spending time to study the problem I'm not sure of the key to my
suggested map (equivalenceclass and state?), but your sentences above
seem to be nearly talking about looking something up.
The map can link back to the "natural" representation of the set,
be it array or other data structure.

Not entirely clear to me, but seems to make sense. In fact, you want to
compute all equivalence classes at the same time, having a map mapping a
state to its class. Seems possible, some brainstorming:

- pick one state,
make its class (i.e. new HashSet<State>())
add state1->class1 to map
add state1 to list of visited states
- pick next state,
check whether it is equivalent to the first,
yes -> add to class
no -> make new class
add state2->class2 to map
add state2 to list of states
....
- pick next state,
for all previous states:
check whether it is equivalent,
yes-> add to class
no to all-> make new class
add staten->classn to map
add staten to list of states

Here the list of states represents the equivalence classes by one
element of it. I don?t even need a new list there, but can iterate over
the KeySet of the map.

This needs only one loop over all states, plus an inner loop of maximal
length the number of equivalence classes. Thus it is an O(nm)
algorithm. Not bad, probably best possible.

Waaw, your post seemed cryptic at first, but many thanks!

H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD9GGre+7xMGD3itQRAt7TAJ0Qz61D6P23bZOZI8VtvR8vj3CqKACeLg5Y
yo/j770iG2Ep2aQsfLlrp2o=
=+H7F
-----END PGP SIGNATURE-----

 

[Roedy Green]

Forget the silly mathematic set notation and think like a software
engineer or computer scientist. To find oens you already have what
data structure would you need? I would have some type of map which
allows me to avoids multiple passes over the data. Right off without
spending time to study the problem I'm not sure of the key to my
suggested map (equivalenceclass and state?), but your sentences above
seem to be nearly talking about looking something up.
The map can link back to the "natura

Is there any way to compute a sort of equivalence class hashcode to
help you find the collisions rapidly? You just keep attempting to add
new equivalence classes and have a HashMap refuse to add them if it
has them already.

You'd think HashSet would be a useful tool for arranging unique
Objects. However, it is useless for that purpose because it will only
tell you if an equivalent Object is already in the HashSet. It won't
divulge a reference to the canonical Object itself. To arrange
uniqueness, you need a HashMap with key and value referencing the same
canonical unique Object.

see http://mindprod.com/jgloss/hashset.html

 

[Dimitri Maziuk]

Hendrik Maryns sez:
....

Not entirely clear to me, but seems to make sense. In fact, you want to
compute all equivalence classes at the same time, having a map mapping a
state to its class. Seems possible, some brainstorming:

- pick one state,
make its class (i.e. new HashSet<State>())
add state1->class1 to map
add state1 to list of visited states
- pick next state,
check whether it is equivalent to the first,
yes -> add to class
no -> make new class
add state2->class2 to map
add state2 to list of states
...
- pick next state,
for all previous states:
check whether it is equivalent,
yes-> add to class
no to all-> make new class
add staten->classn to map
add staten to list of states

Here the list of states represents the equivalence classes by one
element of it. I don?t even need a new list there, but can iterate over
the KeySet of the map.

This needs only one loop over all states, plus an inner loop of maximal
length the number of equivalence classes. Thus it is an O(nm)
algorithm. Not bad, probably best possible.

Not sure I understand what you're trying to do, but it looks like
if you use state as map key you should get O(n) performance:
override equals() for the state, hashmap.get( state ) should give you O(1),
if your "state class" is one object, .put( state, class ) is O(1) as well.
So you only have to iterate over all states.

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Roedy Green schreef:

Is there any way to compute a sort of equivalence class hashcode to
help you find the collisions rapidly? You just keep attempting to add
new equivalence classes and have a HashMap refuse to add them if it
has them already.

Equivalence classes are just Sets of states. But they all have to be
disjoint. Indeed I wrote a wrapper class Equivalence<E>, which has
add(Set<E>), and tests for disjointness to all previously entered classes.
The problem is, that I am building up those classes in the process: I
make an empty set, add the element, then go on finding equivalent
elements, and add those, then when I am sure there are no more (i.e.
after I have compared the first with all others), add the class to the
equivalence.

You'd think HashSet would be a useful tool for arranging unique
Objects. However, it is useless for that purpose because it will only
tell you if an equivalent Object is already in the HashSet. It won't
divulge a reference to the canonical Object itself. To arrange
uniqueness, you need a HashMap with key and value referencing the same
canonical unique Object.

Yes, but I plan on making the classes first and then adding them, once
they are complete. Maybe I should rethink my strategy.

And thanks for the pointers to EnumSet (not usable, there are way too
much States to use the State Pattern, and they are created dynamically),
and BitSet. I think I will revert to the latter in a later stage of
implementation, for now, I?m happy if it works, be it less efficiently.

H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD9bKee+7xMGD3itQRAuE9AJ41zbHm5VZY/GcmvgicjgEaaEiyOgCePDzY
08uItSJtho4g6hyWHrbh99M=
=1Cxm
-----END PGP SIGNATURE-----