File indexing completed on 2025-02-16 08:27:28
0001 /*************************************************************************** 0002 * Copyright (C) 2004-2005 by David Saxton * 0003 * david@bluehaze.org * 0004 * * 0005 * This program is free software; you can redistribute it and/or modify * 0006 * it under the terms of the GNU General Public License as published by * 0007 * the Free Software Foundation; either version 2 of the License, or * 0008 * (at your option) any later version. * 0009 ***************************************************************************/ 0010 0011 #include "nodegroup.h" 0012 #include "connector.h" 0013 #include "conrouter.h" 0014 #include "icndocument.h" 0015 #include "node.h" 0016 0017 #include <cassert> 0018 #include <cstdlib> 0019 0020 #include <ktechlab_debug.h> 0021 0022 NodeGroup::NodeGroup(ICNDocument *icnDocument) 0023 : QObject(icnDocument) 0024 { 0025 p_icnDocument = icnDocument; 0026 b_visible = true; 0027 } 0028 0029 NodeGroup::~NodeGroup() 0030 { 0031 clearConList(); 0032 0033 m_extNodeList.removeAll(static_cast<Node *>(nullptr)); 0034 const NodeList::iterator xnEnd = m_extNodeList.end(); 0035 for (NodeList::iterator it = m_extNodeList.begin(); it != xnEnd; ++it) 0036 (*it)->setNodeGroup(nullptr); 0037 m_extNodeList.clear(); 0038 0039 m_nodeList.removeAll(static_cast<Node *>(nullptr)); 0040 const NodeList::iterator nEnd = m_nodeList.end(); 0041 for (NodeList::iterator it = m_nodeList.begin(); it != nEnd; ++it) 0042 (*it)->setNodeGroup(nullptr); 0043 m_nodeList.clear(); 0044 } 0045 0046 void NodeGroup::setVisible(bool visible) 0047 { 0048 if (b_visible == visible) 0049 return; 0050 0051 b_visible = visible; 0052 0053 m_nodeList.removeAll(static_cast<Node *>(nullptr)); 0054 const NodeList::iterator nEnd = m_nodeList.end(); 0055 for (NodeList::iterator it = m_nodeList.begin(); it != nEnd; ++it) 0056 (*it)->setVisible(visible); 0057 } 0058 0059 void NodeGroup::addNode(Node *node, bool checkSurrouding) 0060 { 0061 if (!node || node->isChildNode() || m_nodeList.contains(node)) { 0062 return; 0063 } 0064 0065 m_nodeList.append(node); 0066 node->setNodeGroup(this); 0067 node->setVisible(b_visible); 0068 0069 if (checkSurrouding) { 0070 ConnectorList con = node->getAllConnectors(); 0071 ConnectorList::iterator end = con.end(); 0072 for (ConnectorList::iterator it = con.begin(); it != end; ++it) { 0073 if (*it) { 0074 // maybe we can put here a check, because only 1 of there checks should pass 0075 if ((*it)->startNode() != node) 0076 addNode((*it)->startNode(), true); 0077 if ((*it)->endNode() != node) 0078 addNode((*it)->endNode(), true); 0079 } 0080 } 0081 } 0082 } 0083 0084 void NodeGroup::translate(int dx, int dy) 0085 { 0086 if ((dx == 0) && (dy == 0)) 0087 return; 0088 0089 m_conList.removeAll(static_cast<Connector *>(nullptr)); 0090 m_nodeList.removeAll(static_cast<Node *>(nullptr)); 0091 0092 const ConnectorList::iterator conEnd = m_conList.end(); 0093 for (ConnectorList::iterator it = m_conList.begin(); it != conEnd; ++it) { 0094 (*it)->updateConnectorPoints(false); 0095 (*it)->translateRoute(dx, dy); 0096 } 0097 0098 const NodeList::iterator nodeEnd = m_nodeList.end(); 0099 for (NodeList::iterator it = m_nodeList.begin(); it != nodeEnd; ++it) 0100 (*it)->moveBy(dx, dy); 0101 } 0102 0103 void NodeGroup::updateRoutes() 0104 { 0105 resetRoutedMap(); 0106 0107 // Basic algorithm used here: starting with the external nodes, find the 0108 // pair with the shortest distance between them. Route the connectors 0109 // between the two nodes appropriately. Remove that pair of nodes from the 0110 // list, and add the nodes along the connector route (which have been spaced 0111 // equally along the route). Repeat until all the nodes are connected. 0112 0113 const ConnectorList::iterator conEnd = m_conList.end(); 0114 for (ConnectorList::iterator it = m_conList.begin(); it != conEnd; ++it) { 0115 if (*it) 0116 (*it)->updateConnectorPoints(false); 0117 } 0118 0119 Node *n1, *n2; 0120 NodeList currentList = m_extNodeList; 0121 while (!currentList.isEmpty()) { 0122 findBestPair(¤tList, &n1, &n2); 0123 if (n1 == nullptr || n2 == nullptr) { 0124 return; 0125 } 0126 NodeList route = findRoute(n1, n2); 0127 currentList += route; 0128 0129 ConRouter cr(p_icnDocument); 0130 cr.mapRoute(int(n1->x()), int(n1->y()), int(n2->x()), int(n2->y())); 0131 if (cr.pointList(false).size() <= 0) { 0132 qCDebug(KTL_LOG) << "no ConRouter points, giving up"; 0133 return; // continue might get to an infinite loop 0134 } 0135 QPointListList pl = cr.dividePoints(route.size() + 1); 0136 0137 const NodeList::iterator routeEnd = route.end(); 0138 const QPointListList::iterator plEnd = pl.end(); 0139 Node *prev = n1; 0140 NodeList::iterator routeIt = route.begin(); 0141 for (QPointListList::iterator it = pl.begin(); it != plEnd; ++it) { 0142 Node *next = (routeIt == routeEnd) ? n2 : static_cast<Node *>(*(routeIt++)); 0143 removeRoutedNodes(¤tList, prev, next); 0144 QPointList pointList = *it; 0145 if (!pointList.isEmpty() && prev != n1) { 0146 QPoint first = pointList.first(); 0147 prev->moveBy(first.x() - prev->x(), first.y() - prev->y()); 0148 } 0149 Connector *con = findCommonConnector(prev, next); 0150 if (con) { 0151 con->updateConnectorPoints(false); 0152 con->setRoutePoints(pointList, false, false); 0153 con->updateConnectorPoints(true); 0154 // con->conRouter()->setPoints( &pointList, con->startNode() != prev ); 0155 // con->conRouter()->setPoints( &pointList, con->pointsAreReverse( &pointList ) ); 0156 // con->calcBoundingPoints(); 0157 } 0158 prev = next; 0159 } 0160 } 0161 } 0162 0163 NodeList NodeGroup::findRoute(Node *startNode, Node *endNode) 0164 { 0165 NodeList nl; 0166 if (!startNode || !endNode || startNode == endNode) { 0167 return nl; 0168 } 0169 0170 IntList temp; 0171 IntList il = findRoute(temp, getNodePos(startNode), getNodePos(endNode)); 0172 0173 const IntList::iterator end = il.end(); 0174 for (IntList::iterator it = il.begin(); it != end; ++it) { 0175 Node *node = getNodePtr(*it); 0176 if (node) { 0177 nl += node; 0178 } 0179 } 0180 0181 nl.removeAll(startNode); 0182 nl.removeAll(endNode); 0183 0184 return nl; 0185 } 0186 0187 IntList NodeGroup::findRoute(IntList used, int currentNode, int endNode, bool *success) 0188 { 0189 bool temp; 0190 if (!success) { 0191 success = &temp; 0192 } 0193 *success = false; 0194 0195 if (!used.contains(currentNode)) { 0196 used.append(currentNode); 0197 } 0198 0199 if (currentNode == endNode) { 0200 *success = true; 0201 return used; 0202 } 0203 0204 const uint n = m_nodeList.size() + m_extNodeList.size(); 0205 for (uint i = 0; i < n; ++i) { 0206 if (b_routedMap[i * n + currentNode] && !used.contains(i)) { 0207 IntList il = findRoute(used, i, endNode, success); 0208 if (*success) { 0209 return il; 0210 } 0211 } 0212 } 0213 0214 IntList il; 0215 return il; 0216 } 0217 0218 Connector *NodeGroup::findCommonConnector(Node *n1, Node *n2) 0219 { 0220 if (!n1 || !n2 || n1 == n2) { 0221 return nullptr; 0222 } 0223 0224 ConnectorList n1Con = n1->getAllConnectors(); 0225 ConnectorList n2Con = n2->getAllConnectors(); 0226 0227 const ConnectorList::iterator end = n1Con.end(); 0228 for (ConnectorList::iterator it = n1Con.begin(); it != end; ++it) { 0229 if (n2Con.contains(*it)) { 0230 return *it; 0231 } 0232 } 0233 return nullptr; 0234 } 0235 0236 void NodeGroup::findBestPair(NodeList *list, Node **n1, Node **n2) 0237 { 0238 *n1 = nullptr; 0239 *n2 = nullptr; 0240 0241 if (list->size() < 2) { 0242 return; 0243 } 0244 0245 const NodeList::iterator end = list->end(); 0246 int shortest = 1 << 30; 0247 0248 // Try and find any that are aligned horizontally 0249 for (NodeList::iterator it1 = list->begin(); it1 != end; ++it1) { 0250 NodeList::iterator it2 = it1; 0251 for (++it2; it2 != end; ++it2) { 0252 if (*it1 != *it2 && (*it1)->y() == (*it2)->y() && canRoute(*it1, *it2)) { 0253 const int distance = std::abs(int((*it1)->x() - (*it2)->x())); 0254 if (distance < shortest) { 0255 shortest = distance; 0256 *n1 = *it1; 0257 *n2 = *it2; 0258 } 0259 } 0260 } 0261 } 0262 if (*n1) { 0263 return; 0264 } 0265 0266 // Try and find any that are aligned vertically 0267 for (NodeList::iterator it1 = list->begin(); it1 != end; ++it1) { 0268 NodeList::iterator it2 = it1; 0269 for (++it2; it2 != end; ++it2) { 0270 if (*it1 != *it2 && (*it1)->x() == (*it2)->x() && canRoute(*it1, *it2)) { 0271 const int distance = std::abs(int((*it1)->y() - (*it2)->y())); 0272 if (distance < shortest) { 0273 shortest = distance; 0274 *n1 = *it1; 0275 *n2 = *it2; 0276 } 0277 } 0278 } 0279 } 0280 if (*n1) { 0281 return; 0282 } 0283 0284 // Now, lets just find the two closest nodes 0285 for (NodeList::iterator it1 = list->begin(); it1 != end; ++it1) { 0286 NodeList::iterator it2 = it1; 0287 for (++it2; it2 != end; ++it2) { 0288 if (*it1 != *it2 && canRoute(*it1, *it2)) { 0289 const int dx = int((*it1)->x() - (*it2)->x()); 0290 const int dy = int((*it1)->y() - (*it2)->y()); 0291 const int distance = std::abs(dx) + std::abs(dy); 0292 if (distance < shortest) { 0293 shortest = distance; 0294 *n1 = *it1; 0295 *n2 = *it2; 0296 } 0297 } 0298 } 0299 } 0300 0301 if (!*n1) { 0302 qCCritical(KTL_LOG) << "NodeGroup::findBestPair: Could not find a routable pair of nodes!"; 0303 } 0304 } 0305 0306 bool NodeGroup::canRoute(Node *n1, Node *n2) 0307 { 0308 if (!n1 || !n2) { 0309 return false; 0310 } 0311 0312 IntList reachable; 0313 getReachable(&reachable, getNodePos(n1)); 0314 return reachable.contains(getNodePos(n2)); 0315 } 0316 0317 void NodeGroup::getReachable(IntList *reachable, int node) 0318 { 0319 if (!reachable || reachable->contains(node)) { 0320 return; 0321 } 0322 reachable->append(node); 0323 0324 const uint n = m_nodeList.size() + m_extNodeList.size(); 0325 assert(node < int(n)); 0326 for (uint i = 0; i < n; ++i) { 0327 if (b_routedMap[i * n + node]) { 0328 getReachable(reachable, i); 0329 } 0330 } 0331 } 0332 0333 void NodeGroup::resetRoutedMap() 0334 { 0335 const uint n = m_nodeList.size() + m_extNodeList.size(); 0336 0337 b_routedMap.resize(n * n); 0338 0339 const ConnectorList::iterator end = m_conList.end(); 0340 for (ConnectorList::iterator it = m_conList.begin(); it != end; ++it) { 0341 Connector *con = *it; 0342 if (con) { 0343 int n1 = getNodePos(con->startNode()); 0344 int n2 = getNodePos(con->endNode()); 0345 if (n1 != -1 && n2 != -1) { 0346 b_routedMap[n1 * n + n2] = b_routedMap[n2 * n + n1] = true; 0347 } 0348 } 0349 } 0350 } 0351 0352 void NodeGroup::removeRoutedNodes(NodeList *nodes, Node *n1, Node *n2) 0353 { 0354 if (!nodes) { 0355 return; 0356 } 0357 0358 // Lets get rid of any duplicate nodes in nodes (as a general cleaning operation) 0359 const NodeList::iterator end = nodes->end(); 0360 for (NodeList::iterator it = nodes->begin(); it != end; ++it) { 0361 // if ( nodes->contains(*it) > 1 ) { 0362 if (nodes->count(*it) > 1) { 0363 *it = nullptr; 0364 } 0365 } 0366 nodes->removeAll(static_cast<Node *>(nullptr)); 0367 0368 const int n1pos = getNodePos(n1); 0369 const int n2pos = getNodePos(n2); 0370 0371 if (n1pos == -1 || n2pos == -1) { 0372 return; 0373 } 0374 0375 const uint n = m_nodeList.size() + m_extNodeList.size(); 0376 0377 b_routedMap[n1pos * n + n2pos] = b_routedMap[n2pos * n + n1pos] = false; 0378 0379 bool n1HasCon = false; 0380 bool n2HasCon = false; 0381 0382 for (uint i = 0; i < n; ++i) { 0383 n1HasCon |= b_routedMap[n1pos * n + i]; 0384 n2HasCon |= b_routedMap[n2pos * n + i]; 0385 } 0386 0387 if (!n1HasCon) { 0388 nodes->removeAll(n1); 0389 } 0390 if (!n2HasCon) { 0391 nodes->removeAll(n2); 0392 } 0393 } 0394 0395 int NodeGroup::getNodePos(Node *n) 0396 { 0397 if (!n) { 0398 return -1; 0399 } 0400 int pos = m_nodeList.indexOf(n); 0401 if (pos != -1) { 0402 return pos; 0403 } 0404 pos = m_extNodeList.indexOf(n); 0405 if (pos != -1) { 0406 return pos + m_nodeList.size(); 0407 } 0408 return -1; 0409 } 0410 0411 Node *NodeGroup::getNodePtr(int n) 0412 { 0413 if (n < 0) { 0414 return nullptr; 0415 } 0416 const int a = m_nodeList.size(); 0417 if (n < a) { 0418 return m_nodeList[n]; 0419 } 0420 const int b = m_extNodeList.size(); 0421 if (n < a + b) { 0422 return m_extNodeList[n - a]; 0423 } 0424 return nullptr; 0425 } 0426 0427 void NodeGroup::clearConList() 0428 { 0429 const ConnectorList::iterator end = m_conList.end(); 0430 for (ConnectorList::iterator it = m_conList.begin(); it != end; ++it) { 0431 Connector *con = *it; 0432 if (con) { 0433 con->setNodeGroup(nullptr); 0434 disconnect(con, &Connector::removed, this, &NodeGroup::connectorRemoved); 0435 } 0436 } 0437 m_conList.clear(); 0438 } 0439 0440 void NodeGroup::init() 0441 { 0442 NodeList::iterator xnEnd = m_extNodeList.end(); 0443 for (NodeList::iterator it = m_extNodeList.begin(); it != xnEnd; ++it) { 0444 (*it)->setNodeGroup(nullptr); 0445 } 0446 m_extNodeList.clear(); 0447 0448 clearConList(); 0449 0450 // First, lets get all of our external nodes and internal connectors 0451 const NodeList::iterator nlEnd = m_nodeList.end(); 0452 for (NodeList::iterator nodeIt = m_nodeList.begin(); nodeIt != nlEnd; ++nodeIt) { 0453 // 2. rewrite 0454 ConnectorList conList = (*nodeIt)->getAllConnectors(); 0455 0456 ConnectorList::iterator conIt, conEnd = conList.end(); 0457 for (conIt = conList.begin(); conIt != conEnd; ++conIt) { 0458 Connector *con = *conIt; 0459 0460 // possible check: only 1 of these ifs should be true 0461 if (con->startNode() != *nodeIt) { 0462 addExtNode(con->startNode()); 0463 if (!m_conList.contains(con)) { 0464 m_conList += con; 0465 con->setNodeGroup(this); 0466 } 0467 } 0468 if (con->endNode() != *nodeIt) { 0469 addExtNode(con->endNode()); 0470 if (!m_conList.contains(con)) { 0471 m_conList += con; 0472 con->setNodeGroup(this); 0473 } 0474 } 0475 connect(con, &Connector::removed, this, &NodeGroup::connectorRemoved); 0476 } 0477 0478 // Connect the node up to us 0479 connect(*nodeIt, SIGNAL(removed(Node *)), this, SLOT(nodeRemoved(Node *))); 0480 } 0481 0482 // And connect up our external nodes 0483 xnEnd = m_extNodeList.end(); 0484 for (NodeList::iterator it = m_extNodeList.begin(); it != xnEnd; ++it) { 0485 // connect( *it, SIGNAL(moved(Node*)), this, SLOT(extNodeMoved()) ); 0486 connect(*it, SIGNAL(removed(Node *)), this, SLOT(nodeRemoved(Node *))); 0487 } 0488 } 0489 0490 void NodeGroup::nodeRemoved(Node *node) 0491 { 0492 // We are probably about to get deleted by ICNDocument anyway...so no point in doing anything 0493 m_nodeList.removeAll(node); 0494 node->setNodeGroup(nullptr); 0495 node->setVisible(true); 0496 m_extNodeList.removeAll(node); 0497 } 0498 0499 void NodeGroup::connectorRemoved(Connector *connector) 0500 { 0501 m_conList.removeAll(connector); 0502 } 0503 0504 void NodeGroup::addExtNode(Node *node) 0505 { 0506 if (!m_extNodeList.contains(node) && !m_nodeList.contains(node)) { 0507 m_extNodeList.append(node); 0508 node->setNodeGroup(this); 0509 } 0510 } 0511 0512 #include "moc_nodegroup.cpp"