complex.hh

// Copyright (C) 2008, 2009, 2010 EPITA Research and Development
// Laboratory (LRDE)
//
// This file is part of Olena.
//
// Olena 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, version 2 of the License.
//
// Olena 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.
//
// You should have received a copy of the GNU General Public License
// along with Olena.  If not, see <http://www.gnu.org/licenses/>.
//
// As a special exception, you may use this file as part of a free
// software project without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to produce
// an executable, this file does not by itself cause the resulting
// executable to be covered by the GNU General Public License.  This
// exception does not however invalidate any other reasons why the
// executable file might be covered by the GNU General Public License.

#ifndef MLN_TOPO_COMPLEX_HH
# define MLN_TOPO_COMPLEX_HH


# include <cstddef>

# include <iosfwd>

# include <mln/metal/bool.hh>

# include <mln/util/tracked_ptr.hh>

# include <mln/topo/face_data.hh>
# include <mln/topo/algebraic_face.hh>
# include <mln/topo/algebraic_n_face.hh>
# include <mln/topo/n_faces_set.hh>

# include <mln/topo/complex_iterators.hh>


namespace mln
{

  namespace topo
  {

    // Forward declarations (external).
    template <unsigned N, unsigned D> class n_faces_set;
    template <unsigned D> class face_fwd_iter;
    template <unsigned D> class face_bkd_iter;
// FIXME: Disabled (moved to the attic).
# if 0
    template <unsigned N, unsigned D> class faces_fwd_iter_;
    template <unsigned N, unsigned D> class faces_bkd_iter_;
#endif

    // Forward declarations (internal).
    namespace internal
    {
      template <unsigned D>
      struct complex_data;

      template <unsigned N, unsigned D>
      struct faces_set_mixin;
    }


    /*----------.
    | Complex.  |
    `----------*/

    //
    template <unsigned D>
    class complex
    {
    public:
      typedef face_fwd_iter<D> fwd_citer;
      typedef face_bkd_iter<D> bkd_citer;

// FIXME: Disabled (moved to the attic).
# if 0

      template <unsigned N>
      struct fwd_fiter { typedef faces_fwd_iter_<N, D> ret; };
      template <unsigned N>
      struct bkd_fiter { typedef faces_bkd_iter_<N, D> ret; };
#endif

      complex();

      n_face<0u, D> add_face();

      template <unsigned N>
      n_face<N + 1, D> add_face(const n_faces_set<N, D>& adjacent_faces);

      unsigned nfaces() const;

      template <unsigned N>
      unsigned nfaces_of_static_dim() const;

      unsigned nfaces_of_dim(unsigned n) const;

      void print(std::ostream& ostr) const;
      template <unsigned N>
      void print_faces(std::ostream& ostr) const;

      const void* addr() const;

    private:
      util::tracked_ptr< internal::complex_data<D> > data_;

      template <unsigned D_>
      friend bool operator==(const complex<D_>& lhs, const complex<D_>& rhs);

      template <unsigned N, unsigned D_> friend class n_face;
      template <unsigned D_> friend class face;

      template <unsigned N>
      face_data<N, D>& face_data_(unsigned face_id);

      template <unsigned N>
      const face_data<N, D>& face_data_(unsigned face_id) const;

      /* FIXME: Use something more constraining than the STL's
         UnaryFunction/BinaryFunction.  Use Function or Function_v2v?
         Or a new subclass of Function?  */

      /* FIXME: Replace F and ACCU by a Milena accumulator?  */

      template <typename BinaryFunction, typename T>
      T fold_left_(const BinaryFunction& f, const T& accu) const;

      template <typename UnaryFunction>
      typename UnaryFunction::result_type
      apply_if_dim_matches_(unsigned n, const UnaryFunction& f) const;

      template <unsigned N>
      void connect_(const algebraic_n_face<N, D>& f1,
                    const n_face<N + 1, D>& f2);
    };


    template <unsigned D>
    bool
    operator==(const complex<D>& lhs, const complex<D>& rhs);


    template <unsigned D>
    std::ostream&
    operator<<(std::ostream& ostr, const complex<D>& c);


    /*---------------.
    | Complex data.  |
    `---------------*/

    /*---------------------.
    | Faces of a complex.  |
    `---------------------*/

    namespace internal
    {

