Updated libs from the Adaptagrams project: libavoid, libcola and libvspc; changed the code to match the new API

Signed-off-by: Sylvain Chiron <chironsylvain@orange.fr>

1 files changed, 300 insertions, 162 deletions

diff --git a/src/libavoid/connector.h b/src/libavoid/connector.h
index 8f7499a29..56f1b0263 100644
--- a/src/libavoid/connector.h
+++ b/src/libavoid/connector.h
@@ -3,7 +3,7 @@
  *
  * libavoid - Fast, Incremental, Object-avoiding Line Router
  *
- * Copyright (C) 2004-2009  Monash University
+ * Copyright (C) 2004-2015  Monash University
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -19,28 +19,32 @@
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
  *
- * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
+ * Author(s):   Michael Wybrow
 */
 
-//! @file    shape.h
+//! @file    connector.h
 //! @brief   Contains the interface for the ConnRef class.
 
 
 #ifndef AVOID_CONNECTOR_H
 #define AVOID_CONNECTOR_H
 
+#include <utility>
 #include <list>
 #include <vector>
 
+#include "libavoid/dllexport.h"
 #include "libavoid/vertices.h"
 #include "libavoid/geometry.h"
-#include "libavoid/shape.h"
+#include "libavoid/connend.h"
 
 
 namespace Avoid {
 
 class Router;
 class ConnRef;
+class JunctionRef;
+class ShapeRef;
 typedef std::list<ConnRef *> ConnRefList;
 
 
@@ -57,91 +61,54 @@ enum ConnType {
     ConnType_Orthogonal = 2
 };
 
-//! @brief  Flags that can be passed to the ConnEnd constructor to specify
-//!         which sides of a shape this point should have visibility to if
-//!         it is located within the shape's area.
+//! @brief  A checkpoint is a point that the route for a particular connector
+//!         must visit.  They may optionally be given an arrival/departure
+//!         direction.
 //!
-//! Like SVG, libavoid considers the Y-axis to point downwards, that is, 
-//! like screen coordinates the coordinates increase from left-to-right and 
-//! also from top-to-bottom.
-//!
-enum ConnDirFlag {
-    ConnDirNone  = 0,
-    //! @brief  This option specifies the point should be given visibility 
-    //!         to the top of the shape that it is located within.
-    ConnDirUp    = 1,
-    //! @brief  This option specifies the point should be given visibility 
-    //!         to the bottom of the shape that it is located within.
-    ConnDirDown  = 2,
-    //! @brief  This option specifies the point should be given visibility 
-    //!         to the left side of the shape that it is located within.
-    ConnDirLeft  = 4,
-    //! @brief  This option specifies the point should be given visibility 
-    //!         to the right side of the shape that it is located within.
-    ConnDirRight = 8,
-    //! @brief  This option, provided for convenience, specifies the point 
-    //!         should be given visibility to all four sides of the shape 
-    //!         that it is located within.
-    ConnDirAll   = 15
-};
-//! @brief  One or more Avoid::ConnDirFlag options.
-//!
-typedef unsigned int ConnDirFlags;
-
-
-static const double ATTACH_POS_TOP = 0;
-static const double ATTACH_POS_CENTER = 0.5;
-static const double ATTACH_POS_BOTTOM = 1;
-static const double ATTACH_POS_LEFT = ATTACH_POS_TOP;
-static const double ATTACH_POS_RIGHT = ATTACH_POS_BOTTOM;
-
-
-//! @brief  The ConnEnd class represents different possible endpoints for 
-//!         connectors.
-//!
-//! Currently this class just allows free-floating endpoints, but in future
-//! will be capable of representing attachments to connection points on shapes.
-//! 
-class ConnEnd 
+class AVOID_EXPORT Checkpoint
 {
     public:
-        //! @brief Constructs a ConnEnd from a free-floating point.
-        //!
-        //! @param[in]  point  The position of the connector endpoint.
+        //! @brief  A point that a route must visit.
         //!
-        ConnEnd(const Point& point);
-
-        //! @brief Constructs a ConnEnd from a free-floating point as well
-        //!        as a set of flags specifying visibility for this point 
-        //!        if it is located inside a shape.
+        //! The connector will be able to enter and leave this checkpoint from 
+        //! any direction.
         //!
-        //! @param[in]  point    The position of the connector endpoint.
-        //! @param[in]  visDirs  One or more Avoid::ConnDirFlag options 
-        //!                      specifying the directions that this point 
-        //!                      should be given visibility if it is inside 
-        //!                      a shape.
+        //! @param[in] p  The Point that must be visited.
+        Checkpoint(const Point& p)
+            : point(p),
+              arrivalDirections(ConnDirAll),
+              departureDirections(ConnDirAll)
+        {
+        }
+        //! @brief  A point that a route must visit.
         //!
-        ConnEnd(const Point& point, const ConnDirFlags visDirs);
-
-        ConnEnd(ShapeRef *shapeRef, const double x_pos, const double y_pos,
-                const double insideOffset = 0.0,
-                const ConnDirFlags visDirs = ConnDirNone);
-
-        //! @brief Returns the position of this connector endpoint
+        //! The connector will be able to enter and leave this checkpoint from 
+        //! the directions specified.  Give Avoid::ConnDirAll to specify all
+        //! directions.
         //!
-        //! @return The position of this connector endpoint.
-        const Point point(void) const;
+        //! @param[in] p  The Point that must be visited.
+        //! @param[in] ad Avoid::ConnDirFlags denoting arrival directions for
+        //!               the connector portion leading up to this checkpoint.
+        //! @param[in] dd Avoid::ConnDirFlags denoting departure directions 
+        //!               for the connector portion leading away from this 
+        //!               checkpoint.
+        Checkpoint(const Point& p, ConnDirFlags ad, ConnDirFlags dd)
+            : point(p),
+              arrivalDirections(ad),
+              departureDirections(dd)
+        {
+        }
+        // Default constructor.
+        Checkpoint()
+            : point(Point()),
+              arrivalDirections(ConnDirAll),
+              departureDirections(ConnDirAll)
+        {
+        }
 
-        ConnDirFlags directions(void) const;
-    private:
-        Point _point;
-        ConnDirFlags _directions;
-        
-        // For referencing ConnEnds
-        ShapeRef *_shapeRef;
-        double _xPosition;
-        double _yPosition;
-        double _insideOffset;
+        Point point;
+        ConnDirFlags arrivalDirections;
+        ConnDirFlags departureDirections;
 };
 
 
@@ -161,13 +128,38 @@ class ConnEnd
 //! Usually, it is expected that you would create a ConnRef for each connector 
 //! in your diagram and keep that reference in your own connector class.
 //!
-class ConnRef
+class AVOID_EXPORT ConnRef
 {
     public:
         //! @brief Constructs a connector with no endpoints specified.
         //!
+        //! The constructor requires a valid Router instance.  This router
+        //! will take ownership of the connector.  Hence, you should not
+        //! call the destructor yourself, but should instead call
+        //! Router::deleteConnector() and the router instance will remove
+        //! and then free the connector's memory.
+        //!
+        //! @note Regarding IDs:
+        //!       You can let libavoid manually handle IDs by not specifying
+        //!       them.  Alternatively, you can specify all IDs yourself, but 
+        //!       you must be careful to makes sure that each object in the 
+        //!       scene (shape, connector, cluster, etc) is given a unique, 
+        //!       positive ID.  This uniqueness is checked if assertions are
+        //!       enabled, but if not and there are clashes then strange 
+        //!       things can happen.
+        //!
         //! @param[in]  router  The router scene to place the connector into.
-        //! @param[in]  id      A unique positive integer ID for the connector.  
+        //! @param[in]  id      Optionally, a positive integer ID unique
+        //!                     among all objects.
+        //!
+        ConnRef(Router *router, const unsigned int id = 0);
+        //! @brief Constructs a connector with endpoints specified.
+        //!
+        //! The constructor requires a valid Router instance.  This router
+        //! will take ownership of the connector.  Hence, you should not
+        //! call the destructor yourself, but should instead call
+        //! Router::deleteConnector() and the router instance will remove
+        //! and then free the connector's memory.
         //!
         //! If an ID is not specified, then one will be assigned to the shape.
         //! If assigning an ID yourself, note that it should be a unique 
@@ -175,42 +167,58 @@ class ConnRef
         //! so the same ID cannot be given to a shape and a connector for 
         //! example.
         //!
-        ConnRef(Router *router, const unsigned int id = 0);
-        //! @brief Constructs a connector with endpoints specified.
-        //!
         //! @param[in]  router  The router scene to place the connector into.
         //! @param[in]  id      A unique positive integer ID for the connector.
         //! @param[in]  src     The source endpoint of the connector.
         //! @param[in]  dst     The destination endpoint of the connector.
         //!
-        //! If an ID is not specified, then one will be assigned to the shape.
-        //! If assigning an ID yourself, note that it should be a unique 
-        //! positive integer.  Also, IDs are given to all objects in a scene,
-        //! so the same ID cannot be given to a shape and a connector for 
-        //! example.
-        //!
         ConnRef(Router *router, const ConnEnd& src, const ConnEnd& dst,
                 const unsigned int id = 0);
-        //! @brief  Destuctor.
+
+// To prevent C++ objects from being destroyed in garbage collected languages
+// when the libraries are called from SWIG, we hide the declarations of the
+// destructors and prevent generation of default destructors.
+#ifndef SWIG
+        //! @brief  Connector reference destuctor.
+        //!
+        //! Do not call this yourself, instead call
+        //! Router::deleteConnector().  Ownership of this object
+        //! belongs to the router scene.
         ~ConnRef();
-        
-        //! @brief  Sets both new source and destination endpoints for this 
+#endif        
+        //! @brief  Sets both a new source and destination endpoint for this 
         //!         connector.
         //!
+        //! If the router is using transactions, then this action will occur
+        //! the next time Router::processTransaction() is called.  See
+        //! Router::setTransactionUse() for more information.
+        //!
         //! @param[in]  srcPoint  New source endpoint for the connector.
         //! @param[in]  dstPoint  New destination endpoint for the connector.
         void setEndpoints(const ConnEnd& srcPoint, const ConnEnd& dstPoint);
+        
         //! @brief  Sets just a new source endpoint for this connector.
         //!
+        //! If the router is using transactions, then this action will occur
+        //! the next time Router::processTransaction() is called.  See
+        //! Router::setTransactionUse() for more information.
+        //!
         //! @param[in]  srcPoint  New source endpoint for the connector.
         void setSourceEndpoint(const ConnEnd& srcPoint);
+        
         //! @brief  Sets just a new destination endpoint for this connector.
         //!
+        //! If the router is using transactions, then this action will occur
+        //! the next time Router::processTransaction() is called.  See
+        //! Router::setTransactionUse() for more information.
+        //!
         //! @param[in]  dstPoint  New destination endpoint for the connector.
         void setDestEndpoint(const ConnEnd& dstPoint);
+        
         //! @brief   Returns the ID of this connector.
         //! @returns The ID of the connector. 
         unsigned int id(void) const;
+        
         //! @brief   Returns a pointer to the router scene this connector is in.
         //! @returns A pointer to the router scene for this connector.
         Router *router(void) const;
@@ -219,7 +227,8 @@ class ConnRef
         //!          new route and thus needs to be repainted.
         //!
         //! If the connector has been rerouted and need repainting, the  
-        //! route() method can be called to get a reference to the new route.
+        //! displayRoute() method can be called to get a reference to the 
+        //! new route.
         //!
         //! @returns Returns true if the connector requires repainting, or 
         //!          false if it does not.
@@ -261,10 +270,12 @@ class ConnRef
         //! @param[in]  ptr  A generic pointer that will be passed to the 
         //!                  callback function.
         void setCallback(void (*cb)(void *), void *ptr);
+        
         //! @brief   Returns the type of routing performed for this connector.
         //! @return  The type of routing performed.
         //!
         ConnType routingType(void) const;
+        
         //! @brief       Sets the type of routing to be performed for this 
         //!              connector.
         //! 
@@ -276,108 +287,212 @@ class ConnRef
         //! @param type  The type of routing to be performed.
         //!
         void setRoutingType(ConnType type);
-
        
+        //! @brief   Splits a connector in the centre of the segmentNth 
+        //!          segment and creates a junction point there as well 
+        //!          as a second connector.
+        //!
+        //! The new junction and connector will be automatically added to 
+        //! the router scene.  A slight preference will be given to the 
+        //! connectors connecting to the junction in the same orientation
+        //! the line segment already existed in.
+        //!
+        //! @return  A pair containing pointers to the new JunctionRef and 
+        //!          ConnRef.
+        std::pair<JunctionRef *, ConnRef *> splitAtSegment(
+                const size_t segmentN);
+
+        //! @brief  Allows the user to specify a set of checkpoints that this
+        //!         connector will route via.
+        //!
+        //! When routing, the connector will attempt to visit each of the 
+        //! points in the checkpoints list in order.  It will route from the
+        //! source point to the first checkpoint, to the second checkpoint, 
+        //! etc.  If a checkpoint is unreachable because it lies inside an
+        //! obstacle, then that checkpoint will be skipped.
+        //! 
+        //! @param[in] checkpoints  An ordered list of Checkpoints that the 
+        //!                         connector will attempt to route via.
+        void setRoutingCheckpoints(const std::vector<Checkpoint>& checkpoints);
+
+        //! @brief   Returns the current set of routing checkpoints for this
+        //!          connector.
+        //! @returns The ordered list of Checkpoints that this connector will 
+        //!          route via.
+        std::vector<Checkpoint> routingCheckpoints(void) const;
+        
+        //! @brief   Returns ConnEnds specifying what this connector is 
+        //!          attached to.
+        //!
+        //! This may be useful during hyperedge rerouting.  You can check the 
+        //! type and properties of the ConnEnd objects to find out what this 
+        //! connector is attached to.  The ConnEnd::type() will be ConnEndEmpty
+        //! if the connector has not had its endpoints initialised.
+        //!
+        //! @note  If the router is using transactions, you might get 
+        //!        unexpected results if you call this after changing objects
+        //!        but before calling Router::processTransaction().  In this
+        //!        case changes to ConnEnds for the connector may be queued 
+        //!        and not yet applied, so you will get old (or empty) values.
+        //!
+        //! @returns A pair of ConnEnd objects specifying what the connector
+        //!          is attached to.
+        //!
+        std::pair<ConnEnd, ConnEnd> endpointConnEnds(void) const;
 
         // @brief   Returns the source endpoint vertex in the visibility graph.
         // @returns The source endpoint vertex.
-        VertInf *src(void);
+        VertInf *src(void) const;
         // @brief   Returns the destination endpoint vertex in the 
         //          visibility graph.
         // @returns The destination endpoint vertex.
-        VertInf *dst(void);
+        VertInf *dst(void) const;
         
+        //! @brief  Sets a fixed user-specified route for this connector.
+        //!
+        //! libavoid will no longer calculate object-avoiding paths for this
+        //! connector but instead just return the specified route.  The path
+        //! of this connector will still be considered for the purpose of 
+        //! nudging and routing other non-fixed connectors.
+        //!
+        //! @note  This will reset the endpoints of the connector to the two
+        //!        ends of the given route, which may cause it to become 
+        //!        dettached from any shapes or junctions.  You can
+        //!        alternatively call setFixedExistingRoute() for connectors
+        //!        with valid routes in hyperedges that you would like to
+        //!        remain attached.
+        //!
+        //! @param[in] route  The new fixed route for the connector.
+        //! @sa  setFixedExistingRoute()
+        //! @sa  clearFixedRoute()
+        //!
+        void setFixedRoute(const PolyLine& route);
+
+        //! @brief  Sets a fixed existing route for this connector.
+        //!
+        //! libavoid will no longer calculate object-avoiding paths for this
+        //! connector but instead just return the current exisitng route.  
+        //! The path of this connector will still be considered for the 
+        //! purpose of nudging and routing other non-fixed connectors.
+        //!
+        //! @note  The endpoints of this connector will remain at their current
+        //!        positions, even while remaining 'attached' to shapes 
+        //!        or junctions that move.
+        //!
+        //! @sa  setFixedRoute()
+        //! @sa  clearFixedRoute()
+        //!
+        void setFixedExistingRoute(void);
+
+        //! @brief  Returns whether the connector route is marked as fixed.
+        //!
+        //! @return True if the connector route is fixed, false otherwise.
+        //!
+        bool hasFixedRoute(void) const;
+
+        //! @brief  Returns the connector to being automatically routed if it
+        //!         was marked as fixed.
+        //!
+        //! @sa  setFixedRoute()
+        //!
+        void clearFixedRoute(void);
 
         void set_route(const PolyLine& route);
         void calcRouteDist(void);
-        void setEndPointId(const unsigned int type, const unsigned int id);
-        unsigned int getSrcShapeId(void);
-        unsigned int getDstShapeId(void);
         void makeActive(void);
         void makeInactive(void);
         VertInf *start(void);
         void removeFromGraph(void);
-        bool isInitialised(void);
+        bool isInitialised(void) const;
         void makePathInvalid(void);
         void setHateCrossings(bool value);
-        bool doesHateCrossings(void);
+        bool doesHateCrossings(void) const;
         void setEndpoint(const unsigned int type, const ConnEnd& connEnd);
         bool setEndpoint(const unsigned int type, const VertID& pointID, 
                 Point *pointSuggestion = NULL);
+        std::vector<Point> possibleDstPinPoints(void) const;
     
     private:
         friend class Router;
+        friend class ConnEnd;
+        friend class JunctionRef;
+        friend class ConnRerouteFlagDelegate;
+        friend class HyperedgeImprover;
+        friend struct HyperedgeTreeEdge;
+        friend struct HyperedgeTreeNode;
+        friend class HyperedgeRerouter;
 
         PolyLine& routeRef(void);
         void freeRoutes(void);
         void performCallback(void);
         bool generatePath(void);
-        bool generatePath(Point p0, Point p1);
+        void generateCheckpointsPath(std::vector<Point>& path,
+                std::vector<VertInf *>& vertices);
+        void generateStandardPath(std::vector<Point>& path,
+                std::vector<VertInf *>& vertices);
         void unInitialise(void);
         void updateEndPoint(const unsigned int type, const ConnEnd& connEnd);
-        void common_updateEndPoint(const unsigned int type, const ConnEnd& connEnd);
-        Router *_router;
-        unsigned int _id;
-        ConnType _type;
-        unsigned int _srcId, _dstId;
-        bool _orthogonal;
-        bool _needs_reroute_flag;
-        bool _false_path;
-        bool _needs_repaint;
-        bool _active;
-        PolyLine _route;
-        Polygon _display_route;
-        double _route_dist;
-        ConnRefList::iterator _pos;
-        VertInf *_srcVert;
-        VertInf *_dstVert;
-        VertInf *_startVert;
-        bool _initialised;
-        void (*_callback)(void *);
-        void *_connector;
-        bool _hateCrossings;
-};
-
-
-class PointRep;
-typedef std::set<PointRep *> PointRepSet;
-typedef std::list<PointRep *> PointRepList;
-
-class PointRep
-{
-    public:
-        PointRep(Point *p, const ConnRef *c)
-            : point(p),
-              conn(c)
-
-        {
-        }
-        bool follow_inner(PointRep *target);
-
-        Point *point;
-        const ConnRef *conn;
-        // inner_set: Set of pointers to the PointReps 'inner' of 
-        // this one, at this corner.
-        PointRepSet inner_set;
+        void common_updateEndPoint(const unsigned int type, ConnEnd connEnd);
+        void freeActivePins(void);
+        bool getConnEndForEndpointVertex(VertInf *vertex, ConnEnd& connEnd) 
+                const;
+        std::pair<Obstacle *, Obstacle *> endpointAnchors(void) const;
+        void outputCode(FILE *fp) const;
+        std::pair<bool, bool> assignConnectionPinVisibility(const bool connect);
+
+
+        Router *m_router;
+        unsigned int m_id;
+        ConnType m_type;
+        bool *m_reroute_flag_ptr;
+        bool m_needs_reroute_flag:1;
+        bool m_false_path:1;
+        bool m_needs_repaint:1;
+        bool m_active:1;
+        bool m_initialised:1;
+        bool m_hate_crossings:1;
+        bool m_has_fixed_route:1;
+        PolyLine m_route;
+        Polygon m_display_route;
+        double m_route_dist;
+        ConnRefList::iterator m_connrefs_pos;
+        VertInf *m_src_vert;
+        VertInf *m_dst_vert;
+        VertInf *m_start_vert;
+        void (*m_callback_func)(void *);
+        void *m_connector;
+        ConnEnd *m_src_connend;
+        ConnEnd *m_dst_connend;
+        std::vector<Checkpoint> m_checkpoints;
+        std::vector<VertInf *> m_checkpoint_vertices;
 };
 
 
 typedef std::pair<Point *, ConnRef *> PtConnPtrPair;
 
+typedef std::vector< PtConnPtrPair > PointRepVector;
+typedef std::list<std::pair<size_t, size_t> > NodeIndexPairLinkList;
+
 class PtOrder
 {
     public:
-        PtOrder()
-        {
-        }
+        PtOrder();
         ~PtOrder();
-        bool addPoints(const int dim, PtConnPtrPair innerArg, 
-                PtConnPtrPair outerArg, bool swapped);
-        void sort(const int dim);
-        int positionFor(const ConnRef *conn, const size_t dim) const;
+        void addPoints(const size_t dim, const PtConnPtrPair& arg1, 
+                const PtConnPtrPair& arg2);
+        void addOrderedPoints(const size_t dim, const PtConnPtrPair& innerArg, 
+                const PtConnPtrPair& outerArg, bool swapped);
+        int positionFor(const size_t dim, const ConnRef *conn);
+        PointRepVector sortedPoints(const size_t dim);
+    private:
+        size_t insertPoint(const size_t dim, const PtConnPtrPair& point);
+        void sort(const size_t dim);
 
         // One for each dimension.
-        PointRepList connList[2];
+        bool sorted[2];
+        PointRepVector nodes[2];
+        NodeIndexPairLinkList links[2];
+        PointRepVector sortedConnVector[2];
 };
 
 typedef std::map<Avoid::Point,PtOrder> PtOrderMap;
@@ -392,12 +507,35 @@ const unsigned int CROSSING_SHARES_FIXED_SEGMENT = 8;
 
 
 typedef std::pair<int, unsigned int> CrossingsInfoPair;
+typedef std::vector<Avoid::Point> PointList;
+typedef std::vector<PointList> SharedPathList;
+
+class ConnectorCrossings
+{
+    public:
+        ConnectorCrossings(Avoid::Polygon& poly, bool polyIsConn, 
+                Avoid::Polygon& conn, ConnRef *polyConnRef = NULL, 
+                ConnRef *connConnRef = NULL);
+        void clear(void);
+        void countForSegment(size_t cIndex, const bool finalSegment);
+
+        Avoid::Polygon& poly;
+        bool polyIsConn; 
+        Avoid::Polygon& conn; 
+        bool checkForBranchingSegments;
+        ConnRef *polyConnRef;
+        ConnRef *connConnRef;
+        
+        unsigned int crossingCount;
+        unsigned int crossingFlags;
+        PointSet *crossingPoints;
+        PtOrderMap *pointOrders;
+        SharedPathList *sharedPaths;
+        
+        double firstSharedPathAtEndLength;
+        double secondSharedPathAtEndLength;
+};
 
-extern CrossingsInfoPair countRealCrossings( Avoid::Polygon& poly, 
-        bool polyIsConn, Avoid::Polygon& conn, size_t cIndex, 
-        bool checkForBranchingSegments, const bool finalSegment = false, 
-        PointSet *crossingPoints = NULL, PtOrderMap *pointOrders = NULL, 
-        ConnRef *polyConnRef = NULL, ConnRef *connConnRef = NULL);
 extern void splitBranchingSegments(Avoid::Polygon& poly, bool polyIsConn,
         Avoid::Polygon& conn, const double tolerance = 0);
 extern bool validateBendPoint(VertInf *aInf, VertInf *bInf, VertInf *cInf);