/* Copyright (c) 1997-2004
   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_PSEUDO_COMPLEX_H
#define _POLYMAKE_PSEUDO_COMPLEX_H "$Project: polymake $$Id: PseudoComplex.h,v 1.4 2004/11/23 16:55:07 witte Exp $"

#include <HasseDiagram.h>
#include <Graph.h>
#include <Bitset.h>
#include <Set.h>

#include <list>
#include <vector>


namespace polymake { namespace topaz {
   
class PseudoComplex : public Graph< Set<int>,nothing,directed > {
   
/* Face-lattice of a pseudo simpicial complex. The node attributes carry the
 * vertex sets of the corresponding face. Vertices may be numbered arbitrarily.
 * There is no prescribed relation between the nodes and faces.
 *
 * super:           face lattice
 * node attr:       vertex set
 * dim_map:         list of nodes of dim d, d=0..dim()
 * the_bottom_node: node corresp. to empty face
 * the_top_node:    node corresp. to the entire complex
 * dim():           max dim of the facets
 */

protected:
   std::vector< std::list<int> > dim_map;
   int the_top_node;
   int the_bottom_node;
   
public:
   typedef Graph< Set<int>,nothing,directed > super;
   
   PseudoComplex() : the_top_node(0), the_bottom_node(0) {};
   
   PseudoComplex(const HasseDiagram<>& HD) {
      the_top_node = HD.top_node();   
      the_bottom_node = HD.bottom_node();   
      dim_map.resize(HD.dim());  // dim of bound. compl. of P = dim(P) - 1 

      super::resize(HD.nodes());

      for (int d=0; d<HD.dim(); ++d)
	 for (Entire<sequence>::const_iterator n=entire(HD.nodes_of_dim(d));
	      !n.at_end(); ++n) {
	    super::node(*n) = HD.node(*n);
	    dim_map[d].push_back(*n);

	    if (d==0)  // add edges from the_bottom_node
	      super::edge(the_bottom_node,*n);
	    
	    for (Entire<HasseDiagram<>::out_edge_list>::const_iterator e=entire(HD.out_edges(*n));
		 !e.at_end(); ++e)
	      super::edge(*n,e.to_node());
	 }
   }
   
   void clear() {
     super::clear();
     dim_map.clear();
   }
   
   int dim() const { return dim_map.size()-1; }
   
   const std::list< int, std::allocator<int> >& nodes_of_dim(int d) const
     {
       int D=dim();
       if (d<0) d+=D;
       DIMENSION_CHECK((d<0 || d>D), "PseudoComplex::nodes_of_dim - dimension out of range");
       return dim_map[d];
     }
   
   int bottom_node() const
     {
       return the_bottom_node;
     }
   
   int top_node() const
     {
       return the_top_node;
     }
   
   int n_facets() const
   {
      return super::in_edges(the_top_node).size();
   }

   void restore_dim_map()
     {
       dim_map.clear();
       int dim = -1;
       
       for (int n=0; n<super::nodes(); ++n) {
	  const int in_edges = super::in_edges(n).size();
	  const int out_edges = super::out_edges(n).size();

	  if (out_edges==0 && in_edges==0)  // ignor isolated nodes
	     continue;

	  if (out_edges==0) {
	     the_top_node = n;
	     continue;
	  }
	  if (in_edges==0) {
	     the_bottom_node = n;
	     continue;
	  }
	  
	  const int d=super::node(n).size()-1;
	  if (dim_map.size() <= size_t(d))
	     dim_map.resize(2*d+1);
	  if (d>dim)
	     dim = d;
	  
	  dim_map[d].push_back(n);
       }
       
       dim_map.resize(dim+1);
     }
   
   void restore_vertex_sets()
   {
      // find bottom node
      if (the_bottom_node >=  super::nodes())
	 the_bottom_node = 0;
      for ( ; !super::in_edges(the_bottom_node).empty();
	    the_bottom_node = super::in_edges(the_bottom_node).begin().from_node()); 
      
      // compute vetex sets
      Bitset visited(super::nodes());
      std::list<int> node_queue;
      
      node_queue.push_back(the_bottom_node);
      visited += the_bottom_node;
   
      while (!node_queue.empty()) {
	 const int n=node_queue.front();
	 node_queue.pop_front();

	 for (Entire<super::out_edge_list>::const_iterator e=entire(super::out_edges(n));
	      !e.at_end(); ++e) {
	    const int nn=e.to_node();
	    
	    if (super::out_edges(nn).empty()) {
	       the_top_node = nn;
	       continue;
	    }

	    if (!visited.contains(nn)) {
	       node_queue.push_back(nn);
	       visited+=nn;
	       super::node(nn).clear();
	    }
	    
	    if (n == the_bottom_node)  // nn is vertex
	       super::node(nn)= scalar2set(nn);
	    else
	       super::node(nn) += super::node(n);
	 }
      }
   }
   
   void restore()
   {
      super::squeeze();
      restore_vertex_sets();
      restore_dim_map();
   }
   
   template <typename Input> friend
     Input& operator>> (GenericInput<Input>& is, PseudoComplex& C)
     {
       is >> static_cast<super&>(C);
       C.restore_dim_map();
       return is.top();
     }
};
 
} } // end namespace polymake::topaz


#endif // _POLYMAKE_PSEUDO_COMPLEX_H


// Local Variables:
// mode:C++
// c-basic-offset:3
// End:
