Avoiding failsafe behaviour of iterators

Discussion in 'Java' started by Hendrik Maryns, Feb 15, 2006.

  1. -----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-----
     
    Hendrik Maryns, Feb 15, 2006
    #1
    1. Advertising

  2. Hendrik Maryns wrote:
    > - 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
     
    tom fredriksen, Feb 15, 2006
    #2
    1. Advertising

  3. Hendrik Maryns

    Adam Maass Guest

    "Hendrik Maryns" <> wrote:
    > -----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.)
     
    Adam Maass, Feb 15, 2006
    #3
  4. Hendrik Maryns

    Chris Uppal Guest

    Hendrik Maryns wrote:

    > 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
     
    Chris Uppal, Feb 15, 2006
    #4
  5. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1
    NotDashEscaped: You need GnuPG to verify this message

    tom fredriksen schreef:
    > Hendrik Maryns wrote:
    >> - 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.


    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, Feb 15, 2006
    #5
  6. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1
    NotDashEscaped: You need GnuPG to verify this message

    Adam Maass schreef:
    > "Hendrik Maryns" <> wrote:
    >> 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.


    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, Feb 15, 2006
    #6
  7. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1
    NotDashEscaped: You need GnuPG to verify this message

    Chris Uppal schreef:
    > Hendrik Maryns wrote:
    >
    >> 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
    > }
    > }


    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-----
     
    Hendrik Maryns, Feb 15, 2006
    #7
  8. 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
    --
    The most horrifying thing about Unix is that, no matter how many times you hit
    yourself over the head with it, you never quite manage to lose consciousness.
    It just goes on and on. -- Patrick Sobalvarro
     
    Dimitri Maziuk, Feb 15, 2006
    #8
  9. Adam Maass wrote:
    >
    > 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
    --
    Unemployed English Java programmer
    http://jroller.com/page/tackline/
     
    Thomas Hawtin, Feb 15, 2006
    #9
  10. Hendrik Maryns

    P.Hill Guest

    Hendrik Maryns wrote:
    > 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
     
    P.Hill, Feb 16, 2006
    #10
  11. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1
    NotDashEscaped: You need GnuPG to verify this message

    P.Hill schreef:
    > Hendrik Maryns wrote:
    >> 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.


    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-----
     
    Hendrik Maryns, Feb 16, 2006
    #11
  12. Hendrik Maryns

    Roedy Green Guest

    On Wed, 15 Feb 2006 19:24:07 -0800, "P.Hill"
    <> wrote, quoted or indirectly quoted
    someone who said :

    >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
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
     
    Roedy Green, Feb 16, 2006
    #12
  13. 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.

    --
    All whitespace is equivalent except in certain situations
    -- ANSI C standard committee
     
    Dimitri Maziuk, Feb 16, 2006
    #13
  14. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1
    NotDashEscaped: You need GnuPG to verify this message

    Roedy Green schreef:
    > On Wed, 15 Feb 2006 19:24:07 -0800, "P.Hill"
    > <> wrote, quoted or indirectly quoted
    > someone who said :
    >
    >> 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.


    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-----
     
    Hendrik Maryns, Feb 17, 2006
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    510
    Kai-Uwe Bux
    May 8, 2005
  2. Replies:
    3
    Views:
    351
    =?iso-8859-1?q?Kirit_S=E6lensminde?=
    May 2, 2007
  3. Andy Chambers
    Replies:
    1
    Views:
    403
    Daniel Dyer
    May 14, 2007
  4. ZikO
    Replies:
    7
    Views:
    359
  5. , India
    Replies:
    10
    Views:
    1,099
    James Kanze
    Aug 8, 2009
Loading...

Share This Page