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?
klao@1909:     typedef False UTag;
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@1909:   class IterableUGraphExtender : 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.
klao@1909:     typedef True UTag;
alpar@1448: 
klao@962:     typedef IterableGraphExtender<_Base> Parent;
klao@1909:     typedef IterableUGraphExtender<_Base> Graph;
klao@1021:     typedef typename Parent::Node Node;
deba@1627:     typedef typename Parent::Edge Edge;
klao@1909:     typedef typename Parent::UEdge UEdge;
klao@962: 
klao@1909:     class UEdgeIt : public Parent::UEdge { 
klao@962:       const Graph* graph;
klao@962:     public:
klao@962: 
klao@1909:       UEdgeIt() { }
klao@962: 
klao@1909:       UEdgeIt(Invalid i) : UEdge(i) { }
klao@962: 
klao@1909:       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
klao@1909: 	_graph.first(*static_cast<UEdge*>(this));
klao@962:       }
klao@962: 
klao@1909:       UEdgeIt(const Graph& _graph, const UEdge& e) : 
klao@1909: 	UEdge(e), graph(&_graph) { }
klao@962: 
klao@1909:       UEdgeIt& operator++() { 
klao@962: 	graph->next(*this);
klao@962: 	return *this; 
klao@962:       }
klao@962: 
klao@962:     };
klao@962: 
klao@1909:     class IncEdgeIt : public Parent::UEdge { 
klao@1021:       const Graph* graph;
deba@1704:       bool direction;
klao@1909:       friend class IterableUGraphExtender;
klao@1021:     public:
klao@1021: 
klao@1030:       IncEdgeIt() { }
klao@1021: 
klao@1909:       IncEdgeIt(Invalid i) : UEdge(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@1909:       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
klao@1909: 	: graph(&_graph), UEdge(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.
klao@1909:     Node oppositeNode(const Node& n, const UEdge& 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@1910:   class IterableBpUGraphExtender : public _Base {
deba@1820:   public:
deba@1820:     typedef _Base Parent;
deba@1910:     typedef IterableBpUGraphExtender Graph;
deba@1820:    
deba@1820:     typedef typename Parent::Node Node;
deba@1910:     typedef typename Parent::ANode ANode;
deba@1910:     typedef typename Parent::BNode BNode;
deba@1820:     typedef typename Parent::Edge Edge;
klao@1909:     typedef typename Parent::UEdge UEdge;
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@1910:     class ANodeIt : public Node { 
deba@1910:       friend class IterableBpUGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1910:       ANodeIt() { }
deba@1820:     
deba@1910:       ANodeIt(Invalid i) : Node(INVALID) { }
deba@1820:     
deba@1910:       explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
deba@1910: 	graph->firstANode(static_cast<Node&>(*this));
deba@1820:       }
deba@1820: 
deba@1910:       ANodeIt(const Graph& _graph, const Node& node) 
deba@1820: 	: Node(node), graph(&_graph) {}
deba@1820:     
deba@1910:       ANodeIt& operator++() { 
deba@1910: 	graph->nextANode(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820:     };
deba@1820: 
deba@1910:     class BNodeIt : public Node { 
deba@1910:       friend class IterableBpUGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
deba@1910:       BNodeIt() { }
deba@1820:     
deba@1910:       BNodeIt(Invalid i) : Node(INVALID) { }
deba@1820:     
deba@1910:       explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
deba@1910: 	graph->firstBNode(static_cast<Node&>(*this));
deba@1820:       }
deba@1820: 
deba@1910:       BNodeIt(const Graph& _graph, const Node& node) 
deba@1820: 	: Node(node), graph(&_graph) {}
deba@1820:     
deba@1910:       BNodeIt& operator++() { 
deba@1910: 	graph->nextBNode(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820:     };
deba@1820: 
deba@1820:     class EdgeIt : public Edge { 
deba@1910:       friend class IterableBpUGraphExtender;
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: 
klao@1909:     class UEdgeIt : public UEdge { 
deba@1910:       friend class IterableBpUGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:     public:
deba@1820:     
klao@1909:       UEdgeIt() { }
deba@1820:     
klao@1909:       UEdgeIt(Invalid i) : UEdge(INVALID) { }
deba@1820:     
klao@1909:       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
klao@1909: 	graph->first(static_cast<UEdge&>(*this));
deba@1820:       }
deba@1820: 
klao@1909:       UEdgeIt(const Graph& _graph, const UEdge& edge) 
klao@1909: 	: UEdge(edge), graph(&_graph) { }
deba@1820:     
klao@1909:       UEdgeIt& operator++() { 
deba@1820: 	graph->next(*this);
deba@1820: 	return *this; 
deba@1820:       }
deba@1820:     };
deba@1820: 
deba@1820:     class OutEdgeIt : public Edge { 
deba@1910:       friend class IterableBpUGraphExtender;
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@1910:       friend class IterableBpUGraphExtender;
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:   
klao@1909:     class IncEdgeIt : public Parent::UEdge { 
deba@1910:       friend class IterableBpUGraphExtender;
deba@1820:       const Graph* graph;
deba@1820:       bool direction;
deba@1820:     public:
deba@1820:     
deba@1820:       IncEdgeIt() { }
deba@1820:     
klao@1909:       IncEdgeIt(Invalid i) : UEdge(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: 
klao@1909:       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
klao@1909: 	: graph(&_graph), UEdge(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