From 0ddedab9c6185028661dcaaac9f6fbca4c9e93fc Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 12 Jun 2011 18:27:29 +0000 Subject: work in progress cmake commit: - cmake now builds all files that automake does but does NOT link yet - inlcudes nasty hard coded paths and libs (will replace once linking works) (bzr r10272) --- src/libvpsc/CMakeLists.txt | 25 +++++++++++++------------ 1 file changed, 13 insertions(+), 12 deletions(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/CMakeLists.txt b/src/libvpsc/CMakeLists.txt index 4c3398b0f..57811ad0a 100644 --- a/src/libvpsc/CMakeLists.txt +++ b/src/libvpsc/CMakeLists.txt @@ -1,13 +1,14 @@ -SET(libvpsc_SRC -block.cpp -blocks.cpp -constraint.cpp -csolve_VPSC.cpp -generate-constraints.cpp -remove_rectangle_overlap.cpp -solve_VPSC.cpp -variable.cpp +set(libvpsc_SRC + block.cpp + blocks.cpp + constraint.cpp + csolve_VPSC.cpp + generate-constraints.cpp + remove_rectangle_overlap.cpp + solve_VPSC.cpp + variable.cpp + pairingheap/PairingHeap.cpp ) -ADD_LIBRARY(vpsc STATIC ${libvpsc_SRC}) -TARGET_LINK_LIBRARIES(vpsc -${INKSCAPE_LIBS}) \ No newline at end of file + +add_library(vpsc STATIC ${libvpsc_SRC}) +target_link_libraries(vpsc ${INKSCAPE_LIBS}) -- cgit v1.2.3 From de03354959190a2c5392d79e03dd22dc45777e41 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 12 Jun 2011 21:27:00 +0000 Subject: cmake: give all libs a _LIB suffix, workaround 'debug' being confused with cake keyword, and also dont mix up dor names with libs. (bzr r10274) --- src/libvpsc/CMakeLists.txt | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/CMakeLists.txt b/src/libvpsc/CMakeLists.txt index 57811ad0a..0a91c3516 100644 --- a/src/libvpsc/CMakeLists.txt +++ b/src/libvpsc/CMakeLists.txt @@ -10,5 +10,5 @@ set(libvpsc_SRC pairingheap/PairingHeap.cpp ) -add_library(vpsc STATIC ${libvpsc_SRC}) -target_link_libraries(vpsc ${INKSCAPE_LIBS}) +add_library(vpsc_LIB STATIC ${libvpsc_SRC}) +target_link_libraries(vpsc_LIB ${INKSCAPE_LIBS}) -- cgit v1.2.3 From 7172735786c43c2305a92ffd4e5d285d11f88f7f Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Mon, 13 Jun 2011 00:19:17 +0000 Subject: cmake: turns out my recent commits (which I undid) were not incorrect, variables were set in subdirectories then used in the parent directory, where they were still unset. Fixing this broke the build because some files in the subdir were not compiling. (bzr r10276) --- src/libvpsc/CMakeLists.txt | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/CMakeLists.txt b/src/libvpsc/CMakeLists.txt index 0a91c3516..ebc1e79d6 100644 --- a/src/libvpsc/CMakeLists.txt +++ b/src/libvpsc/CMakeLists.txt @@ -1,3 +1,4 @@ + set(libvpsc_SRC block.cpp blocks.cpp @@ -10,5 +11,4 @@ set(libvpsc_SRC pairingheap/PairingHeap.cpp ) -add_library(vpsc_LIB STATIC ${libvpsc_SRC}) -target_link_libraries(vpsc_LIB ${INKSCAPE_LIBS}) +add_library(vpsc_LIB ${libvpsc_SRC}) -- cgit v1.2.3 From b7a4f23ed217a36eaaefe8f707bcc1b968d1e562 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Mon, 13 Jun 2011 05:39:42 +0000 Subject: cmake: - group source/headers per library (for some IDE's) - include headers with source listing (also for IDE's) - remove unneeded Find modules (bzr r10281) --- src/libvpsc/CMakeLists.txt | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/CMakeLists.txt b/src/libvpsc/CMakeLists.txt index ebc1e79d6..8db059b5d 100644 --- a/src/libvpsc/CMakeLists.txt +++ b/src/libvpsc/CMakeLists.txt @@ -9,6 +9,21 @@ set(libvpsc_SRC solve_VPSC.cpp variable.cpp pairingheap/PairingHeap.cpp + + + # ------- + # Headers + block.h + blocks.h + constraint.h + csolve_VPSC.h + generate-constraints.h + pairingheap/PairingHeap.h + pairingheap/dsexceptions.h + placement_SolveVPSC.h + remove_rectangle_overlap.h + solve_VPSC.h + variable.h ) -add_library(vpsc_LIB ${libvpsc_SRC}) +add_inkscape_lib(vpsc_LIB "${libvpsc_SRC}") -- cgit v1.2.3 From 1079b1b4c0331e5d4bd62f3c93349aec50f520f0 Mon Sep 17 00:00:00 2001 From: Krzysztof Kosi??ski Date: Thu, 23 Jun 2011 18:38:51 +0200 Subject: Update 2Geom to pull in integer rectangle class (bzr r10347.1.1) --- src/libvpsc/generate-constraints.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/generate-constraints.cpp b/src/libvpsc/generate-constraints.cpp index c57966e26..0c35ab51c 100644 --- a/src/libvpsc/generate-constraints.cpp +++ b/src/libvpsc/generate-constraints.cpp @@ -16,7 +16,7 @@ #include "generate-constraints.h" #include "constraint.h" -#include "2geom/isnan.h" /* Include last */ +#include <2geom/math-utils.h> using std::set; using std::vector; -- cgit v1.2.3 From dcf765f3dcbff2e65428e0f002bb5ea3648940f0 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 25 Jun 2011 15:35:01 +0000 Subject: warning cleanup (no functional changes) - enclose && / || with brackets to avoid ambiguity. - don't cast from booleans to pointers. (bzr r10359) --- src/libvpsc/block.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp index 221df536a..0bd662f28 100644 --- a/src/libvpsc/block.cpp +++ b/src/libvpsc/block.cpp @@ -72,7 +72,7 @@ void Block::setUpConstraintHeap(PairingHeap* &h,bool in) { for (Cit j=cs->begin();j!=cs->end();++j) { Constraint *c=*j; c->timeStamp=blockTimeCtr; - if (c->left->block != this && in || c->right->block != this && !in) { + if ((c->left->block != this && in) || (c->right->block != this && !in)) { h->insert(c); } } -- cgit v1.2.3 From 4d613dc583b96ea9205cd06f229956d6ec56c9e6 Mon Sep 17 00:00:00 2001 From: Nick Drobchenko Date: Tue, 5 Jul 2011 19:12:43 +0400 Subject: Gcodetools have been upgraded to v. 1.7. (bzr r10417) --- src/libvpsc/CMakeLists.txt | 58 +++++++++++++++++++++++----------------------- 1 file changed, 29 insertions(+), 29 deletions(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/CMakeLists.txt b/src/libvpsc/CMakeLists.txt index 8db059b5d..4099900b5 100644 --- a/src/libvpsc/CMakeLists.txt +++ b/src/libvpsc/CMakeLists.txt @@ -1,29 +1,29 @@ - -set(libvpsc_SRC - block.cpp - blocks.cpp - constraint.cpp - csolve_VPSC.cpp - generate-constraints.cpp - remove_rectangle_overlap.cpp - solve_VPSC.cpp - variable.cpp - pairingheap/PairingHeap.cpp - - - # ------- - # Headers - block.h - blocks.h - constraint.h - csolve_VPSC.h - generate-constraints.h - pairingheap/PairingHeap.h - pairingheap/dsexceptions.h - placement_SolveVPSC.h - remove_rectangle_overlap.h - solve_VPSC.h - variable.h -) - -add_inkscape_lib(vpsc_LIB "${libvpsc_SRC}") + +set(libvpsc_SRC + block.cpp + blocks.cpp + constraint.cpp + csolve_VPSC.cpp + generate-constraints.cpp + remove_rectangle_overlap.cpp + solve_VPSC.cpp + variable.cpp + pairingheap/PairingHeap.cpp + + + # ------- + # Headers + block.h + blocks.h + constraint.h + csolve_VPSC.h + generate-constraints.h + pairingheap/PairingHeap.h + pairingheap/dsexceptions.h + placement_SolveVPSC.h + remove_rectangle_overlap.h + solve_VPSC.h + variable.h +) + +add_inkscape_lib(vpsc_LIB "${libvpsc_SRC}") -- cgit v1.2.3 From 7cd2a14069d9d39b42b19a87d9cc6ba238c71924 Mon Sep 17 00:00:00 2001 From: "Jon A. Cruz" Date: Sun, 23 Oct 2011 01:01:33 -0700 Subject: Documentation update pass. (bzr r10692) --- src/libvpsc/blocks.h | 14 ++++++-------- src/libvpsc/constraint.cpp | 5 +---- src/libvpsc/constraint.h | 10 ++++++---- src/libvpsc/generate-constraints.cpp | 5 ++++- src/libvpsc/generate-constraints.h | 6 +++++- 5 files changed, 22 insertions(+), 18 deletions(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/blocks.h b/src/libvpsc/blocks.h index bfe99f271..e3223822e 100644 --- a/src/libvpsc/blocks.h +++ b/src/libvpsc/blocks.h @@ -1,10 +1,4 @@ -/** - * \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 - * +/* * Authors: * Tim Dwyer * @@ -24,13 +18,17 @@ #include namespace vpsc { + class Block; class Variable; class Constraint; + /** * 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 + * are satisfied by keeping the variables fixed relative to one another. + * + * @todo check on this class being copy-n-paste duplicated. */ class Blocks : public std::set { diff --git a/src/libvpsc/constraint.cpp b/src/libvpsc/constraint.cpp index af5da941a..2bd173155 100644 --- a/src/libvpsc/constraint.cpp +++ b/src/libvpsc/constraint.cpp @@ -1,7 +1,4 @@ -/** - * \brief A constraint determines a minimum or exact spacing required between - * two variables. - * +/* * Authors: * Tim Dwyer * diff --git a/src/libvpsc/constraint.h b/src/libvpsc/constraint.h index 8a8529d7e..a3173359c 100644 --- a/src/libvpsc/constraint.h +++ b/src/libvpsc/constraint.h @@ -1,7 +1,4 @@ -/** - * \brief A constraint determines a minimum or exact spacing required between - * two variables. - * +/* * Authors: * Tim Dwyer * @@ -17,6 +14,11 @@ #include "variable.h" namespace vpsc { +/** + * A constraint determines a minimum or exact spacing required between + * two variables. + * + */ class Constraint { friend std::ostream& operator <<(std::ostream &os,const Constraint &c); diff --git a/src/libvpsc/generate-constraints.cpp b/src/libvpsc/generate-constraints.cpp index 0c35ab51c..8dd2d9331 100644 --- a/src/libvpsc/generate-constraints.cpp +++ b/src/libvpsc/generate-constraints.cpp @@ -1,6 +1,9 @@ /** - * \brief Functions to automatically generate constraints for the + * @file + * Functions to automatically generate constraints for the * rectangular node overlap removal problem. + */ +/* * * Authors: * Tim Dwyer diff --git a/src/libvpsc/generate-constraints.h b/src/libvpsc/generate-constraints.h index 8b858af3f..b8d7cdcd9 100644 --- a/src/libvpsc/generate-constraints.h +++ b/src/libvpsc/generate-constraints.h @@ -1,6 +1,10 @@ /** - * \brief Functions to automatically generate constraints for the + * @file + * Functions to automatically generate constraints for the * rectangular node overlap removal problem. + */ +/* TODO replace file comment with appropriate doc comment on vpsc::Rectangle */ +/* * * Authors: * Tim Dwyer -- cgit v1.2.3 From 1a5d5d8a7e796035bc70d5c727d4d901dda50726 Mon Sep 17 00:00:00 2001 From: "Jon A. Cruz" Date: Tue, 25 Oct 2011 00:45:35 -0700 Subject: Cleanup pass on documentation that was dumping garbage into doxygen output. (bzr r10696) --- src/libvpsc/block.h | 11 ++++++----- src/libvpsc/csolve_VPSC.h | 6 ++++-- src/libvpsc/pairingheap/PairingHeap.cpp | 6 ++++-- src/libvpsc/pairingheap/PairingHeap.h | 15 ++++++++------- src/libvpsc/solve_VPSC.h | 6 ++++-- src/libvpsc/variable.h | 3 +-- 6 files changed, 27 insertions(+), 20 deletions(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/block.h b/src/libvpsc/block.h index fe4a18b78..a4625b202 100644 --- a/src/libvpsc/block.h +++ b/src/libvpsc/block.h @@ -1,8 +1,4 @@ -/** - * \brief A block is a group of variables that must be moved together to improve - * the goal function without violating already active constraints. - * The variables in a block are spanned by a tree of active constraints. - * +/* * Authors: * Tim Dwyer * @@ -21,6 +17,11 @@ namespace vpsc { class Variable; class Constraint; +/** + * A block is a group of variables that must be moved together to improve + * the goal function without violating already active constraints. + * The variables in a block are spanned by a tree of active constraints. + */ class Block { typedef std::vector Variables; diff --git a/src/libvpsc/csolve_VPSC.h b/src/libvpsc/csolve_VPSC.h index 81e50d990..92179fc77 100644 --- a/src/libvpsc/csolve_VPSC.h +++ b/src/libvpsc/csolve_VPSC.h @@ -1,6 +1,8 @@ /** - * \brief Bridge for C programs to access solve_VPSC (which is in C++) - * + * @file + * Bridge for C programs to access solve_VPSC (which is in C++). + */ +/* * Authors: * Tim Dwyer * diff --git a/src/libvpsc/pairingheap/PairingHeap.cpp b/src/libvpsc/pairingheap/PairingHeap.cpp index 202980b70..6e003f99c 100644 --- a/src/libvpsc/pairingheap/PairingHeap.cpp +++ b/src/libvpsc/pairingheap/PairingHeap.cpp @@ -1,12 +1,14 @@ /** - * \brief Pairing heap datastructure implementation + * @file + * Pairing heap datastructure implementation. * * Based on example code in "Data structures and Algorithm Analysis in C++" * by Mark Allen Weiss, used and released under the LGPL by permission * of the author. * * No promises about correctness. Use at your own risk! - * + */ +/* * Authors: * Mark Allen Weiss * Tim Dwyer diff --git a/src/libvpsc/pairingheap/PairingHeap.h b/src/libvpsc/pairingheap/PairingHeap.h index 6159e96c1..62c782d5d 100644 --- a/src/libvpsc/pairingheap/PairingHeap.h +++ b/src/libvpsc/pairingheap/PairingHeap.h @@ -1,10 +1,4 @@ -/** - * \brief Pairing heap datastructure implementation - * - * Based on example code in "Data structures and Algorithm Analysis in C++" - * by Mark Allen Weiss, used and released under the LGPL by permission - * of the author. - * +/* * No promises about correctness. Use at your own risk! * * Authors: @@ -67,6 +61,13 @@ public: virtual bool isLessThan(T const &lhs, T const &rhs) const = 0; }; +/** + * Pairing heap datastructure implementation. + * + * Based on example code in "Data structures and Algorithm Analysis in C++" + * by Mark Allen Weiss, used and released under the LGPL by permission + * of the author. + */ template class PairingHeap { diff --git a/src/libvpsc/solve_VPSC.h b/src/libvpsc/solve_VPSC.h index 0f919a22a..84f646226 100644 --- a/src/libvpsc/solve_VPSC.h +++ b/src/libvpsc/solve_VPSC.h @@ -1,7 +1,9 @@ /** - * \brief Solve an instance of the "Variable Placement with Separation + * @file + * Solve an instance of the "Variable Placement with Separation * Constraints" problem. - * + */ +/* * Authors: * Tim Dwyer * diff --git a/src/libvpsc/variable.h b/src/libvpsc/variable.h index 25239ff20..022754a7d 100644 --- a/src/libvpsc/variable.h +++ b/src/libvpsc/variable.h @@ -1,5 +1,4 @@ -/** - * +/* * Authors: * Tim Dwyer * -- cgit v1.2.3 From 2633767789e4264b13ef91a684accf734fb4e94f Mon Sep 17 00:00:00 2001 From: "Jon A. Cruz" Date: Wed, 26 Oct 2011 21:55:51 -0700 Subject: Fixing more broken and split doc comments. (bzr r10697) --- src/libvpsc/block.cpp | 36 +++------------ src/libvpsc/block.h | 55 ++++++++++++++++++++--- src/libvpsc/blocks.cpp | 31 +++---------- src/libvpsc/blocks.h | 63 ++++++++++++++++++++++----- src/libvpsc/csolve_VPSC.cpp | 4 +- src/libvpsc/remove_rectangle_overlap.cpp | 17 ++------ src/libvpsc/remove_rectangle_overlap.h | 16 ++++++- src/libvpsc/solve_VPSC.cpp | 40 +++-------------- src/libvpsc/solve_VPSC.h | 75 +++++++++++++++++++++++++++----- src/libvpsc/variable.cpp | 4 +- 10 files changed, 203 insertions(+), 138 deletions(-) (limited to 'src/libvpsc') diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp index 0bd662f28..8171780d4 100644 --- a/src/libvpsc/block.cpp +++ b/src/libvpsc/block.cpp @@ -1,8 +1,4 @@ -/** - * \brief A block is a group of variables that must be moved together to improve - * the goal function without violating already active constraints. - * The variables in a block are spanned by a tree of active constraints. - * +/* * Authors: * Tim Dwyer * @@ -95,13 +91,7 @@ void Block::merge(Block* b, Constraint* c) { f<<" merged block="<<(b->deleted?*this:*b)<front(),NULL); @@ -363,12 +350,7 @@ bool Block::isActiveDirectedPathBetween(Variable* u, Variable *v) { } return false; } -/** - * Block needs to be split because of a violated constraint between vl and vr. - * We need to search the active constraint tree between l and r and find the constraint - * with min lagrangrian multiplier and split at that point. - * Returns the split constraint - */ + Constraint* Block::splitBetween(Variable* const vl, Variable* const vr, Block* &lb, Block* &rb) { #ifdef RECTANGLE_OVERLAP_LOGGING @@ -383,11 +365,7 @@ Constraint* Block::splitBetween(Variable* const vl, Variable* const vr, deleted = true; return c; } -/** - * Creates two new blocks, l and r, and splits this block across constraint c, - * placing the left subtree of constraints (and associated variables) into l - * and the right into r. - */ + void Block::split(Block* &l, Block* &r, Constraint* c) { c->active=false; l=new Block(); @@ -396,10 +374,6 @@ void Block::split(Block* &l, Block* &r, Constraint* c) { populateSplitBlock(r,c->right,c->left); } -/** - * Computes the cost (squared euclidean distance from desired positions) of the - * current positions for variables in this block - */ double Block::cost() { double c = 0; for (Vit v=vars->begin();v!=vars->end();++v) { diff --git a/src/libvpsc/block.h b/src/libvpsc/block.h index a4625b202..9c90fc87e 100644 --- a/src/libvpsc/block.h +++ b/src/libvpsc/block.h @@ -36,22 +36,57 @@ public: double wposn; Block(Variable* const v=NULL); virtual ~Block(void); - Constraint* findMinLM(); + + /** + * finds the constraint with the minimum lagrange multiplier, that is, the constraint + * that most wants to split + */ + Constraint* findMinLM(); + Constraint* findMinLMBetween(Variable* const lv, Variable* const rv); Constraint* findMinInConstraint(); Constraint* findMinOutConstraint(); void deleteMinInConstraint(); void deleteMinOutConstraint(); double desiredWeightedPosition(); - void merge(Block *b, Constraint *c, double dist); + + /** + * Merges b into this block across c. Can be either a + * right merge or a left merge + * @param b block to merge into this + * @param c constraint being merged + * @param distance separation required to satisfy c + */ + void merge(Block *b, Constraint *c, double dist); + void merge(Block *b, Constraint *c); void mergeIn(Block *b); void mergeOut(Block *b); - void split(Block *&l, Block *&r, Constraint *c); - Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb); + + /** + * Creates two new blocks, l and r, and splits this block across constraint c, + * placing the left subtree of constraints (and associated variables) into l + * and the right into r. + */ + void split(Block *&l, Block *&r, Constraint *c); + + /** + * Block needs to be split because of a violated constraint between vl and vr. + * We need to search the active constraint tree between l and r and find the constraint + * with min lagrangrian multiplier and split at that point. + * Returns the split constraint + */ + Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb); + void setUpInConstraints(); void setUpOutConstraints(); - double cost(); + + /** + * Computes the cost (squared euclidean distance from desired positions) of the + * current positions for variables in this block + */ + double cost(); + bool deleted; long timeStamp; PairingHeap *in; @@ -75,3 +110,13 @@ private: } #endif // SEEN_REMOVEOVERLAP_BLOCK_H +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : diff --git a/src/libvpsc/blocks.cpp b/src/libvpsc/blocks.cpp index fe0caacfc..7eff1e6c4 100644 --- a/src/libvpsc/blocks.cpp +++ b/src/libvpsc/blocks.cpp @@ -1,9 +1,5 @@ -/** - * \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 +/* + * A block structure defined over the variables. * * Authors: * Tim Dwyer @@ -47,10 +43,6 @@ Blocks::~Blocks(void) 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;i *order) { #endif order->push_front(v); } -/** - * Processes incoming constraints, most violated to least, merging with the - * neighbouring (left) block until no more violated constraints are found - */ + void Blocks::mergeLeft(Block *r) { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); @@ -115,9 +104,7 @@ void Blocks::mergeLeft(Block *r) { f<<"merged "<<*r<split(l,r,c); #ifdef RECTANGLE_OVERLAP_LOGGING @@ -184,10 +168,7 @@ void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) { insert(l); insert(r); } -/** - * 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) { diff --git a/src/libvpsc/blocks.h b/src/libvpsc/blocks.h index e3223822e..b711a529f 100644 --- a/src/libvpsc/blocks.h +++ b/src/libvpsc/blocks.h @@ -33,21 +33,62 @@ class Constraint; class Blocks : public std::set { public: - Blocks(const int n, Variable* const vs[]); + Blocks(const int n, Variable* const vs[]); + virtual ~Blocks(void); - void mergeLeft(Block *r); - void mergeRight(Block *l); - void split(Block *b, Block *&l, Block *&r, Constraint *c); - std::list *totalOrder(); - void cleanup(); - double cost(); + + /** + * Processes incoming constraints, most violated to least, merging with the + * neighbouring (left) block until no more violated constraints are found. + */ + void mergeLeft(Block *r); + + /** + * Symmetrical to mergeLeft. + * @see mergeLeft + */ + void mergeRight(Block *l); + + /** + * Splits block b across constraint c into two new blocks, l and r (c's left + * and right sides respectively). + */ + void split(Block *b, Block *&l, Block *&r, Constraint *c); + + /** + * Returns a list of variables with total ordering determined by the constraint + * DAG. + */ + std::list *totalOrder(); + + void cleanup(); + + /** + * Returns the cost total squared distance of variables from their desired + * positions. + */ + double cost(); + private: - void dfsVisit(Variable *v, std::list *order); - void removeBlock(Block *doomed); - Variable* const *vs; - int nvs; + void dfsVisit(Variable *v, std::list *order); + + void removeBlock(Block *doomed); + + Variable* const *vs; + + int nvs; }; extern long blockTimeCtr; } #endif // SEEN_REMOVEOVERLAP_BLOCKS_H +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : diff --git a/src/libvpsc/csolve_VPSC.cpp b/src/libvpsc/csolve_VPSC.cpp index 5176242d5..24459d09f 100644 --- a/src/libvpsc/csolve_VPSC.cpp +++ b/src/libvpsc/csolve_VPSC.cpp @@ -1,5 +1,5 @@ -/** - * \brief Bridge for C programs to access solve_VPSC (which is in C++) +/* + * Bridge for C programs to access solve_VPSC (which is in C++). * * Authors: * Tim Dwyer diff --git a/src/libvpsc/remove_rectangle_overlap.cpp b/src/libvpsc/remove_rectangle_overlap.cpp index 4d2750b9e..381759f3c 100644 --- a/src/libvpsc/remove_rectangle_overlap.cpp +++ b/src/libvpsc/remove_rectangle_overlap.cpp @@ -1,5 +1,5 @@ -/** @file - * @brief remove overlaps between a set of rectangles. +/* + * remove overlaps between a set of rectangles. * * Authors: * Tim Dwyer @@ -28,18 +28,7 @@ using namespace vpsc; double Rectangle::xBorder=0; double Rectangle::yBorder=0; -/** - * Takes an array of n rectangles and moves them as little as possible - * such that rectangles are separated by at least xBorder horizontally - * and yBorder vertically - * - * Works in three passes: - * 1) removes some overlap horizontally - * 2) removes remaining overlap vertically - * 3) a last horizontal pass removes all overlap starting from original - * x-positions - this corrects the case where rectangles were moved - * too much in the first pass. - */ + void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder) { try { // The extra gap avoids numerical imprecision problems diff --git a/src/libvpsc/remove_rectangle_overlap.h b/src/libvpsc/remove_rectangle_overlap.h index 1af90a754..3e2f4cc8f 100644 --- a/src/libvpsc/remove_rectangle_overlap.h +++ b/src/libvpsc/remove_rectangle_overlap.h @@ -1,5 +1,5 @@ -/** @file - * @brief Declaration of main internal remove-overlaps function. +/* + * Declaration of main internal remove-overlaps function. */ /* Authors: * Tim Dwyer @@ -16,6 +16,18 @@ namespace vpsc { class Rectangle; } +/** + * Takes an array of n rectangles and moves them as little as possible + * such that rectangles are separated by at least xBorder horizontally + * and yBorder vertically + * + * Works in three passes: + * 1) removes some overlap horizontally + * 2) removes remaining overlap vertically + * 3) a last horizontal pass removes all overlap starting from original + * x-positions - this corrects the case where rectangles were moved + * too much in the first pass. + */ void removeRectangleOverlap(unsigned n, vpsc::Rectangle *rs[], double xBorder, double yBorder); diff --git a/src/libvpsc/solve_VPSC.cpp b/src/libvpsc/solve_VPSC.cpp index ec2c48d46..f9bed649c 100644 --- a/src/libvpsc/solve_VPSC.cpp +++ b/src/libvpsc/solve_VPSC.cpp @@ -1,5 +1,5 @@ -/** - * \brief Solve an instance of the "Variable Placement with Separation +/* + * Solve an instance of the "Variable Placement with Separation * Constraints" problem. * * Authors: @@ -59,16 +59,7 @@ void Solver::printBlocks() { } #endif } -/** -* Produces a feasible - though not necessarily optimal - solution by -* examining blocks in the partial order defined by the directed acyclic -* graph of constraints. For each block (when processing left to right) we -* maintain the invariant that all constraints to the left of the block -* (incoming constraints) are satisfied. This is done by repeatedly merging -* blocks into bigger blocks across violated constraints (most violated -* first) fixing the position of variables inside blocks relative to one -* another so that constraints internal to the block are satisfied. -*/ + void Solver::satisfy() { list *vs=bs->totalOrder(); for(list::iterator i=vs->begin();i!=vs->end();++i) { @@ -129,12 +120,7 @@ void Solver::refine() { } } } -/** - * Calculate the optimal solution. After using satisfy() to produce a - * feasible solution, refine() examines each block to see if further - * refinement is possible by splitting the block. This is done repeatedly - * until no further improvement is possible. - */ + void Solver::solve() { satisfy(); refine(); @@ -156,19 +142,7 @@ void IncSolver::solve() { #endif } while(fabs(lastcost-cost)>0.0001); } -/** - * incremental version of satisfy that allows refinement after blocks are - * moved. - * - * - move blocks to new positions - * - repeatedly merge across most violated constraint until no more - * violated constraints exist - * - * Note: there is a special case to handle when the most violated constraint - * is between two variables in the same block. Then, we must split the block - * over an active constraint between the two variables. We choose the - * constraint with the most negative lagrangian multiplier. - */ + void IncSolver::satisfy() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); @@ -270,10 +244,6 @@ void IncSolver::splitBlocks() { bs->cleanup(); } -/** - * Scan constraint list for the most violated constraint, or the first equality - * constraint - */ Constraint* IncSolver::mostViolated(ConstraintList &l) { double minSlack = DBL_MAX; Constraint* v=NULL; diff --git a/src/libvpsc/solve_VPSC.h b/src/libvpsc/solve_VPSC.h index 84f646226..e416ef9c6 100644 --- a/src/libvpsc/solve_VPSC.h +++ b/src/libvpsc/solve_VPSC.h @@ -34,8 +34,26 @@ class Blocks; */ class Solver { public: - virtual void satisfy(); - virtual void solve(); + + /** + * Produces a feasible - though not necessarily optimal - solution by + * examining blocks in the partial order defined by the directed acyclic + * graph of constraints. For each block (when processing left to right) we + * maintain the invariant that all constraints to the left of the block + * (incoming constraints) are satisfied. This is done by repeatedly merging + * blocks into bigger blocks across violated constraints (most violated + * first) fixing the position of variables inside blocks relative to one + * another so that constraints internal to the block are satisfied. + */ + virtual void satisfy(); + + /** + * Calculate the optimal solution. After using satisfy() to produce a + * feasible solution, refine() examines each block to see if further + * refinement is possible by splitting the block. This is done repeatedly + * until no further improvement is possible. + */ + virtual void solve(); Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); virtual ~Solver(); @@ -56,16 +74,51 @@ private: class IncSolver : public Solver { public: - unsigned splitCnt; - void satisfy(); - void solve(); - void moveBlocks(); - void splitBlocks(); - IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); + unsigned splitCnt; + + /** + * incremental version of satisfy that allows refinement after blocks are + * moved. + * + * - move blocks to new positions + * - repeatedly merge across most violated constraint until no more + * violated constraints exist + * + * Note: there is a special case to handle when the most violated constraint + * is between two variables in the same block. Then, we must split the block + * over an active constraint between the two variables. We choose the + * constraint with the most negative lagrangian multiplier. + */ + void satisfy(); + + void solve(); + + void moveBlocks(); + + void splitBlocks(); + + IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); private: - typedef std::vector ConstraintList; - ConstraintList inactive; - Constraint* mostViolated(ConstraintList &l); + + typedef std::vector ConstraintList; + + ConstraintList inactive; + + /** + * Scan constraint list for the most violated constraint, or the first equality + * constraint. + */ + Constraint* mostViolated(ConstraintList &l); }; } #endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : diff --git a/src/libvpsc/variable.cpp b/src/libvpsc/variable.cpp index 19dc0746a..29bf8dc5c 100644 --- a/src/libvpsc/variable.cpp +++ b/src/libvpsc/variable.cpp @@ -1,5 +1,4 @@ -/** - * +/* * Authors: * Tim Dwyer * @@ -8,6 +7,7 @@ * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include "variable.h" + namespace vpsc { std::ostream& operator <<(std::ostream &os, const Variable &v) { os << "(" << v.id << "=" << v.position() << ")"; -- cgit v1.2.3