planarlayout/mixed_model_layout/IOPoints.h

/** \file
 * \brief Declaration of classes InOutPoint and IOPoints which
 * implement the management of in-/out-points
 *
 * \author Carsten Gutwenger
 *
 * \par License:
 * This file is part of the Open Graph Drawing Framework (OGDF).
 *
 * \par
 * Copyright (C)<br>
 * See README.md in the OGDF root directory for details.
 *
 * \par
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * Version 2 or 3 as published by the Free Software Foundation;
 * see the file LICENSE.txt included in the packaging of this file
 * for details.
 *
 * \par
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * \par
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, see
 * http://www.gnu.org/copyleft/gpl.html
 */

#pragma once

#include <ogdf/planarity/PlanRep.h>


namespace ogdf {


//! Representation of an in- or outpoint
struct InOutPoint
{
	int  m_dx, m_dy;
	adjEntry m_adj;

	InOutPoint() {
		m_dx = m_dy = 0; m_adj = nullptr;
	}
	explicit InOutPoint(adjEntry adj) {
		m_adj = adj; m_dx = m_dy = 0;
	}
};


//! Representation of in- and outpoint lists
class IOPoints {
public:
	IOPoints() { }
	explicit IOPoints(const Graph &G) : m_depth(G,0), m_height(G,0), m_in(G), m_out(G),
		m_mark(G,false), m_pointOf(G,nullptr)  { }

	~IOPoints () { }


	// length of in- or outpoint list
	int out(node v) const {
		return m_out[v].size();
	}
	int in(node v) const {
		return m_in[v].size();
	}

	// getting a const-reference to in- or outpoint list
	const List<InOutPoint> &inpoints(node v) const {
		return m_in [v];
	}
	List<InOutPoint> &inpoints(node v) {
		return m_in [v];
	}

	const List<InOutPoint> &outpoints(node v) const {
		return m_out [v];
	}
	List<InOutPoint> &outpoints(node v) {
		return m_out [v];
	}

	// getting the in-/outpoint belonging to an adjacency entry
	const InOutPoint *pointOf(adjEntry adj) const {
		return m_pointOf[adj];
	}

	// marking adjacency entries
	bool marked(adjEntry adj) const {
		return m_mark[adj];
	}

	bool marked(node v) {
		return v->outdeg() == 1 && marked(v->firstAdj());
	}

	// finding outpoints belonging to non-marked edges
	ListConstIterator<InOutPoint> firstRealOut(node v) const {
		return searchRealForward(m_out[v].begin());
	}

	ListConstIterator<InOutPoint> lastRealOut(node v) const {
		return searchRealBackward(m_out[v].rbegin());
	}

	ListConstIterator<InOutPoint> nextRealOut(ListConstIterator<InOutPoint> it) const {
		return searchRealForward(it.succ());
	}

	ListConstIterator<InOutPoint> prevRealOut(ListConstIterator<InOutPoint> it) const {
		return searchRealBackward(it.pred());
	}

	// building in-/outpoint lists
	void appendInpoint(adjEntry adj) {
		node v = adj->theNode();
		m_pointOf[adj] = &(*m_in[v].pushBack(InOutPoint(adj)));
	}
	void appendOutpoint(adjEntry adj) {
		node v = adj->theNode();
		m_pointOf[adj] = &(*m_out[v].pushBack(InOutPoint(adj)));
	}
	void pushInpoint(adjEntry adj) {
		node v = adj->theNode();
		m_pointOf[adj] = &(*m_in[v].pushFront(InOutPoint(adj)));
	}

	// setting relative coordinates
	void setOutCoord (ListIterator<InOutPoint> it, int dx, int dy) {
		(*it).m_dx = dx;
		(*it).m_dy = dy;
	}
	void setInCoord (ListIterator<InOutPoint> it, int dx, int dy) {
		(*it).m_dx = dx;
		(*it).m_dy = dy;
	}

	void setOutDx(ListIterator<InOutPoint> it, int dx) {
		(*it).m_dx = dx;
	}

	void restoreDeg1Nodes(PlanRep &PG, ArrayBuffer<PlanRep::Deg1RestoreInfo> &S);

	void changeEdge(node v, adjEntry adj_new) {
		m_out[v].popBack();
		appendInpoint(adj_new);
	}

	// belongs v to a chain (= at most to non-marked incoming edges
	bool isChain(node v) const {
		int i = 0;
		for(const InOutPoint &iop : m_in[v])
			if (!marked(iop.m_adj)) ++i;
		return i <= 2;
	}

	// width of the left-/right side of an in-/outpoint list
	int outLeft(node v) const {
		return (m_out[v].empty()) ? 0 : (-m_out[v].front().m_dx);
	}

	int outRight(node v) const {
		return (m_out[v].empty()) ? 0 : (m_out[v].back().m_dx);
	}

	int inLeft(node v) const {
		return (m_in[v].empty()) ? 0 : (-m_in[v].front().m_dx);
	}

	int inRight(node v) const {
		return (m_in[v].empty()) ? 0 : (m_in[v].back().m_dx);
	}

	int maxLeft(node v) const {
		return max(inLeft(v), outLeft(v));
	}

	int maxRight(node v) const {
		return max(inRight(v), outRight(v));
	}

	int maxPlusLeft(node v) const {
		return (in(v) >= 3) ?
			max(inLeft(v)+1, outLeft(v)) : maxLeft(v);
	}

	int maxPlusRight(node v) const {
		return (in(v) >= 3) ?
			max(inRight(v)+1, outRight(v)) : maxRight(v);
	}

	InOutPoint middleNeighbor(node z1) const;

	void numDeg1(node v, int &xl, int &xr,
		bool doubleCount) const;

	adjEntry switchBeginIn(node v);
	adjEntry switchEndIn  (node v);

	void switchBeginOut(node v);
	void switchEndOut  (node v);


	NodeArray<int> m_depth, m_height;


private:
	NodeArray<List<InOutPoint> > m_in, m_out;
	AdjEntryArray<bool> m_mark;
	AdjEntryArray<InOutPoint *> m_pointOf;

	ListConstIterator<InOutPoint> searchRealForward (ListConstIterator<InOutPoint> it) const;
	ListConstIterator<InOutPoint> searchRealBackward(ListConstIterator<InOutPoint> it) const;
};

}