home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 March / PCWK3A99.iso / Linux / DDD331 / DDD-3_1_.000 / DDD-3_1_ / ddd-3.1.1 / ddd / GraphEdge.C < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-25  |  6.8 KB  |  306 lines
  1. // $Id: GraphEdge.C,v 1.7 1998/03/25 12:43:17 zeller Exp $
  2. // GraphEdge class
  3.  
  4. // Copyright (C) 1995 Technische Universitaet Braunschweig, Germany.
  5. // Written by Andreas Zeller <zeller@ips.cs.tu-bs.de>.
  6. // 
  7. // This file is part of DDD.
  8. // 
  9. // DDD is free software; you can redistribute it and/or
  10. // modify it under the terms of the GNU General Public
  11. // License as published by the Free Software Foundation; either
  12. // version 2 of the License, or (at your option) any later version.
  13. // 
  14. // DDD is distributed in the hope that it will be useful,
  15. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. // See the GNU General Public License for more details.
  18. // 
  19. // You should have received a copy of the GNU General Public
  20. // License along with DDD -- see the file COPYING.
  21. // If not, write to the Free Software Foundation, Inc.,
  22. // 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23. // 
  24. // DDD is the data display debugger.
  25. // For details, see the DDD World-Wide-Web page, 
  26. // `http://www.cs.tu-bs.de/softech/ddd/',
  27. // or send a mail to the DDD developers <ddd@ips.cs.tu-bs.de>.
  28.  
  29. char GraphEdge_rcsid[] = 
  30.     "$Id: GraphEdge.C,v 1.7 1998/03/25 12:43:17 zeller Exp $";
  31.  
  32. #ifdef __GNUG__
  33. #pragma implementation
  34. #endif
  35.  
  36.  
  37. #include "GraphEdge.h"
  38. #include "GraphNode.h"
  39. #include "printBox.h"
  40. #include <stdlib.h>
  41.  
  42. DEFINE_TYPE_INFO_0(GraphEdge)
  43.  
  44. void GraphEdge::enqueue()
  45. {
  46.     assert (_nextFrom == 0);
  47.     assert (_nextTo   == 0);
  48.     assert (_prevFrom == 0);
  49.     assert (_prevTo   == 0);
  50.     
  51.     if (from()->_firstFrom == 0)
  52.     {
  53.     _nextFrom = this;
  54.     _prevFrom = this;
  55.     from()->_firstFrom = this;
  56.     }
  57.     else
  58.     {
  59.     _nextFrom = from()->_firstFrom->_nextFrom;
  60.     _prevFrom = from()->_firstFrom;
  61.  
  62.     _nextFrom->_prevFrom = this;
  63.     _prevFrom->_nextFrom = this;
  64.     }
  65.  
  66.     if (to()->_firstTo == 0)
  67.     {
  68.     _nextTo = this;
  69.     _prevTo = this;
  70.     to()->_firstTo = this;
  71.     }
  72.     else
  73.     {
  74.     _nextTo = to()->_firstTo->_nextTo;
  75.     _prevTo = to()->_firstTo;
  76.  
  77.     _nextTo->_prevTo = this;
  78.     _prevTo->_nextTo = this;
  79.     }
  80. }
  81.  
  82. void GraphEdge::dequeue()
  83. {
  84.     // dequeue from "from" chain
  85.     if (_nextFrom != 0 || _prevFrom != 0)
  86.     {
  87.     assert(_nextFrom != 0);
  88.     assert(_prevFrom != 0);
  89.  
  90.     if (_from->_firstFrom == this)
  91.         _from->_firstFrom = _nextFrom;
  92.  
  93.     if (_from->_firstFrom == this)
  94.     {
  95.         assert(_nextFrom == this);
  96.         assert(_prevFrom == this);
  97.         _from->_firstFrom = 0;
  98.     }
  99.     else
  100.     {
  101.         _nextFrom->_prevFrom = _prevFrom;
  102.         _prevFrom->_nextFrom = _nextFrom;
  103.     }
  104.  
  105.     _nextFrom = 0;
  106.     _prevFrom = 0;
  107.     }
  108.  
  109.     // dequeue from "to" chain
  110.     if (_nextTo != 0 || _prevTo != 0)
  111.     {
  112.     assert(_nextTo != 0);
  113.     assert(_prevTo != 0);
  114.  
  115.     if (_to->_firstTo == this)
  116.         _to->_firstTo = _nextTo;
  117.  
  118.     if (_to->_firstTo == this)
  119.     {
  120.         assert(_nextTo == this);
  121.         assert(_prevTo == this);
  122.         _to->_firstTo = 0;
  123.     }
  124.     else
  125.     {
  126.         _nextTo->_prevTo = _prevTo;
  127.         _prevTo->_nextTo = _nextTo;
  128.     }
  129.  
  130.     _nextTo = 0;
  131.     _prevTo = 0;
  132.     }
  133. }
  134.  
  135.     
  136.     
  137.  
  138. ostream& operator << (ostream& s, GraphEdge& e)
  139. {
  140.     return s << "( " << *(e.from()) << " -> " << *(e.to()) << " )";
  141. }
  142.  
  143.  
  144. // representation invariant
  145. bool GraphEdge::OK() const
  146. {
  147.     GraphEdge *e;
  148.  
  149.     // assert that prev/next is okay
  150.     assert(_nextTo == 0 || _nextTo->_prevTo == this);
  151.     assert(_prevTo == 0 || _prevTo->_nextTo == this);
  152.  
  153.     assert(_nextFrom == 0 || _nextFrom->_prevFrom == this);
  154.     assert(_prevFrom == 0 || _prevFrom->_nextFrom == this);
  155.  
  156.     // assert that this is contained in from and to lists
  157.     if (_nextFrom || _prevFrom)
  158.     {
  159.     for (e = from()->firstFrom(); e != 0 && e != this; 
  160.          e = from()->nextFrom(e))
  161.         ;
  162.     assert(e == this);
  163.     }
  164.  
  165.     if (_nextTo || _prevTo)
  166.     {
  167.     for (e = to()->firstTo(); e != 0 && e != this; 
  168.          e = to()->nextTo(e))
  169.         ;
  170.     assert(e == this);
  171.     }
  172.  
  173.     return true;
  174. }
  175.  
  176.  
  177. // printing
  178.  
  179. // internal types
  180.  
  181. enum Side { North = 1 , South = 2  , East = 4  , West = 8 } ;
  182.  
  183. // prototypes for internal usage
  184.  
  185. static Side crosside (BoxRegion  ®ion, BoxPoint &p) ;
  186. static BoxPoint crosspoint (BoxRegion ®ion, BoxPoint &p);
  187.  
  188. //
  189. // crossside
  190. // 
  191.  
  192. static Side crosside (BoxRegion  ®ion, BoxPoint &p)
  193. {
  194.     BoxPoint center = region.origin() + (region.space() / BoxPoint(2)) ;
  195.     BoxPoint delta = center  - p ;
  196.     
  197.     int side = North | South | East | West ;
  198.     
  199.     // exclude opposite side
  200.     
  201.     if (p[X] > center[X]) 
  202.     side &= ~West ;
  203.     else
  204.     side &= ~East ;
  205.     if (p[Y] > center[Y])
  206.     side &= ~North ;
  207.     else
  208.     side &= ~South ;
  209.     
  210.     delta[X] = abs(delta[X]);
  211.     delta[Y] = abs(delta[Y]);
  212.     
  213.     if (region.space(Y) * delta[X] > region.space(X) * delta[Y]) 
  214.     side &= ~(North | South);
  215.     else
  216.     side &= ~(East | West);
  217.     
  218.     return Side(side);
  219. }
  220.  
  221. //
  222. // crosspoint
  223. // 
  224.  
  225. static BoxPoint crosspoint (BoxRegion ®ion, BoxPoint &p)
  226. {
  227.     int side = crosside (region, p);
  228.     
  229.     BoxDimension d1, d2;
  230.     BoxPoint center = region.origin() + (region.space() / BoxPoint(2)) ;
  231.     BoxPoint cross = center;
  232.     int offset;
  233.     
  234.     offset = (side & (North | West)? -1 : 1) ;
  235.     if (side & (North | South)) {
  236.     d1 = X ; 
  237.     d2 = Y ;
  238.     } else {
  239.     d1 = Y ;
  240.     d2 = X ;
  241.     }
  242.     
  243.     if (center[d1] != p[d1] && center[d2] != p[d2]) {
  244.     cross[d1] += offset * (region.space(d2) / 2) 
  245.         * ( center[d1] - p[d1]) / ( center[d2] - p[d2] ) ;
  246.     } 
  247.     cross[d2] += offset * region.space(d2) / 2;
  248.     
  249.     return cross ;
  250. }
  251.  
  252. //
  253. // drawEdge
  254. // 
  255.  
  256. void GraphEdge::_print(ostream& os, const GraphGC &gc) const
  257. {
  258.     // Don't print if we're hidden
  259.     if (hidden())
  260.     return;
  261.     
  262.     // Fetch the regions
  263.     BoxRegion start = from()->region(gc);
  264.     BoxRegion end   = to()->region(gc);
  265.  
  266.     // Don't print edges with zero length
  267.     if (start <= end)
  268.     return;
  269.     
  270.     BoxPoint startc = start.origin() + (start.space() / BoxPoint(2));
  271.     BoxPoint endc   = end.origin()   + (end.space()   / BoxPoint(2));
  272.  
  273.     BoxPoint startp = crosspoint (start, endc);
  274.     BoxPoint endp   = crosspoint (end, startc);
  275.  
  276.     // This should come from gc.edgeGC
  277.     BoxCoordinate line_width = 1;
  278.  
  279.     if (gc.printGC->isFig()) {
  280.     if (!gc.drawArrowHeads || to()->isHint()) {
  281.         os << EDGEHEAD1 << line_width;
  282.         os << EDGEHEAD2 ;
  283.         os << startp[X] << " " << startp[Y] << " " ;
  284.         os << endp[X] << " " << endp[Y] << " " ;
  285.         os << "9999 9999\n" ;
  286.     } else {
  287.         os << ARROWHEAD1 << line_width;
  288.         os << ARROWHEAD2 ;
  289.         os << startp[X] << " " << startp[Y] << " " ;
  290.         os << endp[X] << " " << endp[Y] << " " ;
  291.         os << "9999 9999\n" ;
  292.     }
  293.     } else if (gc.printGC->isPostScript()) {
  294.     if (!gc.drawArrowHeads || to()->isHint()) {
  295.         os << startp[X] << " " << startp[Y] << " " ;
  296.         os << endp[X] << " " << endp[Y] << " " ;
  297.         os << line_width << " line*\n";
  298.     } else {
  299.         os << gc.arrowAngle << " " << gc.arrowLength << " ";
  300.         os << startp[X] << " " << startp[Y] << " " ;
  301.         os << endp[X] << " " << endp[Y] << " " ;
  302.         os << line_width << " arrowline*\n";
  303.     }
  304.     }
  305. }
  306.