      // Forward declarations.
      template <unsigned N, unsigned D> struct lower_dim_faces_set_mixin;
      template <unsigned N, unsigned D> struct higher_dim_faces_set_mixin;

      // -------------------------------------- //
      // mln::topo::internal::faces_set_mixin.  //
      // -------------------------------------- //


      template <unsigned N, unsigned D> struct faces_set_mixin;


      template <unsigned N, unsigned D>
      struct faces_set_mixin : public faces_set_mixin<N - 1, D>,
                               public lower_dim_faces_set_mixin<N, D>,
                               public higher_dim_faces_set_mixin<N, D>
      {
        std::vector< face_data<N, D> > faces_;

        void print(std::ostream& ostr) const;
        void print_rec_asc(std::ostream& ostr) const;

        template <typename BinaryFunction, typename T>
        T fold_left_(const BinaryFunction& f, const T& accu) const;
        template <typename UnaryFunction>
        typename UnaryFunction::result_type
        apply_if_dim_matches_(unsigned n, const UnaryFunction& f) const;
      };

      template <unsigned D>
      struct faces_set_mixin<D, D> : public faces_set_mixin<D - 1, D>,
                                     public lower_dim_faces_set_mixin<D, D>
      {
        std::vector< face_data<D, D> > faces_;

        void print(std::ostream& ostr) const;
        void print_rec_asc(std::ostream& ostr) const;

        template <typename BinaryFunction, typename T>
        T fold_left_(const BinaryFunction& f, const T& accu) const;
        template <typename UnaryFunction>
        typename UnaryFunction::result_type
        apply_if_dim_matches_(unsigned n, const UnaryFunction& f) const;
      };

      template <unsigned D>
      struct faces_set_mixin<0u, D> : public higher_dim_faces_set_mixin<0u, D>
      {
        std::vector< face_data<0u, D> > faces_;

        void print(std::ostream& ostr) const;
        void print_rec_asc(std::ostream& ostr) const;

        template <typename BinaryFunction, typename T>
        T fold_left_(const BinaryFunction& f, const T& accu) const;
        template <typename UnaryFunction>
        typename UnaryFunction::result_type
        apply_if_dim_matches_(unsigned n, const UnaryFunction& f) const;
      };

      template <>
      struct faces_set_mixin<0u, 0u>
      {
        std::vector< face_data<0u, 0u> > faces_;

        void print(std::ostream& ostr) const;
        void print_rec_asc(std::ostream& ostr) const;

        template <typename BinaryFunction, typename T>
        T fold_left_(const BinaryFunction& f, const T& accu) const;
        template <typename UnaryFunction>
        typename UnaryFunction::result_type
        apply_if_dim_matches_(unsigned n, const UnaryFunction& f) const;
      };


      // Tech note: g++-2.95 highly prefers to have the complex_data
      // class to be defined after the specializations of
      // 'faces_set_mixin'.

      template <unsigned D>
      struct complex_data : public faces_set_mixin<D, D>
      {
        // Data is contained in super classes.
      };


      // ------------------------------------------------- //
      // mln::topo::internal::lower_dim_faces_set_mixin.   //
      // mln::topo::internal::higher_dim_faces_set_mixin.  //
      // ------------------------------------------------- //

      template <unsigned N, unsigned D>
      struct lower_dim_faces_set_mixin
      {
        void print(std::ostream& ostr, const face_data<N, D>& f) const;
      };

      template <unsigned N, unsigned D>
      struct higher_dim_faces_set_mixin
      {
        void print(std::ostream& ostr, const face_data<N, D>& f) const;
      };

    } // end of namespace mln::topo::internal



# ifndef MLN_INCLUDE_ONLY

    /*-----------------------.
    | Complex construction.  |
    `-----------------------*/

    template <unsigned D>
    inline
    complex<D>::complex()
      // Allocate data for this complex.
      : data_(new internal::complex_data<D>())
    {
    }

    template <unsigned D>
    inline
    n_face<0u, D>
    complex<D>::add_face()
    {
      /* FIXME: This is not thread-proof (these two lines should
         form an atomic section).  */
      data_->internal::faces_set_mixin<0u, D>::faces_.push_back(face_data<0u, D>());
      unsigned id = nfaces_of_static_dim<0u>() - 1;
      return n_face<0u, D>(*this, id);
    }

