1 /***************************************************************************
2 * Copyright (C) 2004-2005 by David Saxton *
3 * david@bluehaze.org *
4 * *
5 * This program is free software; you can redistribute it and/or modify *
6 * it under the terms of the GNU General Public License as published by *
7 * the Free Software Foundation; either version 2 of the License, or *
8 * (at your option) any later version. *
9 ***************************************************************************/
10
11 #include "icndocument.h"
12 #include "connector.h"
13 #include "conrouter.h"
14 #include "node.h"
15 #include "nodegroup.h"
16
17 #include <QDebug>
18 #include <cassert>
19 #include <cstdlib>
20
NodeGroup(ICNDocument * icnDocument,const char * name)21 NodeGroup::NodeGroup( ICNDocument *icnDocument, const char *name )
22 : QObject( icnDocument /*, name */ )
23 {
24 setObjectName(name);
25 p_icnDocument = icnDocument;
26 b_visible = true;
27 }
28
29
~NodeGroup()30 NodeGroup::~NodeGroup()
31 {
32 clearConList();
33
34 m_extNodeList.removeAll( (Node*)nullptr );
35 const NodeList::iterator xnEnd = m_extNodeList.end();
36 for ( NodeList::iterator it = m_extNodeList.begin(); it != xnEnd; ++it )
37 (*it)->setNodeGroup(nullptr);
38 m_extNodeList.clear();
39
40 m_nodeList.removeAll( (Node*)nullptr );
41 const NodeList::iterator nEnd = m_nodeList.end();
42 for ( NodeList::iterator it = m_nodeList.begin(); it != nEnd; ++it )
43 (*it)->setNodeGroup(nullptr);
44 m_nodeList.clear();
45 }
46
47
setVisible(bool visible)48 void NodeGroup::setVisible( bool visible )
49 {
50 if ( b_visible == visible )
51 return;
52
53 b_visible = visible;
54
55 m_nodeList.removeAll( (Node*)nullptr );
56 const NodeList::iterator nEnd = m_nodeList.end();
57 for ( NodeList::iterator it = m_nodeList.begin(); it != nEnd; ++it )
58 (*it)->setVisible(visible);
59 }
60
61
addNode(Node * node,bool checkSurrouding)62 void NodeGroup::addNode( Node *node, bool checkSurrouding )
63 {
64 if ( !node || node->isChildNode() || m_nodeList.contains(node) ) {
65 return;
66 }
67
68 m_nodeList.append(node);
69 node->setNodeGroup(this);
70 node->setVisible(b_visible);
71
72 if (checkSurrouding)
73 {
74 ConnectorList con = node->getAllConnectors();
75 ConnectorList::iterator end = con.end();
76 for ( ConnectorList::iterator it = con.begin(); it != end; ++it )
77 {
78 if (*it) {
79 // maybe we can put here a check, because only 1 of there checks should pass
80 if( (*it)->startNode() != node )
81 addNode( (*it)->startNode(), true );
82 if( (*it)->endNode() != node )
83 addNode( (*it)->endNode(), true );
84 }
85 }
86
87 }
88 }
89
90
translate(int dx,int dy)91 void NodeGroup::translate( int dx, int dy )
92 {
93 if ( (dx == 0) && (dy == 0) )
94 return;
95
96 m_conList.removeAll((Connector*)nullptr);
97 m_nodeList.removeAll((Node*)nullptr);
98
99 const ConnectorList::iterator conEnd = m_conList.end();
100 for ( ConnectorList::iterator it = m_conList.begin(); it != conEnd; ++it )
101 {
102 (*it)->updateConnectorPoints(false);
103 (*it)->translateRoute( dx, dy );
104 }
105
106 const NodeList::iterator nodeEnd = m_nodeList.end();
107 for ( NodeList::iterator it = m_nodeList.begin(); it != nodeEnd; ++it )
108 (*it)->moveBy( dx, dy );
109 }
110
111
updateRoutes()112 void NodeGroup::updateRoutes()
113 {
114 resetRoutedMap();
115
116 // Basic algorithm used here: starting with the external nodes, find the
117 // pair with the shortest distance between them. Route the connectors
118 // between the two nodes appropriately. Remove that pair of nodes from the
119 // list, and add the nodes along the connector route (which have been spaced
120 // equally along the route). Repeat until all the nodes are connected.
121
122
123 const ConnectorList::iterator conEnd = m_conList.end();
124 for ( ConnectorList::iterator it = m_conList.begin(); it != conEnd; ++it )
125 {
126 if (*it)
127 (*it)->updateConnectorPoints(false);
128 }
129
130 Node *n1, *n2;
131 NodeList currentList = m_extNodeList;
132 while ( !currentList.isEmpty() )
133 {
134 findBestPair( ¤tList, &n1, &n2 );
135 if ( n1 == nullptr || n2 == nullptr ) {
136 return;
137 }
138 NodeList route = findRoute( n1, n2 );
139 currentList += route;
140
141 ConRouter cr(p_icnDocument);
142 cr.mapRoute( (int)n1->x(), (int)n1->y(), (int)n2->x(), (int)n2->y() );
143 if (cr.pointList(false).size() <= 0) {
144 qDebug() << Q_FUNC_INFO << "no ConRouter points, giving up";
145 return; // continue might get to an infinite loop
146 }
147 QPointListList pl = cr.dividePoints( route.size()+1 );
148
149 const NodeList::iterator routeEnd = route.end();
150 const QPointListList::iterator plEnd = pl.end();
151 Node *prev = n1;
152 NodeList::iterator routeIt = route.begin();
153 for ( QPointListList::iterator it = pl.begin(); it != plEnd; ++it )
154 {
155 Node *next = (routeIt == routeEnd) ? n2 : (Node*)*(routeIt++);
156 removeRoutedNodes( ¤tList, prev, next );
157 QPointList pointList = *it;
158 if ( prev != n1 )
159 {
160 QPoint first = pointList.first();
161 prev->moveBy( first.x() - prev->x(), first.y() - prev->y() );
162 }
163 Connector *con = findCommonConnector( prev, next );
164 if (con)
165 {
166 con->updateConnectorPoints(false);
167 con->setRoutePoints( pointList, false, false );
168 con->updateConnectorPoints(true);
169 // con->conRouter()->setPoints( &pointList, con->startNode() != prev );
170 // con->conRouter()->setPoints( &pointList, con->pointsAreReverse( &pointList ) );
171 // con->calcBoundingPoints();
172 }
173 prev = next;
174 }
175 }
176 }
177
178
findRoute(Node * startNode,Node * endNode)179 NodeList NodeGroup::findRoute( Node *startNode, Node *endNode )
180 {
181 NodeList nl;
182 if ( !startNode || !endNode || startNode == endNode ) {
183 return nl;
184 }
185
186 IntList temp;
187 IntList il = findRoute( temp, getNodePos(startNode), getNodePos(endNode) );
188
189 const IntList::iterator end = il.end();
190 for ( IntList::iterator it = il.begin(); it != end; ++it )
191 {
192 Node *node = getNodePtr(*it);
193 if (node) {
194 nl += node;
195 }
196 }
197
198 nl.removeAll(startNode);
199 nl.removeAll(endNode);
200
201 return nl;
202 }
203
204
findRoute(IntList used,int currentNode,int endNode,bool * success)205 IntList NodeGroup::findRoute( IntList used, int currentNode, int endNode, bool *success )
206 {
207 bool temp;
208 if (!success) {
209 success = &temp;
210 }
211 *success = false;
212
213 if ( !used.contains(currentNode) ) {
214 used.append(currentNode);
215 }
216
217 if ( currentNode == endNode ) {
218 *success = true;
219 return used;
220 }
221
222 const uint n = m_nodeList.size()+m_extNodeList.size();
223 for ( uint i=0; i<n; ++i )
224 {
225 if ( b_routedMap[i*n+currentNode] && !used.contains(i) )
226 {
227 IntList il = findRoute( used, i, endNode, success );
228 if (*success) {
229 return il;
230 }
231 }
232 }
233
234 IntList il;
235 return il;
236 }
237
238
findCommonConnector(Node * n1,Node * n2)239 Connector* NodeGroup::findCommonConnector( Node *n1, Node *n2 )
240 {
241 if ( !n1 || !n2 || n1==n2 ) {
242 return nullptr;
243 }
244
245 ConnectorList n1Con = n1->getAllConnectors();
246 ConnectorList n2Con = n2->getAllConnectors();
247
248 const ConnectorList::iterator end = n1Con.end();
249 for ( ConnectorList::iterator it = n1Con.begin(); it != end; ++it )
250 {
251 if ( n2Con.contains(*it) ) {
252 return *it;
253 }
254 }
255 return nullptr;
256 }
257
258
findBestPair(NodeList * list,Node ** n1,Node ** n2)259 void NodeGroup::findBestPair( NodeList *list, Node **n1, Node **n2 )
260 {
261 *n1 = nullptr;
262 *n2 = nullptr;
263
264 if ( list->size() < 2 ) {
265 return;
266 }
267
268 const NodeList::iterator end = list->end();
269 int shortest = 1<<30;
270
271 // Try and find any that are aligned horizontally
272 for ( NodeList::iterator it1 = list->begin(); it1 != end; ++it1 )
273 {
274 NodeList::iterator it2 = it1;
275 for ( ++it2; it2 != end; ++it2 )
276 {
277 if ( *it1 != *it2 && (*it1)->y() == (*it2)->y() && canRoute( *it1, *it2 ) )
278 {
279 const int distance = std::abs(int( (*it1)->x()-(*it2)->x() ));
280 if ( distance < shortest )
281 {
282 shortest = distance;
283 *n1 = *it1;
284 *n2 = *it2;
285 }
286 }
287 }
288 }
289 if (*n1) {
290 return;
291 }
292
293 // Try and find any that are aligned vertically
294 for ( NodeList::iterator it1 = list->begin(); it1 != end; ++it1 )
295 {
296 NodeList::iterator it2 = it1;
297 for ( ++it2; it2 != end; ++it2 )
298 {
299 if ( *it1 != *it2 && (*it1)->x() == (*it2)->x() && canRoute( *it1, *it2 ) )
300 {
301 const int distance = std::abs(int( (*it1)->y()-(*it2)->y() ));
302 if ( distance < shortest )
303 {
304 shortest = distance;
305 *n1 = *it1;
306 *n2 = *it2;
307 }
308 }
309 }
310 }
311 if (*n1) {
312 return;
313 }
314
315 // Now, lets just find the two closest nodes
316 for ( NodeList::iterator it1 = list->begin(); it1 != end; ++it1 )
317 {
318 NodeList::iterator it2 = it1;
319 for ( ++it2; it2 != end; ++it2 )
320 {
321 if ( *it1 != *it2 && canRoute( *it1, *it2 ) )
322 {
323 const int dx = (int)((*it1)->x()-(*it2)->x());
324 const int dy = (int)((*it1)->y()-(*it2)->y());
325 const int distance = std::abs(dx) + std::abs(dy);
326 if ( distance < shortest )
327 {
328 shortest = distance;
329 *n1 = *it1;
330 *n2 = *it2;
331 }
332 }
333 }
334 }
335
336 if (!*n1) {
337 qCritical() << "NodeGroup::findBestPair: Could not find a routable pair of nodes!"<<endl;
338 }
339 }
340
341
canRoute(Node * n1,Node * n2)342 bool NodeGroup::canRoute( Node *n1, Node *n2 )
343 {
344 if ( !n1 || !n2 ) {
345 return false;
346 }
347
348 IntList reachable;
349 getReachable( &reachable, getNodePos(n1) );
350 return reachable.contains(getNodePos(n2));
351 }
352
353
getReachable(IntList * reachable,int node)354 void NodeGroup::getReachable( IntList *reachable, int node )
355 {
356 if ( !reachable || reachable->contains(node) ) {
357 return;
358 }
359 reachable->append(node);
360
361 const uint n = m_nodeList.size() + m_extNodeList.size();
362 assert( node < int(n) );
363 for ( uint i=0; i<n; ++i )
364 {
365 if ( b_routedMap[i*n + node] ) {
366 getReachable(reachable,i);
367 }
368 }
369 }
370
371
resetRoutedMap()372 void NodeGroup::resetRoutedMap()
373 {
374 const uint n = m_nodeList.size() + m_extNodeList.size();
375
376 b_routedMap.resize( n*n );
377
378 const ConnectorList::iterator end = m_conList.end();
379 for ( ConnectorList::iterator it = m_conList.begin(); it != end; ++it )
380 {
381 Connector *con = *it;
382 if (con)
383 {
384 int n1 = getNodePos(con->startNode());
385 int n2 = getNodePos(con->endNode());
386 if ( n1 != -1 && n2 != -1 )
387 {
388 b_routedMap[n1*n + n2] = b_routedMap[n2*n + n1] = true;
389 }
390 }
391 }
392 }
393
394
removeRoutedNodes(NodeList * nodes,Node * n1,Node * n2)395 void NodeGroup::removeRoutedNodes( NodeList *nodes, Node *n1, Node *n2 )
396 {
397 if (!nodes) {
398 return;
399 }
400
401 // Lets get rid of any duplicate nodes in nodes (as a general cleaning operation)
402 const NodeList::iterator end = nodes->end();
403 for ( NodeList::iterator it = nodes->begin(); it != end; ++it )
404 {
405 //if ( nodes->contains(*it) > 1 ) {
406 if ( nodes->count(*it) > 1 ) {
407 *it = nullptr;
408 }
409 }
410 nodes->removeAll((Node*)nullptr);
411
412 const int n1pos = getNodePos(n1);
413 const int n2pos = getNodePos(n2);
414
415 if ( n1pos == -1 || n2pos == -1 ) {
416 return;
417 }
418
419 const uint n = m_nodeList.size() + m_extNodeList.size();
420
421 b_routedMap[n1pos*n + n2pos] = b_routedMap[n2pos*n + n1pos] = false;
422
423 bool n1HasCon = false;
424 bool n2HasCon = false;
425
426 for ( uint i=0; i<n; ++i )
427 {
428 n1HasCon |= b_routedMap[n1pos*n + i];
429 n2HasCon |= b_routedMap[n2pos*n + i];
430 }
431
432 if (!n1HasCon) {
433 nodes->removeAll(n1);
434 }
435 if (!n2HasCon) {
436 nodes->removeAll(n2);
437 }
438 }
439
440
getNodePos(Node * n)441 int NodeGroup::getNodePos( Node *n )
442 {
443 if (!n) {
444 return -1;
445 }
446 int pos = m_nodeList.indexOf(n);
447 if ( pos != -1 ) {
448 return pos;
449 }
450 pos = m_extNodeList.indexOf(n);
451 if ( pos != -1 ) {
452 return pos+m_nodeList.size();
453 }
454 return -1;
455 }
456
457
getNodePtr(int n)458 Node* NodeGroup::getNodePtr( int n )
459 {
460 if ( n<0 ) {
461 return nullptr;
462 }
463 const int a = m_nodeList.size();
464 if (n<a) {
465 return m_nodeList[n];
466 }
467 const int b = m_extNodeList.size();
468 if (n<a+b) {
469 return m_extNodeList[n-a];
470 }
471 return nullptr;
472 }
473
474
clearConList()475 void NodeGroup::clearConList()
476 {
477 const ConnectorList::iterator end = m_conList.end();
478 for ( ConnectorList::iterator it = m_conList.begin(); it != end; ++it )
479 {
480 Connector *con = *it;
481 if (con)
482 {
483 con->setNodeGroup(nullptr);
484 disconnect( con, SIGNAL(removed(Connector*)), this, SLOT(connectorRemoved(Connector*)) );
485 }
486 }
487 m_conList.clear();
488 }
489
490
init()491 void NodeGroup::init()
492 {
493 NodeList::iterator xnEnd = m_extNodeList.end();
494 for ( NodeList::iterator it = m_extNodeList.begin(); it != xnEnd; ++it )
495 {
496 (*it)->setNodeGroup(nullptr);
497 }
498 m_extNodeList.clear();
499
500 clearConList();
501
502 // First, lets get all of our external nodes and internal connectors
503 const NodeList::iterator nlEnd = m_nodeList.end();
504 for ( NodeList::iterator nodeIt = m_nodeList.begin(); nodeIt != nlEnd; ++nodeIt )
505 {
506 // 2. rewrite
507 ConnectorList conList = ( *nodeIt )->getAllConnectors();
508
509 ConnectorList::iterator conIt,
510 conEnd = conList.end();
511 for ( conIt = conList.begin(); conIt != conEnd; ++conIt )
512 {
513
514 Connector *con = *conIt;
515
516 // possible check: only 1 of these ifs should be true
517 if ( con->startNode() != *nodeIt )
518 {
519 addExtNode ( con->startNode() );
520 if ( !m_conList.contains ( con ) )
521 {
522 m_conList += con;
523 con->setNodeGroup ( this );
524 }
525 }
526 if ( con->endNode() != *nodeIt )
527 {
528 addExtNode ( con->endNode() );
529 if ( !m_conList.contains ( con ) )
530 {
531 m_conList += con;
532 con->setNodeGroup ( this );
533 }
534 }
535 connect ( con, SIGNAL ( removed ( Connector* ) ), this, SLOT ( connectorRemoved ( Connector* ) ) );
536 }
537
538 // Connect the node up to us
539 connect ( *nodeIt, SIGNAL ( removed ( Node* ) ), this, SLOT ( nodeRemoved ( Node* ) ) );
540 }
541
542 // And connect up our external nodes
543 xnEnd = m_extNodeList.end();
544 for ( NodeList::iterator it = m_extNodeList.begin(); it != xnEnd; ++it )
545 {
546 // connect( *it, SIGNAL(moved(Node*)), this, SLOT(extNodeMoved()) );
547 connect( *it, SIGNAL(removed(Node*)), this, SLOT(nodeRemoved(Node*)) );
548 }
549 }
550
551
nodeRemoved(Node * node)552 void NodeGroup::nodeRemoved( Node *node )
553 {
554 // We are probably about to get deleted by ICNDocument anyway...so no point in doing anything
555 m_nodeList.removeAll(node);
556 node->setNodeGroup(nullptr);
557 node->setVisible(true);
558 m_extNodeList.removeAll(node);
559 }
560
561
connectorRemoved(Connector * connector)562 void NodeGroup::connectorRemoved( Connector *connector )
563 {
564 m_conList.removeAll(connector);
565 }
566
567
addExtNode(Node * node)568 void NodeGroup::addExtNode( Node *node )
569 {
570 if ( !m_extNodeList.contains(node) && !m_nodeList.contains(node) )
571 {
572 m_extNodeList.append(node);
573 node->setNodeGroup(this);
574 }
575 }
576