EquivalenceClasses: findValue vs. findLeader

Given an object o of ElemType in an instance of EquivalenceClasses, I need
to get a list of all members of the equivalence class that o is in. For
various reasons, it is easiest if I could get an EquivalenceClasses::iterator
that I can pass to member_begin and member_end.

So naturally, I did something like this (pseudo-C++):

EquivalenceClasses::iterator i = equiv.findValue(o);
for(equiv.member_begin(i); member_end(i); ++i) {
   // Do stuff
}

Unfortunately, this doesn't seem to work. findValue returns an iterator that
is not end(), but the member set of the equivalence class is empty.

Strangly, when I just iterate through the EquivalenceClasses object like this:

        for(iterator i = equiv.begin(),
                iend = equiv.end();
            i != iend;
            ++i) {
          DOUT << "### New set:\n";
          for(member_iterator j =
                  equiv.member_begin(i),
                  jend = equiv.member_end(i);
                j != jend;
                ++j) {
            dump_member(*j);
            DOUT << "\n";
          }
        }

I get something like this:

### New set:
### New set:
### New set:
### New set:
### New set:
### New set:
a
b
### New set:
### New set:
c
d
e
f
### New set:
g
### New set:
h
### New set:
i
j

Why all the empty sets? Is this an artifact of the path compression?

What does findLeader do? Does it return a member iterator that is at the
beginning of the list of equivalence class members? The Doxygen
documentation seems to indicate that it does not, but returns a
member_iterator pointing to o. But then what is a "Leader" and why do
I care?

                                               -Dave

Given an object o of ElemType in an instance of EquivalenceClasses, I need
to get a list of all members of the equivalence class that o is in. For
various reasons, it is easiest if I could get an EquivalenceClasses::iterator
that I can pass to member_begin and member_end.

ok

So naturally, I did something like this (pseudo-C++):

EquivalenceClasses::iterator i = equiv.findValue(o);
for(equiv.member_begin(i); member_end(i); ++i) {
  // Do stuff
}

Unfortunately, this doesn't seem to work. findValue returns an iterator that
is not end(), but the member set of the equivalence class is empty.

Right. Conceptually, the range of elements in a set consist of [leader, end). You want something like this:

  EquivalenceClasses::iterator i = equiv.findValue(o);
  i = equiv.getleaderfor(i);
  for(equiv.member_begin(i); member_end(i); ++i) {
    // Do stuff
  }

Strangly, when I just iterate through the EquivalenceClasses object like this:

...

I get something like this:

### New set:
a
b
### New set:
c
Why all the empty sets? Is this an artifact of the path compression?

This is an artifact of member_begin:

   /// member_* Iterate over the members of an equivalence class.
   ///
   class member_iterator;
   member_iterator member_begin(iterator I) const {
     // Only leaders provide anything to iterate over.
     return member_iterator(I->isLeader() ? &*I : 0);
   }

member_begin only works on leaders.

What does findLeader do? Does it return a member iterator that is at the
beginning of the list of equivalence class members?

Yep.

The Doxygen
documentation seems to indicate that it does not, but returns a
member_iterator pointing to o. But then what is a "Leader" and why do
I care?

You care a lot, you need it to get the start of the member range of the subset.

-Chris