    template <unsigned D>
    template <unsigned N>
    inline
    n_face<N + 1, D>
    complex<D>::add_face(const n_faces_set<N, D>& adjacent_faces)
    {
      typedef typename std::vector< algebraic_n_face<N, D> >::const_iterator
        iter_t;

      // Ensure ADJACENT_FACES are already part of the complex.
      if (!HAS_NDEBUG)
        for (iter_t a = adjacent_faces.faces().begin();
             a != adjacent_faces.faces().end(); ++a)
          {
            mln_precondition(a->cplx() == *this);
            mln_precondition(a->is_valid());
          }

      face_data<N + 1, D> f;
      /* FIXME: This is not thread-proof (these two lines should
         form an atomic section).  */
      data_->internal::faces_set_mixin<N + 1, D>::faces_.push_back(f);
      unsigned id = nfaces_of_static_dim<N + 1>() - 1;

      n_face<N + 1, D> fh(*this, id);
      // Connect F and its ADJACENT_FACES.
      for (iter_t a = adjacent_faces.faces().begin();
           a != adjacent_faces.faces().end(); ++a)
        /* Connect
           - algebraic n-face *A,
           - and an (n+1)-algebraic face based on FH and having the
             sign of *A.  */
        connect_(*a, fh);
      return fh;
    }


    /*-------.
    | Misc.  |
    `-------*/

    namespace internal
    {

      struct add_size
      {
        template <typename T, typename Container>
        T operator()(const T& x, const Container& c) const
        {
          return x + c.size();
        }
      };

      struct get_size
      {
        typedef std::size_t result_type;

        template <typename Container>
        typename Container::size_type operator()(const Container& c) const
        {
          return c.size();
        }
      };

    } // end of namespace mln::topo::internal


    /*----------------------.
    | Static manipulators.  |
    `----------------------*/

    template <unsigned D>
    inline
    unsigned
    complex<D>::nfaces() const
    {
      return fold_left_(internal::add_size(), 0);
    }

    template <unsigned D>
    template <unsigned N>
    inline
    unsigned
    complex<D>::nfaces_of_static_dim() const
    {
      return data_->internal::faces_set_mixin<N, D>::faces_.size();
    }


    /*-----------------------.
    | Dynamic manipulators.  |
    `-----------------------*/

    template <unsigned D>
    inline
    unsigned
    complex<D>::nfaces_of_dim(unsigned n) const
    {
      // Ensure N is compatible with D.
      mln_precondition(n <= D);
      return apply_if_dim_matches_(n, internal::get_size());
    }


    /*-------------------.
    | Internal methods.  |
    `-------------------*/

    template <unsigned D>
    template <unsigned N>
    inline
    face_data<N, D>&
    complex<D>::face_data_(unsigned face_id)
    {
      return data_->internal::faces_set_mixin<N, D>::faces_[face_id];
    }

    template <unsigned D>
    template <unsigned N>
    inline
    const face_data<N, D>&
    complex<D>::face_data_(unsigned face_id) const
    {
      return data_->internal::faces_set_mixin<N, D>::faces_[face_id];
    }

    template <unsigned D>
    template <unsigned N>
    inline
    void
    complex<D>::connect_(const algebraic_n_face<N, D>& f1,
                         const n_face<N + 1, D>& f2)
    {
      // Ensure N is compatible with D.
      metal::bool_< N <= D >::check();

      /* Connect
         - F1, an algebraic n-face,
         - and AF2, an algebraic (n+1)-face based on F2 and having the
           sign of F1.  */
      f1.data().connect_higher_dim_face(make_algebraic_n_face(f2, f1.sign()));
      f2.data().connect_lower_dim_face(f1);
    }


    /*-------------.
    | Comparison.  |
    `-------------*/

    template <unsigned D>
    inline
    bool
    operator==(const complex<D>& lhs, const complex<D>& rhs)
    {
      return lhs.data_.ptr_ == rhs.data_.ptr_;
    }


    /*------------------.
    | Pretty-printing.  |
    `------------------*/

    template <unsigned D>
    inline
    std::ostream&
    operator<<(std::ostream& ostr, const complex<D>& c)
    {
      c.print(ostr);
      return ostr;
    }

    template <unsigned D>
    inline
    void
    complex<D>::print(std::ostream& ostr) const
    {
      data_->internal::faces_set_mixin<D, D>::print_rec_asc(ostr);
    }

