/* 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_HASSE_DIAGRAM_H
#define _POLYMAKE_HASSE_DIAGRAM_H "$Project: polymake $$Id: HasseDiagram.h 6800 2006-01-19 14:24:44Z gawrilow $"

#ifndef _POLYMAKE_GRAPH_H
#  include <Graph.h>
#endif
#ifndef _POLYMAKE_SET_H
#  include <Set.h>
#endif

#include <vector>
#include STD_EXT_HEADER1(algorithm)

namespace pm {

template <typename VertexSet, typename EdgeAttr, typename ApparentAttr>
class HasseDiagramIgnoredAttr;

template <typename VertexSet=Set<int>, typename EdgeAttr=nothing>
class HasseDiagram : public graph::Graph< VertexSet, EdgeAttr, graph::directed> {
protected:
   std::vector<int> dim_map;
public:
   typedef graph::Graph< VertexSet, EdgeAttr, graph::directed> super;

   bool built_dually() const { return this->in_degree(0)!=0; }

   void next_layer()
   {
      dim_map.push_back(this->nodes());
   }

   HasseDiagram() { }

   void clear()
   {
      super::clear();
      dim_map.clear();
   }

   int dim() const { return dim_map.size()-1; }

   const sequence nodes_of_dim(int d) const
   {
      int D=dim();
      if (d<0) d+=D;
      DIMENSION_CHECK((d<0 || d>D), "nodes_of_dim - dimension out of range");
      if (d==D) return sequence(top_node(), 1);
      if (built_dually()) d=D-1-d;
      return range(dim_map[d], dim_map[d+1]-1);
   }

   const sequence nodes_of_dim(int d1, int d2) const
   {
      int D=dim();
      if (d1<0) d1+=D;
      if (d2<0) d2+=D;
      DIMENSION_CHECK((d1<0 || d2>D || d1>d2), "nodes_of_dim - dimension out of range");
      if (d2==D) {
	 if (built_dually()) {
	    return range(0, dim_map[D-d1]-1);
	 } else {
	    return range(dim_map[d1], this->nodes()-1);
	 }
      }
      if (built_dually()) {
	 int _d1=d1; d1=D-1-d2; d2=D-1-_d1;
      }
      return range(dim_map[d1], dim_map[d2+1]-1);
   }

   int bottom_node() const
   {
      return built_dually() ? this->nodes()-1 : 0;
   }

   int top_node() const
   {
      return built_dually() ? 0 : this->nodes()-1;
   }

   int dim_of_node(int n) const {
      INDEX_CHECK((n<0 || n>=this->nodes()), "dim_of_node - node index out of range");
      int d = std::upper_bound(dim_map.begin(), dim_map.end(), n) - dim_map.begin();
      int D=dim();
      return built_dually() ? D-d : d-1;
   }

protected:
   void update_dim_after_delete()
   {
      std::vector<int>::iterator map_begin=dim_map.begin(), map_end=dim_map.end();
      const int n=this->nodes()-1;
      std::vector<int>::iterator d=map_end-2;
      while (d >= map_begin && *d==n) --d;
      dim_map.erase(d+1, map_end-1);
      d=map_begin+1;
      while (d < map_end && *d==1) ++d;
      dim_map.erase(map_begin+1, d);
   }

   template <typename Iterator>
   void update_map_after_delete(Iterator n)
   {
      int cnt=0;
      typename std::vector<int>::iterator map_end=dim_map.end();
      for (typename std::vector<int>::iterator d=std::upper_bound(dim_map.begin(), map_end, *n);
	   d != map_end;  ++d) {
	 while (!n.at_end() && *n<*d) ++n, ++cnt;
	 *d -= cnt;
      }
      update_dim_after_delete();
   }
public:
   void delete_node(int n)
   {
      INDEX_CHECK((n<=0 || n>=this->nodes()-1), "delete_node - node number out of range");
      super::delete_node(n);
      for (std::vector<int>::iterator map_end=dim_map.end(), d=std::upper_bound(dim_map.begin(), map_end, n);
	   d != map_end;  ++d)
	 *d -= 1;
      update_dim_after_delete();
   }

   template <typename Top>
   void delete_nodes(const GenericSet<Top>& nodes_to_delete)
   {
      if (nodes_to_delete.top().empty()) return;
      INDEX_CHECK((nodes_to_delete.top().front() <= 0 || nodes_to_delete.top().back() >= this->nodes()-1),
		  "delete_nodes - node numbers out of range");
      super::delete_nodes(nodes_to_delete);
      update_map_after_delete(entire(nodes_to_delete));
   }

   template <typename Top>
   void delete_nodes(const Complement<Top>& nodes_to_delete)
   {
      INDEX_CHECK((nodes_to_delete.top().empty() ||
		   nodes_to_delete.top().front() != 0 || nodes_to_delete.top().back() != this->nodes()-1),
		  "delete_nodes - node numbers out of range");
      super::delete_nodes(nodes_to_delete);
      update_map_after_delete(entire(sequence(0,this->nodes())*nodes_to_delete));
   }

   class _filler {
   protected:
      mutable HasseDiagram* G;
   public:
      _filler(HasseDiagram& G_arg) : G(&G_arg) {
	 if (G->nodes()) G->clear();
      }

      _filler(const _filler& f) : G(f.G) { f.G=0; }

      template <typename _Set>
      int add_node(const GenericSet<_Set>& vertex_set) const {
	 int n=G->nodes();
	 G->resize(n+1);
	 G->node(n)=vertex_set;
	 return n;
      }

      template <typename Iterator>
      int add_nodes(int n, Iterator vertex_sets) const {
	 int n_old=G->nodes();
	 G->resize(n_old+n);
	 std_ext::copy_n(vertex_sets, n, pm::nodes(*G).begin()+n_old);
	 return n_old;
      }

      /// face n_from must be included in face n_to
      void add_edge(int n_from, int n_to) const {
	 G->edge(n_from, n_to);
      }

      void increase_dim() const { G->next_layer(); }

      ~_filler() {
	 if (G) G->get_table().resize(G->nodes());
      }
   };

   class _flex_filler : public _filler {
      const bool primal;
   public:
      _flex_filler(HasseDiagram& G_arg, bool primal_arg) : _filler(G_arg), primal(primal_arg) { }

      _flex_filler(const _flex_filler& f) : _filler(f), primal(f.primal) { }

      template <typename VSet, typename FSet>
      int add_node(const GenericSet<VSet>& vertex_set, const GenericSet<FSet>& facet_set) const
      {
	 int n=this->G->nodes();
	 this->G->resize(n+1);
	 if (primal)
	    this->G->node(n)=vertex_set;
	 else
	    this->G->node(n)=facet_set;
	 return n;
      }

      template <typename Iterator1, typename Iterator2>
      int add_nodes(int n, Iterator1 vertex_sets, Iterator2 facet_sets) const
      {
	 int n_old=this->G->nodes();
	 this->G->resize(n_old+n);
	 if (primal)
	    std_ext::copy_n(vertex_sets, n, pm::nodes(*this->G).begin()+n_old);
	 else
	    std_ext::copy_n(facet_sets, n, pm::nodes(*this->G).begin()+n_old);
	 return n_old;
      }

      void add_edge(int n_from, int n_to) const
      {
	 if (primal)
	    this->G->edge(n_from, n_to);
	 else
	    this->G->edge(n_to, n_from);
      }
   };

   friend
   _filler filler(HasseDiagram& G) { return _filler(G); }
   friend
   _flex_filler filler(HasseDiagram& G, bool primal) { return _flex_filler(G,primal); }

   template <typename,typename,typename> friend class HasseDiagramIgnoredAttr;
   friend class generic_object_traits<HasseDiagram>;
};

template <typename VertexSet, typename EdgeAttr>
struct generic_object_traits< HasseDiagram<VertexSet, EdgeAttr> >
   : spec_object_traits<is_composite> {
   typedef cons< std::vector<int>, typename HasseDiagram<VertexSet, EdgeAttr>::super > elements;

   template <typename Me, typename Visitor> static
   void visit_elements(Me& x, Visitor& v)
   {
      v << x.dim_map
	<< static_cast<typename inherit_const<typename HasseDiagram<VertexSet, EdgeAttr>::super, Me>::type&>(x);
   }
};

template <typename VertexSet, typename EdgeAttr, typename ApparentAttr>
class HasseDiagramIgnoredAttr {
protected:
   ~HasseDiagramIgnoredAttr();
public:
   typedef HasseDiagram<VertexSet, EdgeAttr> hidden_type;

   hidden_type& hidden() { return reinterpret_cast<hidden_type&>(*this); }
   const hidden_type& hidden() const { return reinterpret_cast<const hidden_type&>(*this); }

   typedef graph::CompositeContainer<typename hidden_type::super::node_container_ref, ApparentAttr>
      graph_composite_type;
   typedef graph::CompositeContainer<typename hidden_type::super::const_node_container_ref, ApparentAttr>
      const_graph_composite_type;
protected:
   std::vector<int>& dim_map() { return hidden().dim_map; }
   const std::vector<int>& dim_map() const { return hidden().dim_map; }

   graph_composite_type& graph() { return hidden().template pretend<graph_composite_type&>(); }
   const const_graph_composite_type& graph() const { return hidden().template pretend<const const_graph_composite_type&>(); }

   friend class spec_object_traits<HasseDiagramIgnoredAttr>;
};

template <typename VertexSet, typename EdgeAttr, typename ApparentAttr>
struct spec_object_traits< HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, ApparentAttr> >
   : spec_object_traits<is_composite> {

   typedef cons< std::vector<int>, typename HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, ApparentAttr>::graph_composite_type > elements;

   template <typename Me, typename Visitor> static
   void visit_elements(Me& x, Visitor& v)
   {
      v << x.dim_map() << x.graph();
   }
};

template <typename VertexSet, typename EdgeAttr> inline
HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, cons<nothing,nothing> >&
ignore_attrs(HasseDiagram<VertexSet,EdgeAttr>& H)
{
   return reinterpret_cast<HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, cons<nothing,nothing> >&>(H);
}
template <typename VertexSet, typename EdgeAttr> inline
const HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, cons<nothing,nothing> >&
ignore_attrs(const HasseDiagram<VertexSet,EdgeAttr>& H)
{
   return reinterpret_cast<const HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, cons<nothing,nothing> >&>(H);
}
template <typename VertexSet, typename EdgeAttr> inline
HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, cons<nothing,void> >&
ignore_node_attrs(HasseDiagram<VertexSet,EdgeAttr>& H)
{
   return reinterpret_cast<HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, cons<nothing,void> >&>(H);
}
template <typename VertexSet, typename EdgeAttr> inline
const HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, cons<nothing,void> >&
ignore_node_attrs(const HasseDiagram<VertexSet,EdgeAttr>& H)
{
   return reinterpret_cast<const HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, cons<nothing,void> >&>(H);
}
template <typename VertexSet, typename EdgeAttr> inline
HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, nothing>&
ignore_edge_attrs(HasseDiagram<VertexSet,EdgeAttr>& H)
{
   return reinterpret_cast<HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, nothing>&>(H);
}
template <typename VertexSet, typename EdgeAttr> inline
const HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, nothing>&
ignore_edge_attrs(const HasseDiagram<VertexSet,EdgeAttr>& H)
{
   return reinterpret_cast<const HasseDiagramIgnoredAttr<VertexSet, EdgeAttr, nothing>&>(H);
}

} // end namespace pm

namespace polymake {
   using pm::HasseDiagram;
}

#endif // _POLYMAKE_HASSE_DIAGRAM_H

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