diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libvpsc')
28 files changed, 6314 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libvpsc/CMakeLists.txt b/src/3rdparty/adaptagrams/libvpsc/CMakeLists.txt new file mode 100644 index 0000000..538ad30 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/CMakeLists.txt @@ -0,0 +1,28 @@ + +set(libvpsc_SRC + block.cpp + blocks.cpp + cbuffer.cpp + constraint.cpp + rectangle.cpp + solve_VPSC.cpp + variable.cpp + + + # ------- + # Headers + assertions.h + block.h + blocks.h + cbuffer.h + constraint.h + exceptions.h + linesegment.h + pairing_heap.h + rectangle.h + solve_VPSC.h + variable.h +) + +include_directories("${CMAKE_CURRENT_SOURCE_DIR}/..") +add_inkscape_lib(vpsc_LIB "${libvpsc_SRC}") diff --git a/src/3rdparty/adaptagrams/libvpsc/COPYING b/src/3rdparty/adaptagrams/libvpsc/COPYING new file mode 100644 index 0000000..6ff1d7b --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/COPYING @@ -0,0 +1,505 @@ + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. + + <one line to give the library's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + 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. + + 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. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James Random Hacker. + + <signature of Ty Coon>, 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! + + + diff --git a/src/3rdparty/adaptagrams/libvpsc/Makefile.am b/src/3rdparty/adaptagrams/libvpsc/Makefile.am new file mode 100644 index 0000000..12e779a --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/Makefile.am @@ -0,0 +1,42 @@ +EXTRA_DIST=libvpsc.pc.in +lib_LTLIBRARIES = libvpsc.la +libvpsc_la_CPPFLAGS = -I$(top_srcdir) -I$(includedir)/libvpsc -fPIC +libvpsc_la_LDFLAGS = -no-undefined + +#DEFS=-DLIBVPSC_LOGGING + + +libvpsc_la_SOURCES = block.cpp\ + blocks.cpp\ + constraint.cpp\ + rectangle.cpp\ + solve_VPSC.cpp\ + variable.cpp\ + cbuffer.cpp\ + isnan.h\ + block.h\ + blocks.h\ + constraint.h\ + rectangle.h\ + pairingheap.h\ + solve_VPSC.h\ + variable.h\ + cbuffer.h\ + linesegment.h\ + assertions.h + +libvpscincludedir = $(includedir)/libvpsc + +libvpscinclude_HEADERS = solve_VPSC.h \ + block.h\ + constraint.h\ + exceptions.h\ + rectangle.h\ + variable.h \ + assertions.h + +pkgconfigdir = $(libdir)/pkgconfig +pkgconfig_DATA = libvpsc.pc + +SUBDIRS = . tests + diff --git a/src/3rdparty/adaptagrams/libvpsc/assertions.h b/src/3rdparty/adaptagrams/libvpsc/assertions.h new file mode 100644 index 0000000..f197069 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/assertions.h @@ -0,0 +1,102 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2009 Monash University + * + * 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. + * +*/ + +#ifndef VPSC_ASSERTIONS_H +#define VPSC_ASSERTIONS_H + +#ifdef NDEBUG + + #define COLA_ASSERT(expr) static_cast<void>(0) + +#else // Not NDEBUG + + // sstream needs ::strcpy_s under MinGW so include cstring. + #include <cstring> + + #include <sstream> + #include <cassert> + + #if defined(USE_ASSERT_EXCEPTIONS) + + // String seems to be missing on MinGW's gcc, + // so define it here if it is missing. + #ifndef __STRING + #define __STRING(x) #x + #endif + + #if !defined(__ASSERT_FUNCTION) + #define COLA_ASSERT(expr) \ + if (!(expr)) { \ + throw vpsc::CriticalFailure(__STRING(expr), __FILE__, __LINE__); \ + } + #else + #define COLA_ASSERT(expr) \ + if (!(expr)) { \ + throw vpsc::CriticalFailure(__STRING(expr), __FILE__, __LINE__, \ + __ASSERT_FUNCTION); \ + } + #endif + + #else + #define COLA_ASSERT(expr) assert(expr) + #endif + +namespace vpsc { + +// Critical failure: either something went wrong, or (more likely) there +// was infeasible input. +class CriticalFailure +{ + public: + CriticalFailure(const char *expr, const char *file, int line, + const char *function = nullptr) + : expr(expr), + file(file), + line(line), + function(function) + { + } + std::string what() const + { + std::stringstream s; + s << "ERROR: Critical assertion failed.\n"; + s << " expression: " << expr << "\n"; + s << " at line " << line << " of " << file << "\n"; + if (function) + { + s << " in: " << function << "\n"; + } + + return s.str(); + } + private: + const char *expr; + const char *file; + int line; + const char *function; +}; + +} + +#endif // NDEBUG + + +#endif // VPSC_ASSERTIONS_H + diff --git a/src/3rdparty/adaptagrams/libvpsc/block.cpp b/src/3rdparty/adaptagrams/libvpsc/block.cpp new file mode 100644 index 0000000..dfcf6c9 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/block.cpp @@ -0,0 +1,647 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 +*/ + +/* + * @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. + * + */ + +#include "libvpsc/block.h" +#include "libvpsc/variable.h" +#include <cassert> +#include "libvpsc/pairing_heap.h" +#include "libvpsc/constraint.h" +#include "libvpsc/exceptions.h" +#include "libvpsc/blocks.h" + +#ifdef LIBVPSC_LOGGING +#include <fstream> +using std::ios; +using std::ofstream; +using std::endl; +#endif + +#define __NOTNAN(p) (p)==(p) + +namespace vpsc { +void PositionStats::addVariable(Variable* v) { + double ai=scale/v->scale; + double bi=v->offset/v->scale; + double wi=v->weight; + AB+=wi*ai*bi; + AD+=wi*ai*v->desiredPosition; + A2+=wi*ai*ai; + /* +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f << "adding v[" << v->id << "], blockscale=" << scale << ", despos=" + << v->desiredPosition << ", ai=" << ai << ", bi=" << bi + << ", AB=" << AB << ", AD=" << AD << ", A2=" << A2; +#endif +*/ +} +void Block::addVariable(Variable* v) { + v->block=this; + vars->push_back(v); + if(ps.A2==0) ps.scale=v->scale; + //weight+= v->weight; + //wposn += v->weight * (v->desiredPosition - v->offset); + //posn=wposn/weight; + ps.addVariable(v); + posn=(ps.AD - ps.AB) / ps.A2; + COLA_ASSERT(__NOTNAN(posn)); + /* +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f << ", posn=" << posn << endl; +#endif +*/ +} +Block::Block(Blocks *blocks, Variable* const v) + : vars(new std::vector<Variable*>) + , posn(0) + //, weight(0) + //, wposn(0) + , deleted(false) + , timeStamp(0) + , in(nullptr) + , out(nullptr) + , blocks(blocks) +{ + if(v!=nullptr) { + v->offset=0; + addVariable(v); + } +} + +void Block::updateWeightedPosition() { + //wposn=0; + ps.AB=ps.AD=ps.A2=0; + for (Vit v=vars->begin();v!=vars->end();++v) { + //wposn += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight; + ps.addVariable(*v); + } + posn=(ps.AD - ps.AB) / ps.A2; + COLA_ASSERT(__NOTNAN(posn)); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f << ", posn=" << posn << endl; +#endif +} +Block::~Block(void) +{ + delete vars; + delete in; + delete out; +} +void Block::setUpInConstraints() { + setUpConstraintHeap(in,true); +} +void Block::setUpOutConstraints() { + setUpConstraintHeap(out,false); +} +void Block::setUpConstraintHeap(PairingHeap<Constraint*,CompareConstraints>* &h,bool in) { + delete h; + h = new PairingHeap<Constraint*,CompareConstraints>(); + for (Vit i=vars->begin();i!=vars->end();++i) { + Variable *v=*i; + std::vector<Constraint*> *cs=in?&(v->in):&(v->out); + for (Cit j=cs->begin();j!=cs->end();++j) { + Constraint *c=*j; + c->timeStamp=blocks->blockTimeCtr; + if ( ((c->left->block != this) && in) || + ((c->right->block != this) && !in) ) + { + h->insert(c); + } + } + } +} +Block* Block::merge(Block* b, Constraint* c) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl; +#endif + double dist = c->right->offset - c->left->offset - c->gap; + Block *l=c->left->block; + Block *r=c->right->block; + if (l->vars->size() < r->vars->size()) { + r->merge(l,c,dist); + } else { + l->merge(r,c,-dist); + } + Block* mergeBlock=b->deleted?this:b; +#ifdef LIBVPSC_LOGGING + f<<" merged block="<<*mergeBlock<<endl; +#endif + return mergeBlock; +} +/* + * 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 Block::merge(Block *b, Constraint *c, double dist) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging: "<<*b<<"dist="<<dist<<endl; +#endif + c->active=true; + //wposn+=b->wposn-dist*b->weight; + //weight+=b->weight; + for(Vit i=b->vars->begin();i!=b->vars->end();++i) { + Variable *v=*i; + //v->block=this; + //vars->push_back(v); + v->offset+=dist; + addVariable(v); + } +#ifdef LIBVPSC_LOGGING + for(Vit i=vars->begin();i!=vars->end();++i) { + Variable *v=*i; + f<<" v["<<v->id<<"]: d="<<v->desiredPosition + <<" a="<<v->scale<<" o="<<v->offset + <<endl; + } + f<<" AD="<<ps.AD<<" AB="<<ps.AB<<" A2="<<ps.A2<<endl; +#endif + //posn=wposn/weight; + //COLA_ASSERT(wposn==ps.AD - ps.AB); + posn=(ps.AD - ps.AB) / ps.A2; + COLA_ASSERT(__NOTNAN(posn)); + b->deleted=true; +} + +void Block::mergeIn(Block *b) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging constraint heaps... "<<endl; +#endif + // We check the top of the heaps to remove possible internal constraints + findMinInConstraint(); + b->findMinInConstraint(); + in->merge(b->in); +#ifdef LIBVPSC_LOGGING + f<<" merged heap: "<<*in<<endl; +#endif +} +void Block::mergeOut(Block *b) { + findMinOutConstraint(); + b->findMinOutConstraint(); + out->merge(b->out); +} +Constraint *Block::findMinInConstraint() { + Constraint *v = nullptr; + std::vector<Constraint*> outOfDate; + while (!in->isEmpty()) { + v = in->findMin(); + Block *lb=v->left->block; + Block *rb=v->right->block; + // rb may not be this if called between merge and mergeIn +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" checking constraint ... "<<*v; + f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl; +#endif + if(lb == rb) { + // constraint has been merged into the same block +#ifdef LIBVPSC_LOGGING + if(v->slack()<0) { + f<<" violated internal constraint found! "<<*v<<endl; + f<<" lb="<<*lb<<endl; + f<<" rb="<<*rb<<endl; + } +#endif + in->deleteMin(); +#ifdef LIBVPSC_LOGGING + f<<" ... skipping internal constraint"<<endl; +#endif + } else if(v->timeStamp < lb->timeStamp) { + // block at other end of constraint has been moved since this + in->deleteMin(); + outOfDate.push_back(v); +#ifdef LIBVPSC_LOGGING + f<<" reinserting out of date (reinsert later)"<<endl; +#endif + } else { + break; + } + } + for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) { + v=*i; + v->timeStamp=blocks->blockTimeCtr; + in->insert(v); + } + if(in->isEmpty()) { + v=nullptr; + } else { + v=in->findMin(); + } + return v; +} +Constraint *Block::findMinOutConstraint() { + if(out->isEmpty()) return nullptr; + Constraint *v = out->findMin(); + while (v->left->block == v->right->block) { + out->deleteMin(); + if(out->isEmpty()) return nullptr; + v = out->findMin(); + } + return v; +} +void Block::deleteMinInConstraint() { + in->deleteMin(); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"deleteMinInConstraint... "<<endl; + f<<" result: "<<*in<<endl; +#endif +} +void Block::deleteMinOutConstraint() { + out->deleteMin(); +} +inline bool Block::canFollowLeft(Constraint const* c, Variable const* last) const { + return c->left->block==this && c->active && last!=c->left; +} +inline bool Block::canFollowRight(Constraint const* c, Variable const* last) const { + return c->right->block==this && c->active && last!=c->right; +} + +// computes the derivative of v and the lagrange multipliers +// of v's out constraints (as the recursive sum of those below. +// Does not backtrack over u. +// also records the constraint with minimum lagrange multiplier +// in min_lm +double Block::compute_dfdv(Variable* const v, Variable* const u, + Constraint *&min_lm) { + double dfdv=v->dfdv(); + for(Cit it=v->out.begin();it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + c->lm=compute_dfdv(c->right,v,min_lm); + dfdv+=c->lm*c->left->scale; + if(!c->equality&&(min_lm==nullptr||c->lm<min_lm->lm)) min_lm=c; + } + } + for(Cit it=v->in.begin();it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + c->lm=-compute_dfdv(c->left,v,min_lm); + dfdv-=c->lm*c->right->scale; + if(!c->equality&&(min_lm==nullptr||c->lm<min_lm->lm)) min_lm=c; + } + } + return dfdv/v->scale; +} +double Block::compute_dfdv(Variable* const v, Variable* const u) { + double dfdv = v->dfdv(); + for(Cit it = v->out.begin(); it != v->out.end(); ++it) { + Constraint *c = *it; + if(canFollowRight(c,u)) { + c->lm = compute_dfdv(c->right,v); + dfdv += c->lm * c->left->scale; + } + } + for(Cit it=v->in.begin();it!=v->in.end();++it) { + Constraint *c = *it; + if(canFollowLeft(c,u)) { + c->lm = - compute_dfdv(c->left,v); + dfdv -= c->lm * c->right->scale; + } + } + return dfdv/v->scale; +} + +// The top level v and r are variables between which we want to find the +// constraint with the smallest lm. +// Similarly, m is initially nullptr and is only assigned a value if the next +// variable to be visited is r or if a possible min constraint is returned from +// a nested call (rather than nullptr). +// Then, the search for the m with minimum lm occurs as we return from +// the recursion (checking only constraints traversed left-to-right +// in order to avoid creating any new violations). +// We also do not consider equality constraints as potential split points +bool Block::split_path( + Variable* r, + Variable* const v, + Variable* const u, + Constraint* &m, + bool desperation=false + ) +{ + for(Cit it(v->in.begin());it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" left split path: "<<*c<<endl; +#endif + if(c->left==r) { + if(desperation&&!c->equality) m=c; + return true; + } else { + if(split_path(r,c->left,v,m)) { + if(desperation && !c->equality && (!m||c->lm<m->lm)) { + m=c; + } + return true; + } + } + } + } + for(Cit it(v->out.begin());it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" right split path: "<<*c<<endl; +#endif + if(c->right==r) { + if(!c->equality) m=c; + return true; + } else { + if(split_path(r,c->right,v,m)) { + if(!c->equality && (!m||c->lm<m->lm)) + m=c; + return true; + } + } + } + } + return false; +} +/* +Block::Pair Block::compute_dfdv_between( + Variable* r, Variable* const v, Variable* const u, + const Direction dir = NONE, bool changedDirection = false) { + double dfdv=v->weight*(v->position() - v->desiredPosition); + Constraint *m=nullptr; + for(Cit it(v->in.begin());it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + if(dir==RIGHT) { + changedDirection = true; + } + if(c->left==r) { + r=nullptr; + if(!c->equality) m=c; + } + Pair p=compute_dfdv_between(r,c->left,v, + LEFT,changedDirection); + dfdv -= c->lm = -p.first; + if(r && p.second) + m = p.second; + } + } + for(Cit it(v->out.begin());it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + if(dir==LEFT) { + changedDirection = true; + } + if(c->right==r) { + r=nullptr; + if(!c->equality) m=c; + } + Pair p=compute_dfdv_between(r,c->right,v, + RIGHT,changedDirection); + dfdv += c->lm = p.first; + if(r && p.second) + m = changedDirection && !c->equality && c->lm < p.second->lm + ? c + : p.second; + } + } + return Pair(dfdv,m); +} +*/ + +// resets LMs for all active constraints to 0 by +// traversing active constraint tree starting from v, +// not back tracking over u +void Block::reset_active_lm(Variable* const v, Variable* const u) { + for(Cit it=v->out.begin();it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + c->lm=0; + reset_active_lm(c->right,v); + } + } + for(Cit it=v->in.begin();it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + c->lm=0; + reset_active_lm(c->left,v); + } + } +} +void Block::list_active(Variable* const v, Variable* const u) { + for(Cit it=v->out.begin();it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" "<<*c<<endl; +#endif + list_active(c->right,v); + } + } + for(Cit it=v->in.begin();it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" "<<*c<<endl; +#endif + list_active(c->left,v); + } + } +} +/* + * finds the constraint with the minimum lagrange multiplier, that is, the constraint + * that most wants to split + */ +Constraint *Block::findMinLM() { + Constraint *min_lm=nullptr; + reset_active_lm(vars->front(),nullptr); + compute_dfdv(vars->front(),nullptr,min_lm); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" langrangians: "<<endl; + list_active(vars->front(),nullptr); +#endif + return min_lm; +} +Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) { + reset_active_lm(vars->front(),nullptr); + compute_dfdv(vars->front(),nullptr); + Constraint *min_lm=nullptr; + split_path(rv,lv,nullptr,min_lm); +#if 0 + if(min_lm==nullptr) { + split_path(rv,lv,nullptr,min_lm,true); + } +#else + if(min_lm==nullptr) { +#ifdef LIBVPSC_DEBUG + fprintf(stderr,"Couldn't find split point!\n"); +#endif + UnsatisfiableException e; + getActivePathBetween(e.path,lv,rv,nullptr); + throw e; + } + COLA_ASSERT(min_lm!=nullptr); +#endif + return min_lm; +} + +// populates block b by traversing the active constraint tree adding variables as they're +// visited. Starts from variable v and does not backtrack over variable u. +void Block::populateSplitBlock(Block *b, Variable* v, Variable const* u) { + b->addVariable(v); + for (Cit c=v->in.begin();c!=v->in.end();++c) { + if (canFollowLeft(*c,u)) + populateSplitBlock(b, (*c)->left, v); + } + for (Cit c=v->out.begin();c!=v->out.end();++c) { + if (canFollowRight(*c,u)) + populateSplitBlock(b, (*c)->right, v); + } +} +/* + * Returns the active path between variables u and v... not back tracking over w + */ +bool Block::getActivePathBetween(Constraints& path, Variable const* u, + Variable const* v, Variable const *w) const { + if(u==v) return true; + for (Cit_const c=u->in.begin();c!=u->in.end();++c) { + if (canFollowLeft(*c,w)) { + if(getActivePathBetween(path, (*c)->left, v, u)) { + path.push_back(*c); + return true; + } + } + } + for (Cit_const c=u->out.begin();c!=u->out.end();++c) { + if (canFollowRight(*c,w)) { + if(getActivePathBetween(path, (*c)->right, v, u)) { + path.push_back(*c); + return true; + } + } + } + return false; +} +// Search active constraint tree from u to see if there is a directed path to v. +// Returns true if path is found with all constraints in path having their visited flag +// set true. +bool Block::isActiveDirectedPathBetween(Variable const* u, Variable const* v) const { + if(u==v) return true; + for (Cit_const c=u->out.begin();c!=u->out.end();++c) { + if(canFollowRight(*c,nullptr)) { + if(isActiveDirectedPathBetween((*c)->right,v)) { + return true; + } + } + } + return false; +} +bool Block::getActiveDirectedPathBetween( + Constraints& path, Variable const* u, Variable const* v) const { + if(u==v) return true; + for (Cit_const c=u->out.begin();c!=u->out.end();++c) { + if(canFollowRight(*c,nullptr)) { + if(getActiveDirectedPathBetween(path,(*c)->right,v)) { + path.push_back(*c); + return true; + } + } + } + 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 LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" need to split between: "<<*vl<<" and "<<*vr<<endl; +#endif + Constraint *c=findMinLMBetween(vl, vr); +#ifdef LIBVPSC_LOGGING + f<<" going to split on: "<<*c<<endl; +#endif + if(c!=nullptr) { + split(lb,rb,c); + 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(blocks); + populateSplitBlock(l,c->left,c->right); + //COLA_ASSERT(l->weight>0); + r=new Block(blocks); + populateSplitBlock(r,c->right,c->left); + //COLA_ASSERT(r->weight>0); +} + +/* + * 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) { + double diff = (*v)->position() - (*v)->desiredPosition; + c += (*v)->weight * diff * diff; + } + return c; +} +std::ostream& operator <<(std::ostream &os, const Block& b) +{ + os<<"Block(posn="<<b.posn<<"):"; + for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) { + os<<" "<<**v; + } + if(b.deleted) { + os<<" Deleted!"; + } + return os; +} + +} + diff --git a/src/3rdparty/adaptagrams/libvpsc/block.h b/src/3rdparty/adaptagrams/libvpsc/block.h new file mode 100644 index 0000000..448ead0 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/block.h @@ -0,0 +1,113 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 +*/ + +/* + * \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. + */ + +#ifndef VPSC_BLOCK_H +#define VPSC_BLOCK_H + +#include <iostream> +#include <vector> + +template <class T, class TCompare> class PairingHeap; + +namespace vpsc { +class Variable; +class Constraint; +class CompareConstraints; +class Blocks; + +struct PositionStats { + PositionStats() : scale(0), AB(0), AD(0), A2(0) {} + void addVariable(Variable* const v); + double scale; + double AB; + double AD; + double A2; +}; + +class Block +{ + typedef std::vector<Variable*> Variables; + typedef std::vector<Constraint*> Constraints; + typedef Variables::iterator Vit; + typedef Constraints::iterator Cit; + typedef Constraints::const_iterator Cit_const; + + friend std::ostream& operator <<(std::ostream &os,const Block &b); +public: + Variables *vars; + double posn; + //double weight; + //double wposn; + PositionStats ps; + Block(Blocks *blocks, Variable* const v=nullptr); + ~Block(void); + Constraint* findMinLM(); + Constraint* findMinLMBetween(Variable* const lv, Variable* const rv); + Constraint* findMinInConstraint(); + Constraint* findMinOutConstraint(); + void deleteMinInConstraint(); + void deleteMinOutConstraint(); + void updateWeightedPosition(); + void merge(Block *b, Constraint *c, double dist); + Block* 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); + void setUpInConstraints(); + void setUpOutConstraints(); + double cost(); + bool deleted; + long timeStamp; + PairingHeap<Constraint*,CompareConstraints> *in; + PairingHeap<Constraint*,CompareConstraints> *out; + bool getActivePathBetween(Constraints& path, Variable const* u, + Variable const* v, Variable const *w) const; + bool isActiveDirectedPathBetween( + Variable const* u, Variable const* v) const; + bool getActiveDirectedPathBetween(Constraints& path, Variable const * u, Variable const * v) const; +private: + typedef enum {NONE, LEFT, RIGHT} Direction; + typedef std::pair<double, Constraint*> Pair; + void reset_active_lm(Variable* const v, Variable* const u); + void list_active(Variable* const v, Variable* const u); + double compute_dfdv(Variable* const v, Variable* const u); + double compute_dfdv(Variable* const v, Variable* const u, Constraint *&min_lm); + bool split_path(Variable*, Variable* const, Variable* const, + Constraint* &min_lm, bool desperation); + bool canFollowLeft(Constraint const* c, Variable const* last) const; + bool canFollowRight(Constraint const* c, Variable const* last) const; + void populateSplitBlock(Block *b, Variable* v, Variable const* u); + void addVariable(Variable* v); + void setUpConstraintHeap(PairingHeap<Constraint*,CompareConstraints>* &h,bool in); + + // Parent container, that holds the blockTimeCtr. + Blocks *blocks; +}; +} + +#endif // VPSC_BLOCK_H diff --git a/src/3rdparty/adaptagrams/libvpsc/blocks.cpp b/src/3rdparty/adaptagrams/libvpsc/blocks.cpp new file mode 100644 index 0000000..7481084 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/blocks.cpp @@ -0,0 +1,249 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2012 Monash University + * + * 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 "libvpsc/blocks.h" +#include "libvpsc/block.h" +#include "libvpsc/constraint.h" +#include "libvpsc/variable.h" +#include "libvpsc/assertions.h" + +#ifdef LIBVPSC_LOGGING +#include <fstream> +using std::ios; +using std::ofstream; +using std::endl; +#endif +using std::vector; +using std::iterator; +using std::list; +using std::copy; +#define __NOTNAN(p) (p)==(p) + +namespace vpsc { + + +Blocks::Blocks(vector<Variable*> const &vs) : vs(vs),nvs(vs.size()) { + blockTimeCtr=0; + m_blocks.resize(nvs); + for(size_t i=0;i<nvs;i++) { + m_blocks[i] = new Block(this, vs[i]); + } +} +Blocks::~Blocks(void) +{ + 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<Variable*> *Blocks::totalOrder() { + list<Variable*> *order = new list<Variable*>; + for(size_t i=0;i<nvs;i++) { + vs[i]->visited=false; + } + for(size_t i=0;i<nvs;i++) { + if(vs[i]->in.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<Variable*> *order) { + v->visited=true; + vector<Constraint*>::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<<endl; +#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 LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"mergeLeft called on "<<*r<<endl; +#endif + r->timeStamp=++blockTimeCtr; + r->setUpInConstraints(); + Constraint *c=r->findMinInConstraint(); + while (c != nullptr && c->slack()<0) { +#ifdef LIBVPSC_LOGGING + f<<"mergeLeft on constraint: "<<*c<<endl; +#endif + r->deleteMinInConstraint(); + Block *l = c->left->block; + if (l->in==nullptr) 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<<endl; +#endif +} +/* + * Symmetrical to mergeLeft + */ +void Blocks::mergeRight(Block *l) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"mergeRight called on "<<*l<<endl; +#endif + l->setUpOutConstraints(); + Constraint *c = l->findMinOutConstraint(); + while (c != nullptr && c->slack()<0) { +#ifdef LIBVPSC_LOGGING + f<<"mergeRight on constraint: "<<*c<<endl; +#endif + 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<<endl; +#endif +} +void Blocks::removeBlock(Block *doomed) { + 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); + m_blocks.push_back(l); + m_blocks.push_back(r); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Split left: "<<*l<<endl; + f<<"Split right: "<<*r<<endl; +#endif + 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); + + 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; + size_t length = m_blocks.size(); + for (size_t i = 0; i < length; ++i) + { + c += m_blocks[i]->cost(); + } + return c; +} + +} diff --git a/src/3rdparty/adaptagrams/libvpsc/blocks.h b/src/3rdparty/adaptagrams/libvpsc/blocks.h new file mode 100644 index 0000000..a3613db --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/blocks.h @@ -0,0 +1,96 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2012 Monash University + * + * 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 + * + */ + +#ifndef VPSC_BLOCKS_H +#define VPSC_BLOCKS_H + +#ifdef LIBVPSC_LOGGING +#define LOGFILE "libvpsc.log" +#endif + +#include <list> +#include <vector> + +// size_t is strangely not defined on some older MinGW GCC versions. +#include <cstddef> + +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 + */ +class Blocks +{ +public: + Blocks(std::vector<Variable*> const &vs); + ~Blocks(void); + void mergeLeft(Block *r); + void mergeRight(Block *l); + void split(Block *b, Block *&l, Block *&r, Constraint *c); + std::list<Variable*> *totalOrder(); + void cleanup(); + double cost(); + + size_t size() const; + Block *at(size_t index) const; + void insert(Block *block); + + long blockTimeCtr; +private: + void dfsVisit(Variable *v, std::list<Variable*> *order); + void removeBlock(Block *doomed); + + std::vector<Block*> m_blocks; + std::vector<Variable*> const &vs; + size_t nvs; +}; + +inline size_t Blocks::size() const +{ + return m_blocks.size(); +} + +inline Block *Blocks::at(size_t index) const +{ + return m_blocks[index]; +} + +inline void Blocks::insert(Block *block) +{ + m_blocks.push_back(block); +} + +} +#endif // VPSC_BLOCKS_H diff --git a/src/3rdparty/adaptagrams/libvpsc/cbuffer.cpp b/src/3rdparty/adaptagrams/libvpsc/cbuffer.cpp new file mode 100644 index 0000000..9428922 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/cbuffer.cpp @@ -0,0 +1,95 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 + * +*/ + +#include <cfloat> + +#include "libvpsc/cbuffer.h" +#include "libvpsc/constraint.h" +#include "libvpsc/assertions.h" + +namespace vpsc { + static const double ZERO_UPPERBOUND=-0.0000001; + void CBuffer::load() { + size=0; + double buffMaxSlack=-DBL_MAX; + unsigned buffMaxSlackPos=0; + for(Constraints::iterator i=master_list.begin(); + i!=master_list.end();++i) { + Constraint *c=*i; + double slack = c->slack(); + if(c->equality||slack<ZERO_UPPERBOUND) { + if(size<maxsize) { + // make sure buffer is full + buffer[size]=c; + if(slack>buffMaxSlack) { + buffMaxSlack=slack; + buffMaxSlackPos=size; + } + size++; + } else { + // if c is more violated than the least violated + // constraint in the buffer then replace it + buffer[buffMaxSlackPos]=c; + // need to search the buffer for the new least + // violated constraint + buffMaxSlack=-DBL_MAX; + for(unsigned i=0;i<size;i++) { + c=buffer[i]; + if(!c->equality&&buffMaxSlack < c->slack()) { + buffMaxSlack = slack; + buffMaxSlackPos = i; + } + } + } + } + } + } + Constraint* CBuffer::mostViolated() { + Constraint* v=nullptr; + while(true) { + if(size==0) { + load(); + if(size==0) break; + } + double minSlack=DBL_MAX; + int i,deletePos=-1; + for(i=0;i<(int)size;i++) { + Constraint *c=buffer[i]; + double slack = c->slack(); + if(!(c->equality||slack < ZERO_UPPERBOUND)) { + COLA_ASSERT(size>0); + buffer[i--]=buffer[--size]; + } else if(c->equality||slack < minSlack) { + v=c; + deletePos=i; + minSlack=slack; + } + } + if(deletePos>=0) { + COLA_ASSERT(size>0); + buffer[deletePos]=buffer[--size]; + break; + } + } + return v; + } +} diff --git a/src/3rdparty/adaptagrams/libvpsc/cbuffer.h b/src/3rdparty/adaptagrams/libvpsc/cbuffer.h new file mode 100644 index 0000000..9cf302c --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/cbuffer.h @@ -0,0 +1,49 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 + * + */ +#ifndef VPSC_CBUFFER_H +#define VPSC_CBUFFER_H + +#include <vector> + +namespace vpsc { + class Constraint; + class CBuffer { + public: + CBuffer(std::vector<Constraint*>& l, + const unsigned maxsize=5) + : master_list(l), maxsize(maxsize), size(0) { + buffer.resize(maxsize); + load(); + } + void reset() { size=0; } + void load(); + Constraint* mostViolated(); + private: + std::vector<Constraint*>& master_list; + std::vector<Constraint*> buffer; + const unsigned maxsize; + unsigned size; + }; +} + +#endif // VPSC_CBUFFER_H + diff --git a/src/3rdparty/adaptagrams/libvpsc/constraint.cpp b/src/3rdparty/adaptagrams/libvpsc/constraint.cpp new file mode 100644 index 0000000..96581c7 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/constraint.cpp @@ -0,0 +1,218 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 +*/ + + +#include <map> +#include <list> +#include <sstream> +#include <cassert> +#include <cfloat> +#include <cmath> + + +#include "libvpsc/constraint.h" +#include "libvpsc/variable.h" + +namespace vpsc { +Constraint::Constraint(Variable *left, Variable *right, double gap, bool equality) +: left(left), + right(right), + gap(gap), + timeStamp(0), + active(false), + equality(equality), + unsatisfiable(false), + needsScaling(true), + creator(nullptr) +{ + // In hindsight I think it's probably better to build the constraint DAG + // (by creating variable in/out lists) when needed, rather than in advance + //left->out.push_back(this); + //right->in.push_back(this); +} +Constraint::~Constraint() { + // see constructor: the following is just way too slow. + // Better to create a + // new DAG on demand than maintain the lists dynamically. + //Constraints::iterator i; + //for(i=left->out.begin(); i!=left->out.end(); i++) { + //if(*i==this) break; + //} + //left->out.erase(i); + //for(i=right->in.begin(); i!=right->in.end(); i++) { + //if(*i==this) break; + //} + //right->in.erase(i); +} +std::ostream& operator <<(std::ostream &os, const Constraint &c) +{ + const char *type = c.equality ? "=" : "<="; + std::ostringstream lscale, rscale; + if (c.left->scale != 1) + { + lscale << c.left->scale << "*"; + } + if (c.right->scale != 1) + { + rscale << c.right->scale << "*"; + } + os << lscale.str() << *c.left << "+" << c.gap << type << + rscale.str() << *c.right; + if (c.left->block && c.right->block) + { + os << "(" << c.slack() << ")" << (c.active ? "-active" : "") << + "(lm=" << c.lm << ")"; + } + else + { + os << "(vars have no position)"; + } + return os; +} +#include "libvpsc/block.h" +bool CompareConstraints::operator() ( + Constraint *const &l, Constraint *const &r +) const { + double const sl = + l->left->block->timeStamp > l->timeStamp + ||l->left->block==l->right->block + ?-DBL_MAX:l->slack(); + double const sr = + r->left->block->timeStamp > r->timeStamp + ||r->left->block==r->right->block + ?-DBL_MAX:r->slack(); + if(sl==sr) { + // arbitrary choice based on id + if(l->left->id==r->left->id) { + if(l->right->id<r->right->id) return true; + return false; + } + if(l->left->id<r->left->id) return true; + return false; + } + return sl < sr; +} + + +typedef std::list<std::map<Variable *, double> > VarOffsetMapList; + +class EqualityConstraintSet +{ + public: + EqualityConstraintSet(Variables vs) + { + for (size_t i = 0; i < vs.size(); ++i) + { + std::map<Variable *, double> varSet; + varSet[vs[i]] = 0; + variableGroups.push_back(varSet); + } + } + bool isRedundant(Variable *lhs, Variable *rhs, double sep) + { + VarOffsetMapList::iterator lhsSet = setForVar(lhs); + VarOffsetMapList::iterator rhsSet = setForVar(rhs); + COLA_ASSERT(lhsSet != variableGroups.end()); + COLA_ASSERT(rhsSet != variableGroups.end()); + if (lhsSet == rhsSet) + { + // Check if this is a redundant constraint. + if (fabs(((*lhsSet)[lhs] + sep) - (*rhsSet)[rhs]) < 0.0001) + { + // If so, return true. + return true; + } + } + return false; + } + void mergeSets(Variable *lhs, Variable *rhs, double sep) + { + VarOffsetMapList::iterator lhsSet = setForVar(lhs); + VarOffsetMapList::iterator rhsSet = setForVar(rhs); + if (lhsSet == rhsSet) + { + return; + } + + double rhsOldOffset = (*rhsSet)[rhs]; + double rhsNewOffset = (*lhsSet)[lhs] + sep; + double offset = rhsNewOffset - rhsOldOffset; + + // Update offsets + for (std::map<Variable *, double>::iterator it = rhsSet->begin(); + it != rhsSet->end(); ++it) + { + it->second += offset; + } + + // Merge rhsSet into lhsSet + lhsSet->insert(rhsSet->begin(), rhsSet->end()); + variableGroups.erase(rhsSet); + } + + private: + VarOffsetMapList::iterator setForVar(Variable *var) + { + for (VarOffsetMapList::iterator it = variableGroups.begin(); + it != variableGroups.end(); ++it) + { + if (it->find(var) != it->end()) + { + return it; + } + } + return variableGroups.end(); + } + + VarOffsetMapList variableGroups; +}; + +Constraints constraintsRemovingRedundantEqualities(const Variables& vars, + const Constraints& constraints) +{ + EqualityConstraintSet equalitySets(vars); + Constraints cs = Constraints(constraints.size()); + int csSize = 0; + + for (unsigned i = 0; i < constraints.size(); ++i) + { + Constraint *c = constraints[i]; + if (c->equality) + { + if (!equalitySets.isRedundant(c->left, c->right, c->gap)) + { + // Only add non-redundant equalities + equalitySets.mergeSets(c->left, c->right, c->gap); + cs[csSize++] = c; + } + } + else + { + // Add all non-equalities + cs[csSize++] = c; + } + } + cs.resize(csSize); + return cs; +} + + +} diff --git a/src/3rdparty/adaptagrams/libvpsc/constraint.h b/src/3rdparty/adaptagrams/libvpsc/constraint.h new file mode 100644 index 0000000..271a2cf --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/constraint.h @@ -0,0 +1,139 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 +*/ + + +#ifndef VPSC_CONSTRAINT_H +#define VPSC_CONSTRAINT_H + +// cmath needs ::strcpy_s under MinGW so include cstring. +#include <cstring> + +#include <cfloat> +#include <iostream> +#include <vector> +#include <sstream> + +#include "libvpsc/variable.h" + +namespace vpsc { + +class Variable; +typedef std::vector<Variable *> Variables; + +//! @brief A constraint determines a minimum or exact spacing required between +//! two Variable objects. +//! +class Constraint +{ + friend std::ostream& operator <<(std::ostream &os,const Constraint &c); +public: + //! @brief Constructs a minimum or exact spacing constraint between two + //! Variable objects. + //! + //! (left + gap < right) or (left + gap == right) + //! + //! @param[in] left The left Variable. + //! @param[in] right The right Variable. + //! @param[in] gap The minimum or exact distance to separate the + //! variables by. + //! @param[in] equality Whether the separation is an exact distance or + //! not. The default is false. + Constraint(Variable *left, Variable *right, double gap, + bool equality = false); + ~Constraint(); + + /** + * @brief Returns a textual description of the constraint. + * + * @return A string describing the constraint. + */ + std::string toString(void) const + { + std::stringstream stream; + stream << "Constraint: var(" << left->id << ") "; + if (gap < 0) + { + stream << "- " << -gap << " "; + } + else + { + stream << "+ " << gap << " "; + } + stream << ((equality) ? "==" : "<="); + stream << " var(" << right->id << ") "; + return stream.str(); + } + + inline double slack(void) const + { + if (unsatisfiable) + { + return DBL_MAX; + } + if (needsScaling) + { + return right->scale * right->position() - gap - + left->scale * left->position(); + } + COLA_ASSERT(left->scale == 1); + COLA_ASSERT(right->scale == 1); + return right->unscaledPosition() - gap - left->unscaledPosition(); + } + + //! @brief The left Variable. + Variable *left; + //! @brief The right Variable. + Variable *right; + //! @brief The minimum or exact distance to separate the variables by. + double gap; + double lm; + long timeStamp; + bool active; + //! @brief Whether the separation is an exact distance or not. + const bool equality; + //! @brief Denote whether this constraint was unsatisifable (once the VPSC + //! instance has been solved or satisfied). + bool unsatisfiable; + bool needsScaling; + void *creator; +}; + +class CompareConstraints { +public: + bool operator() (Constraint *const &l, Constraint *const &r) const; +}; + +//! @brief A vector of pointers to Constraint objects. +typedef std::vector<Constraint*> Constraints; + +/** @brief Given a set of variables and constraints, returns a modified set + * of constraints with all redundant equality constraints removed. + * + * VPSC doesn't work well with redundant equality constraints, usually showing + * them as unsatisfiable. This function looks for cycles of equality + * constraints and removes the redundant ones. + */ +extern Constraints constraintsRemovingRedundantEqualities( + const Variables& vars, const Constraints& constraints); + +} + +#endif // VPSC_CONSTRAINT_H diff --git a/src/3rdparty/adaptagrams/libvpsc/doc/description.doc b/src/3rdparty/adaptagrams/libvpsc/doc/description.doc new file mode 100644 index 0000000..ee66b35 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/doc/description.doc @@ -0,0 +1,36 @@ +/*! + +\if LIBVPSC_DOC +@mainpage libvpsc: Variable Placement with Separation Constraints solver +\endif +\if ADAPTAGRAMS_DOC +@page libvpsc libvpsc — Overview +\endif + + +libvpsc is a cross-platform C++ library for solving for the Variable Placement with Separation Constraints problem. This is a quadratic programming problem in which the squared differences between a placement vector and some ideal placement are minimised subject to a set of separation constraints. This is very useful in a number of layout problems. + +libvpsc is part of the +<a href="http://www.adaptagrams.org/">Adaptagrams project</a>. +There are no official releases yet, though the code is stable and +available from the Adaptagrams +<a href="https://github.com/mjwybrow/adaptagrams">GitHub +repository</a>. + +The API is documented using Doxygen. The documentation you are currently +reading can be obtained by running doxygen in the cola directory. + +libcola is written and maintained by +<a href="http://users.monash.edu/~mwybrow/">Michael Wybrow</a> and +<a href="http://ialab.it.monash.edu/~dwyer/">Tim Dwyer</a>, +members of <a href="http://ialab.it.monash.edu/">Immersive Analytics Lab</a> at Monash University, Australia. + +The algorithms used for VPSC are described in the following papers. If you use libcola, please cite the relevant paper. +- Tim Dwyer, Kim Marriott, and Peter J. Stuckey. Fast node overlap removal.\n + In Proceedings 13th International Symposium on Graph Drawing (GD '05),\n + volume 3843 of LNCS, pages 153-164. Springer, 2006. + + +*/ + + diff --git a/src/3rdparty/adaptagrams/libvpsc/exceptions.h b/src/3rdparty/adaptagrams/libvpsc/exceptions.h new file mode 100644 index 0000000..5f66afe --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/exceptions.h @@ -0,0 +1,36 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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. + * +*/ + +#ifndef VPSC_EXCEPTIONS_H +#define VPSC_EXCEPTIONS_H + +#include <vector> +namespace vpsc { +class Constraint; +struct UnsatisfiableException { + std::vector<Constraint*> path; +}; +struct UnsatisfiedConstraint { + UnsatisfiedConstraint(Constraint& c):c(c) {} + Constraint& c; +}; +} // namespace vpsc + +#endif // VPSC_EXCEPTIONS_H diff --git a/src/3rdparty/adaptagrams/libvpsc/libvpsc.pc.in b/src/3rdparty/adaptagrams/libvpsc/libvpsc.pc.in new file mode 100644 index 0000000..9b6ff52 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/libvpsc.pc.in @@ -0,0 +1,12 @@ +prefix=@prefix@ +exec_prefix=@exec_prefix@ +libdir=@libdir@ +includedir=@includedir@ + +Name: libvpsc +Description: A solver for the Variable Placement with Separation Constraints problem. +URL: http://www.adaptagrams.org/ +Version: @VERSION@ +Requires: +Libs: -L${libdir} -lvpsc +Cflags: -I${includedir}/libvpsc
\ No newline at end of file diff --git a/src/3rdparty/adaptagrams/libvpsc/linesegment.h b/src/3rdparty/adaptagrams/libvpsc/linesegment.h new file mode 100644 index 0000000..caca3a2 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/linesegment.h @@ -0,0 +1,138 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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. + * +*/ + +//////////////////////////////////////////////////////////////////////////////// +// +// 2D Line Segment Intersection example +// Implementation of the theory provided by Paul Bourke +// +// Written by Damian Coventry +// Tuesday, 9 January 2007 +// +//////////////////////////////////////////////////////////////////////////////// + +#ifndef VPSC_LINESEGMENT_H +#define VPSC_LINESEGMENT_H + +namespace linesegment { +class Vector +{ +public: + double x_, y_; + + Vector(double f = 0.0f) + : x_(f), y_(f) {} + + Vector(double x, double y) + : x_(x), y_(y) {} +}; + +class LineSegment +{ +public: + Vector begin_; + Vector end_; + + LineSegment(const Vector& begin, const Vector& end) + : begin_(begin), end_(end) {} + + enum IntersectResult { PARALLEL, COINCIDENT, NOT_INTERSECTING, INTERSECTING }; + + IntersectResult Intersect(const LineSegment& other_line, Vector& intersection) + { + double dx1=end_.x_ - begin_.x_; + double dy1=end_.y_ - begin_.y_; + double dx2=other_line.end_.x_ - other_line.begin_.x_; + double dy2=other_line.end_.y_ - other_line.begin_.y_; + + double denom = dy2 * dx1 - dy1 * dx2; + + double nume_a = dx2 * (begin_.y_ - other_line.begin_.y_) - + dy2 * (begin_.x_ - other_line.begin_.x_); + + double nume_b = dx1 * (begin_.y_ - other_line.begin_.y_) - + dy1 * (begin_.x_ - other_line.begin_.x_); + + if(denom == 0.0f) + { + if(nume_a == 0.0f && nume_b == 0.0f) + { + return COINCIDENT; + } + return PARALLEL; + } + + double ua = nume_a / denom; + double ub = nume_b / denom; + + if(ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) + { + // Get the intersection point. + intersection.x_ = begin_.x_ + ua*dx1; + intersection.y_ = begin_.y_ + ua*dy1; + + return INTERSECTING; + } + + return NOT_INTERSECTING; + } +}; + +void DoLineSegmentIntersection(const Vector& p0, const Vector& p1, const Vector& p2, const Vector& p3) +{ + LineSegment linesegment0(p0, p1); + LineSegment linesegment1(p2, p3); + + Vector intersection; + + std::cout << "Line Segment 0: (" << p0.x_ << ", " << p0.y_ << ") to (" << p1.x_ << ", " << p1.y_ << ")\n" + << "Line Segment 1: (" << p2.x_ << ", " << p2.y_ << ") to (" << p3.x_ << ", " << p3.y_ << ")\n"; + + switch(linesegment0.Intersect(linesegment1, intersection)) + { + case LineSegment::PARALLEL: + std::cout << "The lines are parallel\n\n"; + break; + case LineSegment::COINCIDENT: + std::cout << "The lines are coincident\n\n"; + break; + case LineSegment::NOT_INTERSECTING: + std::cout << "The lines do not intersect\n\n"; + break; + case LineSegment::INTERSECTING: + std::cout << "The lines intersect at (" << intersection.x_ << ", " << intersection.y_ << ")\n\n"; + break; + } +} + +int test() +{ + DoLineSegmentIntersection(Vector(0.0f, 0.0f), Vector(5.0f, 5.0f), Vector(5.0f, 0.0f), Vector(0.0f, 5.0f)); + DoLineSegmentIntersection(Vector(1.0f, 3.0f), Vector(9.0f, 3.0f), Vector(0.0f, 1.0f), Vector(2.0f, 1.0f)); + DoLineSegmentIntersection(Vector(1.0f, 5.0f), Vector(6.0f, 8.0f), Vector(0.5f, 3.0f), Vector(6.0f, 4.0f)); + DoLineSegmentIntersection(Vector(1.0f, 1.0f), Vector(3.0f, 8.0f), Vector(0.5f, 2.0f), Vector(4.0f, 7.0f)); + DoLineSegmentIntersection(Vector(1.0f, 2.0f), Vector(3.0f, 6.0f), Vector(2.0f, 4.0f), Vector(4.0f, 8.0f)); + DoLineSegmentIntersection(Vector(3.5f, 9.0f), Vector(3.5f, 0.5f), Vector(3.0f, 1.0f), Vector(9.0f, 1.0f)); + DoLineSegmentIntersection(Vector(2.0f, 3.0f), Vector(7.0f, 9.0f), Vector(1.0f, 2.0f), Vector(5.0f, 7.0f)); + return 0; +} +} // namespace linesegment + +#endif // VPSC_LINESEGMENT_H diff --git a/src/3rdparty/adaptagrams/libvpsc/pairing_heap.h b/src/3rdparty/adaptagrams/libvpsc/pairing_heap.h new file mode 100644 index 0000000..479519a --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/pairing_heap.h @@ -0,0 +1,394 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005 Mark Allen Weiss + * Copyright (C) 2005-2008 Monash University + * + * ---------------------------------------------------------------------------- + * 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! + * ---------------------------------------------------------------------------- + * + * 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): Mark Allen Weiss + * Tim Dwyer +*/ + +#ifndef VPSC_PAIRING_HEAP_H +#define VPSC_PAIRING_HEAP_H + +#include <cstdlib> +#include <fstream> +#include <vector> +#include <list> + +#include "libvpsc/assertions.h" + +class Underflow { }; + +// Pairing heap class +// +// CONSTRUCTION: with no parameters +// +// ******************PUBLIC OPERATIONS********************* +// PairNode & insert( x ) --> Insert x +// deleteMin( minItem ) --> Remove (and optionally return) smallest item +// T findMin( ) --> Return smallest item +// bool isEmpty( ) --> Return true if empty; else false +// void makeEmpty( ) --> Remove all items +// void decreaseKey( PairNode p, newVal ) +// --> Decrease value in node p +// ******************ERRORS******************************** +// Throws Underflow as warranted + + +template <class T> +struct PairNode +{ + T element; + PairNode *leftChild; + PairNode *nextSibling; + PairNode *prev; + + PairNode( const T & theElement ) : + element( theElement ), + leftChild(nullptr), nextSibling(nullptr), prev(nullptr) + { } +}; + +template <class T, class TCompare> +class PairingHeap; + +template <class T,class TCompare> +std::ostream& operator <<(std::ostream &os, const PairingHeap<T,TCompare> &b); + +template <class T, class TCompare = std::less<T> > +class PairingHeap +{ +#ifndef SWIG + friend std::ostream& operator<< <T,TCompare> (std::ostream &os, const PairingHeap<T,TCompare> &b); +#endif +public: + PairingHeap() : root(nullptr), counter(0), siblingsTreeArray(5) { } + PairingHeap(const PairingHeap & rhs) { + // uses operator= to make deep copy + *this = rhs; + } + ~PairingHeap() { makeEmpty(); } + const PairingHeap & operator=( const PairingHeap & rhs ); + bool isEmpty() const { return root == nullptr; } + unsigned size() const { return counter; } + PairNode<T> *insert( const T & x ); + const T & findMin( ) const; + void deleteMin( ); + const T extractMin( ) { + T v = findMin(); + deleteMin(); + return v; + } + void makeEmpty() { + reclaimMemory(root); + root = nullptr; + counter = 0; + } + void decreaseKey( PairNode<T> *p, const T & newVal ); + void merge( PairingHeap<T,TCompare> *rhs ); +protected: + // Destructively gets the root for merging into another heap. + PairNode<T> * removeRootForMerge(unsigned& size) { + PairNode<T> *r=root; + root=nullptr; + size=counter; + counter=0; + return r; + } + TCompare lessThan; +private: + PairNode<T> *root; + unsigned counter; + + // Used by PairingHeap::combineSiblings(). We keep this as member + // variable to save some vector resize operations during subsequent uses. + std::vector<PairNode<T> *> siblingsTreeArray; + + void reclaimMemory( PairNode<T> *t ) const; + void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const; + PairNode<T> * combineSiblings( PairNode<T> *firstSibling ); + PairNode<T> * clone( PairNode<T> * t ) const; +}; + + +/** +* Insert item x into the priority queue, maintaining heap order. +* Return a pointer to the node containing the new item. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::insert( const T & x ) +{ + PairNode<T> *newNode = new PairNode<T>( x ); + + if( root == nullptr ) + root = newNode; + else + compareAndLink( root, newNode ); + counter++; + return newNode; +} + +/** +* Find the smallest item in the priority queue. +* Return the smallest item, or throw Underflow if empty. +*/ +template <class T,class TCompare> +const T & PairingHeap<T,TCompare>::findMin( ) const +{ + if( isEmpty( ) ) + throw Underflow( ); + return root->element; +} +/** + * Remove the smallest item from the priority queue. + * Throws Underflow if empty. + */ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::deleteMin( ) +{ + if( isEmpty( ) ) + throw Underflow( ); + + PairNode<T> *oldRoot = root; + + if( root->leftChild == nullptr ) + root = nullptr; + else + root = combineSiblings( root->leftChild ); + COLA_ASSERT(counter); + counter--; + delete oldRoot; +} + +/** +* Deep copy. +*/ +template <class T,class TCompare> +const PairingHeap<T,TCompare> & +PairingHeap<T,TCompare>::operator=( const PairingHeap<T,TCompare> & rhs ) +{ + if( this != &rhs ) + { + makeEmpty( ); + root = clone( rhs.root ); + counter = rhs.size(); + } + + return *this; +} + +/** +* Internal method to make the tree empty. +* WARNING: This is prone to running out of stack space. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::reclaimMemory( PairNode<T> * t ) const +{ + if( t != nullptr ) + { + reclaimMemory( t->leftChild ); + reclaimMemory( t->nextSibling ); + delete t; + } +} + +/** +* Change the value of the item stored in the pairing heap. +* Does nothing if newVal is larger than currently stored value. +* p points to a node returned by insert. +* newVal is the new value, which must be smaller +* than the currently stored value. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::decreaseKey( PairNode<T> *p, + const T & newVal ) +{ + COLA_ASSERT(!lessThan(p->element,newVal)); // newVal cannot be bigger + p->element = newVal; + if( p != root ) + { + if( p->nextSibling != nullptr ) + p->nextSibling->prev = p->prev; + if( p->prev->leftChild == p ) + p->prev->leftChild = p->nextSibling; + else + p->prev->nextSibling = p->nextSibling; + + p->nextSibling = nullptr; + compareAndLink( root, p ); + } +} + +/** + * Merges rhs into this pairing heap by inserting its root + */ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::merge( PairingHeap<T,TCompare> *rhs ) +{ + unsigned rhsSize; + PairNode<T> *broot=rhs->removeRootForMerge(rhsSize); + if (root == nullptr) { + root = broot; + } else { + compareAndLink(root, broot); + } + counter+=rhsSize; +} + +/** +* Internal method that is the basic operation to maintain order. +* Links first and second together to satisfy heap order. +* first is root of tree 1, which may not be nullptr. +* first->nextSibling MUST be nullptr on entry. +* second is root of tree 2, which may be nullptr. +* first becomes the result of the tree merge. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>:: +compareAndLink( PairNode<T> * & first, + PairNode<T> *second ) const +{ + if( second == nullptr ) + return; + + if( lessThan(second->element,first->element) ) + { + // Attach first as leftmost child of second + second->prev = first->prev; + first->prev = second; + first->nextSibling = second->leftChild; + if( first->nextSibling != nullptr ) + first->nextSibling->prev = first; + second->leftChild = first; + first = second; + } + else + { + // Attach second as leftmost child of first + second->prev = first; + first->nextSibling = second->nextSibling; + if( first->nextSibling != nullptr ) + first->nextSibling->prev = first; + second->nextSibling = first->leftChild; + if( second->nextSibling != nullptr ) + second->nextSibling->prev = second; + first->leftChild = second; + } +} + +/** +* Internal method that implements two-pass merging. +* firstSibling the root of the conglomerate; +* assumed not nullptr. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::combineSiblings( PairNode<T> *firstSibling ) +{ + if( firstSibling->nextSibling == nullptr ) + return firstSibling; + + // Store the subtrees in an array + int numSiblings = 0; + for( ; firstSibling != nullptr; numSiblings++ ) + { + if( numSiblings == (int)siblingsTreeArray.size( ) ) + siblingsTreeArray.resize( numSiblings * 2 ); + siblingsTreeArray[ numSiblings ] = firstSibling; + firstSibling->prev->nextSibling = nullptr; // break links + firstSibling = firstSibling->nextSibling; + } + if( numSiblings == (int)siblingsTreeArray.size( ) ) + siblingsTreeArray.resize( numSiblings + 1 ); + siblingsTreeArray[ numSiblings ] = nullptr; + + // Combine subtrees two at a time, going left to right + int i = 0; + for( ; i + 1 < numSiblings; i += 2 ) + compareAndLink( siblingsTreeArray[ i ], siblingsTreeArray[ i + 1 ] ); + + int j = i - 2; + + // j has the result of last compareAndLink. + // If an odd number of trees, get the last one. + if( j == numSiblings - 3 ) + compareAndLink( siblingsTreeArray[ j ], siblingsTreeArray[ j + 2 ] ); + + // Now go right to left, merging last tree with + // next to last. The result becomes the new last. + for( ; j >= 2; j -= 2 ) + compareAndLink( siblingsTreeArray[ j - 2 ], siblingsTreeArray[ j ] ); + return siblingsTreeArray[ 0 ]; +} + +/** +* Internal method to clone subtree. +* WARNING: This is prone to running out of stack space. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::clone( PairNode<T> * t ) const +{ + if( t == nullptr ) + return nullptr; + else + { + PairNode<T> *p = new PairNode<T>( t->element ); + if( ( p->leftChild = clone( t->leftChild ) ) != nullptr ) + p->leftChild->prev = p; + if( ( p->nextSibling = clone( t->nextSibling ) ) != nullptr ) + p->nextSibling->prev = p; + return p; + } +} + +template <class T,class TCompare> +std::ostream& operator <<(std::ostream &os, const PairingHeap<T,TCompare> &b) +{ + os<<"Heap:"; + if (b.root != nullptr) { + PairNode<T> *r = b.root; + std::list<PairNode<T>*> q; + q.push_back(r); + while (!q.empty()) { + r = q.front(); + q.pop_front(); + if (r->leftChild != nullptr) { + os << *r->element << ">"; + PairNode<T> *c = r->leftChild; + while (c != nullptr) { + q.push_back(c); + os << "," << *c->element; + c = c->nextSibling; + } + os << "|"; + } + } + } + return os; +} + +#endif /* VPSC_PAIRING_HEAP_H */ diff --git a/src/3rdparty/adaptagrams/libvpsc/rectangle.cpp b/src/3rdparty/adaptagrams/libvpsc/rectangle.cpp new file mode 100644 index 0000000..6d80c34 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/rectangle.cpp @@ -0,0 +1,744 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 +*/ + +/* + * @brief Functions to automatically generate constraints for the + * rectangular node overlap removal problem. + * + */ + +#include <cmath> +#include <set> +#include <cstdlib> +#include <algorithm> +#include <cstdio> + +#include "libvpsc/assertions.h" +#include "libvpsc/solve_VPSC.h" +#include "libvpsc/rectangle.h" +#include "libvpsc/constraint.h" +#include "libvpsc/variable.h" + +using std::set; +using std::vector; + +namespace vpsc { + +double Rectangle::xBorder = 0; +double Rectangle::yBorder = 0; + +std::ostream& operator <<(std::ostream &os, const Rectangle &r) { + os << "Hue[0.17],Rectangle[{"<<r.getMinX()<<","<<r.getMinY()<<"},{"<<r.getMaxX()<<","<<r.getMaxY()<<"}]"; + return os; +} + +Rectangle::Rectangle(double x, double X, double y, double Y,bool allowOverlap) + : minX(x), + maxX(X), + minY(y), + maxY(Y), + overlap(allowOverlap) +{ + COLA_ASSERT(x<X); + COLA_ASSERT(y<Y); + COLA_ASSERT(getMinX()<getMaxX()); + COLA_ASSERT(getMinY()<getMaxY()); +} + +Rectangle::Rectangle() + : minX(1), + maxX(-1), + minY(1), + maxY(-1), + overlap(false) +{ + // Creates an invalid Rectangle +} + +bool Rectangle::isValid(void) const +{ + return ((minX <= maxX) && (minY <= maxY)); +} + +Rectangle Rectangle::unionWith(const Rectangle& rhs) const +{ + if (!isValid()) + { + return Rectangle(rhs); + } + else if (!rhs.isValid()) + { + return Rectangle(*this); + } + + double newMaxY = std::max(rhs.getMaxY(),maxY); + double newMinY = std::min(rhs.getMinY(),minY); + double newMinX = std::min(rhs.getMinX(),minX); + double newMaxX = std::max(rhs.getMaxX(),maxX); + + return Rectangle(newMinX, newMaxX, newMinY, newMaxY); +} + +void Rectangle::reset(unsigned d, double x, double X) { + if(d==0) { + minX=x; + maxX=X; + } else { + minY=x; + maxY=X; + } +} + +struct Node; +struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; }; + +typedef set<Node*,CmpNodePos> NodeSet; + +struct Node { + Variable *v; + Rectangle *r; + double pos; + Node *firstAbove, *firstBelow; + NodeSet *leftNeighbours, *rightNeighbours; + Node(Variable *v, Rectangle *r, double p) + : v(v),r(r),pos(p), + firstAbove(nullptr), firstBelow(nullptr), + leftNeighbours(nullptr), rightNeighbours(nullptr) + + { + COLA_ASSERT(r->width()<1e40); + } + ~Node() { + delete leftNeighbours; + delete rightNeighbours; + } + void addLeftNeighbour(Node *u) { + COLA_ASSERT(leftNeighbours!=nullptr); + leftNeighbours->insert(u); + } + void addRightNeighbour(Node *u) { + COLA_ASSERT(rightNeighbours!=nullptr); + rightNeighbours->insert(u); + } + void setNeighbours(NodeSet *left, NodeSet *right) { + leftNeighbours=left; + rightNeighbours=right; + for(NodeSet::iterator i=left->begin();i!=left->end();++i) { + Node *v=*(i); + v->addRightNeighbour(this); + } + for(NodeSet::iterator i=right->begin();i!=right->end();++i) { + Node *v=*(i); + v->addLeftNeighbour(this); + } + } +}; +bool CmpNodePos::operator() (const Node* u, const Node* v) const { + COLA_ASSERT(!std::isnan(u->pos)); + COLA_ASSERT(!std::isnan(v->pos)); + if (u->pos < v->pos) { + return true; + } + if (v->pos < u->pos) { + return false; + } + return u < v; +} + +NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) { + NodeSet *leftv = new NodeSet; + NodeSet::iterator i=scanline.find(v); + while(i!=scanline.begin()) { + Node *u=*(--i); + if(u->r->overlapX(v->r)<=0) { + leftv->insert(u); + return leftv; + } + if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) { + leftv->insert(u); + } + } + return leftv; +} +NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) { + NodeSet *rightv = new NodeSet; + NodeSet::iterator i=scanline.find(v); + for(++i;i!=scanline.end(); ++i) { + Node *u=*(i); + if(u->r->overlapX(v->r)<=0) { + rightv->insert(u); + return rightv; + } + if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) { + rightv->insert(u); + } + } + return rightv; +} + +typedef enum {Open, Close} EventType; +struct Event { + EventType type; + Node *v; + double pos; + Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {}; +}; +int compare_events(const void *a, const void *b) { + Event *ea=*(Event**)a; + Event *eb=*(Event**)b; + if(ea->pos==eb->pos) { + // when comparing opening and closing + // open must come first + if(ea->type==Open) return -1; + return 1; + } else if(ea->pos > eb->pos) { + return 1; + } else if(ea->pos < eb->pos) { + return -1; + } else if(std::isnan(ea->pos) != std::isnan(ea->pos)) { + /* See comment in CmpNodePos. */ + return ( std::isnan(ea->pos) + ? -1 + : 1 ); + } + return 0; +} + +/* + * Prepares constraints in order to apply VPSC horizontally. Assumes + * variables have already been created. + * useNeighbourLists determines whether or not a heuristic is used to + * deciding whether to resolve all overlap in the x pass, or leave some + * overlaps for the y pass. + */ +void generateXConstraints(const Rectangles& rs, const Variables& vars, + Constraints& cs, const bool useNeighbourLists) +{ + const unsigned n = rs.size(); + COLA_ASSERT(vars.size()>=n); + Event **events=new Event*[2*n]; + unsigned i,ctr=0; + for(i=0;i<n;i++) { + vars[i]->desiredPosition=rs[i]->getCentreX(); + Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX()); + events[ctr++]=new Event(Open,v,rs[i]->getMinY()); + events[ctr++]=new Event(Close,v,rs[i]->getMaxY()); + } + qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events ); + + NodeSet scanline; + for(i=0;i<2*n;i++) { + Event *e=events[i]; + Node *v=e->v; + if(e->type==Open) { + scanline.insert(v); + if(useNeighbourLists) { + v->setNeighbours( + getLeftNeighbours(scanline,v), + getRightNeighbours(scanline,v) + ); + } else { + NodeSet::iterator it=scanline.find(v); + if(it!=scanline.begin()) { + Node *u=*(--it); + v->firstAbove=u; + u->firstBelow=v; + } + it=scanline.find(v); + if(++it!=scanline.end()) { + Node *u=*it; + v->firstBelow=u; + u->firstAbove=v; + } + } + } else { + size_t result; + // Close event + if(useNeighbourLists) { + for(NodeSet::iterator i=v->leftNeighbours->begin(); + i!=v->leftNeighbours->end();i++ + ) { + Node *u=*i; + double sep = (v->r->width()+u->r->width())/2.0; + cs.push_back(new Constraint(u->v,v->v,sep)); + result=u->rightNeighbours->erase(v); + COLA_ASSERT(result==1); + } + + for(NodeSet::iterator i=v->rightNeighbours->begin(); + i!=v->rightNeighbours->end();i++ + ) { + Node *u=*i; + double sep = (v->r->width()+u->r->width())/2.0; + cs.push_back(new Constraint(v->v,u->v,sep)); + result=u->leftNeighbours->erase(v); + COLA_ASSERT(result==1); + } + } else { + Node *l=v->firstAbove, *r=v->firstBelow; + if(l!=nullptr) { + double sep = (v->r->width()+l->r->width())/2.0; + cs.push_back(new Constraint(l->v,v->v,sep)); + l->firstBelow=v->firstBelow; + } + if(r!=nullptr) { + double sep = (v->r->width()+r->r->width())/2.0; + cs.push_back(new Constraint(v->v,r->v,sep)); + r->firstAbove=v->firstAbove; + } + } + result=scanline.erase(v); + COLA_ASSERT(result==1); + delete v; + } + delete e; + } + COLA_ASSERT(scanline.size()==0); + delete [] events; +} + +/* + * Prepares constraints in order to apply VPSC vertically to remove ALL + * overlap. + */ +void generateYConstraints(const Rectangles& rs, const Variables& vars, + Constraints& cs) +{ + const unsigned n = rs.size(); + COLA_ASSERT(vars.size()>=n); + Event **events=new Event*[2*n]; + unsigned ctr=0; + Rectangles::const_iterator ri=rs.begin(), re=rs.end(); + Variables::const_iterator vi=vars.begin(), ve=vars.end(); + for(;ri!=re&&vi!=ve;++ri,++vi) { + Rectangle* r=*ri; + Variable* v=*vi; + v->desiredPosition=r->getCentreY(); + Node *node = new Node(v,r,r->getCentreY()); + COLA_ASSERT(r->getMinX()<r->getMaxX()); + events[ctr++]=new Event(Open,node,r->getMinX()); + events[ctr++]=new Event(Close,node,r->getMaxX()); + } + COLA_ASSERT(ri==rs.end()); + qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events ); + NodeSet scanline; +#ifndef NDEBUG + size_t deletes=0; +#endif + for(unsigned i=0;i<2*n;i++) { + Event *e=events[i]; + Node *v=e->v; + if(e->type==Open) { + scanline.insert(v); + NodeSet::iterator it=scanline.find(v); + if(it!=scanline.begin()) { + Node *u=*(--it); + v->firstAbove=u; + u->firstBelow=v; + } + it=scanline.find(v); + if(++it!=scanline.end()) { + Node *u=*it; + v->firstBelow=u; + u->firstAbove=v; + } + } else { + // Close event + Node *l=v->firstAbove, *r=v->firstBelow; + if(l!=nullptr) { + double sep = (v->r->height()+l->r->height())/2.0; + cs.push_back(new Constraint(l->v,v->v,sep)); + l->firstBelow=v->firstBelow; + } + if(r!=nullptr) { + double sep = (v->r->height()+r->r->height())/2.0; + cs.push_back(new Constraint(v->v,r->v,sep)); + r->firstAbove=v->firstAbove; + } +#ifndef NDEBUG + deletes++; + size_t erased= +#endif + scanline.erase(v); + COLA_ASSERT(erased==1); + delete v; + } + delete e; + } + COLA_ASSERT(scanline.size()==0); + COLA_ASSERT(deletes==n); + delete [] events; +} +#include "libvpsc/linesegment.h" +using namespace linesegment; +inline bool checkIntersection( + const LineSegment::IntersectResult result, + Vector const &intersection, + RectangleIntersections &ri, + bool &side, double &sideX, double &sideY) { + switch(result) { + case LineSegment::INTERSECTING: + ri.intersects=side=true; + sideX=intersection.x_; + sideY=intersection.y_; + case LineSegment::PARALLEL: + case LineSegment::NOT_INTERSECTING: + return true; + case LineSegment::COINCIDENT: + ri.intersects=ri.top=ri.bottom=ri.left=ri.right=false; + return false; + } + return false; +} +void Rectangle:: +lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const { + Vector intersection; + LineSegment l(Vector(x1,y1),Vector(x2,y2)); + LineSegment top(Vector(getMinX(),getMaxY()),Vector(getMaxX(),getMaxY())); + if(!checkIntersection( + l.Intersect(top,intersection),intersection, + ri,ri.top,ri.topX,ri.topY)) { + return; + } + LineSegment bottom(Vector(getMinX(),getMinY()),Vector(getMaxX(),getMinY())); + if(!checkIntersection( + l.Intersect(bottom,intersection),intersection, + ri,ri.bottom,ri.bottomX,ri.bottomY)) { + return; + } + LineSegment left(Vector(getMinX(),getMinY()),Vector(getMinX(),getMaxY())); + if(!checkIntersection( + l.Intersect(left,intersection),intersection, + ri,ri.left,ri.leftX,ri.leftY)) { + return; + } + LineSegment right(Vector(getMaxX(),getMinY()),Vector(getMaxX(),getMaxY())); + if(!checkIntersection( + l.Intersect(right,intersection),intersection, + ri,ri.right,ri.rightX,ri.rightY)) { + return; + } +} +static const double ERROR_MARGIN = 1e-4; +inline bool eq(double a, double b) { + return fabs(a-b)<ERROR_MARGIN; + //return a==b; +} +/* +bool Rectangle::inside(double x, double y) const { + return x>(minX+ERROR_MARGIN) && x<(maxX-ERROR_MARGIN) + && y>(minY+ERROR_MARGIN) && y<(maxY-ERROR_MARGIN); +} +*/ +// p1=(x1,y1),p2=(x2,y2) are points on the boundary. Puts the shortest +// path round the outside of the rectangle from p1 to p2 into xs, ys. +void Rectangle::routeAround(double x1, double y1, double x2, double y2, + std::vector<double> &xs, std::vector<double> &ys) { + COLA_ASSERT(eq(x1,minX) || eq(x1,maxX) || eq(y1,minY) || eq(y1,maxY)); + COLA_ASSERT(eq(x2,minX) || eq(x2,maxX) || eq(y2,minY) || eq(y2,maxY)); + xs.push_back(x1); + ys.push_back(y1); + bool top1=eq(y1,maxY), top2=eq(y2,maxY), + bottom1=eq(y1,minY), bottom2=eq(y2,minY); + bool left1=eq(x1,minX), left2=eq(x2,minX), + right1=eq(x1,maxX), right2=eq(x2,maxX); + bool leftright = (left1 && right2) || (right1 && left2); + bool topbottom = (top1 && bottom2) || (bottom1 && top2); + bool lefttop = (left1 && top2) || (top1 && left2); + bool righttop = (right1 && top2) || (top1 && right2); + bool leftbottom = (left1 && bottom2) || (bottom1 && left2); + bool rightbottom = (right1 && bottom2) || (bottom1 && right2); + if(lefttop) { + xs.push_back(minX); + ys.push_back(maxY); + } else if(righttop) { + xs.push_back(maxX); + ys.push_back(maxY); + } else if(leftbottom) { + xs.push_back(minX); + ys.push_back(minY); + } else if(rightbottom) { + xs.push_back(maxX); + ys.push_back(minY); + } else if(leftright) { + double midY = y1+(y2-y1)/2.0; + if(left1) { // left to right + if(midY<getCentreY()) { // route below + // bottom left + xs.push_back(getMinX()); + ys.push_back(getMinY()); + // bottom right + xs.push_back(getMaxX()); + ys.push_back(getMinY()); + } else { // route above + // top left + xs.push_back(getMinX()); + ys.push_back(getMaxY()); + // top right + xs.push_back(getMaxX()); + ys.push_back(getMaxY()); + } + } else { // right to left + if(midY<getCentreY()) { // route below + // bottom right + xs.push_back(getMaxX()); + ys.push_back(getMinY()); + // bottom left + xs.push_back(getMinX()); + ys.push_back(getMinY()); + } else { // route above + // top right + xs.push_back(getMaxX()); + ys.push_back(getMaxY()); + // top left + xs.push_back(getMinX()); + ys.push_back(getMaxY()); + } + } + } else if(topbottom) { + double midX = x1+(x2-x1)/2.0; + if(top1) { + if(midX<getCentreX()) { // route left + // top left + xs.push_back(getMinX()); + ys.push_back(getMaxY()); + // bottom left + xs.push_back(getMinX()); + ys.push_back(getMinY()); + } else { // route right + // top right + xs.push_back(getMaxX()); + ys.push_back(getMaxY()); + // bottom right + xs.push_back(getMaxX()); + ys.push_back(getMinY()); + } + } else { // bottom to top + if(midX<getCentreX()) { // route left + // bottom left + xs.push_back(getMinX()); + ys.push_back(getMinY()); + // top left + xs.push_back(getMinX()); + ys.push_back(getMaxY()); + } else { // route right + // bottom right + xs.push_back(getMaxX()); + ys.push_back(getMinY()); + // top right + xs.push_back(getMaxX()); + ys.push_back(getMaxY()); + } + } + } + xs.push_back(x2); + ys.push_back(y2); +} + +/* + * moves all the rectangles to remove all overlaps. Heuristic + * attempts to move by as little as possible. + * no overlaps guaranteed. + * @param rs the rectangles which will be moved to remove overlap + */ +void removeoverlaps(Rectangles& rs) { + const set<unsigned> fixed = set<unsigned>(); + removeoverlaps(rs,fixed); +} +#define ISNOTNAN(d) (d)==(d) +/* + * Moves rectangles to remove all overlaps. A heuristic + * attempts to move by as little as possible. The heuristic is + * that the overlaps are removed horizontally and then vertically, + * each pass being a quadratic program in which the total squared movement + * is minimised subject to non-overlap constraints. An optional third + * horizontal pass (in addition to the first horizontal pass and the second + * vertical pass) can be applied wherein the x-positions of rectangles are reset to their + * original positions and overlap removal repeated. This may avoid some + * unnecessary movement. + * @param rs the rectangles which will be moved to remove overlap + * @param fixed a set of indices to rectangles which should not be moved + * @param thirdPass optionally run the third horizontal pass described above. + */ +void removeoverlaps(Rectangles& rs, const set<unsigned>& fixed, bool thirdPass) { + const double xBorder=Rectangle::xBorder, yBorder=Rectangle::yBorder; + static const double EXTRA_GAP=1e-3; + static const size_t ARRAY_UNUSED=1; + unsigned n=rs.size(); + try { + // The extra gap avoids numerical imprecision problems + Rectangle::setXBorder(xBorder+EXTRA_GAP); + Rectangle::setYBorder(yBorder+EXTRA_GAP); + Variables vs(n); + Variables::iterator v; + unsigned i=0; + vector<double> initX(thirdPass?n:ARRAY_UNUSED); + for(v=vs.begin();v!=vs.end();++v,++i) { + double weight=1; + if(fixed.find(i)!=fixed.end()) { + weight=10000; + } + *v=new Variable(i,0,weight); + if(thirdPass) { + initX[i]=rs[i]->getCentreX(); + } + } + Constraints cs; + generateXConstraints(rs,vs,cs,true); + Solver vpsc_x(vs,cs); + vpsc_x.solve(); + Rectangles::iterator r=rs.begin(); + for(v=vs.begin();v!=vs.end();++v,++r) { + COLA_ASSERT(ISNOTNAN((*v)->finalPosition)); + (*r)->moveCentreX((*v)->finalPosition); + } + COLA_ASSERT(r==rs.end()); + for_each(cs.begin(),cs.end(),delete_object()); + cs.clear(); + // Removing the extra gap here ensures things that were moved to be + // adjacent to one another above are not considered overlapping + Rectangle::setXBorder(xBorder); + generateYConstraints(rs,vs,cs); + Solver vpsc_y(vs,cs); + vpsc_y.solve(); + r=rs.begin(); + for(v=vs.begin();v!=vs.end();++v,++r) { + COLA_ASSERT(ISNOTNAN((*v)->finalPosition)); + (*r)->moveCentreY((*v)->finalPosition); + } + for_each(cs.begin(),cs.end(),delete_object()); + cs.clear(); + Rectangle::setYBorder(yBorder); + if(thirdPass) { + // we reset x positions to their original values + // and apply a third pass horizontally so that + // rectangles which were moved unnecessarily in the + // first horizontal pass (i.e. their overlap + // was later resolved vertically) have an + // opportunity now to stay put. + Rectangle::setXBorder(xBorder+EXTRA_GAP); + r=rs.begin(); + for(v=vs.begin();v!=vs.end();++v,++r) { + (*r)->moveCentreX(initX[(*v)->id]); + } + generateXConstraints(rs,vs,cs,false); + Solver vpsc_x2(vs,cs); + vpsc_x2.solve(); + r=rs.begin(); + for(v=vs.begin();v!=vs.end();++v,++r) { + COLA_ASSERT(ISNOTNAN((*v)->finalPosition)); + (*r)->moveCentreX((*v)->finalPosition); + } + } + Rectangle::setXBorder(xBorder); + for_each(cs.begin(),cs.end(),delete_object()); + for_each(vs.begin(),vs.end(),delete_object()); + } catch (char *str) { + std::cerr<<str<<std::endl; + for(Rectangles::iterator r=rs.begin();r!=rs.end();++r) { + std::cerr << **r <<std::endl; + } + } + COLA_ASSERT(noRectangleOverlaps(rs)); +} + + +bool noRectangleOverlaps(const Rectangles& rs) +{ + Rectangle *u, *v; + Rectangles::const_iterator i=rs.begin(), j, e=rs.end(); + for (;i!=e;++i) + { + u=*i; + for (j=i+1;j!=e;++j) + { + v=*j; + if (u->overlapX(v)>0) + { + COLA_ASSERT(u->overlapY(v)==0); + } + } + } + return true; +} + +// checks if line segment is strictly overlapping. +// That is, if any point on the line is inside the rectangle. +bool Rectangle::overlaps(double x1, double y1, double x2, double y2) +{ + RectangleIntersections ri; + lineIntersections(x1,y1,x2,y2,ri); + if(ri.intersects) { + if(ri.countIntersections()==1) { + // special case when one point is touching + // the boundary of the rectangle but no part + // of the line is interior + if(!inside(x1,y1)&&!inside(x2,y2)) { + return false; + } + } + printf("Rectangle/Segment intersection (SVG):\n"); + printf("<svg style=\"stroke: black; fill: none;\">\n"); + printf("<polyline points=\"%f,%f %f,%f\" />\n",x1,y1,x2,y2); + printf("<rect x=\"%f\" y=\"%f\" width=\"%f\" height=\"%f\" />\n", + getMinX(),getMinY(),width(),height()); + printf("</svg>\n"); + ri.printIntersections(); + return true; + } + return false; +} + + +void RectangleIntersections::printIntersections() +{ + printf("intersections:\n"); + if(top) printf(" top=%d:(%f,%f)\n",top,topX,topY); + if(bottom) printf(" bottom=%d:(%f,%f)\n",bottom,bottomX,bottomY); + if(left) printf(" left=%d:(%f,%f)\n",left,leftX,leftY); + if(right) printf(" right=%d:(%f,%f)\n",right,rightX,rightY); +} + +// Of the stored intersections, this returns the one closest to the +// specified point +void RectangleIntersections::nearest(double x, double y, double &xi, double &yi) { + bool is[]={top, right, bottom, left}; + double xs[]={topX, rightX, bottomX, leftX}; + double ys[]={topY, rightY, bottomY, leftY}; + double dx, dy, l, minl = 999999999999999.0; + for(unsigned i=0;i<4;i++) + { + if(is[i]) + { + dx=xs[i]-x; + dy=ys[i]-y; + l=dx*dx + dy*dy; + if(l<minl) + { + minl=l; + xi=xs[i]; + yi=ys[i]; + } + } + } +} + +} diff --git a/src/3rdparty/adaptagrams/libvpsc/rectangle.h b/src/3rdparty/adaptagrams/libvpsc/rectangle.h new file mode 100644 index 0000000..df76399 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/rectangle.h @@ -0,0 +1,302 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2010 Monash University + * + * 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 +*/ + +/* + * Functions to automatically generate constraints for the + * rectangular node overlap removal problem. + * + */ +#ifndef VPSC_RECTANGLE_H +#define VPSC_RECTANGLE_H + +#include <iostream> +#include <vector> +#include <set> +#include <cassert> +#include <cmath> + +#include "libvpsc/assertions.h" + +namespace vpsc { + +//! @brief Indicates the x- or y-dimension. +enum Dim { + //! The x-dimension (0). + HORIZONTAL = 0, + //! The x-dimension (0). + XDIM = 0, + //! The y-dimension (1). + VERTICAL = 1, + //! The y-dimension (1). + YDIM = 1, + // The dimension is not set. + UNSET = 2 +}; + +inline Dim conjugate(Dim d) { + return static_cast<Dim>(!d); +} +/* records the positions and sides through which a particular line intersects with a rectangle + */ +struct RectangleIntersections { + bool intersects, top, bottom, left, right; + double topX, topY, bottomX, bottomY, leftX, leftY, rightX, rightY; + RectangleIntersections() + : intersects(false),top(false),bottom(false),left(false),right(false), + topX(0),topY(0),bottomX(0),bottomY(0),leftX(0),leftY(0),rightX(0),rightY(0) {} + int countIntersections() { + return left+right+top+bottom; + } + void printIntersections(void); + // Of the stored intersections, this returns the one closest to the + // specified point + void nearest(double x, double y, double & xi, double & yi); +}; + +/** + * @brief A rectangle represents a fixed-size shape in the diagram that may + * be moved to prevent overlaps and satisfy constraints. + */ +class Rectangle { +public: + /** + * @brief Constructs a rectangle by specifying the positions of all + * four sides. + * + * @param[in] x Minimum horizontal value. + * @param[in] X Maximum horizontal value. + * @param[in] y Minimum vertical value. + * @param[in] Y Maximum vertical value. + * @param[in] allowOverlap not used currently. + */ + Rectangle(double x, double X, double y, double Y, + bool allowOverlap = false); + Rectangle(Rectangle const &Other) + : minX(Other.minX) + , maxX(Other.maxX) + , minY(Other.minY) + , maxY(Other.maxY) + , overlap(Other.overlap) { } + Rectangle(); + bool isValid(void) const; + Rectangle unionWith(const Rectangle& rhs) const; + /* + * reset the dimensions in one axis + * @param d axis (0==X, 1==Y) + * @param x min value + * @param X max value + */ + void reset(const unsigned d, double x, double X); + double getMaxX() const { return maxX+xBorder; } + double getMaxY() const { return maxY+yBorder; } + double getMinX() const { return minX-xBorder; } + double getMinY() const { return minY-yBorder; } + /* + * @param d axis: 0=horizontal 1=vertical + */ + double getMinD(unsigned const d) const { + COLA_ASSERT(d==0||d==1); + return ( d == 0 ? getMinX() : getMinY() ); + } + /* + * @param d axis: 0=horizontal 1=vertical + */ + double getMaxD(unsigned const d) const { + COLA_ASSERT(d==0||d==1); + return ( d == 0 ? getMaxX() : getMaxY() ); + } + void setMinD(unsigned const d, const double val) + { if ( d == 0) { minX = val; } else { minY = val; } } + void setMaxD(unsigned const d, const double val) + { if ( d == 0) { maxX = val; } else { maxY = val; } } + double getCentreX() const { return getMinX()+width()/2.0; } + double getCentreY() const { return getMinY()+height()/2.0; } + /* + * @param d axis: 0=horizontal 1=vertical + */ + double getCentreD(unsigned const d) const { + COLA_ASSERT(d==0||d==1); + return getMinD(d)+length(d)/2.0; + } + double width() const { return getMaxX()-getMinX(); } + double height() const { return getMaxY()-getMinY(); } + /* + * @param d axis: 0=width 1=height + * @return width or height + */ + double length(unsigned const d) const { + COLA_ASSERT(d==0||d==1); + return ( d == 0 ? width() : height() ); + } + void set_width(double w) { maxX = minX + w - 2.0*xBorder; } + void set_height(double h) { maxY = minY + h - 2.0*yBorder; } + void moveCentreD(const unsigned d, double p) { + COLA_ASSERT(d==0||d==1); + if(d == 0) { moveCentreX(p); + } else { moveCentreY(p); } + } + void moveCentreX(double x) { + moveMinX(x-width()/2.0); + } + void moveCentreY(double y) { + moveMinY(y-height()/2.0); + } + void moveCentre(double x, double y) { + moveCentreX(x); + moveCentreY(y); + } + void moveMinX(double x) { + double w=width(); + minX=x+xBorder; + maxX=x+w-xBorder; + COLA_ASSERT(fabs(width()-w)<1e-9); + } + void moveMinY(double y) { + double h=height(); + maxY=y+h-yBorder; + minY=y+yBorder; + COLA_ASSERT(fabs(height()-h)<1e-9); + } + double overlapD(const unsigned d, Rectangle* r) { + if(d==0) { + return overlapX(r); + } else { + return overlapY(r); + } + } + double overlapX(Rectangle *r) const { + double ux=getCentreX(), vx=r->getCentreX(); + if (ux <= vx && r->getMinX() < getMaxX()) + return getMaxX() - r->getMinX(); + if (vx <= ux && getMinX() < r->getMaxX()) + return r->getMaxX() - getMinX(); + return 0; + } + double overlapY(Rectangle *r) const { + double uy=getCentreY(), vy=r->getCentreY(); + if (uy <= vy && r->getMinY() < getMaxY()) { + return getMaxY() - r->getMinY(); + } + if (vy <= uy && getMinY() < r->getMaxY()) { + return r->getMaxY() - getMinY(); + } + return 0; + } + bool allowOverlap() { + return overlap; + } + void offset(double dx, double dy) { + minX += dx; + maxX += dx; + minY += dy; + maxY += dy; + } + // returns the intersections between the line segment from (x1,y1) + // to (x2,y2) and this rectangle. Any intersections points with + // sides are reported, lines coincident with a side are considered not + // to intersect. + void lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const; + bool inside(double x, double y) const { + return x>getMinX() && x<getMaxX() && y>getMinY() && y<getMaxY(); + } + // checks if line segment is strictly overlapping. + // That is, if any point on the line is inside the rectangle. + bool overlaps(double x1, double y1, double x2, double y2); + // p1=(x1,y1),p2=(x2,y2) are points on the boundary. Puts the shortest + // path round the outside of the rectangle from p1 to p2 into xs, ys. + void routeAround(double x1, double y1, double x2, double y2, + std::vector<double> &xs, std::vector<double> &ys); + /* + * xBorder and yBorder can be set to add a border to the boundary of the + * rectangle. In other words, the size of the rectangle returned by the + * getters (getMinX, getMaxX, etc) will be slightly larger than the + * internal representation. This is useful in situations where we need the + * size considered in one axis to be slightly different to that considered + * in the other axis for example, to avoid numerical precision problems in + * the axis-by-axis overlap removal process. + */ + static double xBorder,yBorder; + static void setXBorder(double x) {xBorder=x;} + static void setYBorder(double y) {yBorder=y;} + +private: + double minX,maxX,minY,maxY; + bool overlap; +}; + +//! @brief A vector of pointers to Rectangle objects. +typedef std::vector<Rectangle*> Rectangles; + +std::ostream& operator<<(std::ostream& os, vpsc::Rectangle const &r); + +class Variable; +typedef std::vector<Variable *> Variables; +class Constraint; +typedef std::vector<Constraint *> Constraints; + +void generateXConstraints(const Rectangles& rs, const Variables& vars, + Constraints& cs, const bool useNeighbourLists); +void generateYConstraints(const Rectangles& rs, const Variables& vars, + Constraints& cs); + +/** + * @brief Uses VPSC to remove overlaps between rectangles. + * + * Moves rectangles to remove all overlaps. Heuristic attempts to move + * shapes by as little as possible. + * + * @param[in,out] rs The rectangles which will be moved to remove overlap + */ +void removeoverlaps(Rectangles& rs); + +/** + * @brief Uses VPSC to remove overlaps between rectangles, excluding some + * that should not be moved. + * + * Moves rectangles to remove all overlaps. A heuristic attempts to move + * shapes by as little as possible. The heuristic is that the overlaps + * are removed horizontally and then vertically, each pass being a + * quadratic program in which the total squared movement is minimised + * subject to non-overlap constraints. + * + * An optional third horizontal pass (in addition to the first horizontal + * pass and the second vertical pass) can be applied wherein the + * x-positions of rectangles are reset to their original positions and + * overlap removal repeated. This may avoid some unnecessary movement. + * + * @param[in,out] rs The rectangles which will be moved to remove overlap + * @param[in] fixed A set of indices to rectangles which should not be moved. + * @param[in] thirdPass Optionally run the third horizontal pass described above. + */ +void removeoverlaps(Rectangles& rs, const std::set<unsigned>& fixed, + bool thirdPass = true); + +// Useful for assertions: +bool noRectangleOverlaps(const Rectangles& rs); + +struct delete_object +{ + template <typename T> + void operator()(T *ptr){ delete ptr;} +}; + +} // namespace vpsc +#endif // VPSC_RECTANGLE_H diff --git a/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.cpp b/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.cpp new file mode 100644 index 0000000..08cc1e4 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.cpp @@ -0,0 +1,561 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 +*/ + +#include <cmath> +#include <sstream> +#include <map> +#include <cfloat> +#include <set> + +#include "libvpsc/constraint.h" +#include "libvpsc/block.h" +#include "libvpsc/blocks.h" +#include "libvpsc/solve_VPSC.h" +#include "libvpsc/cbuffer.h" +#include "libvpsc/variable.h" +#include "libvpsc/assertions.h" +#include "libvpsc/exceptions.h" + +#ifdef LIBVPSC_LOGGING +#include <fstream> +#endif + +using namespace std; + +namespace vpsc { + +static const double ZERO_UPPERBOUND=-1e-10; +static const double LAGRANGIAN_TOLERANCE=-1e-4; + +IncSolver::IncSolver(Variables const &vs, Constraints const &cs) + : Solver(vs,cs) +{ + inactive=cs; + for(Constraints::iterator i=inactive.begin();i!=inactive.end();++i) { + (*i)->active=false; + } +} +Solver::Solver(Variables const &vs, Constraints const &cs) + : m(cs.size()), + cs(cs), + n(vs.size()), + vs(vs), + needsScaling(false) +{ + for(unsigned i=0;i<n;++i) { + vs[i]->in.clear(); + vs[i]->out.clear(); + + // Set needsScaling if any variables have a scale other than 1. + needsScaling |= (vs[i]->scale != 1); + } + for(unsigned i=0;i<m;++i) { + Constraint *c=cs[i]; + c->left->out.push_back(c); + c->right->in.push_back(c); + c->needsScaling = needsScaling; + } + bs=new Blocks(vs); +#ifdef LIBVPSC_LOGGING + printBlocks(); + //COLA_ASSERT(!constraintGraphIsCyclic(n,vs)); +#endif +} +Solver::~Solver() { + delete bs; +} + +void IncSolver::addConstraint(Constraint *c) +{ + ++m; + c->active = false; + inactive.push_back(c); + c->left->out.push_back(c); + c->right->in.push_back(c); + c->needsScaling = needsScaling; +} + +// useful in debugging +void Solver::printBlocks() { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) { + Block *b=*i; + f<<" "<<*b<<endl; + } + for(unsigned i=0;i<m;i++) { + f<<" "<<*cs[i]<<endl; + } +#endif +} + +/** + * Stores the relative positions of the variables in their finalPosition + * field. + */ +void Solver::copyResult() { + for(Variables::const_iterator i=vs.begin();i!=vs.end();++i) { + Variable* v=*i; + v->finalPosition=v->position(); + COLA_ASSERT(v->finalPosition==v->finalPosition); + } +} +/** +* 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. +*/ +bool Solver::satisfy() { + list<Variable*> *vList=bs->totalOrder(); + for(list<Variable*>::iterator i=vList->begin();i!=vList->end();++i) { + Variable *v=*i; + if(!v->block->deleted) { + bs->mergeLeft(v->block); + } + } + bs->cleanup(); + bool activeConstraints=false; + for(unsigned i=0;i<m;i++) { + if(cs[i]->active) activeConstraints=true; + if(cs[i]->slack() < ZERO_UPPERBOUND) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl; +#endif + //COLA_ASSERT(cs[i]->slack()>-0.0000001); + throw UnsatisfiedConstraint(*cs[i]); + } + } + delete vList; + copyResult(); + return activeConstraints; +} + +void Solver::refine() { + bool solved=false; + // Solve shouldn't loop indefinately + // ... but just to make sure we limit the number of iterations + unsigned maxtries=100; + while(!solved&&maxtries>0) { + solved=true; + maxtries--; + size_t length = bs->size(); + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + b->setUpInConstraints(); + b->setUpOutConstraints(); + } + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + Constraint *c=b->findMinLM(); + if(c!=nullptr && c->lm<LAGRANGIAN_TOLERANCE) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Split on constraint: "<<*c<<endl; +#endif + // Split on c + Block *l=nullptr, *r=nullptr; + bs->split(b,l,r,c); + bs->cleanup(); + // split alters the block set so we have to restart + solved=false; + break; + } + } + } + for(unsigned i=0;i<m;i++) { + if(cs[i]->slack() < ZERO_UPPERBOUND) { + COLA_ASSERT(cs[i]->slack()>ZERO_UPPERBOUND); + throw UnsatisfiedConstraint(*cs[i]); + } + } +} +/** + * 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. + */ +bool Solver::solve() { + satisfy(); + refine(); + copyResult(); + return bs->size()!=n; +} + +bool IncSolver::solve() { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"solve_inc()..."<<endl; +#endif + satisfy(); + double lastcost = DBL_MAX, cost = bs->cost(); + while(fabs(lastcost-cost)>0.0001) { + satisfy(); + lastcost=cost; + cost = bs->cost(); +#ifdef LIBVPSC_LOGGING + f<<" bs->size="<<bs->size()<<", cost="<<cost<<endl; +#endif + } + copyResult(); + return bs->size()!=n; +} +/** + * 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. + */ +bool IncSolver::satisfy() { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"satisfy_inc()..."<<endl; +#endif + splitBlocks(); + //long splitCtr = 0; + Constraint* v = nullptr; + //CBuffer buffer(inactive); + while ( (v = mostViolated(inactive)) && + (v->equality || ((v->slack() < ZERO_UPPERBOUND) && !v->active)) ) + { + COLA_ASSERT(!v->active); + Block *lb = v->left->block, *rb = v->right->block; + if(lb != rb) { + lb->merge(rb,v); + } else { + if(lb->isActiveDirectedPathBetween(v->right,v->left)) { + // cycle found, relax the violated, cyclic constraint + v->unsatisfiable=true; + continue; + //UnsatisfiableException e; + //lb->getActiveDirectedPathBetween(e.path,v->right,v->left); + //e.path.push_back(v); + //throw e; + } + //if(splitCtr++>10000) { + //throw "Cycle Error!"; + //} + // constraint is within block, need to split first + try { + Constraint* splitConstraint + =lb->splitBetween(v->left,v->right,lb,rb); + if(splitConstraint!=nullptr) { + COLA_ASSERT(!splitConstraint->active); + inactive.push_back(splitConstraint); + } else { + v->unsatisfiable=true; + continue; + } + } catch(UnsatisfiableException e) { + e.path.push_back(v); +#ifdef LIBVPSC_DEBUG + std::cerr << "Unsatisfiable:" << std::endl; + for(std::vector<Constraint*>::iterator r=e.path.begin(); + r!=e.path.end();++r) + { + std::cerr << **r <<std::endl; + } +#endif + v->unsatisfiable=true; + continue; + } + if(v->slack()>=0) { + COLA_ASSERT(!v->active); + // v was satisfied by the above split! + inactive.push_back(v); + bs->insert(lb); + bs->insert(rb); + } else { + bs->insert(lb->merge(rb,v)); + delete ((lb->deleted) ? lb : rb); + } + } +#ifdef LIBVPSC_LOGGING + f<<"...remaining blocks="<<bs->size()<<", cost="<<bs->cost()<<endl; +#endif + } +#ifdef LIBVPSC_LOGGING + f<<" finished merges."<<endl; +#endif + bs->cleanup(); + bool activeConstraints=false; + for(unsigned i=0;i<m;i++) { + v=cs[i]; + if(v->active) activeConstraints=true; + if(v->slack() < ZERO_UPPERBOUND) { + ostringstream s; + s<<"Unsatisfied constraint: "<<*v; +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<s.str()<<endl; +#endif + throw (char *) s.str().c_str(); + } + } +#ifdef LIBVPSC_LOGGING + f<<" finished cleanup."<<endl; + printBlocks(); +#endif + copyResult(); + return activeConstraints; +} +void IncSolver::moveBlocks() { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"moveBlocks()..."<<endl; +#endif + size_t length = bs->size(); + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + b->updateWeightedPosition(); + //b->posn = b->wposn / b->weight; + } +#ifdef LIBVPSC_LOGGING + f<<" moved blocks."<<endl; +#endif +} +void IncSolver::splitBlocks() { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); +#endif + moveBlocks(); + splitCnt=0; + // Split each block if necessary on min LM + size_t length = bs->size(); + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + Constraint* v=b->findMinLM(); + if(v!=nullptr && v->lm < LAGRANGIAN_TOLERANCE) { + COLA_ASSERT(!v->equality); +#ifdef LIBVPSC_LOGGING + f<<" found split point: "<<*v<<" lm="<<v->lm<<endl; +#endif + splitCnt++; + Block *b = v->left->block, *l=nullptr, *r=nullptr; + COLA_ASSERT(v->left->block == v->right->block); + //double pos = b->posn; + b->split(l,r,v); + //l->posn=r->posn=pos; + //l->wposn = l->posn * l->weight; + //r->wposn = r->posn * r->weight; + l->updateWeightedPosition(); + r->updateWeightedPosition(); + bs->insert(l); + bs->insert(r); + b->deleted=true; + COLA_ASSERT(!v->active); + inactive.push_back(v); +#ifdef LIBVPSC_LOGGING + f<<" new blocks: "<<*l<<" and "<<*r<<endl; +#endif + } + } + //if(splitCnt>0) { std::cout<<" splits: "<<splitCnt<<endl; } +#ifdef LIBVPSC_LOGGING + f<<" finished splits."<<endl; +#endif + bs->cleanup(); +} + +/** + * Scan constraint list for the most violated constraint, or the first equality + * constraint + */ +Constraint* IncSolver::mostViolated(Constraints &l) +{ + double slackForMostViolated = DBL_MAX; + Constraint* mostViolated = nullptr; +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f << "Looking for most violated..." << endl; +#endif + size_t lSize = l.size(); + size_t deleteIndex = lSize; + Constraint *constraint = nullptr; + double slack = 0; + for (size_t index = 0; index < lSize; ++index) + { + constraint = l[index]; + slack = constraint->slack(); + if (constraint->equality || slack < slackForMostViolated) + { + slackForMostViolated = slack; + mostViolated = constraint; + deleteIndex = index; + if (constraint->equality) + { + break; + } + } + } + // Because the constraint list is not order dependent we just + // move the last element over the deletePoint and resize + // downwards. There is always at least 1 element in the + // vector because of search. + if ( (deleteIndex < lSize) && + (((slackForMostViolated < ZERO_UPPERBOUND) && !mostViolated->active) || + mostViolated->equality) ) + { + l[deleteIndex] = l[lSize-1]; + l.resize(lSize-1); + } +#ifdef LIBVPSC_LOGGING + if (mostViolated) + { + f << " most violated is: " << *mostViolated << endl; + } + else + { + f << " non found." << endl; + } +#endif + return mostViolated; +} + +struct node { + set<node*> in; + set<node*> out; +}; +// useful in debugging - cycles would be BAD +bool Solver::constraintGraphIsCyclic(const unsigned n, Variable* const vs[]) { + map<Variable*, node*> varmap; + vector<node*> graph; + for(unsigned i=0;i<n;i++) { + node *u=new node; + graph.push_back(u); + varmap[vs[i]]=u; + } + for(unsigned i=0;i<n;i++) { + for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) { + Variable *l=(*c)->left; + varmap[vs[i]]->in.insert(varmap[l]); + } + + for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) { + Variable *r=(*c)->right; + varmap[vs[i]]->out.insert(varmap[r]); + } + } + while(graph.size()>0) { + node *u=nullptr; + vector<node*>::iterator i=graph.begin(); + for(;i!=graph.end();++i) { + u=*i; + if(u->in.size()==0) { + break; + } + } + if(i==graph.end() && graph.size()>0) { + //cycle found! + return true; + } else { + graph.erase(i); + for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) { + node *v=*j; + v->in.erase(u); + } + delete u; + } + } + for(unsigned i=0; i<graph.size(); ++i) { + delete graph[i]; + } + return false; +} + +// useful in debugging - cycles would be BAD +bool Solver::blockGraphIsCyclic() { + map<Block*, node*> bmap; + vector<node*> graph; + size_t length = bs->size(); + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + node *u=new node; + graph.push_back(u); + bmap[b]=u; + } + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + b->setUpInConstraints(); + Constraint *c=b->findMinInConstraint(); + while(c!=nullptr) { + Block *l=c->left->block; + bmap[b]->in.insert(bmap[l]); + b->deleteMinInConstraint(); + c=b->findMinInConstraint(); + } + + b->setUpOutConstraints(); + c=b->findMinOutConstraint(); + while(c!=nullptr) { + Block *r=c->right->block; + bmap[b]->out.insert(bmap[r]); + b->deleteMinOutConstraint(); + c=b->findMinOutConstraint(); + } + } + while(graph.size()>0) { + node *u=nullptr; + vector<node*>::iterator i=graph.begin(); + for(;i!=graph.end();++i) { + u=*i; + if(u->in.size()==0) { + break; + } + } + if(i==graph.end() && graph.size()>0) { + //cycle found! + return true; + } else { + graph.erase(i); + for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) { + node *v=*j; + v->in.erase(u); + } + delete u; + } + } + for(unsigned i=0; i<graph.size(); i++) { + delete graph[i]; + } + return false; +} +} diff --git a/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h b/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h new file mode 100644 index 0000000..5f7713c --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h @@ -0,0 +1,130 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2013 Monash University + * + * 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 +*/ + +// +// TODO: Really, we should have three classes: VPSC, IncrementalVPSC and +// StaticVPSC, where the latter two inherit from VPSC. StaticVPSC would be +// the equivalent of what is currently VPSC. +// Also, a lot of the code specific to one or other of these concrete +// implementations should be moved from Block and Blocks: e.g. mergeLeft etc. +// +#ifndef VPSC_SOLVE_VPSC_H +#define VPSC_SOLVE_VPSC_H + +#include <vector> + +/** + * @namespace vpsc + * @brief libvpsc: Variable Placement with Separation Constraints + * quadratic program solver library. + * + * You should use VPSC via an instance of the IncSolver or Solver classes. + */ +namespace vpsc { +class Variable; +typedef std::vector<Variable*> Variables; +class Constraint; +class Blocks; +typedef std::vector<Constraint*> Constraints; + +/** + * @brief Static solver for Variable Placement with Separation Constraints + * problem instance + * + * This class attempts to solve a least-squares problem subject to a set + * of separation constraints. The solve() and satisfy() methods return true + * if any constraints are active, in both cases false means an unconstrained + * optimum has been found. + * + * @sa IncSolver + */ +class Solver { +public: + //! @brief Results in an approximate solution subject to the constraints. + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + virtual bool satisfy(); + //! @brief Results in an optimum solution subject to the constraints + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + virtual bool solve(); + + Solver(Variables const &vs, Constraints const &cs); + virtual ~Solver(); + //! @brief Returns the Variables in this problem instance. + //! @returns A vector of Variable objects. + Variables const & getVariables() { return vs; } +protected: + Blocks *bs; + size_t m; + std::vector<Constraint*> const &cs; + size_t n; + std::vector<Variable*> const &vs; + bool needsScaling; + + void printBlocks(); + void copyResult(); +private: + void refine(); + bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]); + bool blockGraphIsCyclic(); +}; + +/** + * @brief Incremental solver for Variable Placement with Separation Constraints + * problem instance + * + * This class attempts to solve a least-squares problem subject to a set + * of sepation constraints. The solve() and satisfy() methods return true + * if any constraints are active, in both cases false means an unconstrained + * optimum has been found. This is an incremental version of that allows + * refinement after blocks are moved. This version is preferred if you are + * using VPSC in an interactive context. + * + * @sa Solver + */ +class IncSolver : public Solver { +public: + IncSolver(Variables const &vs, Constraints const &cs); + //! @brief Results in an approximate solution subject to the constraints. + //! @return true if any constraints are active, or false if an unconstrained + bool satisfy(); + //! @brief Results in an optimum solution subject to the constraints + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + bool solve(); + //! @brief Adds a constraint to the existing VPSC solver. + //! + //! @param constraint The new additional constraint to add. + void addConstraint(Constraint *constraint); +private: + void moveBlocks(); + void splitBlocks(); + + unsigned splitCnt; + Constraints inactive; + Constraints violated; + Constraint* mostViolated(Constraints &l); +}; + +} +#endif // VPSC_SOLVE_VPSC_H diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/Makefile.am b/src/3rdparty/adaptagrams/libvpsc/tests/Makefile.am new file mode 100644 index 0000000..d155c52 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/Makefile.am @@ -0,0 +1,15 @@ +AM_CPPFLAGS = -I$(top_srcdir) + +check_PROGRAMS = rectangleoverlap block satisfy_inc # cycle +satisfy_inc_SOURCES = satisfy_inc.cpp +satisfy_inc_LDADD = $(top_builddir)/libvpsc/libvpsc.la # -L$(mosek_home)/bin -lmosek -lguide -limf -lirc +block_SOURCES = block.cpp +block_LDADD = $(top_builddir)/libvpsc/libvpsc.la +rectangleoverlap_SOURCES = rectangleoverlap.cpp +rectangleoverlap_LDADD = $(top_builddir)/libvpsc/libvpsc.la + +#cycle_SOURCES = cycle.cpp +#cycle_LDADD = $(top_builddir)/libvpsc/libvpsc.la + +TESTS = $(check_PROGRAMS) + diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/block.cpp b/src/3rdparty/adaptagrams/libvpsc/tests/block.cpp new file mode 100644 index 0000000..08080e9 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/block.cpp @@ -0,0 +1,105 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <cassert> +#include <iostream> + +#include "libvpsc/variable.h" +#include "libvpsc/constraint.h" +#include "libvpsc/blocks.h" +#include "libvpsc/block.h" +using namespace std; +using namespace vpsc; + + +void test1() { + Blocks *blocks = new Blocks(Variables()); + cout << "Block test 1..." << endl; + Variable *a1=new Variable(1,0,1); + Variable *a2=new Variable(2,0,1); + Constraint *c=new Constraint(a1,a2,1); + a1->out.push_back(c); + a2->in.push_back(c); + Block *b1=new Block(blocks, a1); + Block *b2=new Block(blocks, a2); + b1->merge(b2,c); + cout << "Block: " << *b1 << endl; + a1->desiredPosition = -1; + a2->desiredPosition = 2; + Constraint *m = b1->findMinLMBetween(a1,a2); + cout << "Min lm constraint: " << *m << endl; + assert(c==m); + cout << " lm=" << c->lm << endl; + cout << "Block test 1... Success!" << endl; +} + +/* + * Constraint tree: + * \_/ + * / \ + */ +void test2() { + Blocks *blocks = new Blocks(Variables()); + cout << "Block test 2..." << endl; + Variable *a[]={ + new Variable(0,0,1), + new Variable(1,0,1), + new Variable(2,1,1), + new Variable(3,2,1), + new Variable(4,3,1), + new Variable(5,3,1)}; + Constraint *c[]={ + new Constraint(a[0],a[2],2), + new Constraint(a[1],a[2],2), + new Constraint(a[2],a[3],2), + new Constraint(a[3],a[4],2), + new Constraint(a[3],a[5],2)}; + for(int i=0;i<6;i++) { + new Block(blocks,a[i]); + } + for(int i=0;i<5;i++) { + c[i]->left->out.push_back(c[i]); + c[i]->right->in.push_back(c[i]); + } + for(int i=0;i<5;i++) { + Block *l=c[i]->left->block, *r=c[i]->right->block; + l->merge(r,c[i]); + } + Block *b=a[0]->block; + cout << "Block: " << *b << endl; + for(int i=0;i<6;i++) { + a[i]->desiredPosition = i!=4?-2:5; + } + cout << "calc min lm:" << endl; + Constraint *m = b->findMinLMBetween(a[0],a[4]); + cout << "Min lm constraint: " << *m << endl; + assert(m==c[3]); + cout << "Block test 2... Success!" << endl; +} +int main() { + test1(); + test2(); + return 0; +} diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/cycle.cpp b/src/3rdparty/adaptagrams/libvpsc/tests/cycle.cpp new file mode 100644 index 0000000..26dda3a --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/cycle.cpp @@ -0,0 +1,106 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <iostream> +#include <cassert> +#include <cmath> +#include <algorithm> +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +using namespace std; +using namespace vpsc; +inline bool approxEquals(const double a, const double b) { + return fabs((double)a-b)<0.0001; +} +void test1() { + cout << "Test 1..." << endl; + vector<Variable*> a; + a.push_back(new Variable(0,0,1)); + a.push_back(new Variable(1,1,1)); + vector<Constraint*> c; + c.push_back(new Constraint(a[0],a[1],2)); + c.push_back(new Constraint(a[1],a[0],2)); + double expected[]={1.5,-0.5}; + try { + IncSolver vpsc(a,c); + vpsc.solve(); + } catch (UnsatisfiableException& e) { + cerr << "Unsatisfiable" << endl; + for(vector<Constraint*>::iterator i=e.path.begin(); + i!=e.path.end();i++) { + cout << **i << endl; + } + exit(1); + } + //catch(...) { + //cerr << "Unknown error!" << endl; + //exit(1); + //} + + for(size_t i=0;i<a.size();i++) { + assert(approxEquals(a[i]->finalPosition,expected[i])); + } + for_each(a.begin(),a.end(),delete_object()); + for_each(c.begin(),c.end(),delete_object()); + cout << "Test 1... done." << endl; +} +void test2() { + cout << "Test 2..." << endl; + vector<Variable *> a; + a.push_back(new Variable(0,8,1)); + a.push_back(new Variable(1,5,1)); + a.push_back(new Variable(2,3,1)); + a.push_back(new Variable(3,1,1)); + vector<Constraint*> c; + c.push_back(new Constraint(a[0],a[3],3)); + c.push_back(new Constraint(a[0],a[1],3)); + c.push_back(new Constraint(a[1],a[3],3)); + c.push_back(new Constraint(a[1],a[2],3)); + c.push_back(new Constraint(a[2],a[3],3)); + c.push_back(new Constraint(a[2],a[3],3)); + //double expected[]={-3.71429,4,1,-0.714286,2.28571,2.28571,7,5.28571,8.28571,11.2857}; + try { + IncSolver vpsc(a,c); + vpsc.solve(); + } catch (char const *msg) { + cerr << msg << endl; + exit(1); + } + + /* + for(int i=0;i<n;i++) { + assert(approxEquals(a[i]->position(),expected[i])); + } + */ + cout << "Test 2... done." << endl; + for_each(a.begin(),a.end(),delete_object()); + for_each(c.begin(),c.end(),delete_object()); +} +int main() { + test1(); + return 0; +} diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/rectangleoverlap.cpp b/src/3rdparty/adaptagrams/libvpsc/tests/rectangleoverlap.cpp new file mode 100644 index 0000000..d8ad72e --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/rectangleoverlap.cpp @@ -0,0 +1,660 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <cstdio> +#include <cassert> +#include <cstdlib> +#include <math.h> +#include <time.h> +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +using namespace std; +using namespace vpsc; + +inline double getRand(double range) { + return range*rand()/RAND_MAX; +} +void printRects(vector<Rectangle*> &rs) { + printf("Set of %d rectangles:\n",(int)rs.size()); + for(unsigned i=0;i<rs.size();++i) { + cout << *rs[i] << endl; + } +} +void generateRandomRects(unsigned n, vector<Rectangle*> &rs) { + rs.resize(n); + static double const rect_size = 5; + static double const min_rect_size = 1e-4; + static double const fld_size = sqrt(rect_size * n / 2.0); + double coords[4]; + for (unsigned i = 0; i < n; ++i) { + for (unsigned d = 0; d < 2; ++d) { + //unsigned const end = 1 + (rand() % (fld_size - 1)); + //unsigned const start = rand() % end; + double const start = getRand(fld_size); + double const end = start + min_rect_size + + getRand(rect_size); + coords[2 * d] = start; + coords[2 * d + 1] = end; + } + rs[i]=new Rectangle(coords[0],coords[1],coords[2],coords[3]); + } +} +vector<Rectangle*>& generateRects(double coords[][4], unsigned n,vector<Rectangle *>& rs) { + rs.resize(n); + for (unsigned i = 0; i < n; ++i) { + rs[i]=new Rectangle(coords[i][0],coords[i][1],coords[i][2],coords[i][3]); + } + return rs; +} +void test(vector<Rectangle *> &rs, double &cost, double &duration) { + unsigned n=rs.size(); + vector<Rectangle *> ors(n); + for (unsigned i = 0; i < n; ++i) { + ors[i]=new Rectangle(rs[i]->getMinX(),rs[i]->getMaxX(),rs[i]->getMinY(),rs[i]->getMaxY()); + } + + clock_t starttime = clock(); + removeoverlaps(rs); + duration = (double)(clock() - starttime)/CLOCKS_PER_SEC; + cost = 0; + for(unsigned i=0;i<n;i++) { + double dx=rs[i]->getCentreX()-ors[i]->getCentreX(); + double dy=rs[i]->getCentreY()-ors[i]->getCentreY(); + cost+=sqrt(dx*dx+dy*dy); + delete rs[i]; + delete ors[i]; + } +} +double test1[][4]={ { 0, 50, 0, 30 }, { 10, 20, 10, 29 }, +{ 30, 70, 39, 70 }, { 0, 90, 40, 50 }, { 30, 70, 1, 29 } }; +unsigned n1=5; +double test2[][4]={ { 7, 22, 39, 54 }, { 7, 33, 0, 59 }, +{ 3, 26, 16, 56 }, { 7, 17, 18, 20 }, { 1, 59, 11, 26 }, +{ 19, 20, 13, 49 }, { 1, 10, 0, 4 }, { 47, 52, 1, 3 } }; +unsigned n2=8; +double test3[][4]={ { 8, 32, 29, 36 }, { 19, 24, 2, 27 }, +{ 4, 5, 27, 55 }, { 6, 7, 13, 26 }, { 3, 39, 46, 62 }, +{ 6, 23, 2, 19 }, { 18, 39, 5, 23 }, { 35, 63, 42, 78 }, +{ 16, 18, 14, 72 }, { 12, 32, 10, 58 } }; +unsigned n3=10; +double test4[][4]={ { 315.755, 355.288, 353.595, 449.627 }, +{ 395.048, 395.635, 253.943, 362.228 }, +{ 254.439, 393.289, 278.708, 286.346 }, +{ 209.852, 370.831, 326.496, 507.255 }, +{ 271.947, 415.74, 362.228, 450.318 }, +{ 293.408, 405.197, 220.61, 244.119 }, +{ 276.482, 386.472, 286.346, 435.767 }, +{ 268.211, 436.23, 192.807, 220.61 }, +{ 378.008, 502.118, 358.437, 475.587 }, +{ 340.68, 472.597, 249.492, 335.448 } }; +unsigned n4=10; +double test5[][4]={ { 7, 22, 39, 54 }, { 7, 33, 0, 59 }, +{ 3, 26, 16, 56 }, { 7, 17, 18, 20 }, { 1, 59, 11, 26 }, +{ 19, 20, 13, 49 }, { 1, 10, 0, 4 }, { 47, 52, 1, 3 } }; +unsigned n5=8; +double test6[][4]={ { 40, 69, 63, 69 }, { 1, 5, 27, 64 }, +{ 34, 66, 20, 22 }, { 1, 24, 10, 25 }, { 1, 19, 9, 61 }, +{ 0, 56, 8, 70 }, { 33, 35, 13, 28 }, { 11, 31, 33, 35 }, +{ 12, 22, 3, 23 } }; +unsigned n6=9; +double test7[][4]={ { 341.594, 388.459, 373.491, 518.168 }, +{ 271.214, 324.782, 311.332, 409.166 }, +{ 293.848, 475.064, 305.194, 391.162 }, +{ 255.317, 447.738, 342.671, 489.923 }, +{ 228.375, 261.057, 206.422, 327.794 }, +{ 383.552, 462.834, 363.132, 412.843 }, +{ 288.859, 481.054, 351.895, 497.728 }, +{ 201.307, 368.511, 387.02, 394.95 }, +{ 257.961, 259.673, 386.503, 518.403 }, +{ 200.178, 275.606, 364.968, 466.787 } }; +unsigned n7=10; +double test8[][4]={{12.807,15.7566,14.9478,16.7924}, +{7.76228,11.6532,4.75249,4.75349}, +{7.84596,10.1387,15.465,16.7709}, +{1.80748,3.0357,5.9983,6.16279}, +{6.46447,7.47249,12.8694,13.4378}, +{14.0026,17.3342,5.10141,9.81088}, +{6.84223,6.85932,6.40395,9.21135}, +{7.63462,10.3552,6.78124,8.59953}, +{0.26429,2.80847,14.5724,17.7455}, +{14.7686,15.7148,3.46036,5.66776}, +{10.635,11.4893,12.5044,16.941}, +{6.32027,10.7117,14.2953,15.6276}, +{11.9942,13.1118,10.6893,11.4477}, +{11.9384,15.1357,2.20982,6.92982}, +{2.89395,4.29002,11.7058,16.2896}, +{9.44116,12.7547,9.75556,11.1811}, +{5.2475,8.00607,15.3652,17.026}, +{2.09541,3.76981,2.5526,3.16739}, +{3.14595,6.66351,10.3007,14.4881}, +{4.88109,9.38044,9.02416,10.2954}, +{7.55378,9.14715,13.9686,16.0468}, +{1.70299,5.42198,14.1913,14.2191}, +{14.4877,14.4897,6.14013,8.50074}, +{12.9909,14.5163,10.322,12.4457}, +{11.616,12.0848,3.7601,5.45419}, +{10.3087,13.358,3.04666,3.53389}, +{2.28263,2.44881,13.806,15.8206}, +{3.31805,5.47662,3.91187,6.85355}, +{0.484138,2.06164,3.57335,7.87753}, +{4.73784,5.12359,9.383,11.9217}, +{12.2921,12.7769,12.329,12.8139}, +{12.7351,16.7141,12.7658,13.78}, +{3.71614,5.79872,1.53137,4.97126}, +{10.7423,14.8183,2.57104,2.94168}, +{9.93995,10.1557,1.3432,1.499}, +{0.198099,0.204966,9.29459,11.8795}, +{14.1043,18.8473,11.2028,14.1971}, +{4.23857,4.95743,14.7047,17.1439}, +{13.936,15.9612,10.7744,14.8598}, +{11.355,15.6824,2.49113,5.96963}, +{12.8528,16.3913,3.82582,6.67259}, +{13.9445,14.7354,10.8576,12.9503}, +{13.0041,15.6166,2.07035,3.70034}, +{2.31809,5.03195,1.13659,5.8604}, +{10.2454,14.5396,10.9442,15.4321}, +{7.12259,11.3929,7.20864,10.4059}, +{6.54862,9.88399,1.82828,5.89899}, +{4.27072,7.52613,7.99016,11.1703}, +{8.84828,9.15453,10.1489,11.7934}, +{7.71027,8.97206,3.26462,4.02636}, +{14.3383,15.1727,3.02586,3.26268}, +{9.21233,11.1919,13.9814,16.1433}, +{13.1946,16.1613,12.2268,13.1319}, +{13.0462,15.6689,7.03513,8.59752}, +{8.72724,11.3859,5.69193,7.8238}, +{10.6241,14.1033,7.88946,9.95327}, +{8.48376,10.8714,8.86955,11.2137}, +{3.55633,4.14351,13.7308,18.4988}, +{1.79802,4.68843,11.0964,11.6543}, +{13.1535,14.6895,1.52144,2.50643}, +{1.24533,4.27261,13.345,13.4925}, +{14.4031,18.7944,15.4447,18.0096}, +{8.56933,11.3392,0.446787,1.18762}, +{11.311,16.0574,8.41,8.76508}, +{13.5332,17.8479,8.2067,11.4446}, +{5.73826,6.63581,10.8364,11.6186}, +{10.1995,11.5202,6.54248,9.49804}, +{14.6456,16.7915,7.01621,7.57531}, +{15.1444,16.4184,1.45761,2.35577}, +{11.8169,12.0382,14.8149,19.3316}, +{10.148,11.1227,15.0087,18.1595}, +{10.9498,14.7849,12.3852,13.9467}, +{10.7631,10.9141,5.24419,8.64319}, +{11.2486,12.6029,6.25029,10.0076}, +{12.8731,16.0703,4.96619,8.54006}, +{6.92828,8.53172,8.36509,11.8971}, +{3.1677,7.20423,14.5582,17.1794}, +{14.1426,16.9327,15.1198,19.1306}, +{2.52943,6.64027,5.18935,8.58545}, +{6.89613,11.4515,3.7672,6.23813}, +{2.91428,6.40636,1.4231,4.10552}, +{9.81892,12.9687,8.25114,10.1775}, +{14.6192,14.7412,10.8349,15.1725}, +{6.96657,11.7009,11.0638,11.8966}, +{7.03182,9.20687,2.04293,2.60462}, +{7.47955,9.28533,7.45213,8.37318}, +{6.24651,9.79246,8.61803,9.91034}, +{4.73642,7.48461,9.59481,12.748}, +{8.70644,11.1702,2.54172,4.26587}, +{14.9028,19.4109,6.238,8.04256}, +{5.22907,8.45899,1.98714,4.94042}, +{8.96884,12.3636,1.72663,3.39844}, +{6.96563,8.04735,10.6198,11.3663}, +{1.65099,5.65883,10.5002,13.9039}, +{11.3337,11.5138,5.31369,7.75029}, +{2.79561,4.08151,7.04269,9.00167}}; + +unsigned n8=96; +double test9[][4]={{2.67865,4.81342,8.67025,11.5025}, +{5.77912,6.94355,9.80043,12.2904}, +{11.9459,13.8675,3.66967,7.38408}, +{6.72663,8.30474,3.37566,7.24571}, +{9.2081,10.9827,10.9557,11.8868}, +{0.161903,3.31202,3.35371,3.84933}, +{4.46508,9.18934,9.43037,10.9125}, +{3.84059,5.2565,8.66868,8.70713}, +{4.67598,5.15207,5.2252,8.92099}, +{1.19252,1.31215,7.97481,8.27191}, +{4.57641,5.71063,0.440628,4.17365}, +{6.80268,11.5523,3.78375,4.79819}, +{11.2172,13.7652,8.44876,11.1649}, +{11.4673,13.1644,6.09156,7.41026}, +{12.2995,13.585,0.155239,4.63887}, +{12.3513,15.3947,8.3437,11.1337}, +{3.92566,6.15611,12.432,16.3993}, +{12.6351,14.6039,9.96391,13.1152}, +{0.682894,2.48867,7.66904,8.86704}, +{3.50189,7.28939,8.37741,8.96276}, +{2.37719,4.19762,11.1129,12.0465}, +{5.53568,8.1444,11.9056,15.5818}, +{7.32876,11.2713,12.1655,15.0785}, +{2.534,6.15563,9.30845,11.2833}, +{8.00852,12.8051,2.16786,4.90262}, +{11.8095,12.814,11.5818,13.7731}, +{7.54398,9.23043,7.36953,10.7315}, +{8.36918,9.83071,11.8668,11.8776}, +{5.72267,9.66642,1.46379,3.71362}, +{11.2725,14.6538,4.76772,7.30304}, +{5.8638,10.7623,5.99865,10.0994}, +{11.0224,12.6455,0.852638,2.20201}, +{4.03151,8.51056,6.12449,10.3672}, +{7.75136,10.6782,10.648,11.8606}, +{11.9663,14.3993,2.83154,5.46437}, +{6.05275,8.00044,10.9675,15.3426}, +{10.9702,13.146,8.98465,12.4718}, +{4.99665,7.91376,9.19241,9.71153}, +{3.7422,4.00542,2.00556,2.53918}, +{9.01679,10.9439,12.8107,15.1367}, +{10.0117,11.5009,0.194049,3.08568}, +{8.29117,13.1323,6.99045,8.65707}, +{5.97395,10.5816,5.77559,7.35126}, +{5.68856,6.51699,4.40392,5.82242}, +{0.209729,3.89072,7.36013,8.98447}, +{0.360264,1.88558,0.319886,3.22738}, +{2.02163,2.07428,3.2753,8.12958}, +{5.05075,5.86987,12.7958,16.7689}, +{10.6484,15.5931,7.23546,10.4741}, +{7.20998,7.46939,2.44384,5.10459}, +{12.5022,15.1819,10.6593,13.5708}, +{2.3619,2.45407,5.75168,7.28966}, +{12.131,16.661,4.39608,8.19289}, +{9.81023,10.731,6.67919,9.31523}, +{6.97712,10.166,8.4813,13.3432}, +{6.45378,7.44457,8.96504,11.9806}, +{8.70396,11.5729,7.15588,12.1524}, +{9.93058,14.0306,0.849502,1.80855}, +{8.32174,8.34616,7.52595,12.0431}, +{2.79979,5.93358,4.90296,7.6893}, +{0.72484,5.42439,3.48229,5.77743}, +{6.05275,10.2779,7.4252,7.72184}, +{4.41176,6.91184,11.8809,15.3923}, +{6.50435,8.04432,11.4826,15.3172}, +{12.16,14.3518,1.13763,4.17255}, +{7.82506,10.5124,8.05713,9.03876}}; +unsigned n9=66; +double test10[][4]={{15.9875,18.9768,15.3193,17.9811}, +{16.5669,19.7216,1.05824,1.58667}, +{8.80629,9.88527,9.71101,13.2142}, +{19.568,20.1767,3.28922,8.03561}, +{13.6363,15.6827,12.9329,16.6542}, +{2.32913,3.58085,8.28597,12.6503}, +{6.86597,11.2847,5.9172,10.236}, +{8.57413,11.0048,18.0203,18.4095}, +{7.68828,8.89193,9.52038,12.3945}, +{13.5784,15.499,0.824193,4.7533}, +{5.70392,8.26946,10.1955,12.8184}, +{17.9857,22.6483,14.2013,16.0377}, +{14.7965,16.4222,11.9332,16.5984}, +{20.5111,23.1383,0.355473,0.834461}, +{5.88763,9.2761,8.31995,11.6173}, +{13.8307,16.6334,17.2376,19.8715}, +{7.20005,8.99179,19.0137,23.483}, +{3.67112,6.97933,18.6142,21.1208}, +{0.936183,5.81945,5.11063,7.47703}, +{9.85383,12.4861,7.80027,11.677}, +{8.07584,11.1964,13.8571,17.9736}, +{8.07017,10.0661,8.42816,9.79417}, +{10.8259,11.6232,16.7028,19.3248}, +{18.55,19.3911,17.174,22.0082}, +{1.34073,1.93538,17.9341,20.4509}, +{11.7558,12.1994,0.295703,2.19289}, +{12.4063,13.662,0.965124,5.21391}, +{2.2033,2.85518,16.4455,20.0191}, +{6.3853,9.77239,0.892142,2.17773}, +{0.546736,5.29679,12.1949,15.2469}, +{14.1365,17.5213,14.7027,15.1512}, +{9.46879,11.9145,11.8539,14.4408}, +{8.49611,8.98075,17.1388,17.5066}, +{1.53577,2.52014,0.615943,4.13396}, +{7.12078,9.05901,20.3739,23.44}, +{2.7104,7.09713,16.4442,20.8587}, +{12.9707,14.2845,12.5642,16.2281}, +{13.5086,14.3207,17.7611,20.1056}, +{19.2264,24.1481,2.063,5.27645}, +{15.2016,18.2491,1.10228,3.37286}, +{16.7733,18.1385,2.35807,7.0123}, +{19.8272,21.9464,18.27,22.8376}, +{4.27133,8.48869,19.5925,21.488}, +{19.6951,23.7284,10.5207,11.1889}, +{0.799027,3.61863,1.42504,3.44902}, +{1.31871,5.95584,16.4147,18.2479}, +{19.8398,21.0495,15.2495,15.8842}, +{3.15773,5.76599,11.1562,12.2007}, +{4.61422,4.78559,16.6607,16.9497}, +{11.0064,11.5745,16.521,19.5463}, +{13.3865,15.7969,12.215,14.3112}, +{0.272424,4.59201,7.19502,9.58004}, +{15.6377,16.4926,18.5978,19.0178}, +{1.44957,1.65985,5.24023,10.1284}, +{0.0559948,0.138395,3.75354,4.46554}, +{3.24015,3.86196,12.205,14.0543}, +{2.64686,3.51587,16.1429,16.6103}, +{2.56003,5.14236,5.6624,8.31491}, +{13.7143,16.5806,7.32777,10.6354}, +{15.8994,20.4036,0.171759,0.567584}, +{11.1247,11.5263,7.61341,8.80042}, +{10.7869,11.8353,7.73861,8.39933}, +{16.7563,18.1604,15.6377,20.3633}, +{4.7627,5.87556,0.850618,4.25755}, +{11.2178,15.6734,14.2378,15.9026}, +{2.00323,5.94744,1.78428,4.77571}, +{16.0705,20.0359,9.50528,12.9563}, +{14.9808,18.3586,9.56819,10.8817}, +{13.7005,17.173,10.5755,15.5172}, +{6.24185,6.44174,11.9766,16.0609}, +{14.0767,16.1476,11.9904,14.2274}, +{18.3009,20.9378,0.109473,0.330122}, +{0.395109,4.35458,19.8694,23.5078}, +{17.4949,22.4626,6.16132,10.5268}, +{0.992178,2.11099,18.813,22.5419}, +{8.41369,12.6754,20.0682,22.6}, +{19.5239,23.6359,3.22945,3.81068}, +{6.60361,6.84761,11.8174,12.6899}, +{8.95351,9.96275,11.2373,12.3269}, +{13.8414,17.1229,18.182,20.7568}, +{13.0468,17.4872,16.8349,21.2615}, +{16.6053,17.1026,5.24778,8.1272}, +{1.20043,2.96974,10.1904,13.8153}, +{7.73924,7.74809,1.53703,3.76274}, +{15.0915,18.4866,18.6576,18.9426}, +{10.69,13.9811,6.92511,9.44625}, +{8.66032,12.8382,6.67974,9.08735}, +{3.24707,3.91176,7.21641,8.75134}, +{20.5281,23.518,5.04016,5.38868}, +{8.78238,13.6922,11.9149,12.334}, +{19.1358,19.5264,15.9157,16.8192}, +{4.52551,7.52884,12.1049,16.4566}, +{18.467,22.8957,2.97024,7.48362}, +{17.9618,18.9449,2.7601,4.06645}, +{10.8057,15.3718,7.7254,8.32173}, +{19.6416,21.5781,7.62473,11.5731}, +{5.14712,8.87694,0.495145,1.50088}, +{4.11719,6.22953,3.59814,8.25023}, +{6.34314,9.83141,1.90886,3.52039}, +{11.6041,11.7642,12.6177,16.2647}, +{17.4351,19.786,0.846214,2.85357}, +{7.90974,12.4031,10.5818,10.868}, +{3.33578,5.53021,19.271,22.6137}, +{14.3296,18.1074,3.76864,6.21134}, +{1.39798,4.21194,14.7015,18.9814}, +{13.3463,13.89,4.76333,8.78979}, +{7.78517,12.3834,12.0445,12.1204}, +{1.21553,4.14149,10.9523,11.5827}, +{10.7328,15.0635,11.2248,16.0148}, +{1.89816,6.42421,6.21479,9.51491}, +{5.76369,9.87896,0.471237,2.08597}, +{1.10543,3.50571,6.4243,6.85217}, +{13.4916,16.9187,13.4167,14.751}, +{6.61683,9.79075,4.44435,7.2165}, +{17.5276,21.8159,3.22316,7.12862}, +{8.09408,10.3727,0.167984,1.77021}, +{8.04815,12.6168,7.91666,11.0816}, +{1.32248,2.63905,12.5164,17.4845}, +{7.324,11.7358,9.05354,13.7152}, +{15.0274,18.5751,11.55,13.6444}, +{15.3627,16.1478,19.7391,21.3528}, +{16.5701,19.0741,18.0876,18.9877}, +{19.9719,20.1289,10.2999,14.2899}, +{5.77124,9.49847,20.3551,23.9988}, +{9.4065,13.7029,1.45775,2.17524}, +{8.22117,12.8533,16.9079,17.5996}, +{8.20293,12.4012,15.7691,15.783}, +{9.33037,11.8253,0.286895,2.70091}, +{12.5114,14.6471,11.0241,13.8678}, +{14.6423,15.2091,5.08987,9.29257}, +{10.4729,12.308,1.7717,6.27227}, +{9.65187,11.9638,14.3196,18.937}, +{5.1704,6.94718,18.4884,22.8028}, +{4.66015,8.43071,12.6095,14.2635}, +{19.5384,21.1589,7.47562,10.9592}, +{20.3595,24.407,0.804689,2.94465}, +{0.775119,2.53222,1.35017,2.38185}, +{14.1459,18.0717,13.111,17.3643}, +{15.9535,16.9371,3.47482,6.36462}, +{15.1727,17.7769,13.1324,16.2993}, +{17.2678,19.5719,19.2912,23.3942}, +{14.5832,17.1443,19.2559,24.0751}, +{1.57289,3.42857,7.75497,11.9183}, +{2.63994,5.18274,5.84108,8.64802}, +{7.56056,8.51991,0.284378,0.750091}, +{8.4225,12.0985,13.1443,16.5509}, +{12.4397,13.7349,16.1177,21.0089}, +{18.411,22.1179,12.4302,16.1478}, +{16.7343,19.9381,0.87138,4.38391}, +{0.729191,5.0941,0.4316,3.36382}, +{7.96699,10.079,15.0613,19.489}, +{14.4215,16.2705,13.932,15.6623}, +{9.37756,12.4608,12.8857,16.6014}, +{12.0729,12.5163,2.59841,7.39714}, +{7.52658,11.0203,15.2853,19.805}, +{16.0919,20.3462,13.6464,15.1218}, +{6.17075,10.0034,17.5729,21.8258}, +{8.94533,11.0185,7.98461,12.5047}, +{0.249775,1.8787,2.72361,7.6554}, +{11.5167,11.8826,8.7937,10.8008}, +{14.3038,17.8052,19.0873,20.7193}, +{19.7272,24.1131,5.29434,7.64106}, +{19.7624,20.0966,13.2827,17.354}, +{5.58186,7.99298,3.3987,5.8269}, +{19.7479,20.3262,16.1492,17.465}, +{3.25902,6.3684,17.0948,20.9851}, +{12.7549,14.4322,1.40931,6.02218}, +{12.232,13.2567,0.559319,3.07481}, +{0.138414,4.75571,14.9273,18.2745}, +{6.04241,6.23422,9.62104,10.3701}}; +unsigned n10=170; +double test11[][4]={{2.20847,5.99613,25.7684,29.5065}, +{4.38169,7.14163,-7.79499,-7.42678}, +{17.1816,19.4476,-5.03151,-3.38153}, +{10.6383,11.0169,-0.356332,3.85003}, +{13.3309,15.7634,21.4146,24.0122}, +{17.1354,20.5384,27.9053,29.8839}, +{4.82128,7.88931,4.90792,5.71239}, +{13.1802,14.7891,24.0123,26.5035}, +{9.1468,9.95493,-3.73661,-1.29955}, +{14.4021,17.8989,19.2669,23.5805}, +{3.53936,4.95206,17.2632,19.2913}, +{11.2732,15.3951,10.4298,11.6976}, +{9.82902,13.9892,17.9523,19.9811}, +{10.0265,11.0793,16.4791,17.5196}, +{1.27427,5.64116,7.85316,8.33764}, +{3.70992,7.16293,5.06311,6.98578}, +{9.95501,13.9876,-3.13412,-1.29965}, +{17.6086,21.8963,15.3022,17.9743}, +{2.05607,2.66477,-0.552748,0.286511}, +{12.6971,13.3533,-4.23798,-3.73671}, +{7.7961,11.69,7.35371,11.9837}, +{7.68167,9.93012,1.7933,3.98514}, +{1.2176,2.27018,0.286611,3.17168}, +{4.98578,7.91342,12.8464,16.1781}, +{16.5918,21.3527,4.59687,5.72758}, +{9.12809,9.56481,1.38197,2.061}, +{14.6904,19.1649,-3.38143,-1.21492}, +{11.3046,15.5357,14.6315,17.2819}, +{3.69836,4.52282,5.06311,5.67974}, +{12.2713,13.7058,11.6977,14.6314}, +{0.130993,3.26738,-4.32728,-3.7221}, +{11.4317,12.3544,19.9812,22.2083}, +{10.0298,10.1041,11.1483,12.7055}, +{16.2023,16.7313,1.49517,4.59677}, +{12.4149,15.8265,4.33334,6.45789}, +{17.575,19.9519,12.3124,15.3021}, +{17.0991,22.0233,3.78959,6.02599}, +{3.99216,5.32933,0.583351,0.882127}, +{16.5929,18.003,14.3823,17.6574}, +{13.5273,15.1372,16.4791,20.1285}, +{12.3687,15.2044,6.45799,7.83514}, +{8.04258,9.47375,17.3137,21.5515}, +{7.329,10.9322,7.65703,11.5161}, +{1.98895,2.89459,1.84656,3.17168}, +{0.520521,2.46608,6.71895,10.4866}, +{13.184,16.1474,6.45799,7.30869}, +{2.13915,4.58689,17.2632,19.8192}, +{15.8375,18.2786,15.9558,18.1255}, +{14.7223,16.4109,16.4791,17.3636}, +{4.00206,7.29287,-4.32728,-1.41062}, +{16.6028,18.6157,14.6315,17.1786}, +{3.19495,7.10528,-1.41052,0.583251}, +{1.69626,5.11997,0.326338,1.84646}, +{12.1579,12.759,-0.356332,0.328198}, +{3.51735,7.12098,5.71249,7.85306}, +{0.953512,5.10372,3.17178,5.06301}, +{13.2737,14.3319,18.7924,21.1975}, +{1.46188,5.99876,10.3471,12.8463}, +{8.39195,9.77825,1.66426,2.061}, +{1.81344,5.57851,-3.53802,0.326238}, +{1.31773,2.99152,29.5066,33.3419}, +{5.33625,7.15652,19.4265,19.8527}, +{0.432492,3.44635,7.60608,10.3589}, +{1.60933,2.36115,-1.16144,0.286511}, +{9.27774,10.4284,-1.86525,-1.56998}, +{11.8878,13.7671,-5.11518,-4.23808}, +{10.0073,10.2574,11.282,12.9297}, +{10.5778,11.703,0.629406,0.965262}, +{3.17349,7.96657,16.1782,17.2631}, +{11.2281,13.6998,12.2002,12.4339}, +{13.7166,18.3124,19.2669,21.4145}, +{10.5388,15.0813,0.328298,4.33324}, +{9.05987,12.0136,-1.29945,-0.356432}, +{6.74526,7.05518,-8.26859,-7.79509}, +{17.7736,20.6859,5.72768,8.29825}, +{2.22113,7.1491,21.4284,25.7683}, +{16.1247,17.7842,2.70437,3.3773}, +{8.34023,10.0276,13.9827,18.7779}, +{15.1872,18.2348,17.1787,17.2902}, +{16.5308,17.6299,6.45799,8.71682}, +{5.98601,9.22204,23.2905,26.0581}, +{7.64095,10.7424,18.778,22.0208}, +{15.0585,19.52,17.7993,19.2668}, +{17.646,20.037,0.451228,3.78949}, +{0.0160052,1.94859,4.68464,6.71885}, +{7.29434,9.17489,13.9827,17.3136}, +{17.7896,21.639,6.02609,9.48842}, +{4.43065,8.71164,19.8528,23.2904}, +{16.5231,21.0708,3.3774,4.59677}, +{14.2096,16.0172,17.282,17.9522}, +{8.32648,9.09478,3.98524,7.65693}, +{3.6703,7.6841,0.583351,4.90782}, +{9.90605,10.9591,11.5162,13.1508}, +{14.7669,18.5129,-1.21482,3.3773}, +{3.48104,6.74301,29.5066,30.5551}, +{9.22657,10.4539,-5.59946,-1.29955}, +{8.12181,8.34154,-2.11601,1.66416}, +{4.11375,5.37752,30.5552,34.3283}, +{9.11434,12.5991,8.88212,10.4297}, +{11.3365,14.9133,-8.77796,-4.9549}, +{15.7809,16.0235,-2.30357,0.667869}, +{15.4629,16.7224,4.59687,6.45789}, +{13.3766,16.7042,21.4146,25.1652}, +{7.87643,10.2361,12.8464,13.9826}, +{7.38842,11.7536,11.5162,16.479}, +{5.15799,9.74446,-7.42668,-4.32738}, +{16.0009,16.044,-3.82308,0.667869}, +{15.6318,18.7733,8.71692,11.607}, +{10.7258,12.2305,7.30879,8.88202}, +{8.17133,9.84923,-1.56988,1.38187}, +{3.5179,5.38762,0.583351,5.06301}, +{9.4516,10.8319,22.0209,26.7891}, +{9.94456,11.8221,19.9812,21.2926}, +{5.14479,8.31779,3.92878,7.65693}, +{14.6057,18.2633,0.667969,4.59677}, +{5.62784,8.67939,17.3137,19.4264}, +{10.9244,13.5481,-1.29955,-1.29945}, +{5.76759,6.30746,-3.722,-3.5131}, +{7.13259,9.6258,8.33774,11.5161}, +{1.05144,1.32443,10.359,10.9074}, +{16.4807,19.9127,26.5036,27.9052}, +{5.9629,7.66553,-1.41052,-1.14028}, +{13.6489,16.9728,22.2084,25.5279}, +{2.50777,4.43837,19.8193,21.4283}, +{1.57577,3.7409,15.383,18.2258}, +{17.1816,18.8466,17.2903,17.7992}, +{8.43156,13.0154,-4.9548,-3.13422}, +{1.88827,6.19077,6.98588,10.347}, +{14.73,15.2147,17.9523,18.7923}, +{5.55742,8.69305,2.0611,3.92868}}; +unsigned n11=130; +double test12[][4]={ +{4.92744,6.6604,4.27234,8.301}, +{1.54924,2.51053,4.48526,9.19033}, +{1.55587,5.56226,-0.660563,3.35611}, +{1.87055,2.251,3.56944,6.75421}, +{1.58179,2.94863,5.24022,8.78858}, +{1.88069,5.98638,3.94188,5.24012}, +{1.81447,5.62383,5.24022,9.22211}, +{4.06842,6.37182,-0.053975,3.94178}, +{4.03643,4.2387,3.35621,3.94178}, +{1.16362,3.67328,0.29063,3.01001}, +}; +unsigned n12=10; +int main() { + double c,t; + vector<Rectangle*> rs; + cout << "test1" << endl; + test(generateRects(test1,n1,rs),c,t); + cout << "test2" << endl; + test(generateRects(test2,n2,rs),c,t); + cout << "test3" << endl; + test(generateRects(test3,n3,rs),c,t); + cout << "test4" << endl; + test(generateRects(test4,n4,rs),c,t); + cout << "test5" << endl; + test(generateRects(test5,n5,rs),c,t); + cout << "test6" << endl; + test(generateRects(test6,n6,rs),c,t); + cout << "test7" << endl; + test(generateRects(test7,n7,rs),c,t); + cout << "test8" << endl; + test(generateRects(test8,n8,rs),c,t); + cout << "test9" << endl; + test(generateRects(test9,n9,rs),c,t); + cout << "test10" << endl; + test(generateRects(test10,n10,rs),c,t); + cout << "test11" << endl; + test(generateRects(test11,n11,rs),c,t); + cout << "test12" << endl; + test(generateRects(test12,n12,rs),c,t); + int max_size=100, repeats=100,step=10; + //srand(time(nullptr)); + for(int i=10;i<=max_size;i+=step) { + //if(i%5==0) cout << i << endl; + double disp=0, time=0; + for(int repeat=repeats;repeat--;) { + vector<Rectangle*> rs; + generateRandomRects(i,rs); + //printRects(rs); + test(rs,c,t); + disp+=c; + time+=t; + } + disp/=repeats; + time/=repeats; + cout << i << "," << time << "," << disp << endl; + } + return 0; +} diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp b/src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp new file mode 100644 index 0000000..60aeb09 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp @@ -0,0 +1,666 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +#include <algorithm> +#include <cstdio> +#include <ctime> +#include <cmath> +#include <cassert> + +using namespace std; +using namespace vpsc; + +static inline double getRand(const int range) { + return (double)range*rand()/(RAND_MAX+1.0); +} +inline bool approxEquals(const double a, const double b) { + return fabs((double)a-b)<0.01; +} +typedef vector<Constraint*> CS; + +bool checkResult(unsigned n, Variable *a[], unsigned m, Constraint *c[], double expected[]=nullptr) { + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); +#ifdef MOSEK_AVAILABLE + //printf("Checking with mosek..."); + MosekEnv* menv = mosek_init_sep_ls(n,c,m); + float *b=new float[n]; + float *x=new float[n]; + for(unsigned i=0;i<n;i++) { + b[i]=a[i]->desiredPosition; + } + mosek_quad_solve_sep(menv,b,x); + mosek_delete(menv); +#endif + for(unsigned i=0;i<n;i++) { + char s=','; + if(i==n-1) s='\n'; +#ifdef MOSEK_AVAILABLE + //printf("%f(%f)%c",a[i]->finalPosition,x[i],s); + if(!(approxEquals(a[i]->finalPosition,x[i]))) { + return false; + } + assert(approxEquals(a[i]->finalPosition,x[i])); +#endif + if(expected) assert(approxEquals(a[i]->finalPosition,expected[i])); + } +#ifdef MOSEK_AVAILABLE + delete [] b; + delete [] x; +#endif + return true; +} +void dumpMatlabProblem(unsigned n, Variable *a[], unsigned m, Constraint *c[]){ + printf("H=2*eye(%d);\n",n); + printf("f=-2*[ "); + for(unsigned i=0;i<n;i++) { + printf("%f ",a[i]->desiredPosition); + } + printf("];\n"); + printf("s=[ "); + for(unsigned i=0;i<n;i++) { + printf("%f ",a[i]->scale); + } + printf("];\n"); + printf("C=zeros(%d,%d);\n",m,n); + for(unsigned i=0;i<m;i++) { + printf("C(%d,[%d %d])=[1 -1];\n",i+1,c[i]->left->id+1,c[i]->right->id+1); + } + printf("A=C*diag(s);\n"); + printf("b=[ "); + for(unsigned i=0;i<m;i++) { + printf("%f ",-1.*c[i]->gap); + } + printf("];\n"); + printf("quadprog(H,f,A,b)\n"); +} +void test1() { + cout << "Test 1..." << endl; + Variable *a[] = { + new Variable(0,2,1,1.), + new Variable(1,9,1,1), + new Variable(2,9,1,1), + new Variable(3,9,1,1), + new Variable(4,2,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[1],3), + new Constraint(a[1],a[2],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={1.4,4.4,7.4,7.4,10.4}; + checkResult(n,a,m,c,expected); + cout << "Test 1... done." << endl; +} +void test1a() { + cout << "Test 1a..." << endl; + /* matlab: + H=2*eye(2) + f=[0 0] + A=[ 2 -1 ] + b=[ -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,0,1,2.), + new Variable(1,0,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={-0.8,0.4}; + checkResult(n,a,m,c,expected); + cout << "Test 1a... done." << endl; +} +void test1b() { + cout << "Test 1b..." << endl; + /* matlab: + H=2*eye(2) + f=[0 0] + A=[ 1 -2 ] + b=[ -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,0,1,1.), + new Variable(1,0,1,2)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={-0.4,0.8}; + checkResult(n,a,m,c,expected); + cout << "Test 1b... done." << endl; +} +void test1c() { + cout << "Test 1c..." << endl; + /* matlab: + H=2*eye(3) + f=-2*[ 1 1 1 ] + s=[ 3 2 4 ] + C=zeros(2,3) + C(1,1:2)=[1 -1] + C(2,2:3)=[1 -1] + A=C*diag(s) + b=[-2 -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,1,1,3), + new Variable(1,1,1,2), + new Variable(2,1,1,4)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2), + new Constraint(a[1],a[2],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={0.2623, 1.3934, 1.1967}; + checkResult(n,a,m,c,expected); + cout << "Test 1c... done." << endl; +} + +// no splits required +void test2() { + cout << "Test 2..." << endl; + Variable *a[] = { + new Variable(0,4,1), + new Variable(1,6,1), + new Variable(2,9,1), + new Variable(3,2,1), + new Variable(4,5,1)}; + Constraint *c[] = { + new Constraint(a[0],a[2],3), + new Constraint(a[0],a[3],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3)}; + double expected[]={0.5,6,3.5,6.5,9.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 2... done." << endl; +} + +// split required +void test3() { + /* matlab: + H=2*eye(5) + f=-2*[ 5 6 7 4 3 ] + s=[ 1 1 1 1 1 ] + C=zeros(5,5) + C(1,[1 5])=[1 -1] + C(2,[2 3])=[1 -1] + C(3,[3 4])=[1 -1] + C(4,[3 5])=[1 -1] + C(5,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(5,1) + quadprog(H,f,A,b) + */ + cout << "Test 3..." << endl; + Variable *a[] = { + new Variable(0,5,1), + new Variable(1,6,1), + new Variable(2,7,1), + new Variable(3,4,1), + new Variable(4,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[1],a[2],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + double expected[]={5,0.5,3.5,6.5,9.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 3... done." << endl; +} +// split required +void test4() { + /* matlab: + H=2*eye(5) + f=-2*[ 7 1 6 0 2 ] + s=[ 5 8 3 1 7 ] + C=zeros(6,5) + C(1,[1 4])=[1 -1] + C(2,[1 2])=[1 -1] + C(3,[2 5])=[1 -1] + C(4,[3 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(6,1) + quadprog(H,f,A,b) + */ + cout << "Test 4..." << endl; + Variable *a[] = { + new Variable(0,7,1,1), + new Variable(1,1,1,1), + new Variable(2,6,1,1), + new Variable(3,0,1,1), + new Variable(4,2,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[3],3), + new Constraint(a[0],a[1],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3)}; + double expected[]={0.8,3.8,0.8,3.8,6.8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 4... done." << endl; +} +void test5() { + cout << "Test 5..." << endl; + Variable *a[] = { + new Variable(0,0,1), new Variable(1,9,1), new + Variable(2,1,1), new Variable(3,9,1), new + Variable(4,5,1), new Variable(5,1,1), new + Variable(6,2,1), new Variable(7,1,1), new + Variable(8,6,1), new Variable(9,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[3],3), new Constraint(a[1],a[8],3), + new Constraint(a[1],a[6],3), new Constraint(a[2],a[6],3), + new Constraint(a[3],a[5],3), new Constraint(a[3],a[6],3), + new Constraint(a[3],a[7],3), new Constraint(a[4],a[8],3), + new Constraint(a[4],a[7],3), new Constraint(a[5],a[8],3), + new Constraint(a[5],a[7],3), new Constraint(a[5],a[8],3), + new Constraint(a[6],a[9],3), new Constraint(a[7],a[8],3), + new Constraint(a[7],a[9],3), new Constraint(a[8],a[9],3) + }; + double expected[]={-3.71429,4,1,-0.714286,2.28571,2.28571,7,5.28571,8.28571,11.2857}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 5... done." << endl; +} +void test6() { + cout << "Test 6..." << endl; + Variable *a[] = { + new Variable(0,7,1), + new Variable(1,0,1), + new Variable(2,3,1), + new Variable(3,1,1), + new Variable(4,4,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[3],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-0.75,0,2.25,5.25,8.25}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 6... done." << endl; +} +void test7() { + cout << "Test 7..." << endl; + Variable *a[] = { + new Variable(0,4,1), + new Variable(1,2,1), + new Variable(2,3,1), + new Variable(3,1,1), + new Variable(4,8,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[3],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-0.5,2,2.5,5.5,8.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 7... done." << endl; +} +void test8() { + /* matlab: + H=2*eye(5) + f=-2*[ 3 4 0 5 6 ] + s=[ 1 1 1 1 1 ] + C=zeros(6,5) + C(1,[1 2])=[1 -1] + C(2,[1 3])=[1 -1] + C(3,[2 3])=[1 -1] + C(4,[2 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(6,1) + quadprog(H,f,A,b) + */ + // This cycles when using the heuristic of merging on the least + // violated, violated constraint first. + cout << "Test 8..." << endl; + Variable *a[] = { + new Variable(0,3,1), + new Variable(1,4,1), + new Variable(2,0,1), + new Variable(3,5,1), + new Variable(4,6,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[1],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-2.4,0.6,3.6,6.6,9.6}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 8... done." << endl; +} +void test9() { + /* matlab: + H=2*eye(5) + f=-2*[ 8 2 6 5 3 ] + s=[ 1 1 1 1 1 ] + C=zeros(7,5) + C(1,[1 5])=[1 -1] + C(2,[1 4])=[1 -1] + C(3,[2 3])=[1 -1] + C(4,[2 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[3 5])=[1 -1] + C(7,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(7,1) + quadprog(H,f,A,b) + */ + cout << "Test 9..." << endl; + Variable *a[] = { + new Variable(0,8,1), + new Variable(1,2,1), + new Variable(2,6,1), + new Variable(3,5,1), + new Variable(4,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[3],3), + new Constraint(a[1],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + double expected[]={3.6,0.6,3.6,6.6,9.6}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 9... done." << endl; +} + +void test10() { + cout << "Test 10..." << endl; + Variable *a[] = { + new Variable(0,8.56215,1,4.99888), +new Variable(1,1.27641,1,8.06009), +new Variable(2,6.28523,1,1.06585), +new Variable(3,4.09743,1,0.924166), +new Variable(4,0.369025,1,6.12702)}; + + Constraint *c[] = { + new Constraint(a[0],a[2],3), +new Constraint(a[0],a[1],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); + assert(checkResult(n,a,m,c,nullptr)); + cout << "Test 10... done." << endl; +} +void test11() { + cout << "Test 11..." << endl; + Variable *a[] = { + new Variable(0,1.31591,1,9.02545), +new Variable(1,1.48155,1,3.68918), +new Variable(2,3.5091,1,2.07033), +new Variable(3,3.47131,1,8.75145), +new Variable(4,0.77374,1,0.967941)}; + + Constraint *c[] = { +new Constraint(a[0],a[3],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); + assert(checkResult(n,a,m,c,nullptr)); + cout << "Test 11... done." << endl; +} +void test12() { + cout << "Test 12..." << endl; + Variable *a[] = { +new Variable(0,2.83063,1,6.67901), +new Variable(1,6.81696,1,7.28642), +new Variable(2,9.27616,1,0.918345), +new Variable(3,3.4094,1,3.39673), +new Variable(4,2.92492,1,2.36269)}; + + Constraint *c[] = { +new Constraint(a[0],a[3],3), +new Constraint(a[0],a[2],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + assert(checkResult(n,a,m,c,nullptr)); + cout << "Test 12... done." << endl; +} +void test13() { + cout << "Test 13..." << endl; + Variable *a[] = { +new Variable(0,0.485024,1,1), +new Variable(1,3.52714,1,1), +new Variable(2,4.01263,1,1), +new Variable(3,4.58524,1,1), +new Variable(4,5.40796,1,1)}; + + Constraint *c[] = { +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[2],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[3],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + assert(checkResult(n,a,m,c,nullptr)); + cout << "Test 13... done." << endl; +} + +// n=number vars +// m=max constraints per var +void rand_test(unsigned n, unsigned m) { + Variable **a=new Variable*[n]; + CS cs; + for(unsigned i=0;i<n;i++) { + a[i]=new Variable(i,getRand(10),1,1);//getRand(10)); + } + for(unsigned i=0;i<n-1;i++) { + for(int j=0;j<getRand(m)+1;j++) { + int e = static_cast<int>(i + getRand(n-1-i)+1); + cs.push_back(new Constraint(a[i],a[e],3)); + } + } + Constraint **acs=new Constraint*[cs.size()]; + for(unsigned i=0;i<cs.size();i++) { + acs[i]=cs[i]; + } + try { + if(!checkResult(n,a,cs.size(),acs)) { + throw "Check failed!"; + } + } catch (char const *msg) { + cout << msg << endl; + cout<<"digraph g {"<<endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + Constraint *c=*i; + cout << c->left->id << "->" << c->right->id << ";" << endl; + } + cout<<"}"<<endl; + for(unsigned i=0;i<n;i++) { + if(i!=0) cout << "," << endl; + cout << "new Variable("<<i<<","<<a[i]->desiredPosition<< ",1," + << a[i]->scale <<")"; + //cout << "a[i]->Pos="<<a[i]->position() << endl; + } + cout << "};" << endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + if(i!=cs.begin()) cout << "," << endl; + Constraint *c=*i; + //cout << c->left->id << "->" << c->right->id << ";" << endl; + cout << "new Constraint(a[" << c->left->id << "],a[" << c->right->id << "],3)"; + + } + cout << "};" << endl; + throw "test failed!"; + } + /* + for(unsigned i=0;i<n;i++) { + a[i]->desiredPosition=getRand(10); + } + vpsc.solve(); + try { + if(!checkResult(n,a,m,acs)) { + throw "2nd Check failed!"; + } + } catch (char const *msg) { + cout << msg << endl; + for(unsigned i=0;i<n;i++) { + if(i!=0) cout << "," << endl; + cout << "new Variable("<<i<<","<<a[i]->desiredPosition<< ",1)"; + //cout << "a[i]->Pos="<<a[i]->position() << endl; + } + cout << "};" << endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + if(i!=cs.begin()) cout << "," << endl; + Constraint *c=*i; + //cout << c->left->id << "->" << c->right->id << ";" << endl; + cout << "new Constraint(a[" << c->left->id << "],a[" << c->right->id << "],3)"; + + } + cout << "};" << endl; + throw "test failed!"; + } + */ + for_each(a,a+n,delete_object()); + delete [] a; + for_each(cs.begin(),cs.end(),delete_object()); + delete [] acs; +} +int main() { + srand(time(nullptr)); + test10(); + test2(); + test3(); + test4(); + test5(); + test6(); + test7(); + test8(); + test9(); + test10(); + test11(); + test12(); + test13(); + for(int i=0;i<1000;i++) { + if(i%100==0) cout << "i=" << i << endl; + rand_test(100,3); + } + for(int i=0;i<10000;i++) { + if(i%100==0) cout << "i=" << i << endl; + rand_test(5,3); + } + return 0; +} diff --git a/src/3rdparty/adaptagrams/libvpsc/variable.cpp b/src/3rdparty/adaptagrams/libvpsc/variable.cpp new file mode 100644 index 0000000..4466c68 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/variable.cpp @@ -0,0 +1,31 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 +*/ + +#include "libvpsc/variable.h" +namespace vpsc { +std::ostream& operator <<(std::ostream &os, const Variable &v) { + if(v.block) + os << "(" << v.id << "=" << v.position() << ")"; + else + os << "(" << v.id << "=" << v.desiredPosition << ")"; + return os; +} +} diff --git a/src/3rdparty/adaptagrams/libvpsc/variable.h b/src/3rdparty/adaptagrams/libvpsc/variable.h new file mode 100644 index 0000000..aaad753 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/variable.h @@ -0,0 +1,95 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * 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 +*/ + +#ifndef VPSC_VARIABLE_H +#define VPSC_VARIABLE_H + +#include <vector> +#include <iostream> + +#include "libvpsc/block.h" +#include "libvpsc/assertions.h" + +namespace vpsc { + +class Constraint; +typedef std::vector<Constraint*> Constraints; + +/** + * @brief A variable is comprised of an ideal position, final position and + * a weight. + * + * When creating a variable you specify an ideal value, and a weight---how + * much the variable wants to be at its ideal position. After solving the + * problem you can read back the final position for the variable. +*/ +class Variable +{ + friend std::ostream& operator <<(std::ostream &os, const Variable &v); + friend class Block; + friend class Constraint; + friend class Solver; +public: + int id; // useful in log files + double desiredPosition; + double finalPosition; + double weight; // how much the variable wants to + // be at it's desired position + double scale; // translates variable to another space + double offset; + Block *block; + bool visited; + bool fixedDesiredPosition; + Constraints in; + Constraints out; + char *toString(); + inline Variable(const int id, const double desiredPos=-1.0, + const double weight=1.0, const double scale=1.0) + : id(id) + , desiredPosition(desiredPos) + , finalPosition(desiredPos) + , weight(weight) + , scale(scale) + , offset(0) + , block(nullptr) + , visited(false) + , fixedDesiredPosition(false) + { + } + double dfdv(void) const { + return 2. * weight * ( position() - desiredPosition ); + } +private: + inline double position(void) const { + return (block->ps.scale*block->posn+offset)/scale; + } + inline double unscaledPosition(void) const { + COLA_ASSERT(block->ps.scale == 1); + COLA_ASSERT(scale == 1); + return block->posn + offset; + } +}; + +//! @brief A vector of pointers to Variable objects. +typedef std::vector<Variable*> Variables; + +} +#endif // VPSC_VARIABLE_H |