    template <unsigned D>
    template <unsigned N>
    inline
    void
    complex<D>::print_faces(std::ostream& ostr) const
    {
      // Ensure N is compatible with D.
      metal::bool_< N <= D >::check();

      data_->internal::faces_set_mixin<N, D>::print(ostr);
    }

    template <unsigned D>
    inline
    const void* 
    complex<D>::addr() const
    {
      return data_.ptr_;
    }


    namespace internal
    {

      template <unsigned N, unsigned D>
      inline
      void
      faces_set_mixin<N, D>::print_rec_asc(std::ostream& ostr) const
      {
        faces_set_mixin<N - 1, D>::print_rec_asc(ostr);
        print(ostr);
      }

      template <unsigned D>
      inline
      void
      faces_set_mixin<0u, D>::print_rec_asc(std::ostream& ostr) const
      {
        print(ostr);
      }

      template <unsigned D>
      inline
      void
      faces_set_mixin<D, D>::print_rec_asc(std::ostream& ostr) const
      {
        faces_set_mixin<D - 1, D>::print_rec_asc(ostr);
        print(ostr);
      }

      inline
      void
      faces_set_mixin<0u, 0u>::print_rec_asc(std::ostream& ostr) const
      {
        print(ostr);
      }


      template <unsigned N, unsigned D>
      inline
      void
      faces_set_mixin<N, D>::print(std::ostream& ostr) const
      {
        ostr << "Faces of dimension " << N
             << " and their ajacent faces of dimension "
             << N - 1 << " and "
             << N + 1 << std::endl;
        for (unsigned f = 0; f < faces_.size(); ++f)
          {
            ostr << "  " << f << ":  dim " << N - 1 << ": { ";
            lower_dim_faces_set_mixin<N, D>::print(ostr, faces_[f]);
            ostr << "},  dim " << N + 1 << ": { ";
            higher_dim_faces_set_mixin<N, D>::print(ostr, faces_[f]);
            ostr << "}" << std::endl;
          }
      }

      template <unsigned D>
      inline
      void
      faces_set_mixin<0u, D>::print(std::ostream& ostr) const
      {
        const unsigned N = 0u;
        ostr << "Faces of dimension " << N
             << " and their ajacent faces of dimension "
             << N + 1 << std::endl;
        for (unsigned f = 0; f < faces_.size(); ++f)
          {
            ostr << "  " << f << ":  dim " << N + 1 << ": { ";
            higher_dim_faces_set_mixin<N, D>::print(ostr, faces_[f]);
            ostr << "}" << std::endl;
          }
      }

      template <unsigned D>
      inline
      void
      faces_set_mixin<D, D>::print(std::ostream& ostr) const
      {
        const unsigned N = D;
        ostr << "Faces of dimension " << N
             << " and their ajacent faces of dimension "
             << N - 1 << std::endl;
        for (unsigned f = 0; f < faces_.size(); ++f)
          {
            ostr << "  " << f << ":  dim " << N - 1 << ": { ";
            lower_dim_faces_set_mixin<N, D>::print(ostr, faces_[f]);
            ostr << "}" << std::endl;
          }
      }

      inline
      void
      faces_set_mixin<0u, 0u>::print(std::ostream& ostr) const
      {
        const unsigned N = 0u;
        ostr << "Faces of dimension " << N << std::endl;
        for (unsigned f = 0; f < faces_.size(); ++f)
          ostr << "  " << f << std::endl;
      }


      template <unsigned N, unsigned D>
      inline
      void
      lower_dim_faces_set_mixin<N, D>::print(std::ostream& ostr,
                                             const face_data<N, D>& f) const
      {
        for (typename std::vector< algebraic_n_face<N - 1, D> >::const_iterator l =
               f.lower_dim_faces_.begin(); l != f.lower_dim_faces_.end(); ++l)
          ostr << l->face_id() << " ";
      }

      template <unsigned N, unsigned D>
      inline
      void
      higher_dim_faces_set_mixin<N, D>::print(std::ostream& ostr,
                                              const face_data<N, D>& f) const
      {
        for (typename std::vector< algebraic_n_face<N + 1, D> >::const_iterator h =
               f.higher_dim_faces_.begin(); h != f.higher_dim_faces_.end(); ++h)
          ostr << h->face_id() << " ";
      }

    } // end of namespace mln::topo::internal


