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 #ifndef FIRM_ADT_UNIONFIND_H
26 #define FIRM_ADT_UNIONFIND_H
34 * @defgroup unionfind Union-Find
35 * Union-Find datastructure
37 * This implementation uses weighted sets and path compression which results
38 * in (nearly) O(n) complexity for n find and union operations
43 * Call this to initialize an array of @p count elements to be used by the
44 * union find functions.
46 * @param data The array (you have to allocate it yourself)
47 * @param n_elems number of elements handled by the datastructure
49 static inline void uf_init(int* data, size_t n_elems)
52 for(i = 0; i < n_elems; ++i) {
58 * Merge 2 sets (union operation). Note that you have to pass the
59 * representatives of the sets and not just random elements
61 * @param data The union find data
62 * @param set1 Representative of set1
63 * @param set2 Representative of set2
64 * @return the new representative of the set (which is set1 or set2)
66 static inline int uf_union(int* data, int set1, int set2)
75 /* need 2 set representatives */
78 assert(d1 < 0 && d2 < 0);
83 data[set2] = newcount;
87 data[set1] = newcount;
93 * Finds the representative for the set with member @p e.
94 * The representative of a set is unique, so if the find operations finds
95 * the same/different representatives, then the elements are in the
96 * the same/different sets.
98 * @param data The union find data
99 * @param e The element
100 * @return The representative of the set that contains @p e
102 static inline int uf_find(int* data, int e)
104 /* go through list to find representative */
106 while(data[repr] >= 0) {
110 /* update list to point to new representative (path compression) */