From fd733201b82f39655488a286c89142f321ef9dc9 Mon Sep 17 00:00:00 2001 From: Sylvain Chiron Date: Sat, 1 Jul 2017 13:36:41 +0200 Subject: Updated libs from the Adaptagrams project: libavoid, libcola and libvspc; changed the code to match the new API Signed-off-by: Sylvain Chiron --- src/libvpsc/blocks.cpp | 333 +++++++++++++++++++++++++++++-------------------- 1 file changed, 201 insertions(+), 132 deletions(-) (limited to 'src/libvpsc/blocks.cpp') diff --git a/src/libvpsc/blocks.cpp b/src/libvpsc/blocks.cpp index 7eff1e6c4..52e940ce7 100644 --- a/src/libvpsc/blocks.cpp +++ b/src/libvpsc/blocks.cpp @@ -1,180 +1,249 @@ /* - * A block structure defined over the variables. + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Authors: - * Tim Dwyer + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Copyright (C) 2005 Authors + * Copyright (C) 2005-2012 Monash University * - * Released under GNU LGPL. Read the file 'COPYING' for more information. + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * See the file LICENSE.LGPL distributed with the library. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * Author(s): Tim Dwyer + * Michael Wybrow +*/ + +/* + * @brief A block structure defined over the variables + * + * A block structure defined over the variables such that each block contains + * 1 or more variables, with the invariant that all constraints inside a block + * are satisfied by keeping the variables fixed relative to one another */ -#include "blocks.h" -#include "block.h" -#include "constraint.h" -#ifdef RECTANGLE_OVERLAP_LOGGING +#include "libvpsc/blocks.h" +#include "libvpsc/block.h" +#include "libvpsc/constraint.h" +#include "libvpsc/variable.h" +#include "libvpsc/assertions.h" + +#ifdef LIBVPSC_LOGGING #include using std::ios; using std::ofstream; using std::endl; #endif -using std::set; using std::vector; using std::iterator; using std::list; using std::copy; +#define __NOTNAN(p) (p)==(p) namespace vpsc { -long blockTimeCtr; -Blocks::Blocks(const int n, Variable* const vs[]) : vs(vs),nvs(n) { - blockTimeCtr=0; - for(int i=0;i const &vs) : vs(vs),nvs(vs.size()) { + blockTimeCtr=0; + m_blocks.resize(nvs); + for(size_t i=0;i::iterator i=begin();i!=end();++i) { - delete *i; - } - clear(); + blockTimeCtr=0; + size_t length = m_blocks.size(); + for (size_t i = 0; i < length; ++i) + { + delete m_blocks[i]; + } + m_blocks.clear(); } +/* + * returns a list of variables with total ordering determined by the constraint + * DAG + */ list *Blocks::totalOrder() { - list *order = new list; - for(int i=0;ivisited=false; - } - for(int i=0;iin.size()==0) { - dfsVisit(vs[i],order); - } - } - return order; + list *order = new list; + for(size_t i=0;ivisited=false; + } + for(size_t i=0;iin.size()==0) { + dfsVisit(vs[i],order); + } + } + return order; } // Recursive depth first search giving total order by pushing nodes in the DAG // onto the front of the list when we finish searching them void Blocks::dfsVisit(Variable *v, list *order) { - v->visited=true; - vector::iterator it=v->out.begin(); - for(;it!=v->out.end();++it) { - Constraint *c=*it; - if(!c->right->visited) { - dfsVisit(c->right, order); - } - } -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<" order="<<*v<visited=true; + vector::iterator it=v->out.begin(); + for(;it!=v->out.end();++it) { + Constraint *c=*it; + if(!c->right->visited) { + dfsVisit(c->right, order); + } + } +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" order="<<*v<push_front(v); + order->push_front(v); } - -void Blocks::mergeLeft(Block *r) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"mergeLeft called on "<<*r<timeStamp=++blockTimeCtr; - r->setUpInConstraints(); - Constraint *c=r->findMinInConstraint(); - while (c != NULL && c->slack()<0) { -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<"mergeLeft on constraint: "<<*c<timeStamp=++blockTimeCtr; + r->setUpInConstraints(); + Constraint *c=r->findMinInConstraint(); + while (c != NULL && c->slack()<0) { +#ifdef LIBVPSC_LOGGING + f<<"mergeLeft on constraint: "<<*c<deleteMinInConstraint(); - Block *l = c->left->block; - if (l->in==NULL) l->setUpInConstraints(); - double dist = c->right->offset - c->left->offset - c->gap; - if (r->vars->size() < l->vars->size()) { - dist=-dist; - std::swap(l, r); - } - blockTimeCtr++; - r->merge(l, c, dist); - r->mergeIn(l); - r->timeStamp=blockTimeCtr; - removeBlock(l); - c=r->findMinInConstraint(); - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<"merged "<<*r<deleteMinInConstraint(); + Block *l = c->left->block; + if (l->in==NULL) l->setUpInConstraints(); + double dist = c->right->offset - c->left->offset - c->gap; + if (r->vars->size() < l->vars->size()) { + dist=-dist; + std::swap(l, r); + } + blockTimeCtr++; + r->merge(l, c, dist); + r->mergeIn(l); + r->timeStamp=blockTimeCtr; + removeBlock(l); + c=r->findMinInConstraint(); + } +#ifdef LIBVPSC_LOGGING + f<<"merged "<<*r<setUpOutConstraints(); - Constraint *c = l->findMinOutConstraint(); - while (c != NULL && c->slack()<0) { -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<"mergeRight on constraint: "<<*c<setUpOutConstraints(); + Constraint *c = l->findMinOutConstraint(); + while (c != NULL && c->slack()<0) { +#ifdef LIBVPSC_LOGGING + f<<"mergeRight on constraint: "<<*c<deleteMinOutConstraint(); - Block *r = c->right->block; - r->setUpOutConstraints(); - double dist = c->left->offset + c->gap - c->right->offset; - if (l->vars->size() > r->vars->size()) { - dist=-dist; - std::swap(l, r); - } - l->merge(r, c, dist); - l->mergeOut(r); - removeBlock(r); - c=l->findMinOutConstraint(); - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<"merged "<<*l<deleteMinOutConstraint(); + Block *r = c->right->block; + r->setUpOutConstraints(); + double dist = c->left->offset + c->gap - c->right->offset; + if (l->vars->size() > r->vars->size()) { + dist=-dist; + std::swap(l, r); + } + l->merge(r, c, dist); + l->mergeOut(r); + removeBlock(r); + c=l->findMinOutConstraint(); + } +#ifdef LIBVPSC_LOGGING + f<<"merged "<<*l<deleted=true; - //erase(doomed); -} -void Blocks::cleanup() { - vector bcopy(begin(),end()); - for(vector::iterator i=bcopy.begin();i!=bcopy.end();++i) { - Block *b=*i; - if(b->deleted) { - erase(b); - delete b; - } - } + doomed->deleted=true; + //erase(doomed); } +// Clears up deleted blocks from the blocks list. +void Blocks::cleanup(void) +{ + // We handle removal of items in-place by doing a single linear pass over + // the vector. We use two indexes, j to refer to elements we've checked + // from the original list and i to refer to the current position we are + // writing in the updated list. + size_t i = 0; + + // For all items in the current blocks list... + size_t length = m_blocks.size(); + for (size_t j = 0; j < length; ) + { + if (m_blocks[j]->deleted) + { + // The element is deleted, so free it and increment j. + delete m_blocks[j]; + ++j; + } + else + { + // The current element is still valid. + if (j > i) + { + // If we've not looking at same element, then copy from j to i. + m_blocks[i] = m_blocks[j]; + } + // Increment both indexes. + ++i; + ++j; + } + } + m_blocks.resize(i); +} +/* + * Splits block b across constraint c into two new blocks, l and r (c's left + * and right sides respectively) + */ void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) { - b->split(l,r,c); -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"Split left: "<<*l<split(l,r,c); + m_blocks.push_back(l); + m_blocks.push_back(r); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Split left: "<<*l<posn = b->posn; - r->wposn = r->posn * r->weight; - mergeLeft(l); - // r may have been merged! - r = c->right->block; - r->wposn = r->desiredWeightedPosition(); - r->posn = r->wposn / r->weight; - mergeRight(r); - removeBlock(b); + r->posn = b->posn; + //COLA_ASSERT(r->weight!=0); + //r->wposn = r->posn * r->weight; + mergeLeft(l); + // r may have been merged! + r = c->right->block; + r->updateWeightedPosition(); + //r->posn = r->wposn / r->weight; + mergeRight(r); + removeBlock(b); - insert(l); - insert(r); + COLA_ASSERT(__NOTNAN(l->posn)); + COLA_ASSERT(__NOTNAN(r->posn)); } - +/* + * returns the cost total squared distance of variables from their desired + * positions + */ double Blocks::cost() { - double c = 0; - for(set::iterator i=begin();i!=end();++i) { - c += (*i)->cost(); - } - return c; + double c = 0; + size_t length = m_blocks.size(); + for (size_t i = 0; i < length; ++i) + { + c += m_blocks[i]->cost(); + } + return c; } } -- cgit v1.2.3