klao@946: // -*- c++ -*-
klao@946: #ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
klao@946: #define LEMON_ITERABLE_GRAPH_EXTENDER_H
klao@946: 
klao@946: #include <lemon/invalid.h>
alpar@1448: #include <lemon/utility.h>
klao@946: 
klao@946: namespace lemon {
klao@946:   
klao@946:   template <typename _Base>
klao@946:   class IterableGraphExtender : public _Base {
klao@962:   public:
klao@946: 
alpar@1448:     /// Indicates that the graph is undirected.
alpar@1448: 
alpar@1448:     ///\todo Better name?
alpar@1448:     ///
alpar@1448:     ///\bug Should it be here?
alpar@1448:     typedef False UndirTag;
alpar@1448: 
klao@946:     typedef _Base Parent;
klao@946:     typedef IterableGraphExtender<_Base> Graph;
klao@946: 
klao@946:     typedef typename Parent::Node Node;
klao@946:     typedef typename Parent::Edge Edge;
klao@946: 
klao@946: 
klao@946:     class NodeIt : public Node { 
klao@946:       const Graph* graph;
klao@946:     public:
klao@946: 
klao@946:       NodeIt() {}
klao@946: 
klao@946:       NodeIt(Invalid i) : Node(i) { }
klao@946: 
klao@962:       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
klao@946: 	_graph.first(*static_cast<Node*>(this));
klao@946:       }
klao@946: 
klao@946:       NodeIt(const Graph& _graph, const Node& node) 
klao@946: 	: Node(node), graph(&_graph) {}
klao@946: 
klao@946:       NodeIt& operator++() { 
klao@946: 	graph->next(*this);
klao@946: 	return *this; 
klao@946:       }
klao@946: 
klao@946:     };
klao@946: 
klao@946: 
klao@946:     class EdgeIt : public Edge { 
klao@946:       const Graph* graph;
klao@946:     public:
klao@946: 
klao@946:       EdgeIt() { }
klao@946: 
klao@946:       EdgeIt(Invalid i) : Edge(i) { }
klao@946: 
klao@962:       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
klao@946: 	_graph.first(*static_cast<Edge*>(this));
klao@946:       }
klao@946: 
klao@946:       EdgeIt(const Graph& _graph, const Edge& e) : 
klao@946: 	Edge(e), graph(&_graph) { }
klao@946: 
klao@946:       EdgeIt& operator++() { 
klao@946: 	graph->next(*this);
klao@946: 	return *this; 
klao@946:       }
klao@946: 
klao@946:     };
klao@946: 
klao@946: 
klao@946:     class OutEdgeIt : public Edge { 
klao@946:       const Graph* graph;
klao@946:     public:
klao@946: 
klao@946:       OutEdgeIt() { }
klao@946: 
klao@946:       OutEdgeIt(Invalid i) : Edge(i) { }
klao@946: 
klao@946:       OutEdgeIt(const Graph& _graph, const Node& node) 
klao@962: 	: graph(&_graph) {
klao@946: 	_graph.firstOut(*this, node);
klao@946:       }
klao@946: 
klao@946:       OutEdgeIt(const Graph& _graph, const Edge& edge) 
klao@946: 	: Edge(edge), graph(&_graph) {}
klao@946: 
klao@946:       OutEdgeIt& operator++() { 
klao@946: 	graph->nextOut(*this);
klao@946: 	return *this; 
klao@946:       }
klao@946: 
klao@946:     };
klao@946: 
klao@946: 
klao@946:     class InEdgeIt : public Edge { 
klao@946:       const Graph* graph;
klao@946:     public:
klao@946: 
klao@946:       InEdgeIt() { }
klao@946: 
klao@946:       InEdgeIt(Invalid i) : Edge(i) { }
klao@946: 
klao@946:       InEdgeIt(const Graph& _graph, const Node& node) 
klao@962: 	: graph(&_graph) {
klao@946: 	_graph.firstIn(*this, node);
klao@946:       }
klao@946: 
klao@946:       InEdgeIt(const Graph& _graph, const Edge& edge) : 
klao@946: 	Edge(edge), graph(&_graph) {}
klao@946: 
klao@946:       InEdgeIt& operator++() { 
klao@946: 	graph->nextIn(*this);
klao@946: 	return *this; 
klao@946:       }
klao@946: 
klao@946:     };
klao@946: 
deba@1627:     /// \brief Base node of the iterator
klao@1158:     ///
klao@1158:     /// Returns the base node (ie. the source in this case) of the iterator
klao@1158:     Node baseNode(const OutEdgeIt &e) const {
deba@1564:       return Parent::source((Edge)e);
klao@1158:     }
deba@1627:     /// \brief Running node of the iterator
klao@1158:     ///
klao@1158:     /// Returns the running node (ie. the target in this case) of the
klao@1158:     /// iterator
klao@1158:     Node runningNode(const OutEdgeIt &e) const {
deba@1564:       return Parent::target((Edge)e);
klao@1158:     }
klao@1158: 
deba@1627:     /// \brief Base node of the iterator
klao@1158:     ///
klao@1158:     /// Returns the base node (ie. the target in this case) of the iterator
klao@1158:     Node baseNode(const InEdgeIt &e) const {
deba@1564:       return Parent::target((Edge)e);
klao@1158:     }
deba@1627:     /// \brief Running node of the iterator
klao@1158:     ///
klao@1158:     /// Returns the running node (ie. the source in this case) of the
klao@1158:     /// iterator
klao@1158:     Node runningNode(const InEdgeIt &e) const {
deba@1564:       return Parent::source((Edge)e);
klao@1158:     }
klao@1158: 
klao@946:     using Parent::first;
klao@946: 
deba@1627:     /// \brief The opposite node on the given edge.
deba@1627:     ///
deba@1627:     /// Gives back the opposite on the given edge.
deba@1627:     Node oppositeNode(const Node& n, const Edge& e) const {
deba@1627:       if (Parent::source(e) == n) {
deba@1627: 	return Parent::target(e);
deba@1627:       } else {
deba@1627: 	return Parent::source(e);
deba@1627:       }
deba@1627:     }
deba@1627: 
klao@946:   private:
klao@946: 
klao@1230:     // void first(NodeIt &) const;
klao@1230:     // void first(EdgeIt &) const;
klao@1230:     // void first(OutEdgeIt &) const;
klao@1230:     // void first(InEdgeIt &) const;
klao@946: 
klao@946:   };
klao@1158: 
klao@1158: 
klao@1158: 
klao@1158: 
klao@1158: 
klao@946:   
klao@962:   template <typename _Base>
klao@962:   class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
klao@962:   public:
klao@962: 
alpar@1448:     /// Indicates that the graph is undirected.
alpar@1448: 
alpar@1448:     ///\todo Better name?
alpar@1448:     ///
alpar@1448:     ///\bug Should it be here?
alpar@1448:     ///\bug Should be tested in the concept checker whether it is defined
alpar@1448:     ///correctly.
alpar@1448:     typedef True UndirTag;
alpar@1448: 
klao@962:     typedef IterableGraphExtender<_Base> Parent;
klao@962:     typedef IterableUndirGraphExtender<_Base> Graph;
klao@1021:     typedef typename Parent::Node Node;
deba@1627:     typedef typename Parent::Edge Edge;
klao@962:     typedef typename Parent::UndirEdge UndirEdge;
klao@962: 
klao@1230:     class UndirEdgeIt : public Parent::UndirEdge { 
klao@962:       const Graph* graph;
klao@962:     public:
klao@962: 
klao@962:       UndirEdgeIt() { }
klao@962: 
klao@962:       UndirEdgeIt(Invalid i) : UndirEdge(i) { }
klao@962: 
klao@962:       explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
klao@962: 	_graph.first(*static_cast<UndirEdge*>(this));
klao@962:       }
klao@962: 
klao@962:       UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : 
klao@962: 	UndirEdge(e), graph(&_graph) { }
klao@962: 
klao@962:       UndirEdgeIt& operator++() { 
klao@962: 	graph->next(*this);
klao@962: 	return *this; 
klao@962:       }
klao@962: 
klao@962:     };
klao@962: 
klao@1230:     class IncEdgeIt : public Parent::UndirEdge { 
klao@1021:       const Graph* graph;
deba@1704:       bool direction;
klao@1021:       friend class IterableUndirGraphExtender;
klao@1021:     public:
klao@1021: 
klao@1030:       IncEdgeIt() { }
klao@1021: 
deba@1704:       IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { }
klao@1021: 
deba@1704:       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
deba@1704: 	_graph.firstInc(*this, direction, n);
klao@1021:       }
klao@1021: 
klao@1158:       IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
deba@1704: 	: graph(&_graph), UndirEdge(ue) {
deba@1704: 	direction = (_graph.source(ue) == n);
klao@1158:       }
klao@1021: 
klao@1030:       IncEdgeIt& operator++() {
deba@1704: 	graph->nextInc(*this, direction);
klao@1021: 	return *this; 
klao@1021:       }
klao@1021:     };
klao@1021: 
klao@1158:     using Parent::baseNode;
klao@1158:     using Parent::runningNode;
klao@1158: 
klao@1158:     /// Base node of the iterator
klao@1158:     ///
klao@1158:     /// Returns the base node of the iterator
klao@1158:     Node baseNode(const IncEdgeIt &e) const {
deba@1704:       return e.direction ? source(e) : target(e);
klao@1021:     }
klao@1158:     /// Running node of the iterator
klao@1158:     ///
klao@1158:     /// Returns the running node of the iterator
klao@1158:     Node runningNode(const IncEdgeIt &e) const {
deba@1704:       return e.direction ? target(e) : source(e);
klao@1021:     }
klao@1021: 
deba@1627:     /// \brief The opposite node on the given undirected edge.
deba@1627:     ///
deba@1627:     /// Gives back the opposite on the given undirected edge.
deba@1627:     Node oppositeNode(const Node& n, const UndirEdge& e) const {
deba@1627:       if (Parent::source(e) == n) {
deba@1627: 	return Parent::target(e);
deba@1627:       } else {
deba@1627: 	return Parent::source(e);
deba@1627:       }
deba@1627:     }
deba@1627: 
klao@962:   };
deba@1820: 
deba@1820: 
deba@1820:   template <typename _Base>
deba@1820:   class IterableUndirBipartiteGraphExtender : public _Base {
deba@1820:   public:
deba@1820:     typedef _Base Parent;
deba@1820:     typedef IterableUndirBipartiteGraphExtender Graph;
deba@1820:    
deba@1820:     typedef typename Parent::Node Node;
deba@1820:     typedef typename Parent::UpperNode UpperNode;
deba@1820:     typedef typename Parent::LowerNode LowerNode;
deba@1820:     typedef typename Parent::Edge Edge;
deba@1820:     typedef typename Parent::UndirEdge UndirEdge;
deba@1820:   
deba@1820:     class NodeIt : public Node { 
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1820:       NodeIt() { }
deba@1820:     
deba@1820:       NodeIt(Invalid i) : Node(INVALID) { }
deba@1820:     
deba@1820:       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
deba@1820: 	graph->first(static_cast<Node&>(*this));
deba@1820:       }
deba@1820: 
deba@1820:       NodeIt(const Graph& _graph, const Node& node) 
deba@1820: 	: Node(node), graph(&_graph) { }
deba@1820:     
deba@1820:       NodeIt& operator++() { 
deba@1820: 	graph->next(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820: 
deba@1820:     };
deba@1820: 
deba@1820:     class UpperNodeIt : public Node { 
deba@1820:       friend class IterableUndirBipartiteGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1820:       UpperNodeIt() { }
deba@1820:     
deba@1820:       UpperNodeIt(Invalid i) : Node(INVALID) { }
deba@1820:     
deba@1820:       explicit UpperNodeIt(const Graph& _graph) : graph(&_graph) {
deba@1820: 	graph->firstUpper(static_cast<Node&>(*this));
deba@1820:       }
deba@1820: 
deba@1820:       UpperNodeIt(const Graph& _graph, const Node& node) 
deba@1820: 	: Node(node), graph(&_graph) {}
deba@1820:     
deba@1820:       UpperNodeIt& operator++() { 
deba@1820: 	graph->nextUpper(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820:     };
deba@1820: 
deba@1820:     class LowerNodeIt : public Node { 
deba@1820:       friend class IterableUndirBipartiteGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1820:       LowerNodeIt() { }
deba@1820:     
deba@1820:       LowerNodeIt(Invalid i) : Node(INVALID) { }
deba@1820:     
deba@1820:       explicit LowerNodeIt(const Graph& _graph) : graph(&_graph) {
deba@1820: 	graph->firstLower(static_cast<Node&>(*this));
deba@1820:       }
deba@1820: 
deba@1820:       LowerNodeIt(const Graph& _graph, const Node& node) 
deba@1820: 	: Node(node), graph(&_graph) {}
deba@1820:     
deba@1820:       LowerNodeIt& operator++() { 
deba@1820: 	graph->nextLower(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820:     };
deba@1820: 
deba@1820:     class EdgeIt : public Edge { 
deba@1820:       friend class IterableUndirBipartiteGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1820:       EdgeIt() { }
deba@1820:     
deba@1820:       EdgeIt(Invalid i) : Edge(INVALID) { }
deba@1820:     
deba@1820:       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
deba@1820: 	graph->first(static_cast<Edge&>(*this));
deba@1820:       }
deba@1820: 
deba@1820:       EdgeIt(const Graph& _graph, const Edge& edge) 
deba@1820: 	: Edge(edge), graph(&_graph) { }
deba@1820:     
deba@1820:       EdgeIt& operator++() { 
deba@1820: 	graph->next(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820: 
deba@1820:     };
deba@1820: 
deba@1820:     class UndirEdgeIt : public UndirEdge { 
deba@1820:       friend class IterableUndirBipartiteGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1820:       UndirEdgeIt() { }
deba@1820:     
deba@1820:       UndirEdgeIt(Invalid i) : UndirEdge(INVALID) { }
deba@1820:     
deba@1820:       explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
deba@1820: 	graph->first(static_cast<UndirEdge&>(*this));
deba@1820:       }
deba@1820: 
deba@1820:       UndirEdgeIt(const Graph& _graph, const UndirEdge& edge) 
deba@1820: 	: UndirEdge(edge), graph(&_graph) { }
deba@1820:     
deba@1820:       UndirEdgeIt& operator++() { 
deba@1820: 	graph->next(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820:     };
deba@1820: 
deba@1820:     class OutEdgeIt : public Edge { 
deba@1820:       friend class IterableUndirBipartiteGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1820:       OutEdgeIt() { }
deba@1820:     
deba@1820:       OutEdgeIt(Invalid i) : Edge(i) { }
deba@1820:     
deba@1820:       OutEdgeIt(const Graph& _graph, const Node& node) 
deba@1820: 	: graph(&_graph) {
deba@1820: 	graph->firstOut(*this, node);
deba@1820:       }
deba@1820:     
deba@1820:       OutEdgeIt(const Graph& _graph, const Edge& edge) 
deba@1820: 	: Edge(edge), graph(&_graph) {}
deba@1820:     
deba@1820:       OutEdgeIt& operator++() { 
deba@1820: 	graph->nextOut(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820: 
deba@1820:     };
deba@1820: 
deba@1820: 
deba@1820:     class InEdgeIt : public Edge { 
deba@1820:       friend class IterableUndirBipartiteGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1820:       InEdgeIt() { }
deba@1820:     
deba@1820:       InEdgeIt(Invalid i) : Edge(i) { }
deba@1820:     
deba@1820:       InEdgeIt(const Graph& _graph, const Node& node) 
deba@1820: 	: graph(&_graph) {
deba@1820: 	graph->firstIn(*this, node);
deba@1820:       }
deba@1820:     
deba@1820:       InEdgeIt(const Graph& _graph, const Edge& edge) : 
deba@1820: 	Edge(edge), graph(&_graph) {}
deba@1820:     
deba@1820:       InEdgeIt& operator++() { 
deba@1820: 	graph->nextIn(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820: 
deba@1820:     };
deba@1820:   
deba@1820:     /// \brief Base node of the iterator
deba@1820:     ///
deba@1820:     /// Returns the base node (ie. the source in this case) of the iterator
deba@1820:     Node baseNode(const OutEdgeIt &e) const {
deba@1820:       return Parent::source((Edge&)e);
deba@1820:     }
deba@1820:     /// \brief Running node of the iterator
deba@1820:     ///
deba@1820:     /// Returns the running node (ie. the target in this case) of the
deba@1820:     /// iterator
deba@1820:     Node runningNode(const OutEdgeIt &e) const {
deba@1820:       return Parent::target((Edge&)e);
deba@1820:     }
deba@1820:   
deba@1820:     /// \brief Base node of the iterator
deba@1820:     ///
deba@1820:     /// Returns the base node (ie. the target in this case) of the iterator
deba@1820:     Node baseNode(const InEdgeIt &e) const {
deba@1820:       return Parent::target((Edge&)e);
deba@1820:     }
deba@1820:     /// \brief Running node of the iterator
deba@1820:     ///
deba@1820:     /// Returns the running node (ie. the source in this case) of the
deba@1820:     /// iterator
deba@1820:     Node runningNode(const InEdgeIt &e) const {
deba@1820:       return Parent::source((Edge&)e);
deba@1820:     }
deba@1820:   
deba@1820:     class IncEdgeIt : public Parent::UndirEdge { 
deba@1820:       friend class IterableUndirBipartiteGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:       bool direction;
deba@1820:     public:
deba@1820:     
deba@1820:       IncEdgeIt() { }
deba@1820:     
deba@1820:       IncEdgeIt(Invalid i) : UndirEdge(i), direction(true) { }
deba@1820:     
deba@1820:       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
deba@1820: 	graph->firstInc(*this, direction, n);
deba@1820:       }
deba@1820: 
deba@1820:       IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
deba@1820: 	: graph(&_graph), UndirEdge(ue) {
deba@1820: 	direction = (graph->source(ue) == n);
deba@1820:       }
deba@1820: 
deba@1820:       IncEdgeIt& operator++() {
deba@1820: 	graph->nextInc(*this, direction);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820:     };
deba@1820:   
deba@1820: 
deba@1820:     /// Base node of the iterator
deba@1820:     ///
deba@1820:     /// Returns the base node of the iterator
deba@1820:     Node baseNode(const IncEdgeIt &e) const {
deba@1820:       return e.direction ? source(e) : target(e);
deba@1820:     }
deba@1820: 
deba@1820:     /// Running node of the iterator
deba@1820:     ///
deba@1820:     /// Returns the running node of the iterator
deba@1820:     Node runningNode(const IncEdgeIt &e) const {
deba@1820:       return e.direction ? target(e) : source(e);
deba@1820:     }
deba@1820:   
deba@1820:   };
deba@1820: 
klao@946: }
klao@946: 
klao@946: #endif // LEMON_GRAPH_EXTENDER_H