/* 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_COMPLEX_TOOLS_H
#define _POLYMAKE_COMPLEX_TOOLS_H "$Project: polymake $$Id: complex_tools.h 7462 2006-11-13 19:28:29Z witte $"

#include <list>
#include <string>

#include <Array.h>
#include <PowerSet.h>
#include <HasseDiagram.h>
#include <FacetList.h>

/** Tools to treat simplicial complexes.
 *
 *  A simplicial complex is represented as a list of its FACETS, encode as their vertex sets.
 *  Therefore any container of GenericSet of int (template <typename Complex>) may be used to
 *  represent a complex. In the following std::list< polymake::Set<int> >, polymake::PowerSet<int>
 *  and polymake::Array< polymake::Set<int> > are used.
 */


namespace polymake { namespace topaz {

   // Computes the k_skeleton of a simplicial complex.
   template <typename Complex>
   PowerSet<int> k_skeleton(const Complex& C, const int k);

   template <typename Complex, typename Set>
   struct link_helper {
      typedef pm::SelectedContainerPairSubset< const Complex&, pm::masquerade_keep_ref<pm::unlimited_constant_container, const Set&>,
					       operations::includes >
          selected_facets;
      typedef pm::SelectedContainerPairSubset< const Complex&, pm::masquerade_keep_ref<pm::unlimited_constant_container, const Set&>,
					       operations::composed21<operations::includes,operations::logical_not> >
          deletion_type;
      typedef pm::TransformedContainerPair< selected_facets, pm::masquerade_keep_ref<pm::unlimited_constant_container, const Set&>,
					    operations::sub >
          result_type;
   };

   // Computes the star of a given face F.
   template <typename Complex, typename Set> inline
   typename link_helper<Complex,Set>::selected_facets
   star(const Complex& C, const GenericSet< Set,int >& F)
   {
      return typename link_helper<Complex,Set>::selected_facets(C, F.top());
   }

   // Computes the deletion of a given face F.
   template <typename Complex, typename Set> inline
   typename link_helper<Complex,Set>::deletion_type
   deletion(const Complex& C, const GenericSet< Set,int >& F)
   {
      return typename link_helper<Complex,Set>::deletion_type(C, F.top());
   }

   // Computes the link of a given face F.
   template <typename Complex, typename Set> inline
   typename link_helper<Complex,Set>::result_type
   link(const Complex& C, const GenericSet< Set,int >& F)
   {
      return typename link_helper<Complex,Set>::result_type(star(C,F), F.top());
   }

   // Computes the star of a face (specified by it's index in the 
   // HasseDiagram.
   FacetList star_in_HD (const HasseDiagram<>& HD, const int f);
  
   // Computes the link of a face (specified by it's index in the 
   // HasseDiagram.
   FacetList link_in_HD (const HasseDiagram<>& HD, const int f);
  
   // Computes the vertex star of a complex represented as a
   // Hasse Diagram and a given vertex v.
   std::list< Set<int> > vertexStar_of_HD(const HasseDiagram<>& HD, const int v);

   // Computes the vertex link of a complex represented as a
   // Hasse Diagram and a given vertex v.
   std::list< Set<int> > vertexLink_of_HD(const HasseDiagram<>& HD, const int v);

   // Computes the vertex set of the link of the vertex v. 
   Set<int> vert_of_vertexLink(const HasseDiagram<>& HD, const int v);


   // Computes the Hasse Diagram of a complex C. The parameter d
   // is a lower bound for the dimension of the complex, default is 0.
   // The parameter end_dim determines which levels (starting at
   // the top) of the Hasse Diagram are computed.
   template <typename VertexSet, typename Complex>
   HasseDiagram<VertexSet> hasse_diagram(const Complex& C, const int d=0, const int end_dim=0);

   template <typename Complex> inline
   HasseDiagram<> hasse_diagram(const Complex& C, const int d=0, const int end_dim=0) {
     return hasse_diagram< Set<int> >(C,d,end_dim);
   }

