Line data Source code
1 : /* src/vm/jit/compiler2/UnionFind.hpp - UnionFind
2 :
3 : Copyright (C) 1996-2013
4 : CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
5 :
6 : This file is part of CACAO.
7 :
8 : This program is free software; you can redistribute it and/or
9 : modify it under the terms of the GNU General Public License as
10 : published by the Free Software Foundation; either version 2, or (at
11 : your option) any later version.
12 :
13 : This program is distributed in the hope that it will be useful, but
14 : WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 : General Public License for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with this program; if not, write to the Free Software
20 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 : 02110-1301, USA.
22 :
23 : */
24 :
25 : #ifndef _TOOLBOX_UNIONFIND_HPP
26 : #define _TOOLBOX_UNIONFIND_HPP
27 :
28 : #include <list>
29 : #include <set>
30 :
31 : namespace cacao {
32 :
33 :
34 : template <typename T>
35 0 : class UnionFind {
36 : public:
37 : /**
38 : * Create a new set
39 : *
40 : * @param s elements
41 : **/
42 : virtual void make_set(T s) = 0;
43 : /**
44 : * union the set that contains r with the set that contains s
45 : *
46 : * @param r repres of a set
47 : * @param s repres of a set
48 : * @return the new repres
49 : *
50 : **/
51 : virtual T set_union(T r, T s) = 0;
52 : /**
53 : * find the repres to of a given element x
54 : *
55 : * @param x an element of the union find ds
56 : * @return the repres of x
57 : **/
58 : virtual T find(T x) = 0;
59 :
60 : };
61 :
62 : template <typename T>
63 0 : class UnionFindImpl : public UnionFind<T> {
64 : private:
65 : typedef typename std::set<T> SetTy;
66 : typedef typename std::set<SetTy> SetSetTy;
67 : SetSetTy sets;
68 : T &my_end;
69 :
70 0 : typename SetSetTy::iterator find_it(T x) {
71 0 : for (typename SetSetTy::iterator i = sets.begin(), e = sets.end();
72 : i != e; ++i) {
73 0 : SetTy set = *i;
74 0 : if (std::find(set.begin(),set.end(),x) != set.end()) {
75 0 : return i;
76 : }
77 : }
78 0 : return sets.end();
79 : }
80 : public:
81 0 : UnionFindImpl(T &end) : my_end(end) {}
82 :
83 0 : virtual void make_set(T s) {
84 0 : assert(find(s) == end() && "Element already in a set!");
85 : //LOG2("UnionFindImpl:make_set: " << s << nl);
86 0 : SetTy list;
87 0 : list.insert(s);
88 0 : sets.insert(list);
89 0 : }
90 :
91 0 : virtual T set_union(T r, T s) {
92 0 : typename SetSetTy::iterator r_it, s_it;
93 0 : r_it = find_it(r);
94 0 : s_it = find_it(s);
95 :
96 0 : if ( r_it == s_it )
97 0 : return *(r_it->begin());
98 0 : if ( r_it == sets.end() || s_it == sets.end() )
99 0 : return end();
100 0 : SetTy merged;
101 0 : merged.insert(s_it->begin(), s_it->end());
102 0 : merged.insert(r_it->begin(), r_it->end());
103 :
104 : //LOG2("UnionFindImpl:merginig: ");
105 : //DEBUG2(print_container(dbg(), s_it->begin(), s_it->end()) << " and ");
106 : //DEBUG2(print_container(dbg(), r_it->begin(), r_it->end()) << nl);
107 : //LOG2("UnionFindImpl:result: ");
108 : //DEBUG2(print_container(dbg(), merged.begin(), merged.end()) << nl);
109 :
110 0 : sets.erase(s_it);
111 0 : sets.erase(r_it);
112 0 : sets.insert(merged);
113 0 : return *merged.begin();
114 : }
115 :
116 0 : virtual T find(T x) {
117 0 : typename SetSetTy::iterator i = find_it(x);
118 : //LOG2("UnionFindImpl:find: " << x << nl);
119 0 : if (i != sets.end())
120 0 : return *(*i).begin();
121 0 : return end();
122 : }
123 :
124 0 : T &end() {
125 0 : return my_end;
126 : }
127 :
128 : };
129 :
130 : } // end namespace cacao
131 :
132 : #endif /* _TOOLBOX_UNIONFIND_HPP */
133 :
134 : /*
135 : * These are local overrides for various environment variables in Emacs.
136 : * Please do not remove this and leave it at the end of the file, where
137 : * Emacs will automagically detect them.
138 : * ---------------------------------------------------------------------
139 : * Local variables:
140 : * mode: c++
141 : * indent-tabs-mode: t
142 : * c-basic-offset: 4
143 : * tab-width: 4
144 : * End:
145 : * vim:noexpandtab:sw=4:ts=4:
146 : */
147 :
|
