3 * File name: ir/adt/unionfind.h
4 * Purpose: Union-Find datastructure
5 * Author: Matthias Braun
8 * Copyright: (c) 2006, Matthias Braun
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
15 * Union-Find datastructure
17 * This implementation uses weighted sets and path compression which results
18 * in O(n) complexity for n find and union operations (actually it's
19 * n * alpha(n) with alpha being the inverse of the ackermann function and
20 * therefore smaller than 5 for all 64bit values of n)
28 * Call this to initialize an array of @p count elements to be used by the
29 * union find functions.
31 * @param data The array (you have to allocate it yourself)
32 * @param from The first element that should be intialized
33 * @param to the index of the first element which is not initialized anymore
35 static INLINE void uf_init(int* data, int from, int to)
38 for(i = from; i < to; ++i) {
44 * Merge 2 sets (union operation). Note that you have to pass the
45 * representatives of the sets and not just random elements
47 * @param data The union find data
48 * @param set1 Representative of set1
49 * @param set2 Representative of set2
50 * @return 0 if the new union set is represented by set1, 1 if it is
53 static INLINE int uf_union(int* data, int set1, int set2) {
61 // need 2 set representatives
62 assert(d1 < 0 && d2 < 0);
67 data[set2] = newcount;
71 data[set1] = newcount;
77 * Finds the representative for the set with member @p e.
78 * The representative of a set is unique, so if the find operations finds
79 * the same/different representatives, then the elements are in the
80 * the same/different sets.
82 * @param data The union find data
83 * @param e The element
84 * @return The representative of the set that contains @p e
86 static INLINE int uf_find(int* data, int e) {
87 // go through list to find representative
89 while(data[repr] >= 0) {
93 // update list to point to new representative (path compression)