2 * Copyright (C) 1995-2008 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 n_elems number of elements handled by the datastructure
43 static inline void uf_init(int* data, size_t n_elems)
46 for(i = 0; i < n_elems; ++i) {
52 * Merge 2 sets (union operation). Note that you have to pass the
53 * representatives of the sets and not just random elements
55 * @param data The union find data
56 * @param set1 Representative of set1
57 * @param set2 Representative of set2
58 * @return 0 if the new union set is represented by set1, 1 if it is
61 static inline int uf_union(int* data, int set1, int set2)
70 /* need 2 set representatives */
73 assert(d1 < 0 && d2 < 0);
78 data[set2] = newcount;
82 data[set1] = newcount;
88 * Finds the representative for the set with member @p e.
89 * The representative of a set is unique, so if the find operations finds
90 * the same/different representatives, then the elements are in the
91 * the same/different sets.
93 * @param data The union find data
94 * @param e The element
95 * @return The representative of the set that contains @p e
97 static inline int uf_find(int* data, int e)
99 /* go through list to find representative */
101 while(data[repr] >= 0) {
105 /* update list to point to new representative (path compression) */