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 from The first element that should be initialized
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) {
46 for(i = from; i < to; ++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) {
69 /* need 2 set representatives */
70 assert(d1 < 0 && d2 < 0);
75 data[set2] = newcount;
79 data[set1] = newcount;
85 * Finds the representative for the set with member @p e.
86 * The representative of a set is unique, so if the find operations finds
87 * the same/different representatives, then the elements are in the
88 * the same/different sets.
90 * @param data The union find data
91 * @param e The element
92 * @return The representative of the set that contains @p e
94 static INLINE int uf_find(int* data, int e) {
95 /* go through list to find representative */
97 while(data[repr] >= 0) {
101 /* update list to point to new representative (path compression) */
111 #endif /* FIRM_ADT_UNIONFIND_H */