2006-08-28 Thierry GERAUD <theo@tegucigalpa.lrde.epita.fr> * oln/lrde/ufmt/rpc_maxtree.hh (nnodes): New attribute. (compute_parent): Sort before calling update. (update): Rename variables and shorten code. Index: 10.249/olena/oln/lrde/ufmt/rpc_maxtree.hh --- 10.249/olena/oln/lrde/ufmt/rpc_maxtree.hh Mon, 21 Aug 2006 17:17:14 +0200 theo (oln/x/14_rup_maxtre 1.2 644) +++ 10.249(w)/olena/oln/lrde/ufmt/rpc_maxtree.hh Mon, 28 Aug 2006 10:33:24 +0200 theo (oln/x/14_rup_maxtre 1.2 644) @@ -31,6 +31,7 @@ # include <oln/lrde/ufmt/utils.hh> # include <oln/lrde/ufmt/ap_maxtree.hh> +# include <vector> namespace oln @@ -54,6 +55,8 @@ using super::par; oln_lrde_ufmt_import_ap_maxtree_typedefs; + unsigned nnodes; + // aux data std::vector<dpoint> dp; unsigned nb; @@ -78,6 +81,7 @@ void init() { nb = pre<I>(nbh, dp); + nnodes = 0; } void compute_parent() @@ -93,7 +97,10 @@ { n = p + dp[i]; if (f.hold(n)) - update(n, p); + if (f[p] >= f[n]) + update(p, n); + else + update(n, p); } } } @@ -107,6 +114,9 @@ { point r = anc(n, f[p]); + if (f[p] != f[r]) + ++nnodes; + if (f[r] <= f[p]) par[p] = r; else @@ -117,9 +127,48 @@ } } + void update(point x, point y) { assert(x != y); // invariant + assert(f[x] >= f[y]); // invariant + + point a = anc(x, f[y]); + point b = find_level_root(y); + + assert(f[x] >= f[a] and f[a] >= f[y] and f[y] == f[b]); // invariant + + if (a == b) + return; // already merged + + if (f[b] != f[a]) + ++nnodes; + + point memo = par[b]; + + if (f[b] == f[a]) + par[b] = a; // simple plug + else + { + if (par[a] != a) + par[b] = par[a]; + par[a] = b; + } + + assert(f[memo] <= f[a]); // invariant + update(a, memo); + + // FIXME: this algo looks ok and seems to work (...?) + // it is very close to the 'insert' algo running with + // "insert(x, find_level_root(y))" after the "if..swap" + // FIXME: so it can be bettered... + } + + + + void update__primary_version(point x, point y) + { + assert(x != y); // invariant if (f[x] < f[y]) swap(x, y); @@ -143,7 +192,7 @@ if (f[xx] == f[yy]) { - par[yy] = xx; // simple plug + par[yy] = xx; // simple plug => 2 nodes merge update(xx, memo); } else