1 /*
2  * vim: ts=4 sw=4 et tw=0 wm=0
3  *
4  * libavoid - Fast, Incremental, Object-avoiding Line Router
5  *
6  * Copyright (C) 2011-2014  Monash University
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  * See the file LICENSE.LGPL distributed with the library.
13  *
14  * Licensees holding a valid commercial license may use this file in
15  * accordance with the commercial license agreement provided with the
16  * library.
17  *
18  * This library is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21  *
22  * Author(s):   Michael Wybrow
23 */
24 
25 #ifndef AVOID_HYPEREDGETREE_H
26 #define AVOID_HYPEREDGETREE_H
27 
28 #include <cstdio>
29 #include <list>
30 #include <map>
31 #include <set>
32 #include <utility>
33 
34 #include "libavoid/geomtypes.h"
35 
36 //#define MAJOR_HYPEREDGE_IMPROVEMENT_DEBUG
37 
38 namespace Avoid {
39 
40 // These classes are not intended for public use.
41 // They are used to represent a hyperedge as a tree that certain
42 // transformations can be easily performed on to improve the routing
43 // of the hyperedge.
44 
45 class JunctionRef;
46 class ConnRef;
47 class HyperedgeShiftSegment;
48 class VertInf;
49 class Router;
50 
51 struct HyperedgeTreeEdge;
52 struct HyperedgeTreeNode;
53 
54 typedef std::map<JunctionRef *, HyperedgeTreeNode *>
55         JunctionHyperedgeTreeNodeMap;
56 typedef std::set<JunctionRef *> JunctionSet;
57 typedef std::list<JunctionRef *> JunctionRefList;
58 typedef std::list<ConnRef *> ConnRefList;
59 
60 class CmpNodesInDim;
61 
62 typedef std::set<HyperedgeTreeNode *, CmpNodesInDim> OrderedHENodeSet;
63 
64 struct HyperedgeTreeNode
65 {
66     HyperedgeTreeNode();
67     ~HyperedgeTreeNode();
68 
69     void deleteEdgesExcept(HyperedgeTreeEdge *ignored);
70     bool removeOtherJunctionsFrom(HyperedgeTreeEdge *ignored,
71             JunctionSet &treeRoots);
72     void outputEdgesExcept(FILE *fp, HyperedgeTreeEdge *ignored);
73     void disconnectEdge(HyperedgeTreeEdge *edge);
74     void spliceEdgesFrom(HyperedgeTreeNode *oldNode);
75     void writeEdgesToConns(HyperedgeTreeEdge *ignored, size_t pass);
76     void addConns(HyperedgeTreeEdge *ignored, Router *router,
77             ConnRefList& oldConns, ConnRef *conn);
78     void updateConnEnds(HyperedgeTreeEdge *ignored, bool forward,
79             ConnRefList& changedConns);
80     void listJunctionsAndConnectors(HyperedgeTreeEdge *ignored,
81             JunctionRefList& junctions, ConnRefList& connectors);
82     bool isImmovable(void) const;
83     void validateHyperedge(const HyperedgeTreeEdge *ignored,
84             const size_t dist) const;
85 
86     std::list<HyperedgeTreeEdge *> edges;
87     JunctionRef *junction;
88     Point point;
89     OrderedHENodeSet *shiftSegmentNodeSet;
90     VertInf *finalVertex;
91     bool isConnectorSource;
92     bool isPinDummyEndpoint;
93     bool visited;
94 };
95 
96 struct HyperedgeTreeEdge
97 {
98     HyperedgeTreeEdge(HyperedgeTreeNode *node1, HyperedgeTreeNode *node2,
99             ConnRef *conn);
100 
101     HyperedgeTreeNode *followFrom(HyperedgeTreeNode *from) const;
102     bool zeroLength(void) const;
103     void splitFromNodeAtPoint(HyperedgeTreeNode *source, const Point& point);
104     bool hasOrientation(const size_t dimension) const;
105     void outputNodesExcept(FILE *file, HyperedgeTreeNode *ignored);
106     void deleteNodesExcept(HyperedgeTreeNode *ignored);
107     bool removeOtherJunctionsFrom(HyperedgeTreeNode *ignored,
108             JunctionSet &treeRoots);
109     void writeEdgesToConns(HyperedgeTreeNode *ignored, size_t pass);
110     void addConns(HyperedgeTreeNode *ignored, Router *router,
111             ConnRefList& oldConns);
112     void updateConnEnds(HyperedgeTreeNode *ignored, bool forward,
113             ConnRefList& changedConns);
114     void disconnectEdge(void);
115     void replaceNode(HyperedgeTreeNode *oldNode,
116             HyperedgeTreeNode *newNode);
117     void listJunctionsAndConnectors(HyperedgeTreeNode *ignored,
118             JunctionRefList& junctions, ConnRefList& connectors);
119     void validateHyperedge(const HyperedgeTreeNode *ignored,
120             const size_t dist) const;
121 
122     std::pair<HyperedgeTreeNode *, HyperedgeTreeNode *> ends;
123     ConnRef *conn;
124     bool hasFixedRoute;
125 };
126 
127 
128 typedef std::map<VertInf *, HyperedgeTreeNode *> VertexNodeMap;
129 
130 
131 class CmpNodesInDim
132 {
133     public:
134         CmpNodesInDim(const size_t dim);
135         bool operator()(const HyperedgeTreeNode *lhs,
136                 const HyperedgeTreeNode *rhs) const;
137     private:
138         const size_t m_dimension;
139 };
140 
141 }
142 
143 #endif
144