1//===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Generic implementation of equivalence classes through the use Tarjan's
11// efficient union-find algorithm.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_EQUIVALENCECLASSES_H
16#define LLVM_ADT_EQUIVALENCECLASSES_H
17
18#include "llvm/Support/DataTypes.h"
19#include <cassert>
20#include <set>
21
22namespace llvm {
23
24/// EquivalenceClasses - This represents a collection of equivalence classes and
25/// supports three efficient operations: insert an element into a class of its
26/// own, union two classes, and find the class for a given element.  In
27/// addition to these modification methods, it is possible to iterate over all
28/// of the equivalence classes and all of the elements in a class.
29///
30/// This implementation is an efficient implementation that only stores one copy
31/// of the element being indexed per entry in the set, and allows any arbitrary
32/// type to be indexed (as long as it can be ordered with operator<).
33///
34/// Here is a simple example using integers:
35///
36///  EquivalenceClasses<int> EC;
37///  EC.unionSets(1, 2);                // insert 1, 2 into the same set
38///  EC.insert(4); EC.insert(5);        // insert 4, 5 into own sets
39///  EC.unionSets(5, 1);                // merge the set for 1 with 5's set.
40///
41///  for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end();
42///       I != E; ++I) {           // Iterate over all of the equivalence sets.
43///    if (!I->isLeader()) continue;   // Ignore non-leader sets.
44///    for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I);
45///         MI != EC.member_end(); ++MI)   // Loop over members in this set.
46///      cerr << *MI << " ";  // Print member.
47///    cerr << "\n";   // Finish set.
48///  }
49///
50/// This example prints:
51///   4
52///   5 1 2
53///
54template <class ElemTy>
55class EquivalenceClasses {
56  /// ECValue - The EquivalenceClasses data structure is just a set of these.
57  /// Each of these represents a relation for a value.  First it stores the
58  /// value itself, which provides the ordering that the set queries.  Next, it
59  /// provides a "next pointer", which is used to enumerate all of the elements
60  /// in the unioned set.  Finally, it defines either a "end of list pointer" or
61  /// "leader pointer" depending on whether the value itself is a leader.  A
62  /// "leader pointer" points to the node that is the leader for this element,
63  /// if the node is not a leader.  A "end of list pointer" points to the last
64  /// node in the list of members of this list.  Whether or not a node is a
65  /// leader is determined by a bit stolen from one of the pointers.
66  class ECValue {
67    friend class EquivalenceClasses;
68    mutable const ECValue *Leader, *Next;
69    ElemTy Data;
70    // ECValue ctor - Start out with EndOfList pointing to this node, Next is
71    // Null, isLeader = true.
72    ECValue(const ElemTy &Elt)
73      : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {}
74
75    const ECValue *getLeader() const {
76      if (isLeader()) return this;
77      if (Leader->isLeader()) return Leader;
78      // Path compression.
79      return Leader = Leader->getLeader();
80    }
81    const ECValue *getEndOfList() const {
82      assert(isLeader() && "Cannot get the end of a list for a non-leader!");
83      return Leader;
84    }
85
86    void setNext(const ECValue *NewNext) const {
87      assert(getNext() == 0 && "Already has a next pointer!");
88      Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader());
89    }
90  public:
91    ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1),
92                                  Data(RHS.Data) {
93      // Only support copying of singleton nodes.
94      assert(RHS.isLeader() && RHS.getNext() == 0 && "Not a singleton!");
95    }
96
97    bool operator<(const ECValue &UFN) const { return Data < UFN.Data; }
98
99    bool isLeader() const { return (intptr_t)Next & 1; }
100    const ElemTy &getData() const { return Data; }
101
102    const ECValue *getNext() const {
103      return (ECValue*)((intptr_t)Next & ~(intptr_t)1);
104    }
105
106    template<typename T>
107    bool operator<(const T &Val) const { return Data < Val; }
108  };
109
110  /// TheMapping - This implicitly provides a mapping from ElemTy values to the
111  /// ECValues, it just keeps the key as part of the value.
112  std::set<ECValue> TheMapping;
113
114public:
115  EquivalenceClasses() {}
116  EquivalenceClasses(const EquivalenceClasses &RHS) {
117    operator=(RHS);
118  }
119
120  const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) {
121    TheMapping.clear();
122    for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I)
123      if (I->isLeader()) {
124        member_iterator MI = RHS.member_begin(I);
125        member_iterator LeaderIt = member_begin(insert(*MI));
126        for (++MI; MI != member_end(); ++MI)
127          unionSets(LeaderIt, member_begin(insert(*MI)));
128      }
129    return *this;
130  }
131
132  //===--------------------------------------------------------------------===//
133  // Inspection methods
134  //
135
136  /// iterator* - Provides a way to iterate over all values in the set.
137  typedef typename std::set<ECValue>::const_iterator iterator;
138  iterator begin() const { return TheMapping.begin(); }
139  iterator end() const { return TheMapping.end(); }
140
141  bool empty() const { return TheMapping.empty(); }
142
143  /// member_* Iterate over the members of an equivalence class.
144  ///
145  class member_iterator;
146  member_iterator member_begin(iterator I) const {
147    // Only leaders provide anything to iterate over.
148    return member_iterator(I->isLeader() ? &*I : 0);
149  }
150  member_iterator member_end() const {
151    return member_iterator(0);
152  }
153
154  /// findValue - Return an iterator to the specified value.  If it does not
155  /// exist, end() is returned.
156  iterator findValue(const ElemTy &V) const {
157    return TheMapping.find(V);
158  }
159
160  /// getLeaderValue - Return the leader for the specified value that is in the
161  /// set.  It is an error to call this method for a value that is not yet in
162  /// the set.  For that, call getOrInsertLeaderValue(V).
163  const ElemTy &getLeaderValue(const ElemTy &V) const {
164    member_iterator MI = findLeader(V);
165    assert(MI != member_end() && "Value is not in the set!");
166    return *MI;
167  }
168
169  /// getOrInsertLeaderValue - Return the leader for the specified value that is
170  /// in the set.  If the member is not in the set, it is inserted, then
171  /// returned.
172  const ElemTy &getOrInsertLeaderValue(const ElemTy &V) {
173    member_iterator MI = findLeader(insert(V));
174    assert(MI != member_end() && "Value is not in the set!");
175    return *MI;
176  }
177
178  /// getNumClasses - Return the number of equivalence classes in this set.
179  /// Note that this is a linear time operation.
180  unsigned getNumClasses() const {
181    unsigned NC = 0;
182    for (iterator I = begin(), E = end(); I != E; ++I)
183      if (I->isLeader()) ++NC;
184    return NC;
185  }
186
187
188  //===--------------------------------------------------------------------===//
189  // Mutation methods
190
191  /// insert - Insert a new value into the union/find set, ignoring the request
192  /// if the value already exists.
193  iterator insert(const ElemTy &Data) {
194    return TheMapping.insert(ECValue(Data)).first;
195  }
196
197  /// findLeader - Given a value in the set, return a member iterator for the
198  /// equivalence class it is in.  This does the path-compression part that
199  /// makes union-find "union findy".  This returns an end iterator if the value
200  /// is not in the equivalence class.
201  ///
202  member_iterator findLeader(iterator I) const {
203    if (I == TheMapping.end()) return member_end();
204    return member_iterator(I->getLeader());
205  }
206  member_iterator findLeader(const ElemTy &V) const {
207    return findLeader(TheMapping.find(V));
208  }
209
210
211  /// union - Merge the two equivalence sets for the specified values, inserting
212  /// them if they do not already exist in the equivalence set.
213  member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) {
214    iterator V1I = insert(V1), V2I = insert(V2);
215    return unionSets(findLeader(V1I), findLeader(V2I));
216  }
217  member_iterator unionSets(member_iterator L1, member_iterator L2) {
218    assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!");
219    if (L1 == L2) return L1;   // Unifying the same two sets, noop.
220
221    // Otherwise, this is a real union operation.  Set the end of the L1 list to
222    // point to the L2 leader node.
223    const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node;
224    L1LV.getEndOfList()->setNext(&L2LV);
225
226    // Update L1LV's end of list pointer.
227    L1LV.Leader = L2LV.getEndOfList();
228
229    // Clear L2's leader flag:
230    L2LV.Next = L2LV.getNext();
231
232    // L2's leader is now L1.
233    L2LV.Leader = &L1LV;
234    return L1;
235  }
236
237  class member_iterator : public std::iterator<std::forward_iterator_tag,
238                                               const ElemTy, ptrdiff_t> {
239    typedef std::iterator<std::forward_iterator_tag,
240                          const ElemTy, ptrdiff_t> super;
241    const ECValue *Node;
242    friend class EquivalenceClasses;
243  public:
244    typedef size_t size_type;
245    typedef typename super::pointer pointer;
246    typedef typename super::reference reference;
247
248    explicit member_iterator() {}
249    explicit member_iterator(const ECValue *N) : Node(N) {}
250    member_iterator(const member_iterator &I) : Node(I.Node) {}
251
252    reference operator*() const {
253      assert(Node != 0 && "Dereferencing end()!");
254      return Node->getData();
255    }
256    reference operator->() const { return operator*(); }
257
258    member_iterator &operator++() {
259      assert(Node != 0 && "++'d off the end of the list!");
260      Node = Node->getNext();
261      return *this;
262    }
263
264    member_iterator operator++(int) {    // postincrement operators.
265      member_iterator tmp = *this;
266      ++*this;
267      return tmp;
268    }
269
270    bool operator==(const member_iterator &RHS) const {
271      return Node == RHS.Node;
272    }
273    bool operator!=(const member_iterator &RHS) const {
274      return Node != RHS.Node;
275    }
276  };
277};
278
279} // End llvm namespace
280
281#endif
282