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
25 * Union-Find datastructure
27 * This implementation uses weighted sets and path compression which results
28 * in (nearly) O(n) complexity for n find and union operations
30 #ifndef FIRM_ADT_UNIONFIND_H
31 #define FIRM_ADT_UNIONFIND_H
38 * Call this to initialize an array of @p count elements to be used by the
39 * union find functions.
41 * @param data The array (you have to allocate it yourself)
42 * @param n_elems number of elements handled by the datastructure
44 static inline void uf_init(int* data, size_t n_elems)
47 for(i = 0; i < n_elems; ++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 the new representative of the set (which is set1 or set2)
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) */