ext/OGDF/src/planarlayout/IOPoints.cpp

   1 /*
   2  * $Revision: 2554 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 11:39:38 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation in-/out-points management.
  11  *
  12  * \author Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #include "IOPoints.h"
  45
  46
  47 namespace ogdf {
  48
  49
  50 ListConstIterator<InOutPoint> IOPoints::searchRealForward(
  51         ListConstIterator<InOutPoint> it) const
  52 {
  53         while (it.valid() && marked((*it).m_adj))
  54                 ++it;
  55
  56         return it;
  57 }
  58
  59 ListConstIterator<InOutPoint> IOPoints::searchRealBackward(
  60         ListConstIterator<InOutPoint> it) const
  61 {
  62         while (it.valid() && marked((*it).m_adj))
  63                 --it;
  64
  65         return it;
  66 }
  67
  68
  69 void IOPoints::restoreDeg1Nodes(PlanRep &PG, Stack<PlanRep::Deg1RestoreInfo> &S)
  70 {
  71         List<node> deg1s;
  72
  73         PG.restoreDeg1Nodes(S,deg1s);
  74
  75         ListConstIterator<node> it;
  76         for(it = deg1s.begin(); it.valid(); ++it) {
  77                 adjEntry adj = (*it)->firstAdj();
  78                 m_mark[adj] = m_mark[adj->twin()] = true;
  79         }
  80 }
  81
  82
  83 adjEntry IOPoints::switchBeginIn(node v)
  84 {
  85         List<InOutPoint> &Lin  = m_in [v];
  86         List<InOutPoint> &Lout = m_out[v];
  87
  88         ListConstIterator<InOutPoint> it;
  89         adjEntry adj;
  90
  91         while ((it = Lin.begin()).valid() && marked(adj = (*it).m_adj))
  92                 m_pointOf[adj] = &(*Lout.pushFront(Lin.popFrontRet()));
  93
  94         return it.valid() ? adj : 0;
  95 }
  96
  97
  98 adjEntry IOPoints::switchEndIn(node v)
  99 {
 100         List<InOutPoint> &Lin  = m_in [v];
 101         List<InOutPoint> &Lout = m_out[v];
 102
 103         ListConstIterator<InOutPoint> it;
 104         adjEntry adj;
 105
 106         while ((it = Lin.rbegin()).valid() && marked(adj = (*it).m_adj))
 107                 m_pointOf[adj] = &(*Lout.pushBack(Lin.popBackRet()));
 108
 109         return it.valid() ? adj : 0;
 110 }
 111
 112
 113 void IOPoints::switchBeginOut(node v)
 114 {
 115         List<InOutPoint> &Lin  = m_in [v];
 116         List<InOutPoint> &Lout = m_out[v];
 117
 118         adjEntry adj = (*Lout.begin()).m_adj;
 119         m_pointOf[adj] = &(*Lin.pushFront(Lout.popFrontRet()));
 120 }
 121
 122
 123 void IOPoints::switchEndOut(node v)
 124 {
 125         List<InOutPoint> &Lin  = m_in [v];
 126         List<InOutPoint> &Lout = m_out[v];
 127
 128         adjEntry adj = (*Lout.rbegin()).m_adj;
 129         m_pointOf[adj] = &(*Lin.pushBack(Lout.popBackRet()));
 130 }
 131
 132
 133 void IOPoints::numDeg1(node v, int &xl, int &xr,
 134         bool doubleCount) const
 135 {
 136         const List<InOutPoint> &L = m_out[v];
 137         ListConstIterator<InOutPoint> it;
 138
 139         xl = xr = 0;
 140         for (it = L.begin(); it.valid() && marked((*it).m_adj); ++it)
 141                 ++xl;
 142
 143         if (doubleCount || it.valid()) // avoid double counting if all are marked
 144                 for (it = L.rbegin(); it.valid() && marked((*it).m_adj); --it)
 145                         ++xr;
 146 }
 147
 148 InOutPoint IOPoints::middleNeighbor(node z1) const
 149 {
 150         const List<InOutPoint> &L = m_in[z1];
 151
 152         ListConstIterator<InOutPoint> it, itFound;
 153         int i,  pos = (L.size()-1)/2;
 154
 155         for (it = L.begin().succ(), i = 1; i <= pos || !itFound.valid(); ++it, ++i)
 156                 if (!marked((*it).m_adj))
 157                         itFound = it;
 158
 159         return *itFound;
 160 }
 161
 162
 163 } // end namespace ogdf