File indexing completed on 2024-05-19 09:39:46

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(&currentList, &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(&currentList, 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"