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