1.1 --- a/src/work/johanna/unionfind.h Sat Apr 24 15:19:17 2004 +0000
1.2 +++ b/src/work/johanna/unionfind.h Sat Apr 24 16:03:25 2004 +0000
1.3 @@ -3,7 +3,11 @@
1.4 #define HUGO_UNION_FIND_H
1.5
1.6 #include <vector>
1.7 +#include <list>
1.8 #include <utility>
1.9 +#include <algorithm>
1.10 +
1.11 +#include <invalid.h>
1.12
1.13 namespace hugo {
1.14
1.15 @@ -22,11 +26,11 @@
1.16 UnionFind(TIntMap& m) : map(m) {}
1.17
1.18
1.19 - int whichComponent(T a)
1.20 + int find(T a)
1.21 {
1.22 int comp0 = map[a];
1.23 if (comp0 < 0) {
1.24 - return insertNewElement(a);
1.25 + return insert(a);
1.26 }
1.27 int comp = comp0;
1.28 int next;
1.29 @@ -41,18 +45,18 @@
1.30 return comp;
1.31 }
1.32
1.33 - int insertNewElement(T a)
1.34 + int insert(T a)
1.35 {
1.36 int n = data.size();
1.37 - data.push_back(make_pair(n, 1));
1.38 + data.push_back(std::make_pair(n, 1));
1.39 map.set(a,n);
1.40 return n;
1.41 }
1.42
1.43 - bool joinComponents(T a, T b)
1.44 + bool join(T a, T b)
1.45 {
1.46 - int ca = whichComponent(a);
1.47 - int cb = whichComponent(b);
1.48 + int ca = find(a);
1.49 + int cb = find(b);
1.50
1.51 if ( ca == cb )
1.52 return false;
1.53 @@ -68,14 +72,303 @@
1.54 return true;
1.55 }
1.56
1.57 - int componentSize(T a)
1.58 + int size(T a)
1.59 {
1.60 - int ca = whichComponent(a);
1.61 + int ca = find(a);
1.62 return data[ca].second;
1.63 }
1.64
1.65 };
1.66
1.67 +
1.68 +
1.69 +
1.70 + /*******************************************************/
1.71 +
1.72 +
1.73 +
1.74 + template <typename T>
1.75 + struct UnionFindEnumItem {
1.76 +
1.77 + typedef std::list<UnionFindEnumItem> ItemList;
1.78 + typedef std::list<ItemList> ClassList;
1.79 + typedef typename ItemList::iterator IIter;
1.80 + typedef typename ClassList::iterator CIter;
1.81 +
1.82 + T me;
1.83 + IIter parent;
1.84 + int size;
1.85 + CIter my_class;
1.86 +
1.87 + UnionFindEnumItem() {}
1.88 + UnionFindEnumItem(const T &_me, CIter _my_class):
1.89 + me(_me), size(1), my_class(_my_class) {}
1.90 + };
1.91 +
1.92 + template <typename T, template <typename Item> class Map>
1.93 + class UnionFindEnum {
1.94 +
1.95 + typedef std::list<UnionFindEnumItem<T> > ItemList;
1.96 + typedef std::list<ItemList> ClassList;
1.97 + typedef typename ItemList::iterator IIter;
1.98 + typedef typename ItemList::const_iterator IcIter;
1.99 + typedef typename ClassList::iterator CIter;
1.100 + typedef typename ClassList::const_iterator CcIter;
1.101 +
1.102 + public:
1.103 + typedef T ElementType;
1.104 + typedef UnionFindEnumItem<T> ItemType;
1.105 + typedef Map< IIter > MapType;
1.106 +
1.107 + private:
1.108 + MapType& m;
1.109 + ClassList classes;
1.110 +
1.111 + // IIter where(const T &a) { return m[a]; }
1.112 + // IIter parent(IIter a) { return a->parent; }
1.113 + // P sibling(P a) { return &m[a->sibling]; }
1.114 +
1.115 + IIter _find(IIter a) const {
1.116 + IIter comp = a;
1.117 + IIter next;
1.118 + while( (next = comp->parent) != comp ) {
1.119 + comp = next;
1.120 + }
1.121 +
1.122 + IIter comp1 = a;
1.123 + while( (next = comp1->parent) != comp ) {
1.124 + comp1->parent = comp->parent;
1.125 + comp1 = next;
1.126 + }
1.127 + return comp;
1.128 + }
1.129 +
1.130 + public:
1.131 + UnionFindEnum(MapType& _m) : m(_m) {}
1.132 +
1.133 + void insert(const T &a)
1.134 + {
1.135 +
1.136 +
1.137 + classes.push_back(ItemList());
1.138 + CIter aclass = classes.end();
1.139 + --aclass;
1.140 +
1.141 + ItemList &alist = *aclass;
1.142 + alist.push_back(ItemType(a, aclass));
1.143 + IIter ai = alist.begin();
1.144 +
1.145 + ai->parent = ai;
1.146 + m.set(a, ai);
1.147 +
1.148 + }
1.149 +
1.150 + T find(const T &a) const {
1.151 + return _find(m[a])->me;
1.152 + }
1.153 +
1.154 + bool join(T a, T b) {
1.155 +
1.156 + IIter ca = _find(m[a]);
1.157 + IIter cb = _find(m[b]);
1.158 +
1.159 + if ( ca == cb ) {
1.160 + return false;
1.161 + }
1.162 +
1.163 + if ( ca->size > cb->size ) {
1.164 +
1.165 + cb->parent = ca->parent;
1.166 + ca->size += cb->size;
1.167 +
1.168 + ItemList &alist = *ca->my_class;
1.169 + alist.splice(alist.end(),*cb->my_class);
1.170 +
1.171 + classes.erase(cb->my_class);
1.172 + cb->my_class = 0;
1.173 + }
1.174 + else {
1.175 +
1.176 + ca->parent = cb->parent;
1.177 + cb->size += ca->size;
1.178 +
1.179 + ItemList &blist = *cb->my_class;
1.180 + blist.splice(blist.end(),*ca->my_class);
1.181 +
1.182 + classes.erase(ca->my_class);
1.183 + ca->my_class = 0;
1.184 + }
1.185 +
1.186 + return true;
1.187 + }
1.188 +
1.189 + int size(const T &a) const {
1.190 + return _find(m[a])->size;
1.191 + }
1.192 +
1.193 +
1.194 + void split(const T &a) {
1.195 +
1.196 + IIter ca = _find(m[a]);
1.197 +
1.198 + if ( ca->size == 1 )
1.199 + return;
1.200 +
1.201 + CIter aclass = ca->my_class;
1.202 +
1.203 + for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
1.204 + classes.push_back(ItemList());
1.205 + CIter nl = --classes.end();
1.206 + nl->splice(nl->end(), *aclass, curr);
1.207 +
1.208 + curr->size=1;
1.209 + curr->parent=curr;
1.210 + curr->my_class = nl;
1.211 + }
1.212 +
1.213 + ca->size=1;
1.214 + return;
1.215 + }
1.216 +
1.217 + void erase(const T &a) {
1.218 +
1.219 + IIter ma = m[a];
1.220 + if (ma == 0) return;
1.221 +
1.222 + IIter la = _find(ma);
1.223 + if (la == ma) {
1.224 + if (ma -> size == 1){
1.225 + classes.erase(ma->my_class);
1.226 + m.set(a,0);
1.227 + return;
1.228 + }
1.229 + ++la;
1.230 + la->size = ma->size - 1;
1.231 + la->my_class = ma->my_class;
1.232 + }
1.233 +
1.234 + for (IIter i = la; i != la->my_class->end(); ++i) {
1.235 + i->parent = la;
1.236 + }
1.237 +
1.238 + la->my_class->erase(ma);
1.239 + m.set(a,0);
1.240 + }
1.241 +
1.242 + void eraseClass(const T &a) {
1.243 + IIter ma = m[a];
1.244 + if (ma == 0) return;
1.245 +# ifdef DEBUG
1.246 + CIter c = _find(ma)->my_class;
1.247 + for (IIter i=c->begin(); i!=c->end(); ++i)
1.248 + m.set(i->me, 0);
1.249 +# endif
1.250 + classes.erase(_find(ma)->my_class);
1.251 + }
1.252 +
1.253 +
1.254 + class ClassIt {
1.255 + friend class UnionFindEnum;
1.256 +
1.257 + CcIter i;
1.258 + public:
1.259 + ClassIt(Invalid): i(0) {}
1.260 + ClassIt() {}
1.261 +
1.262 + operator const T& () const {
1.263 + ItemList const &ll = *i;
1.264 + return (ll.begin())->me; }
1.265 + bool operator == (ClassIt it) const {
1.266 + return (i == it.i);
1.267 + }
1.268 + bool operator != (ClassIt it) const {
1.269 + return (i != it.i);
1.270 + }
1.271 + bool operator < (ClassIt it) const {
1.272 + return (i < it.i);
1.273 + }
1.274 +
1.275 + bool valid() const { return i != 0; }
1.276 + private:
1.277 + void first(const ClassList &l) { i = l.begin(); validate(l); }
1.278 + void next(const ClassList &l) {
1.279 + ++i;
1.280 + validate(l);
1.281 + }
1.282 + void validate(const ClassList &l) {
1.283 + if ( i == l.end() )
1.284 + i = 0;
1.285 + }
1.286 + };
1.287 +
1.288 +
1.289 + ClassIt& first(ClassIt& it) const {
1.290 + it.first(classes);
1.291 + return it;
1.292 + }
1.293 +
1.294 + bool valid(ClassIt const &it) const {
1.295 + return it.valid();
1.296 + }
1.297 +
1.298 + ClassIt& next(ClassIt& it) const {
1.299 + it.next(classes);
1.300 + return it;
1.301 + }
1.302 +
1.303 +
1.304 + class ItemIt {
1.305 + friend class UnionFindEnum;
1.306 +
1.307 + IcIter i;
1.308 + const ItemList *l;
1.309 + public:
1.310 + ItemIt(Invalid): i(0) {}
1.311 + ItemIt() {}
1.312 +
1.313 + operator const T& () const { return i->me; }
1.314 + bool operator == (ItemIt it) const {
1.315 + return (i == it.i);
1.316 + }
1.317 + bool operator != (ItemIt it) const {
1.318 + return (i != it.i);
1.319 + }
1.320 + bool operator < (ItemIt it) const {
1.321 + return (i < it.i);
1.322 + }
1.323 +
1.324 + bool valid() const { return i != 0; }
1.325 + private:
1.326 + void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
1.327 + void next() {
1.328 + ++i;
1.329 + validate();
1.330 + }
1.331 + void validate() {
1.332 + if ( i == l->end() )
1.333 + i = 0;
1.334 + }
1.335 + };
1.336 +
1.337 +
1.338 + ItemIt& first(ItemIt& it, const T& a) const {
1.339 + it.first( * _find(m[a])->my_class );
1.340 + return it;
1.341 + }
1.342 +
1.343 + bool valid(ItemIt const &it) const {
1.344 + return it.valid();
1.345 + }
1.346 +
1.347 + ItemIt& next(ItemIt& it) const {
1.348 + it.next();
1.349 + return it;
1.350 + }
1.351 +
1.352 +
1.353 +
1.354 + };
1.355 +
1.356 } //namespace hugo
1.357
1.358 #endif //HUGO_UNION_FIND_H