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
23 * Call this to initialize an array of @p count elements to be used by the
24 * union find functions.
26 * @param data The array (you have to allocate it yourself)
27 * @param from The first element that should be intialized
28 * @param to the index of the first element which is not initialized anymore
30 static INLINE void uf_init(int* data, int from, int to)
33 for(i = from; i < to; ++i) {
39 * Merge 2 sets (union operation). Note that you have to pass the
40 * representatives of the sets and not just random elements
42 * @param data The union find data
43 * @param set1 Representative of set1
44 * @param set2 Representative of set2
45 * @return 0 if the new union set is represented by set1, 1 if it is
48 static INLINE int uf_union(int* data, int set1, int set2) {
56 // need 2 set represantatives
57 assert(d1 < 0 && d2 < 0);
62 data[set2] = newcount;
66 data[set1] = newcount;
72 * Finds the representative for the set with member @p e.
73 * The representative of a set is unique, so if the find operations
74 * 2 similar/different representatives, then the elements are in the
75 * same/2 different sets.
77 * @param data The union find data
78 * @param e The element
79 * @return The representative of the set that contains @p e
81 static INLINE int uf_find(int* data, int e) {
82 // go through list to find representative
84 while(data[repr] >= 0) {
88 // update list to point to new representative (path compression)