On 5/9/07, <b class="gmail_sendername">David Greene</b> <<a href="mailto:greened@obbligato.org">greened@obbligato.org</a>> wrote:<div><span class="gmail_quote"></span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Can someone explain the terminology used in the Doxygen comments for EquivalenceClasses?  Specifically, what is a "Leader" as opposed to other members of an equivalence class?</blockquote><div> As far as I understand, leader is the first element of the class within the std::set container where all element of all classes are stored altogether. Leader contains a pointer to the last element of the class. The idea is similar to storing multiple linked lists in an array or in a vector. Leader elements allow iterating through class elements only via EquivalenceClasses::member_begin, member_end methods. Except of that there is no difference between the leader and the rest members of an equivalence class here.

<br><br>These leaders doesn't relate to coset leaders or something, AFAIK. It's not a mathematical notion there.<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Say, for example, I want to create a set of equivalence<br>classes to specify subset relationships.  Imagine B is<br>a subset of A, C is a subset of B, E is a subset of D<br>and D has no relation to any other set.  I'd like to

<br>group things into equivalence classes representing<br>"immediate" subsets:<br><br>Class 1: A, B<br>Class 2: B, C<br>Class 3: D, E</blockquote><div><br>I don't understand how A and B, for example, are equivalent. B is a subset of A but not vice versa. Thus your relation is not symmetric. 

<br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Would A, B and D be the "Leaders" of the equivalence classes?<br>Note that I don't want {A, B, C} as an equivalence class

<br>because it breaks the "immediate subset" relationship.<br><br>With a relationship like equality, there is no problem because<br>no member of the equivalence class has any different information<br>about it than any other.  But a relation like "subset" implies

<br>that members of the equivalence class are not all equal.</blockquote><div><br>Equivalence classes are defined via equivalence relation. Subset is not one so this data structure just won't work correctly. I think that your relation should be represented by another structure. 

E.g. undirected graph can be used to represent any binary relation (if you chose binary matrix representation I'd recommend using BitSetVector data structure found in include/llvm/ADT directory).<br></div></div><br>FYI, in linear scan register allocator EquivalenceClasses object is used to divide register classes via "alias" relation. See ComputeRelatedRegClasses method in 

RegAllocLinearScan.cpp.<br>

Anton.