llvm dev - Jun 2007 - [LLVMdev] 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

On Fri, 15 Jun 2007, David A. Greene wrote:
> 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:
> ### New set:
> ### New set:
> ### New set:
> ### New set:
> ### New set:
> a
> b
> ### New set:
> ### 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

-- 
http://nondot.org/sabre/
http://llvm.org/