/*
 * Author: Dmitriy Morozov
 * Department of Computer Science, Duke University, 2005 -- 2008
 */

#ifndef __SIMPLEX_H__
#define __SIMPLEX_H__

#include <vector>
#include <algorithm>
#include <list>
#include <iostream>

#include "utilities/types.h"

#include <boost/compressed_pair.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/serialization/access.hpp>


/**
 * Class: Simplex
 * Basic simplex class. It stores vertices and data of the given types in 
 * a `boost::compressed_pair` (so if data is an Empty class which is the default, 
 * it incurs no space overhead). The class knows how to compute its own <boundary()>. 
 *
 * Parameter:
 *   V -            vertex type
 *   T -            data type
 *
 * \ingroup topology
 */
template<class V, class T = Empty<> >
class Simplex
{
	public:
        /* Typedefs: Public Types
         *
         *    Vertex -              vertex type (template parameter V)
         *    Data -                data type (template parameter T)
         *    Self -
         *    Boundary -            type in which the boundary is stored
         */
		typedef		V																Vertex;
        typedef     T                                                               Data;
		typedef		Simplex<Vertex, Data>										    Self;
		class BoundaryIterator;

        /* Typedefs: Internal representation
         *
         *    VertexContainer -     internal representation of the vertices
         *    VerticesDataPair -    `compressed_pair` of VertexContainer and Data
         */
        typedef		std::vector<Vertex>												VertexContainer;
        typedef     boost::compressed_pair<VertexContainer, Data>                   VerticesDataPair;
		
        // TODO

		/// \name Constructors 
		/// @{
        //
        /// Constructor: Simplex()
        /// Default constructor
		Simplex()														            {}
        /// Constructor: Simplex(Self other)
        /// Copy constructor
		Simplex(const Self& other):	
			vdpair_(other.vertices(), other.data())				                    {}
        /// Constructor: Simplex(Iterator bg, Iterator end)
        /// Initialize simplex by copying vertices in range [bg, end)
		template<class Iterator>
		Simplex(Iterator bg, Iterator end, const Data& d = Data())			        { join(bg, end); data() = d; }
        /// Constructor: Simplex(VertexContainer v)
        /// Initialize simplex by copying the given VertexContainer
		Simplex(const VertexContainer& v, const Data& d = Data()):	
			vdpair_(v, d)														    { std::sort(vertices().begin(), vertices().end()); }
        /// Constructor: Simplex(Dimension d, Vertex v)
        /// Initialize simplex of dimension d, and set its first vertex to v
		Simplex(Dimension d, Vertex v)				                                { vertices().reserve(d+1); add(v); }
        /// Constructor: Simplex(Dimension d)
        /// Initialize simplex of dimension d
		Simplex(Dimension d)                                                        { vertices().resize(d+1); } 
		/// @}
		
		/// \name Core 
		/// @{
        ///
        /// Functions: boundary_begin(), boundary_end()
        /// Returns the iterators over the boundary of the simplex
        BoundaryIterator        boundary_begin() const;
        BoundaryIterator        boundary_end() const;
        /// Function: dimension()
        /// Returns the dimension of the simplex
		Dimension				dimension() const									{ return vertices().size() - 1; }
		/// @}
		
		const Data&	            data() const									    { return vdpair_.second(); }
        Data&                   data()                                              { return vdpair_.second(); }
		const VertexContainer&	vertices() const									{ return vdpair_.first(); }
		
		/// \name Vertex manipulation
		/// @{
        bool					contains(const Vertex& v) const;
		void					add(const Vertex& v);
        template<class Iterator>
        void                    join(Iterator bg, Iterator end);
        void                    join(const Self& other)                             { join(other.vertices().begin(), other.vertices().end()); }
		/// @}

		Self&				    operator=(const Self& s)							{ vdpair_ = s.vdpair_; return *this; }

		std::ostream&			operator<<(std::ostream& out) const;

        /* Classes: Comparisons
         *
         * VertexComparison -           compare simplices based on the lexicographic ordering of their <vertices()>
         * DataComparison -             compare simplices based on their <data()>
         * DataDimensionComparison -    compare simplices based on their <data()> within each <dimension()>
         */
        
        /* Classes: Functors
         * DataEvaluator -              return data given a simplex
         * DimensionExtractor -         return dimesnion given a simplex
         */
        struct VertexComparison;
        struct DataComparison;
        struct DataDimensionComparison;

        struct DataEvaluator;
        struct DimensionExtractor;
	
	private:
		VertexContainer&	    vertices()									        { return vdpair_.first(); }

        VerticesDataPair        vdpair_;

	private:
		/* Serialization */
		friend class boost::serialization::access;
		
		template<class Archive>
		void 					serialize(Archive& ar, version_type );
};


template<class V, class T>
struct Simplex<V,T>::VertexComparison
{
        typedef                 Self                    first_argument_type;
        typedef                 Self                    second_argument_type;
        typedef                 bool                    result_type;

        bool                    operator()(const Self& a, const Self& b) const       { return a.vertices() < b.vertices(); }
};

template<class V, class T>
struct Simplex<V,T>::DataComparison
{
        typedef                 Self                    first_argument_type;
        typedef                 Self                    second_argument_type;
        typedef                 bool                    result_type;

        bool                    operator()(const Self& a, const Self& b) const       { return a.data() < b.data(); }
};

template<class V, class T>
struct Simplex<V,T>::DataDimensionComparison
{
        typedef                 Self                    first_argument_type;
        typedef                 Self                    second_argument_type;
        typedef                 bool                    result_type;

        bool                    operator()(const Self& a, const Self& b) const       
		{
			if (a.dimension() == b.dimension())
				return a.data() < b.data();
			else
				return a.dimension() < b.dimension();
		}
};
        
template<class V, class T>
struct Simplex<V,T>::DataEvaluator
{
        typedef                 Self                    first_argument_type;
        typedef                 Data                    result_type;

        result_type             operator()(const first_argument_type& s) const      { return s.data(); }
};

template<class V, class T>
struct Simplex<V,T>::DimensionExtractor
{
        typedef                 Self                    first_argument_type;
        typedef                 Dimension               result_type;

        result_type             operator()(const first_argument_type& s) const      { return s.dimension(); }
};


// TODO: class DirectSimplex - class which stores indices of the simplices in its boundary
// TODO: class CompactSimplex<V, T, N> - uses arrays instead of vectors to store simplices 
//       (dimension N must be known at compile time)


#include "simplex.hpp"

#endif // __SIMPLEX_H__