   // Computes the Hasse Diagram of a PURE complex C.
   // The parameter end_dim determines which levels (starting at
   // the top) of the Hasse Diagram are computed.
   template <typename VertexSet, typename Complex>
   HasseDiagram<VertexSet> pure_hasse_diagram(const Complex& C, const int end_dim=0);

   template <typename Complex> inline
   HasseDiagram<> pure_hasse_diagram(const Complex& C, const int end_dim=0) {
     return pure_hasse_diagram< Set<int> >(C,end_dim);
   }

   class out_degree_checker {
   public:
      typedef void argument_type;
      typedef bool result_type;
    
      out_degree_checker(int degree_arg=0) : degree(degree_arg) { }
    
      template <typename Iterator>
      result_type operator() (const Iterator& node_it) const
      {
	 return node_it.out_degree()==degree;
      }
   protected:
      int degree;
   };
  
   // Computes the boundary complex (= ridges contained in one facet only) 
   // of a PSEUDO_MANIFOLD. The complex is encoded as a Hasse Diagrams.
  
   typedef pm::SelectedSubset< pm::IndexedSubset<HasseDiagram<>::const_node_container_ref, sequence>, out_degree_checker>
   Boundary_of_PseudoManifold;
  
   inline
   Boundary_of_PseudoManifold boundary_of_pseudo_manifold (const HasseDiagram<>& PM)
   {
      return Boundary_of_PseudoManifold( pm::IndexedSubset<HasseDiagram<>::const_node_container_ref, sequence>(nodes(PM), PM.nodes_of_dim(-2)),
					 out_degree_checker(1) );
   }
  
   // Removes the vertex star of v from a complex C, represented as a Hasse Diagram.
   void remove_vertex_star(HasseDiagram<>& HD, const int v);

   // Removes a facet F from a simplicial complex, represented as a Hasse Diagram.
   template <typename VertexSet, typename Set>
   void remove_facet (HasseDiagram<VertexSet>& HD, const GenericSet< Set,int >& F);

   // Checks whether a 1-complex (graph) is a 1-ball or 1-sphere.
   template <typename Complex>
   bool C1_is_BOS (const Complex& C);

   // Checks whether a 1-complex (graph) is a manifold.
   template <typename Complex>
   bool C1_is_manifold (const Complex& C);

   // Checks whether a 2-complex is a 2-ball or 2-sphere.
   template <typename Complex>
   bool C2_is_BOS (const Complex& C);

   // Checks whether a 2-complex is a manifold.
   template <typename Complex>
   bool C2_is_manifold (const Complex& C);

   // Checks whether a 3-complex is a manifold.
   template <typename Complex>
   bool C3_is_manifold (std::ostream& os, const Complex& C, const bool quiet=false);

   template <typename Complex>
   bool C3_is_manifold (const Complex& C) {
      return C3_is_manifold(std::cout,C);
   }

   /// Adjusts the vertex numbers to 0..n-1.
   /// @retval true if the numbering has been adjusted
   template <typename Complex, typename Set>
   bool adj_numbering (Complex& C, const Set& V);

   // Checks whether a complex, represented as a Hasse Diagram, is a closed pseudo manifold.
   bool is_closed_pseudo_manifold (const HasseDiagram<>& HD);

   // Checks whether a complex, represented as a Hasse Diagram, is a pseudo manifold
   // and computes its boundary.
   template <typename VertexSet, typename OutputIterator>
   bool is_pseudo_manifold (const HasseDiagram<VertexSet>& HD, OutputIterator boundary_consumer, const bool verbose=false);

   // Checks whether a complex, represented as a Hasse Diagram, is a pseudo manifold.
   template <typename VertexSet> inline
   bool is_pseudo_manifold (const HasseDiagram<VertexSet>& HD, const bool verbose)
   {
      return is_pseudo_manifold (HD, black_hole< Set<int> >(), verbose);
   }

   // The torus.
   Array< Set<int> > torus();

   // The projective plane.
   Array< Set<int> > projective_plane();

} }

#include <complex_tools.tcc>
#include <subcomplex_tools.tcc>
#include <1D_tools.tcc>
#include <2D_tools.tcc>
#include <3D_tools.tcc>

#endif // _POLYMAKE_COMPLEX_TOOLS_H

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