/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   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.
*/

#ifndef _POLYMAKE_GENERIC_GRAPH_H
#define _POLYMAKE_GENERIC_GRAPH_H "$Project: polymake $$Id: GenericGraph.h 7402 2006-07-27 23:44:14Z gawrilow $"

#ifndef _POLYMAKE_TRANSFORMED_CONTAINER_H
#  include <TransformedContainer.h>
#endif

namespace pm {
namespace graph {

enum kind { undirected, directed, skew };

template <typename GraphRef>
struct kind_helper {
   typedef typename deref<GraphRef>::type graph_type;
   static const kind dir=graph_type::dir;
};

template <typename NodeAttr=nothing, typename EdgeAttr=nothing, kind dir=undirected>
class Graph;

template <typename NodeIterator, typename ApparentAttr> class composite_entry;

template <typename NodeIterator>
class composite_entry<NodeIterator, void> : public NodeIterator {
protected:
   composite_entry();
   ~composite_entry();
};

template <typename NodeIterator, typename ApparentEdgeAttr>
class edge_list_ignore_attr
   : public modified_container_impl< edge_list_ignore_attr<NodeIterator,ApparentEdgeAttr>,
				     list( Hidden< typename deref<typename NodeIterator::out_edge_list_ref>::type >,
					   Operation< operations::masquerade2<ignore,ApparentEdgeAttr> > ) > {
   typedef modified_container_impl<edge_list_ignore_attr> _super;
public:
   typedef typename _super::iterator iterator;
   iterator insert(int i)
   {
      return iterator(this->hidden().insert(i));
   }
   iterator insert(const iterator& where, int i)
   {
      return iterator(this->hidden().insert(where,i));
   }
   void erase(const iterator& where)
   {
      this->hidden().erase(where);
   }
   void clear() { this->hidden().clear(); }

   typename _super::hidden_type::max_input_dim_type max_input_dim() const
   {
      return this->hidden().max_input_dim();
   }
};

template <typename NodeIterator, typename ApparentEdgeAttr,
	  bool _is_ref=attrib<typename NodeIterator::out_edge_list_ref>::is_reference>
class composite_entry_ignore_edge : public NodeIterator {
protected:
   composite_entry_ignore_edge();
   ~composite_entry_ignore_edge();
public:
   typedef typename inherit_ref<edge_list_ignore_attr<NodeIterator,ApparentEdgeAttr>,
				typename NodeIterator::out_edge_list_ref>::type
      out_edge_list_ref;

   out_edge_list_ref out_edges() const
   {
      return reinterpret_cast<out_edge_list_ref>(static_cast<const NodeIterator*>(this)->out_edges());
   }
};

template <typename NodeIterator, typename ApparentEdgeAttr>
class composite_entry_ignore_edge<NodeIterator, ApparentEdgeAttr, false> : public NodeIterator {
protected:
   composite_entry_ignore_edge();
   ~composite_entry_ignore_edge();
public:
   typedef TransformedContainer<typename NodeIterator::out_edge_list_ref, operations::masquerade2<ignore,ApparentEdgeAttr> >
      out_edge_list_ref;

   out_edge_list_ref out_edges() const
   {
      return out_edge_list_ref(static_cast<const NodeIterator*>(this)->out_edges());
   }
};

template <typename NodeIterator, typename ApparentEdgeAttr>
class composite_entry
   : public composite_entry_ignore_edge<NodeIterator, ApparentEdgeAttr> { };

template <typename NodeIterator, typename ApparentNodeAttr, typename ApparentEdgeAttr>
class composite_entry<NodeIterator, cons<ApparentNodeAttr, ApparentEdgeAttr> >
   : public composite_entry<NodeIterator, ApparentEdgeAttr> {
public:
   typedef ignore<typename iterator_traits<NodeIterator>::value_type, ApparentNodeAttr> value_type;
   typedef typename inherit_const<value_type, typename NodeIterator::reference>::type& reference;

   reference operator* () const
   {
      return reinterpret_cast<reference>(*static_cast<const NodeIterator&>(*this));
   }
};

template <typename NodeContainer, typename ApparentAttr=void>
class CompositeContainer
   : public modified_container_impl< CompositeContainer<NodeContainer,ApparentAttr>,
				     list( Hidden< typename attrib<NodeContainer>::minus_ref >,
					   Operation< operations::masquerade2_it_nonconst<composite_entry, ApparentAttr> > ) > {
protected:
   ~CompositeContainer();
public:
   void clear() { this->hidden().resize(0); }
   void resize(int n) { this->hidden().resize(n); }
};

} // end namespace pm::graph

template <typename Graph,
	  typename NodeAttr=typename Graph::node_attr,
	  typename EdgeAttr=typename Graph::edge_attr,
	  graph::kind _dir=Graph::dir>
class GenericGraph : public Generic<Graph> {
public:
   static const graph::kind dir=_dir;
   typedef NodeAttr node_attr;
   typedef EdgeAttr edge_attr;

