2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Union-Find datastructure
23 * @author Matthias Braun
26 * Union-Find datastructure
28 * This implementation uses weighted sets and path compression which results
29 * in (nearly) O(n) complexity for n find and union operations
31 #ifndef FIRM_ADT_UNIONFIND_H
32 #define FIRM_ADT_UNIONFIND_H
37 * Call this to initialize an array of @p count elements to be used by the
38 * union find functions.
40 * @param data The array (you have to allocate it yourself)
41 * @param from The first element that should be intialized
42 * @param to the index of the first element which is not initialized anymore
44 static INLINE void uf_init(int* data, int from, int to)
47 for(i = from; i < to; ++i) {
53 * Merge 2 sets (union operation). Note that you have to pass the
54 * representatives of the sets and not just random elements
56 * @param data The union find data
57 * @param set1 Representative of set1
58 * @param set2 Representative of set2
59 * @return 0 if the new union set is represented by set1, 1 if it is
62 static INLINE int uf_union(int* data, int set1, int set2) {
70 // need 2 set representatives
71 assert(d1 < 0 && d2 < 0);
76 data[set2] = newcount;
80 data[set1] = newcount;
86 * Finds the representative for the set with member @p e.
87 * The representative of a set is unique, so if the find operations finds
88 * the same/different representatives, then the elements are in the
89 * the same/different sets.
91 * @param data The union find data
92 * @param e The element
93 * @return The representative of the set that contains @p e
95 static INLINE int uf_find(int* data, int e) {
96 // go through list to find representative
98 while(data[repr] >= 0) {
102 // update list to point to new representative (path compression)