    /*-------------------------------.
    | Functional meta-manipulators.  |
    `-------------------------------*/

    /* ------------------------------- */
    /* ``Static Fold Left'' Operator.  */
    /* ------------------------------- */

    template <unsigned D>
    template <typename BinaryFunction, typename T>
    inline
    T
    complex<D>::fold_left_(const BinaryFunction& f, const T& accu) const
    {
      return data_->internal::faces_set_mixin<D, D>::fold_left_(f, accu);
    }

    namespace internal
    {

      // FIXME: Try to factor.

      template <unsigned D>
      template <typename BinaryFunction, typename T>
      inline
      T
      faces_set_mixin<D, D>::fold_left_(const BinaryFunction& f,
                                        const T& accu) const
      {
        return faces_set_mixin<D - 1, D>::fold_left_(f, f(accu, faces_));
      }

      template <unsigned N, unsigned D>
      template <typename BinaryFunction, typename T>
      inline
      T
      faces_set_mixin<N, D>::fold_left_(const BinaryFunction& f,
                                        const T& accu) const
      {
        return faces_set_mixin<N - 1, D>::fold_left_(f, f(accu, faces_));
      }

      template <unsigned D>
      template <typename BinaryFunction, typename T>
      inline
      T
      faces_set_mixin<0u, D>::fold_left_(const BinaryFunction& f,
                                         const T& accu) const
      {
        return f(accu, faces_);
      }

      template <typename BinaryFunction, typename T>
      inline
      T
      faces_set_mixin<0u, 0u>::fold_left_(const BinaryFunction& f,
                                          const T& accu) const
      {
        return f(accu, faces_);
      }

    } // end of namespace mln::topo::internal


    /* ------------------------------------------------ */
    /* ``Static Apply-If-Dimension-Matches'' Operator.  */
    /* ------------------------------------------------ */

    template <unsigned D>
    template <typename UnaryFunction>
    inline
    typename UnaryFunction::result_type
    complex<D>::apply_if_dim_matches_(unsigned n, const UnaryFunction& f) const
    {
      // Ensure N is compatible with D.
      mln_precondition(n <= D);
      return data_->internal::faces_set_mixin<D, D>::apply_if_dim_matches_(n, f);
    }

    namespace internal
    {

      // FIXME: Try to factor.

      template <unsigned D>
      template <typename UnaryFunction>
      inline
      typename UnaryFunction::result_type
      faces_set_mixin<D, D>::apply_if_dim_matches_(unsigned n,
                                                   const UnaryFunction& f) const
      {
        // Ensure N and D are compatible.
        mln_precondition(n <= D);
        return n == D ?
          f(faces_) :
          faces_set_mixin<D - 1, D>::apply_if_dim_matches_(n, f);
      }

      template <unsigned N, unsigned D>
      template <typename UnaryFunction>
      inline
      typename UnaryFunction::result_type
      faces_set_mixin<N, D>::apply_if_dim_matches_(unsigned n,
                                                   const UnaryFunction& f) const
      {
        // Ensure N and D are compatible.
        mln_precondition(n <= D);
        return n == N ?
          f(faces_) :
          faces_set_mixin<N - 1, D>::apply_if_dim_matches_(n, f);
      }

      template <unsigned D>
      template <typename UnaryFunction>
      inline
      typename UnaryFunction::result_type
      faces_set_mixin<0u, D>::apply_if_dim_matches_(unsigned n,
                                                    const UnaryFunction& f) const
      {
        // If we reached this method, then N should be 0.
        mln_precondition(n == 0);
        // Prevent ``unused variable'' warnings when NDEBUG is defined.
        (void) n;
        return f(faces_);
      }

      template <typename UnaryFunction>
      inline
      typename UnaryFunction::result_type
      faces_set_mixin<0u, 0u>::apply_if_dim_matches_(unsigned n,
                                                     const UnaryFunction& f) const
      {
        // If we reached this method, then N should be 0.
        mln_precondition(n == 0);
        // Prevent ``unused variable'' warnings when NDEBUG is defined.
        (void) n;
        return f(faces_);
      }

    } // end of namespace mln::topo::internal

# endif // ! MLN_INCLUDE_ONLY

  } // end of namespace mln::topo

} // end of namespace mln

#endif // ! MLN_TOPO_COMPLEX_HH