   typedef GenericGraph generic_type;
   typedef graph::Graph<NodeAttr, EdgeAttr, dir> persistent_type;

   template <typename Result>
   struct rebind_generic {
      typedef GenericGraph<Result, node_attr, edge_attr, dir> type;
   };

   int nodes() const
   {
      AssertOVERLOADED(GenericGraph,Graph,nodes);
      return this->top().nodes();
   }
};

template <typename NodeIterator, typename ApparentAttr>
struct spec_object_traits< graph::composite_entry<NodeIterator, ApparentAttr> >
   : spec_object_traits<is_composite> {

   typedef cons<typename graph::composite_entry<NodeIterator, ApparentAttr>::value_type,
		typename deref<typename graph::composite_entry<NodeIterator, ApparentAttr>::out_edge_list_ref>::type>
      elements;

   template <typename Me, typename Visitor>
   static void visit_elements(Me& me, Visitor& v)
   {
      v << *me << me.out_edges();
   }
};

template <typename NodeIterator, typename ApparentEdgeAttr>
struct redirect_object_traits< graph::edge_list_ignore_attr<NodeIterator, ApparentEdgeAttr> >
   : object_traits< typename deref<typename NodeIterator::out_edge_list_ref>::type > { };

template <typename NodeIterator, typename ApparentEdgeAttr>
struct check_container_feature< graph::edge_list_ignore_attr<NodeIterator, ApparentEdgeAttr>, sparse > : True { };

struct is_graph;

template <typename Graph, typename NodeAttr, typename EdgeAttr, graph::kind _dir>
struct spec_object_traits< GenericGraph<Graph,NodeAttr,EdgeAttr,_dir> >
   : spec_or_model_traits<Graph,is_scalar> {
   typedef is_graph generic_tag;

   typedef graph::CompositeContainer<typename Graph::node_container_ref> serialized;

   static serialized&
   serialize(Graph& G)
   {
      return composite(G);
   }
   static const graph::CompositeContainer<typename Graph::const_node_container_ref>&
   serialize(const Graph& G)
   {
      return composite(G);
   }

   static const bool IO_ends_with_eol=true;
};

template <typename Graph>
class Nodes : public Graph::node_container {
protected:
   Nodes();
   ~Nodes();
};

template <typename Graph>
class Edges : public Graph::edge_container {
protected:
   Edges();
   ~Edges();
};

template <typename Graph>
class NodeNeighborhood : public Graph::neighborhood_matrix {
protected:
   NodeNeighborhood();
   ~NodeNeighborhood();
};

template <typename Graph> inline
typename Graph::node_container_ref
nodes(GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::node_container_ref>();
}
template <typename Graph> inline
typename Graph::const_node_container_ref
nodes(const GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::const_node_container_ref>();
}

template <typename Graph> inline
typename Graph::edge_container_ref
edges(GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::edge_container_ref>();
}
template <typename Graph> inline
typename Graph::const_edge_container_ref
edges(const GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::const_edge_container_ref>();
}

template <typename Graph> inline
typename Graph::out_edge_list_container_ref
out_edge_lists(GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::out_edge_list_container_ref>();
}
template <typename Graph> inline
typename Graph::const_out_edge_list_container_ref
out_edge_lists(const GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::const_out_edge_list_container_ref>();
}

template <typename Graph> inline
typename Graph::in_edge_list_container_ref
in_edge_lists(GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::in_edge_list_container_ref>();
}
template <typename Graph> inline
typename Graph::const_in_edge_list_container_ref
in_edge_lists(const GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::const_in_edge_list_container_ref>();
}

template <typename Graph> inline
typename Graph::neighborhood_matrix_ref
neighborhood_matrix(GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::neighborhood_matrix_ref>();
}
template <typename Graph> inline
typename Graph::const_neighborhood_matrix_ref
neighborhood_matrix(const GenericGraph<Graph>& G)
{
   return G.top().template pretend<typename Graph::const_neighborhood_matrix_ref>();
}

template <typename ApparentAttr, typename Graph> inline
graph::CompositeContainer<typename Graph::node_container_ref, ApparentAttr>&
composite(GenericGraph<Graph>& G)
{
   return G.top().template pretend< graph::CompositeContainer<typename Graph::node_container_ref, ApparentAttr>& >();
}
template <typename ApparentAttr, typename Graph> inline
const graph::CompositeContainer<typename Graph::const_node_container_ref, ApparentAttr>&
composite(const GenericGraph<Graph>& G)
{
   return G.top().template pretend< const graph::CompositeContainer<typename Graph::const_node_container_ref, ApparentAttr>& >();
}

template <typename Graph> inline
graph::CompositeContainer<typename Graph::node_container_ref>&
composite(GenericGraph<Graph>& G)
{
   return composite<void>(G);
}
template <typename Graph> inline
const graph::CompositeContainer<typename Graph::const_node_container_ref>&
composite(const GenericGraph<Graph>& G)
{
   return composite<void>(G);
}

template <typename Graph> inline
graph::CompositeContainer<typename Graph::node_container_ref, cons<nothing,void> >&
ignore_node_attrs(GenericGraph<Graph>& G)
{
   return composite< cons<nothing,void> >(G);
}

template <typename Graph> inline
const graph::CompositeContainer<typename Graph::const_node_container_ref, cons<nothing,void> >&
ignore_node_attrs(const GenericGraph<Graph>& G)
{
   return composite< cons<nothing,void> >(G);
}

template <typename ExpectedNodeAttr, typename Graph> inline
graph::CompositeContainer<typename Graph::node_container_ref, cons<ExpectedNodeAttr,void> >&
ignore_node_attrs(GenericGraph<Graph>& G)
{
   return composite< cons<ExpectedNodeAttr,void> >(G);
}

template <typename ExpectedNodeAttr, typename Graph> inline
const graph::CompositeContainer<typename Graph::const_node_container_ref, cons<ExpectedNodeAttr,void> >&
ignore_node_attrs(const GenericGraph<Graph>& G)
{
   return composite< cons<ExpectedNodeAttr,void> >(G);
}

template <typename Graph> inline
graph::CompositeContainer<typename Graph::node_container_ref, nothing>&
ignore_edge_attrs(GenericGraph<Graph>& G)
{
   return composite<nothing>(G);
}

template <typename Graph> inline
const graph::CompositeContainer<typename Graph::const_node_container_ref, nothing>&
ignore_edge_attrs(const GenericGraph<Graph>& G)
{
   return composite<nothing>(G);
}

template <typename ExpectedEdgeAttr, typename Graph> inline
graph::CompositeContainer<typename Graph::node_container_ref, ExpectedEdgeAttr>&
ignore_edge_attrs(GenericGraph<Graph>& G)
{
   return composite<ExpectedEdgeAttr>(G);
}

template <typename ExpectedEdgeAttr, typename Graph> inline
const graph::CompositeContainer<typename Graph::const_node_container_ref, ExpectedEdgeAttr>&
ignore_edge_attrs(const GenericGraph<Graph>& G)
{
   return composite<ExpectedEdgeAttr>(G);
}

template <typename Graph> inline
graph::CompositeContainer<typename Graph::node_container_ref, cons<nothing,nothing> >&
ignore_attrs(GenericGraph<Graph>& G)
{
   return composite< cons<nothing,nothing> >(G);
}

template <typename Graph> inline
const graph::CompositeContainer<typename Graph::const_node_container_ref, cons<nothing,nothing> >&
ignore_attrs(const GenericGraph<Graph>& G)
{
   return composite< cons<nothing,nothing> >(G);
}

template <typename ExpectedNodeAttr, typename ExpectedEdgeAttr, typename Graph> inline
graph::CompositeContainer<typename Graph::node_container_ref, cons<ExpectedNodeAttr,ExpectedEdgeAttr> >&
ignore_attrs(GenericGraph<Graph>& G)
{
   return composite< cons<ExpectedNodeAttr,ExpectedEdgeAttr> >(G);
}

template <typename ExpectedNodeAttr, typename ExpectedEdgeAttr, typename Graph> inline
const graph::CompositeContainer<typename Graph::const_node_container_ref, cons<ExpectedNodeAttr,ExpectedEdgeAttr> >&
ignore_attrs(const GenericGraph<Graph>& G)
{
   return composite< cons<ExpectedNodeAttr,ExpectedEdgeAttr> >(G);
}

} // end namespace pm

namespace polymake {
   using pm::GenericGraph;
   using pm::graph::directed;
   using pm::graph::undirected;
   using pm::Nodes;
   using pm::Edges;
   using pm::NodeNeighborhood;
   using pm::ignore_node_attrs;
   using pm::ignore_edge_attrs;
   using pm::ignore_attrs;
}

#endif // _POLYMAKE_GENERIC_GRAPH_H

// Local Variables:
// mode:C++
// End:
