1.1 --- a/lemon/unionfind.h Wed Mar 08 13:10:43 2006 +0000
1.2 +++ b/lemon/unionfind.h Fri Mar 10 18:06:26 2006 +0000
1.3 @@ -257,6 +257,10 @@
1.4 return comp;
1.5 }
1.6
1.7 + const ItemList& classOf(const T &a) const {
1.8 + return *_find(m[a])->my_class;
1.9 + }
1.10 +
1.11 public:
1.12 UnionFindEnum(MapType& _m) : m(_m) {}
1.13
1.14 @@ -343,7 +347,7 @@
1.15 alist.splice(alist.end(),*cb->my_class);
1.16
1.17 classes.erase(cb->my_class);
1.18 - cb->my_class = 0;
1.19 + // ehem: cb->my_class = 0;
1.20 }
1.21 else {
1.22
1.23 @@ -354,7 +358,7 @@
1.24 blist.splice(blist.end(),*ca->my_class);
1.25
1.26 classes.erase(ca->my_class);
1.27 - ca->my_class = 0;
1.28 + // ehem: ca->my_class = 0;
1.29 }
1.30
1.31 return true;
1.32 @@ -416,7 +420,7 @@
1.33 if (la == ia) return;
1.34
1.35 ia->my_class = la->my_class;
1.36 - la->my_class = 0;
1.37 + // ehem: la->my_class = 0;
1.38
1.39 ia->size = la->size;
1.40
1.41 @@ -474,7 +478,7 @@
1.42 }
1.43
1.44 ai->parent = clit;
1.45 - ai->my_class = 0;
1.46 + // ehem: ai->my_class = 0;
1.47 ++clit->size;
1.48
1.49 return true;
1.50 @@ -484,21 +488,21 @@
1.51 /**
1.52 * \brief Removes the given element from the structure.
1.53 *
1.54 - * Removes the given element from the structure.
1.55 - *
1.56 * Removes the element from its component and if the component becomes
1.57 * empty then removes that component from the component list.
1.58 + *
1.59 + * It is an error to remove an element which is not in the structure.
1.60 */
1.61 void erase(const T &a) {
1.62
1.63 IIter ma = m[a];
1.64 - if (ma == 0) return;
1.65 + // ehem: if (ma == 0) return;
1.66
1.67 IIter la = _find(ma);
1.68 if (la == ma) {
1.69 if (ma -> size == 1){
1.70 classes.erase(ma->my_class);
1.71 - m.set(a,0);
1.72 + // ehem: m.set(a,0);
1.73 return;
1.74 }
1.75 ++la;
1.76 @@ -512,23 +516,25 @@
1.77
1.78 la->size--;
1.79 la->my_class->erase(ma);
1.80 - m.set(a,0);
1.81 + // ehem: m.set(a,0);
1.82 }
1.83
1.84 /**
1.85 * \brief Removes the component of the given element from the structure.
1.86 *
1.87 * Removes the component of the given element from the structure.
1.88 + *
1.89 + * It is an error to give an element which is not in the structure.
1.90 */
1.91
1.92 void eraseClass(const T &a) {
1.93 IIter ma = m[a];
1.94 - if (ma == 0) return;
1.95 -# ifdef DEBUG
1.96 - CIter c = _find(ma)->my_class;
1.97 - for (IIter i=c->begin(); i!=c->end(); ++i)
1.98 - m.set(i->me, 0);
1.99 -# endif
1.100 + // ehem: if (ma == 0) return;
1.101 +// # ifdef DEBUG
1.102 +// CIter c = _find(ma)->my_class;
1.103 +// for (IIter i=c->begin(); i!=c->end(); ++i)
1.104 +// m.set(i->me, 0);
1.105 +// # endif
1.106 classes.erase(_find(ma)->my_class);
1.107 }
1.108
1.109 @@ -537,34 +543,54 @@
1.110 friend class UnionFindEnum;
1.111
1.112 CcIter i;
1.113 + const ClassList *l;
1.114 +
1.115 public:
1.116 - ClassIt(Invalid): i(0) {}
1.117 + ClassIt(Invalid): l(0) {}
1.118 ClassIt() {}
1.119 + ClassIt(UnionFindEnum const &ufe) {
1.120 + l = &ufe.classes;
1.121 + i = l->begin();
1.122 + }
1.123
1.124 operator const T& () const {
1.125 ItemList const &ll = *i;
1.126 - return (ll.begin())->me; }
1.127 - bool operator == (ClassIt it) const {
1.128 - return (i == it.i);
1.129 + return (ll.begin())->me;
1.130 }
1.131 - bool operator != (ClassIt it) const {
1.132 - return (i != it.i);
1.133 + bool operator == (ClassIt const &it) const {
1.134 + return (l==it.l && i==it.i) || (!valid() && !it.valid());
1.135 }
1.136 - bool operator < (ClassIt it) const {
1.137 + bool operator != (ClassIt const &it) const {
1.138 + return !(*this == it);
1.139 + }
1.140 + bool operator < (ClassIt const &it) const {
1.141 return (i < it.i);
1.142 }
1.143
1.144 - bool valid() const { return i != 0; }
1.145 + bool operator==(Invalid) const {
1.146 + return !valid();
1.147 + }
1.148 + bool operator!=(Invalid) const {
1.149 + return valid();
1.150 + }
1.151 +
1.152 + ClassIt& operator++() {
1.153 + ++i;
1.154 + return *this;
1.155 + }
1.156 +
1.157 + // obsoleted:
1.158 + bool valid() const { return l!=0 && i!=l->end(); }
1.159 private:
1.160 - void first(const ClassList &l) { i = l.begin(); validate(l); }
1.161 - void next(const ClassList &l) {
1.162 - ++i;
1.163 - validate(l);
1.164 - }
1.165 - void validate(const ClassList &l) {
1.166 - if ( i == l.end() )
1.167 - i = 0;
1.168 - }
1.169 + //void first(const ClassList &l) { i = l.begin(); validate(l); }
1.170 +// void next(const ClassList &l) {
1.171 +// ++i;
1.172 +// validate(l);
1.173 +// }
1.174 +// void validate(const ClassList &l) {
1.175 +// if ( i == l.end() )
1.176 +// i = 0;
1.177 +// }
1.178 };
1.179
1.180 /**
1.181 @@ -583,10 +609,12 @@
1.182 * cout << iter << endl;
1.183 * }
1.184 * \endcode
1.185 + *
1.186 + * \bug obsoleted, use the new LEMON iterator interface instead
1.187 */
1.188
1.189 ClassIt& first(ClassIt& it) const {
1.190 - it.first(classes);
1.191 + it = ClassIt(*this);
1.192 return it;
1.193 }
1.194
1.195 @@ -597,6 +625,8 @@
1.196 *
1.197 * With the \ref first, \ref valid and \ref next methods you can
1.198 * iterate through the components. See the example here: \ref first.
1.199 + *
1.200 + * \bug obsoleted, use the new LEMON iterator interface instead
1.201 */
1.202
1.203 bool valid(ClassIt const &it) const {
1.204 @@ -613,8 +643,7 @@
1.205 */
1.206
1.207 ClassIt& next(ClassIt& it) const {
1.208 - it.next(classes);
1.209 - return it;
1.210 + return ++it;
1.211 }
1.212
1.213
1.214 @@ -624,31 +653,48 @@
1.215 IcIter i;
1.216 const ItemList *l;
1.217 public:
1.218 - ItemIt(Invalid): i(0) {}
1.219 + ItemIt(Invalid): l(0) {}
1.220 ItemIt() {}
1.221 + ItemIt(UnionFindEnum const &ufe, const T& a) {
1.222 + l = &ufe.classOf(a);
1.223 + i = l->begin();
1.224 + }
1.225
1.226 operator const T& () const { return i->me; }
1.227 bool operator == (ItemIt it) const {
1.228 - return (i == it.i);
1.229 + return (l==it.l && i==it.i) || (!valid() && !it.valid());
1.230 }
1.231 bool operator != (ItemIt it) const {
1.232 - return (i != it.i);
1.233 + return !(*this == it);
1.234 }
1.235 bool operator < (ItemIt it) const {
1.236 return (i < it.i);
1.237 }
1.238
1.239 - bool valid() const { return i != 0; }
1.240 + bool operator==(Invalid) const {
1.241 + return !valid();
1.242 + }
1.243 + bool operator!=(Invalid) const {
1.244 + return valid();
1.245 + }
1.246 +
1.247 + ItemIt& operator++() {
1.248 + ++i;
1.249 + return *this;
1.250 + }
1.251 +
1.252 + // obsoleted:
1.253 + bool valid() const { return l!=0 && i!=l->end(); }
1.254 private:
1.255 - void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
1.256 - void next() {
1.257 - ++i;
1.258 - validate();
1.259 - }
1.260 - void validate() {
1.261 - if ( i == l->end() )
1.262 - i = 0;
1.263 - }
1.264 +// void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
1.265 +// void next() {
1.266 +// ++i;
1.267 +// validate();
1.268 +// }
1.269 +// void validate() {
1.270 +// if ( i == l->end() )
1.271 +// i = 0;
1.272 +// }
1.273 };
1.274
1.275
1.276 @@ -673,10 +719,12 @@
1.277 * cout << iiter << endl;
1.278 * }
1.279 * \endcode
1.280 + *
1.281 + * \bug obsoleted, use the new LEMON iterator interface instead
1.282 */
1.283
1.284 ItemIt& first(ItemIt& it, const T& a) const {
1.285 - it.first( * _find(m[a])->my_class );
1.286 + it = ItemIt(*this, a);
1.287 return it;
1.288 }
1.289
1.290 @@ -690,10 +738,12 @@
1.291 * and \ref next2 "next" methods you can
1.292 * iterate through the elements of a component.
1.293 * See the example here: \ref first2 "first".
1.294 + *
1.295 + * \bug obsoleted, use the new LEMON iterator interface instead
1.296 */
1.297
1.298 bool valid(ItemIt const &it) const {
1.299 - return it.valid();
1.300 + return it.valid();
1.301 }
1.302
1.303 /**
1.304 @@ -706,11 +756,12 @@
1.305 * and \ref next2 "next" methods you can
1.306 * iterate through the elements of a component.
1.307 * See the example here: \ref first2 "first".
1.308 + *
1.309 + * \bug obsoleted, use the new LEMON iterator interface instead
1.310 */
1.311
1.312 ItemIt& next(ItemIt& it) const {
1.313 - it.next();
1.314 - return it;
1.315 + return ++it;
1.316 }
1.317
1.318 };