#include "dynadag/DynaDAG.h"
using namespace std;
namespace DynaDAG {
const double EPSILON = 1.0e-5;
Region &getRegion(DDModel::Node *n) {
Layout::Node *vn = DDd(n).multi->layoutN;
return gd<NodeGeom>(vn).region;
}
double Config::LeftExtent(DDModel::Node *n) {
if(!n)
return 0.0;
if(DDd(n).amEdgePart())
return nodeSep.x/2.0;
if(getRegion(n).boundary.valid)
return -getRegion(n).boundary.l;
return EPSILON;
}
double Config::RightExtent(DDModel::Node *n) {
if(!n)
return 0.0;
if(DDd(n).amEdgePart())
return nodeSep.x/2.0;
if(getRegion(n).boundary.valid)
return getRegion(n).boundary.r;
return EPSILON;
}
double Config::TopExtent(DDModel::Node *n) {
if(!n)
return 0.0;
if(DDd(n).amEdgePart())
return EPSILON;
if(getRegion(n).boundary.valid)
return getRegion(n).boundary.t;
return EPSILON;
}
double Config::BottomExtent(DDModel::Node *n) {
if(!n)
return 0.0;
if(DDd(n).amEdgePart())
return EPSILON;
if(getRegion(n).boundary.valid)
return -getRegion(n).boundary.b;
return EPSILON;
}
double Config::UVSep(DDModel::Node *left,DDModel::Node *right) {
double s0 = RightExtent(left),
s1 = LeftExtent(right);
return s0+s1 + nodeSep.x;
}
double Config::CoordBetween(DDModel::Node *L, DDModel::Node *R) {
double x;
if(L || R) {
double lx = L ? DDd(L).cur.x : DDd(R).cur.x - 2.0 * UVSep(0,R),
rx = R ? DDd(R).cur.x : DDd(L).cur.x + 2.0 * UVSep(L,0);
x = (lx + rx) / 2.0;
}
else x = 0.0;
return x;
}
DDModel::Node *Config::RelNode(DDModel::Node *n, int offset) {
unsigned pos = DDd(n).order + offset;
if(pos < 0)
return 0;
Rank *rank = ranking.GetRank(DDd(n).rank);
assert(rank);
if(pos >= rank->order.size())
return 0;
return rank->order[pos];
}
DDModel::Node *Config::Right(DDModel::Node *n) {
return RelNode(n,1);
}
DDModel::Node *Config::Left(DDModel::Node *n) {
return RelNode(n,-1);
}
void Config::InstallAtRight(DDModel::Node *n, int r) {
Rank *rank = *ranking.EnsureRank(r);
DDModel::Node *right = rank->order.size()?rank->order.back():0;
double x = right?DDd(right).cur.x + UVSep(right,n):0.0;
assert(!right||x>DDd(right).cur.x);
rank->order.push_back(n);
DDNode &ddn = DDd(n);
ddn.rank = r;
ddn.order = rank->order.size()-1;
ddn.inConfig = true;
ddn.cur.valid = true;
ddn.cur.x = x;
ddn.cur.y = rank->yBase; model.dirty.insert(n);
}
#ifdef X_STRICTLY_INCREASING
inline bool sameNode(DDModel::Node *n1,DDModel::Node *n2) {
return DDd(n1).amNodePart() && DDd(n1).multi==DDd(n2).multi;
}
#endif
void Config::InstallAtOrder(DDModel::Node *n, int r, unsigned o, double x) {
Rank *rank = *ranking.EnsureRank(r);
assert(o<=rank->order.size() && o>=0);
NodeV::iterator i = rank->order.begin()+o;
i = rank->order.insert(i,n);
DDNode &ddn = DDd(n);
ddn.rank = r;
ddn.order = i - rank->order.begin();
ddn.inConfig = true;
InvalidateAdjMVals(n);
ddn.cur.valid = true;
ddn.cur.x = x;
ddn.cur.y = rank->yBase; #ifndef FLEXIRANKS
double t = TopExtent(n),
b = BottomExtent(n);
if(t>rank->deltaAbove)
rank->deltaAbove = t;
if(b>rank->deltaBelow)
rank->deltaBelow = b;
#endif
for(++i; i!=rank->order.end(); ++i) {
DDd(*i).order++;
InvalidateAdjMVals(*i);
}
model.dirty.insert(n);
}
void Config::InstallAtOrder(DDModel::Node *n, int r, unsigned o) {
Rank *rank = *ranking.EnsureRank(r);
assert(o<=rank->order.size() && o>=0);
DDModel::Node *L = o>0?rank->order[o-1]:0,
*R = o<rank->order.size()?rank->order[o]:0;
InstallAtOrder(n,r,o,CoordBetween(L,R));
}
struct XLess {
bool operator()(DDModel::Node *u,double x) {
return DDd(u).cur.x<x;
}
};
NodePair Config::NodesAround(int r,double x) {
Rank *rank = *ranking.EnsureRank(r);
NodeV::iterator i = lower_bound(rank->order.begin(),rank->order.end(),x,XLess());
DDModel::Node *L = i==rank->order.begin()?0:*(i-1),
*R = i==rank->order.end()?0:*i;
return make_pair(L,R);
}
void Config::InstallAtPos(DDModel::Node *n, int r, double x) {
NodePair lr = NodesAround(r,x);
InstallAtOrder(n,r,lr.second?DDd(lr.second).order:lr.first?DDd(lr.first).order+1:0,x);
}
void Config::Exchange(DDModel::Node *u, DDModel::Node *v) {
DDNode &ddu = DDd(u),
&ddv = DDd(v);
assert(ddu.inConfig);
assert(ddv.inConfig);
assert(ddu.rank == ddv.rank);
report(r_exchange,"exchange %p of %s %p: x %.3f r %d o %d\n\tw/ %p of %s %p: x %.3f r %d o %d\n",
u,type(u),thing(u),ddu.cur.x,ddu.rank,ddu.order,
v,type(v),thing(v),ddv.cur.x,ddv.rank,ddv.order);
Rank *rank = ranking.GetRank(ddu.rank);
int upos = ddu.order,
vpos = ddv.order;
xconOwner->DeleteLRConstraint(u,v);
rank->order[vpos] = u; DDd(u).order = vpos;
rank->order[upos] = v; DDd(v).order = upos;
InvalidateAdjMVals(u);
InvalidateAdjMVals(v);
model.dirty.insert(u);
model.dirty.insert(v);
}
void Config::RemoveNode(DDModel::Node *n) {
xconOwner->RemoveNodeConstraints(n);
InvalidateAdjMVals(n);
DDNode &ddn = DDd(n);
if(!ddn.inConfig)
return;
Rank *rank = ranking.GetRank(DDd(n).rank);
int pos = DDd(n).order;
assert(rank->order[pos] == n);
NodeV::iterator i = rank->order.begin()+pos;
rank->order.erase(i);
if(i!=rank->order.end())
model.dirty.insert(*i); for(;i!=rank->order.end(); ++i)
DDd(*i).order--;
ddn.inConfig = false;
ddn.rank = INT_MIN;
}
void Config::Restore(Ranks &backup) {
ranking = backup;
for(Ranks::iterator ri = ranking.begin(); ri!=ranking.end(); ++ri) {
Rank *r = *ri;
for(NodeV::iterator ni = r->order.begin(); ni!=r->order.end(); ++ni) {
int o = int(ni - r->order.begin());
if(DDd(*ni).order != o) {
InvalidateAdjMVals(*ni);
DDd(*ni).order = o;
}
}
}
}
}