// Cutmesh - Copyright (C) 2010-2018 T. Mouton, E. Bechet 
//
// See the LICENSE file for license information and contributions.
// bugs and problems to <thibaud.mouton@gmail.com>.

#ifndef _TOPO_CUTMESH_H_
#define _TOPO_CUTMESH_H_

#include "common.h"
#include "surface.h"
#include "brep.h"

class EntityManager;
class TopoVolume;
class TopoFace;
class TopoEdge;
class TopoVertex;

class IBrep;

class TopoEntity
{
  protected:
    int _id;
    int _index;
    int _flag;
    std::vector<int> _brep_index;
    std::vector<int> _physical;

  public:

    inline void set_id ( int i )
    {
      _id = i;
    }
    inline int id()
    {
      return _id;
    }
    inline int index()
    {
      return _index;
    }
    inline int potential_brep_index_size()
    {
      return _brep_index.size();
    }
    inline void add_potential_brep_index ( int bri )
    {
      for ( int i = 0; i < _brep_index.size(); i++ )
        if ( _brep_index[i] == bri )
          return;
      _brep_index.push_back ( bri );
    }
    inline void remove_potential_brep_index ( int bri )
    {
//         printf("removing brep index %d to topoEntity %d (init size %d)\n", bri, index(), potential_brep_index_size());
      for ( int i = 0; i < _brep_index.size(); i++ )
        if ( _brep_index[i] == bri )
        {
          _brep_index.erase ( _brep_index.begin() +i );
          return;
        }
    }
    inline int get_potential_brep_index ( int i )
    {
      assert ( i < _brep_index.size() );
      return _brep_index[i];
    }
    inline void clear_potential_brep_index()
    {
      _brep_index.clear();
    }
    inline int physical_size()
    {
      return _physical.size();
    }
    inline void add_physical ( int phy )
    {
      for ( int i = 0; i < _physical.size(); i++ )
        if ( _physical[i] == phy )
          return;
      _physical.push_back ( phy );
    }
    inline void remove_physical ( int phy )
    {
      for ( int i = 0; i < _physical.size(); i++ )
        if ( _physical[i] == phy )
        {
          _physical.erase ( _physical.begin() +i );
          return;
        }
    }
    inline int get_physical ( int i )
    {
      assert ( i < _physical.size() );
      return _physical[i];
    }
    inline void clear_physical()
    {
      _physical.clear();
    }
    inline void setFlag ( int f )
    {
      _flag = f;
    }
    inline void incFlag ()
    {
      _flag++;
    }
    inline void decFlag ()
    {
      _flag--;
    }
    inline int getFlag()
    {
      return _flag;
    }

};

class TopoVertex : public TopoEntity
{
  protected:
    int _imposed;
    int _associated;
    int _locked;
    LVertex *_v;
    std::vector<int> _surf;
    std::vector<TopoEdge *> _edge_list;
//     std::vector<int> _brep_index;

  public:
    TopoVertex ( LVertex *v, int id, int index )
    {
      _v = v;
      _id = id;
      _index = index;
      _associated = 0;
      _imposed = 0;
      _locked = 0;
      _flag = -1;
    }
    inline LVertex *get_vertex()
    {
      return _v;
    }
    inline void add_topoedge ( TopoEdge *te )
    {
      _edge_list.push_back ( te );
    }
    inline TopoEdge *get_topoedge ( int i )
    {
      assert ( i < _edge_list.size() );
      return _edge_list[i];
    }
    inline void remove_topoedge ( int i )
    {
      assert ( i < _edge_list.size() );
      _edge_list.erase ( _edge_list.begin() +i );
    }
    inline void clear_topoedge()
    {
      _edge_list.clear();
    }
    inline int topoedge_size()
    {
      return _edge_list.size();
    }
    inline void set_id ( int i )
    {
      _id = i;
    }
    inline int id()
    {
      return _id;
    }
    inline int index()
    {
      return _index;
    }
    inline int surf_size()
    {
      return _surf.size();
    }
    inline void add_surf ( int s )
    {
      _surf.push_back ( s );
    }
    inline int get_surf ( int i )
    {
      assert ( i < _surf.size() );
      return _surf[i];
    }
    inline void clear_surf()
    {
      _surf.clear();
    }
    inline void set_imposed()
    {
      _imposed = 1;
    }
    inline int imposed()
    {
      return _imposed;
    }
    inline void set_associated()
    {
      _associated = 1;
    }
    inline int associated()
    {
      return _associated;
    }
    inline void lock()
    {
      _locked = 1;
    }
    inline void unlock()
    {
      _locked = 0;
    }
    inline int locked()
    {
      return _locked;
    }
//     inline int potential_brep_index_size()
//     {
//         return _brep_index.size();
//     }
//     inline void add_potential_brep_index(int bri)
//     {
//         for (int i = 0; i < _brep_index.size(); i++)
//             if (_brep_index[i] == bri)
//                 return;
//         _brep_index.push_back(bri);
//     }
//     inline void remove_potential_brep_index(int bri)
//     {
// //   printf("removing brep index %d to topovertex %d (init size %d)\n", bri, index(), potential_brep_index_size());
//         for (int i = 0; i < _brep_index.size(); i++)
//             if (_brep_index[i] == bri)
//      {
//    _brep_index.erase(_brep_index.begin()+i);
//                 return;
//      }
//     }
//     inline int get_potential_brep_index(int i)
//     {
//  assert(i < _brep_index.size());
//         return _brep_index[i];
//     }
//     inline void clear_potential_brep_index()
//     {
//         _brep_index.clear();
//     }
    inline void clear_all()
    {
      _edge_list.clear();
      _brep_index.clear();
      _surf.clear();
    }
    inline void setFlag ( int f )
    {
      _flag = f;
    }
    inline void incFlag ()
    {
      _flag++;
    }
    inline void decFlag ()
    {
      _flag--;
    }
    inline int getFlag()
    {
      return _flag;
    }
    void build_internal ( EntityManager *em );
};

class TopoEdge : public TopoEntity
{
  protected:
    int _id;
    int _index;
    int _color;
    int _imposed;
    int _associated;
    int _flag;
    TopoVertex *_v[2];
    TopoEdge * _ref;
    std::vector<TopoFace *> _face_list;
    std::deque<CutEdge *> _edge_list;
    std::vector<int> _surf;
//     std::vector<int> _brep_index;
    TopoEdge *_parent;
    std::vector<TopoEdge *> _child;

  public:
    TopoEdge ( int id, int color, int index )
    {
      _v[0] = NULL;
      _v[1] = NULL;
      _ref = NULL;
      _parent = NULL;
      _id = id;
      _index = index;
      _color = color;
      _imposed = 0;
      _associated = 0;
      _flag = -1;
    }
    inline void set_topovertex ( int i, TopoVertex *v )
    {
      assert ( i >= 0 );
      assert ( i < 2 );
      _v[i] = v;
    }
    inline TopoVertex *get_topovertex ( int i )
    {
      assert ( i >= 0 );
      assert ( i < 2 );
      return _v[i];
    }
    inline TopoVertex *get_topovertex ( int i, int direction )
    {
      assert ( i < 2 );
      assert ( ( direction == 0 ) || ( direction == 1 ) );
      int v[2][2] = {{1, 0},{0, 1}};
      return _v[v[direction][i]];
    }
    inline LVertex *get_vertex ( int i, int direction )
    {
      assert ( i <= edge_size() );
      assert ( ( direction == 0 ) || ( direction == 1 ) );
      CutEdge *ce = NULL;
      if ( i == edge_size() )
        ce = get_edge ( i-1, direction );
      else
        ce = get_edge ( i, direction );
      if ( i < edge_size() )
        return ce->get_vertex ( !direction );
      else
        return ce->get_vertex ( direction );
    }
    inline int get_direction ( int face_color )
    {
      CutEdge *ce = _edge_list[0];
      for ( int j = 0; j < ce->face_size(); j++ )
      {
        if ( ce->get_face ( j )->get_color() == face_color )
        {
          int edge = ce->get_edge_id ( j );
          CutFace *cf = ce->get_face ( j );
          if ( cf->get_edge_vertex ( edge, 0 ) == get_topovertex ( 0 )->get_vertex() )
            return 1;
          else
          {
            assert ( cf->get_edge_vertex ( edge, 1 ) == get_topovertex ( 0 )->get_vertex() );
            return 0;
          }
        }
      }
      assert ( 0 );
    }
    inline void add_edge ( CutEdge *ce )
    {
      _edge_list.push_back ( ce );
    }
    inline void insert_edge ( int i, CutEdge *ce )
    {
      assert ( i <= _edge_list.size() );
      _edge_list.insert ( _edge_list.begin() +i, ce );
    }
    inline CutEdge *get_edge ( int i, int direction )
    {
      assert ( i < edge_size() );
      assert ( ( direction == 0 ) || ( direction == 1 ) );
      if ( direction )
        return get_edge ( i );
      else
        return get_edge ( edge_size()-1-i );
    }
    inline CutEdge *get_edge ( int i )
    {
      assert ( i < _edge_list.size() );
      return _edge_list[i];
    }
    inline int edge_size()
    {
      return _edge_list.size();
    }
    inline int vertex_size()
    {
      return _edge_list.size() +1;
    }
    inline int topoface_size()
    {
      return _face_list.size();
    }
    inline void add_topoface ( TopoFace *tf )
    {
      _face_list.push_back ( tf );
    }
    inline TopoFace *get_topoface ( int i )
    {
      assert ( i < _face_list.size() );
      return _face_list[i];
    }
    inline void remove_topoface ( int i )
    {
      assert ( i < _face_list.size() );
      _face_list.erase ( _face_list.begin() +i );
    }
    inline void set_ref ( TopoEdge *ref )
    {
      assert ( ref != NULL );
      _ref = ref;
    }
    inline TopoEdge *get_ref()
    {
      return _ref;
    }
    inline void set_id ( int i )
    {
      _id = i;
    }
    inline int id()
    {
      return _id;
    }
    inline int index()
    {
      return _index;
    }
    inline int color()
    {
      return _color;
    }
    inline int surf_size()
    {
      return _surf.size();
    }
    inline void add_surf ( int s )
    {
//  printf("--> adding surf %d\n", s);
      _surf.push_back ( s );
    }
    inline int get_surf ( int i )
    {
      assert ( i < _surf.size() );
      return _surf[i];
    }
    inline void clear_surf()
    {
      _surf.clear();
    }
    inline void set_imposed()
    {
      _imposed = 1;
    }
    inline int imposed()
    {
      return _imposed;
    }
    inline void set_associated()
    {
      _associated = 1;
    }
    inline int associated()
    {
      return _associated;
    }
//     inline int potential_brep_index_size()
//     {
//         return _brep_index.size();
//     }
//     inline void add_potential_brep_index(int bri)
//     {
// //         printf("--> add brep index %d\n", bri);
//         for (int i = 0; i < _brep_index.size(); i++)
//             if (_brep_index[i] == bri)
//                 return;
//         _brep_index.push_back(bri);
//     }
//     inline void remove_potential_brep_index(int bri)
//     {
// //         printf("removing brep index %d to topoedge %d (init size %d)\n", bri, index(), potential_brep_index_size());
//         for (int i = 0; i < _brep_index.size(); i++)
//             if (_brep_index[i] == bri)
//             {
//                 _brep_index.erase(_brep_index.begin()+i);
//                 return;
//             }
//     }
//     inline int get_potential_brep_index(int i)
//     {
//         assert(i < _brep_index.size());
//         return _brep_index[i];
//     }
//     inline void clear_potential_brep_index()
//     {
//         _brep_index.clear();
//     }
    inline void clear_all()
    {
      _edge_list.clear();
      _face_list.clear();
      _brep_index.clear();
      _surf.clear();
    }
    inline void add_child ( TopoEdge *tf )
    {
      _child.push_back ( tf );
    }
    inline int child_size()
    {
      return _child.size();
    }
    inline TopoEdge *get_child ( int i )
    {
      assert ( i < _child.size() );
      return _child[i];
    }
    inline void set_parent ( TopoEdge *tf )
    {
      _parent = tf;
    }
    inline TopoEdge *get_parent()
    {
      return _parent;
    }
    inline void setFlag ( int f )
    {
//         printf("--> setting flag %d to topoedge %d\n", f, index());
      _flag = f;
    }
    inline void incFlag ()
    {
      _flag++;
    }
    inline void decFlag ()
    {
      _flag--;
    }
    inline int getFlag()
    {
      return _flag;
    }
    void build_internal ( EntityManager *em );
    void update_surf ( EntityManager *em );
    void dump()
    {
      printf ( "## Topoedge %d (flag %d) (associated %d) (imposed %d) (color %d) --> %d (v %d) -- %d (v %d)\n", index(), getFlag(), associated(), imposed(), color(), get_topovertex ( 0 )->index(), get_topovertex ( 0 )->get_vertex()->getIndex(), get_topovertex ( 1 )->index(), get_topovertex ( 1 )->get_vertex()->getIndex() );
      printf ( "## --> surf :" );
      for ( int k = 0; k < surf_size(); k++ )
        printf ( " %d", get_surf ( k ) );
      printf ( "\n" );
//  printf("## --> %d edges :", edge_size());
      printf ( "## --> %d indices :", potential_brep_index_size() );
      for ( int k = 0; k < potential_brep_index_size(); k++ )
        printf ( " %d", get_potential_brep_index ( k ) );
      printf ( "\n" );
      printf ( "## tv0 %d (flag %d) --> %d indices :", get_topovertex ( 0 )->index(), get_topovertex ( 0 )->getFlag(), get_topovertex ( 0 )->potential_brep_index_size() );
      for ( int k = 0; k < get_topovertex ( 0 )->potential_brep_index_size(); k++ )
        printf ( " %d", get_topovertex ( 0 )->get_potential_brep_index ( k ) );
      printf ( "\n" );
      printf ( "## tv1 %d (flag %d) --> %d indices :", get_topovertex ( 1 )->index(), get_topovertex ( 1 )->getFlag(), get_topovertex ( 1 )->potential_brep_index_size() );
      for ( int k = 0; k < get_topovertex ( 1 )->potential_brep_index_size(); k++ )
        printf ( " %d", get_topovertex ( 1 )->get_potential_brep_index ( k ) );
      printf ( "\n" );
    }
};

class TopoFace : public TopoEntity
{
  protected:
    int _id;
    int _index;
    int _associated;
    int _color;
    int _flag;
    TopoFace *_ref;
    std::deque<TopoEdge *> _edge_list;
    std::deque<int> _edge_dir_list;
    std::vector<CutFace *> _face_list;
    std::vector<int> _surf;
//     std::vector<int> _brep_index;
//     std::vector<int> _physical;
    TopoFace *_parent;
    int _is_parent;
    std::vector<TopoFace *> _child;
    TopoVolume *_vol[2];

  public:
    TopoFace ( int id, int color, int index )
    {
      _id = id;
      _index = index;
      _color = color;
      _associated = 0;
      _flag = -1;
      _ref = NULL;
      _parent = NULL;
      _vol[0] = NULL;
      _vol[1] = NULL;
      _is_parent = 0;
    }
    inline void set_id ( int i )
    {
      _id = i;
    }
    inline int id()
    {
      return _id;
    }
    inline int index()
    {
      return _index;
    }
    inline int color()
    {
      return _color;
    }
    inline void set_ref ( TopoFace *ref )
    {
      assert ( ref != NULL );
      _ref = ref;
    }
    inline TopoFace *get_ref()
    {
      return _ref;
    }
    inline int surf_size()
    {
      return _surf.size();
    }
    inline void add_surf ( int s )
    {
      for ( int i = 0; i < _surf.size(); i++ )
        if ( _surf[i] == s )
          return;
      _surf.push_back ( s );
    }
    inline int get_surf ( int i )
    {
      assert ( i < _surf.size() );
      return _surf[i];
    }
    inline void clear_surf()
    {
      _surf.clear();
    }
    inline void add_topoedge ( TopoEdge *te )
    {
      _edge_list.push_back ( te );
      _edge_dir_list.push_back ( 1 );
    }
    inline void insert_topoedge ( int i, TopoEdge *te, int dir )
    {
      assert ( i <= _edge_list.size() );
      _edge_list.insert ( _edge_list.begin() +i, te );
      _edge_dir_list.insert ( _edge_dir_list.begin() +i, dir );
//  te->add_topoface(this);
    }
    inline void remove_topoedge ( int i )
    {
      assert ( i < _edge_list.size() );
//         printf("--> removing topoedge %d\n", _edge_list[i]->index());
      _edge_list.erase ( _edge_list.begin() +i );
      _edge_dir_list.erase ( _edge_dir_list.begin() +i );
    }
    inline TopoEdge *get_topoedge ( int i )
    {
      assert ( i < _edge_list.size() );
      return _edge_list[i];
    }
    inline int get_topoedge_dir ( int i )
    {
      assert ( i < _edge_dir_list.size() );
      return _edge_dir_list[i];
    }
    inline void set_reverse_dir ( int i )
    {
      assert ( i < _edge_dir_list.size() );
      _edge_dir_list[i] = 0;
    }
    inline void swap_topoedge ( int e0, int e1 )
    {
      TopoEdge *tmp = _edge_list[e0];
      _edge_list[e0] = _edge_list[e1];
      _edge_list[e1] = tmp;
      int i = _edge_dir_list[e0];
      _edge_dir_list[e0] = _edge_dir_list[e1];
      _edge_dir_list[e1] = i;
    }
    inline TopoVertex *get_topovertex ( int edge, int vertex )
    {
      assert ( edge < topoedge_size() );
      assert ( vertex < 2 );
//       int v[2][2] = {{0, 1},{1, 0}};
      int v[2][2] = {{1, 0},{0, 1}};
      return get_topoedge ( edge )->get_topovertex ( v[get_topoedge_dir ( edge ) ][vertex] );
    }
    inline void set_inside_topovolume ( TopoVolume *tvol )
    {
      _vol[0] = tvol;
    }
    inline TopoVolume *get_inside_topovolume()
    {
      return _vol[0];
    }
    inline void set_outside_topovolume ( TopoVolume *tvol )
    {
      _vol[1] = tvol;
    }
    inline TopoVolume *get_outside_topovolume()
    {
      return _vol[1];
    }
    inline void add_face ( CutFace *cf )
    {
      _face_list.push_back ( cf );
    }
    inline CutFace *get_face ( int i )
    {
      assert ( i < _face_list.size() );
      return _face_list[i];
    }
    inline int topoedge_size()
    {
      return _edge_list.size();
    }
    inline int face_size()
    {
      return _face_list.size();
    }
//     inline int potential_brep_index_size()
//     {
//         return _brep_index.size();
//     }
//     inline void add_potential_brep_index(int bri)
//     {
//         for (int i = 0; i < _brep_index.size(); i++)
//             if (_brep_index[i] == bri)
//                 return;
//         _brep_index.push_back(bri);
//     }
//     inline void remove_potential_brep_index(int bri)
//     {
// //         printf("removing brep index %d to topoface %d (init size %d)\n", bri, index(), potential_brep_index_size());
//         for (int i = 0; i < _brep_index.size(); i++)
//             if (_brep_index[i] == bri)
//             {
//                 _brep_index.erase(_brep_index.begin()+i);
//                 return;
//             }
//     }
//     inline int get_potential_brep_index(int i)
//     {
//         assert(i < _brep_index.size());
//         return _brep_index[i];
//     }
//     inline void clear_potential_brep_index()
//     {
//         _brep_index.clear();
//     }
//     inline int physical_size()
//     {
//         return _physical.size();
//     }
//     inline void add_physical(int phy)
//     {
//         for (int i = 0; i < _physical.size(); i++)
//             if (_physical[i] == phy)
//                 return;
//         _physical.push_back(phy);
//     }
//     inline void remove_physical(int phy)
//     {
//         for (int i = 0; i < _physical.size(); i++)
//             if (_physical[i] == phy)
//             {
//                 _physical.erase(_physical.begin()+i);
//                 return;
//             }
//     }
//     inline int get_physical(int i)
//     {
//         assert(i < _physical.size());
//         return _physical[i];
//     }
//     inline void clear_physical()
//     {
//         _physical.clear();
//     }
    inline void clear_topoedge()
    {
      _edge_list.clear();
    }
    inline void clear_face()
    {
      _face_list.clear();
    }
    inline void clear_all()
    {
      _edge_dir_list.clear();
      _edge_list.clear();
      _face_list.clear();
      _surf.clear();
    }
    inline void set_associated()
    {
      _associated = 1;
    }
    inline int associated()
    {
      return _associated;
    }
    inline void add_child ( TopoFace *tf )
    {
      _child.push_back ( tf );
    }
    inline int child_size()
    {
      return _child.size();
    }
    inline TopoFace *get_child ( int i )
    {
      assert ( i < _child.size() );
      return _child[i];
    }
    inline void set_parent ( TopoFace *tf )
    {
      _parent = tf;
    }
    inline void set_parent()
    {
      _is_parent = 1;
    }
    inline int is_parent()
    {
      return _is_parent;
    }

    inline TopoFace *get_parent()
    {
      return _parent;
    }

    inline void setFlag ( int f )
    {
      _flag = f;
    }
    inline void incFlag ()
    {
      _flag++;
    }
    inline void decFlag ()
    {
      _flag--;
    }
    inline int getFlag()
    {
      return _flag;
    }
    void build_internal ( EntityManager *em );
    void update_surf ( EntityManager *em );
    void update_topoedge();
    void add_common_surfaces();
    void dump()
    {
      printf ( "## Topoface %d, color %d --> %d cutfaces :\n", index(), color(), face_size() );
      printf ( "## %d surf --> ", surf_size() );
      for ( int k = 0; k < surf_size(); k++ )
        printf ( " %d", get_surf ( k ) );
      printf ( "\n" );
      printf ( "## %d brep index --> ", potential_brep_index_size() );
      for ( int k = 0; k < potential_brep_index_size(); k++ )
        printf ( " %d", get_potential_brep_index ( k ) );
      printf ( "\n" );
      printf ( "## %d topoedge --> ", topoedge_size() );
      for ( int k = 0; k < topoedge_size(); k++ )
      {
        TopoEdge *te = get_topoedge ( k );
        while ( te->get_ref() )
          te = te->get_ref();
        printf ( " %d (ref %d flag %d)", get_topoedge ( k )->index(), te->index(), te->getFlag() );
      }
      printf ( "\n" );
    }
};

class TopoVolume : public TopoEntity
{
  protected:
    int _color;
    LTetra *_seed;
    std::vector<TopoFace*> _face_list;
    std::vector<LTetra *> _tetra_list;
    TopoVolume *_parent;
    std::vector<TopoVolume *> _child;

  public:
    TopoVolume ( int id, int color, int index )
    {
      _id = id;
      _index = index;
      _color = color;
      _flag = -1;
      _parent = NULL;
    }
    inline int color()
    {
      return _color;
    }
    inline void set_seed ( LTetra *t )
    {
      _seed = t;
//         add_physical(_seed->getOldVol());
//         add_physical(_seed->getVol());
    }
    inline LTetra *get_seed()
    {
      return _seed;
    }
    inline void add_topoface ( TopoFace *tf )
    {
      _face_list.push_back ( tf );
    }
    inline void add_tetra ( LTetra *t )
    {
      _tetra_list.push_back ( t );
    }
    inline int topoface_size()
    {
      return _face_list.size();
    }
    inline TopoFace *get_topoface ( int i )
    {
      assert ( i < _face_list.size() );
      return _face_list[i];
    }
    inline int get_face_orientation ( int i )
    {
      assert ( i < _face_list.size() );
      if ( _face_list[i]->get_inside_topovolume() == this )
        return 0;
      if ( _face_list[i]->get_outside_topovolume() == this )
        return 1;
      assert ( 0 );
    }
    inline int tetra_size()
    {
      return _tetra_list.size();
    }
    inline LTetra *get_tetra ( int i )
    {
      assert ( i < _tetra_list.size() );
      return _tetra_list[i];
    }
    inline void add_child ( TopoVolume *tv )
    {
      _child.push_back ( tv );
    }
    inline int child_size()
    {
      return _child.size();
    }
    inline TopoVolume *get_child ( int i )
    {
      assert ( i < _child.size() );
      return _child[i];
    }
    inline void set_parent ( TopoVolume *tv )
    {
      _parent = tv;
    }
    inline TopoVolume *get_parent()
    {
      return _parent;
    }
//     inline void setFlag ( int f )
//     {
//         _flag = f;
//     }
//     inline void incFlag ()
//     {
//         _flag++;
//     }
//     inline void decFlag ()
//     {
//         _flag--;
//     }
//     inline int getFlag()
//     {
//         return _flag;
//     }
};

// template <typename T>
// class Link
// {
// private:
//     typename std::map<T*, T*> _link_list;
// public:
//     void add_link(T* orig, T* dest)
//     {
//         T* d = get_dest(dest);
//         if (d != NULL)
//             _link_list.insert(std::pair<T*, T*>(orig, d));
//         else
//             _link_list.insert(std::pair<T*, T*>(orig, dest));
//     }
//
//     T* get_dest(T* orig)
//     {
//         typename std::map<T*, T*>::iterator it;
//  it = _link_list.find(orig);
//         if (it != _link_list.end())
//             return it->second;
//         else
//             return NULL;
//     }
// };

class Topo
{
  protected:
    std::vector<TopoVolume *> _tvol;
    std::vector<TopoFace *> _tface;
    std::vector<TopoEdge *> _tedge;
    std::vector<TopoVertex *> _tvx;

    std::vector<TopoVolume *> _rtvol;
    std::vector<TopoFace *> _rtface;
    std::vector<TopoEdge *> _rtedge;

    std::map<int, int> _previous_face_map;
    std::map<std::pair<int, int>, int> _previous_edge_map;
    std::map<int, int> _previous_vertex_map;

    std::multimap<int, TopoVolume *> _key_vol_map;
    std::multimap<int, TopoFace *> _key_face_map;
    std::multimap<int, TopoEdge *> _key_edge_map;
    std::multimap<int, TopoVertex *> _key_vx_map;

    std::set<int> _key_vol_list;
    std::set<int> _key_face_list;
    std::set<int> _key_edge_list;
    std::set<int> _key_vx_list;

    std::map<TopoEdge*, TopoEdge*> _edge_link;
    std::map<BRepEntity*, LVertex*> _brep_vertex_coord;

    std::multimap<BRepEntity *, TopoVertex*> _entity_to_vertex;
    std::multimap<BRepEntity *, TopoVertex*>::iterator _itev;
    std::pair<std::multimap<BRepEntity *, TopoVertex*>::iterator, std::multimap<BRepEntity *, TopoVertex*>::iterator> _retev;
    std::multimap<BRepEntity *, TopoEdge*> _entity_to_edge;
    std::multimap<BRepEntity *, TopoEdge*>::iterator _itee;
    std::pair<std::multimap<BRepEntity *, TopoEdge*>::iterator, std::multimap<BRepEntity *, TopoEdge*>::iterator> _retee;
    std::multimap<BRepEntity *, TopoFace*> _entity_to_face;
    std::multimap<BRepEntity *, TopoFace*>::iterator _itef;
    std::pair<std::multimap<BRepEntity *, TopoFace*>::iterator, std::multimap<BRepEntity *, TopoFace*>::iterator> _retef;

    std::multimap<int, TopoFace*> _edgekey_face_map;
    std::multimap<int, TopoFace*>::iterator _itefm;
    std::pair<std::multimap<int, TopoFace*>::iterator, std::multimap<int, TopoFace*>::iterator> _retefm;


//     std::vector<int> _face_count;
//     std::vector<int> _edge_count;
//     std::vector<int> _vx_count;

    std::queue<TopoVertex*> _vertex_inspection_queue;
    std::queue<TopoEdge*> _edge_inspection_queue;

    int _nb_associated_vertex;
    int _nb_associated_edge;
    int _nb_associated_face;

//     int _lock;

    EntityManager *_em;
    BRepModel *_brm;
    options *_opts;


  public:
    std::map<int,int> mpvols;
    Topo ( options *opt, EntityManager *em )
    {
      _nb_associated_vertex = 0;
      _nb_associated_edge = 0;
      _nb_associated_face = 0;
//       _lock = 0;
      _em = em;
      _opts = opt;
      _brm = NULL;
    }
    TopoVolume *new_topovolume ( int id_vol, int color )
    {
      TopoVolume *vol = new TopoVolume ( id_vol, color, _tvol.size() );
      _tvol.push_back ( vol );
      return vol;
    }
    TopoFace *new_topoface ( int id_face, int color )
    {
      TopoFace *face = new TopoFace ( id_face, color, _tface.size() );
      _tface.push_back ( face );
      return face;
    }
    TopoEdge *new_topoedge ( int id_edge, int color )
    {
      TopoEdge *edge = new TopoEdge ( id_edge, color, _tedge.size() );
      _tedge.push_back ( edge );
      return edge;
    }
    TopoVertex *new_topovertex ( LVertex *v, int id_vertex )
    {
      TopoVertex *vertex = new TopoVertex ( v, id_vertex, _tvx.size() );
      _tvx.push_back ( vertex );
      return vertex;
    }
    TopoVolume *new_root_topovolume()
    {
      TopoVolume *vol = new TopoVolume ( -1, -1, _rtvol.size() );
      _rtvol.push_back ( vol );
      return vol;
    }
    TopoFace *new_root_topoface()
    {
      TopoFace *face = new TopoFace ( -1, -1, _rtface.size() );
      face->set_parent();
      _rtface.push_back ( face );
      return face;
    }
    TopoEdge *new_root_topoedge()
    {
      TopoEdge *edge = new TopoEdge ( -1, -1, _rtedge.size() );
      _rtedge.push_back ( edge );
      return edge;
    }
    inline TopoVolume *get_topovolume ( int i )
    {
      assert ( i < _tvol.size() );
      return _tvol[i];
    }
    inline TopoVolume * get_topovolume_by_color ( int c )
    {
      for ( int i = 0; i < topovolume_size(); i++ )
      {
        TopoVolume *tv = get_topovolume ( i );
        if ( tv->color() == c )
          return tv;
      }
      return NULL;
    }
    inline TopoFace *get_topoface ( int i )
    {
      assert ( i < _tface.size() );
      return _tface[i];
    }
    inline TopoEdge *get_topoedge ( int i )
    {
      assert ( i < _tedge.size() );
      return _tedge[i];
    }
    inline TopoVertex *get_topovertex ( int i )
    {
      assert ( i < _tvx.size() );
      return _tvx[i];
    }
    inline TopoVolume *get_root_topovolume ( int i )
    {
      assert ( i < _rtvol.size() );
      return _rtvol[i];
    }
    inline TopoFace *get_root_topoface ( int i )
    {
      assert ( i < _rtface.size() );
      return _rtface[i];
    }
    inline TopoEdge *get_root_topoedge ( int i )
    {
      assert ( i < _rtedge.size() );
      return _rtedge[i];
    }
    inline void remove_topovolume ( int i )
    {
      assert ( i < _tvol.size() );
      delete _tvol[i];
      _tvol.erase ( _tvol.begin() +i );
    }
    inline void remove_topoface ( int i )
    {
      assert ( i < _tface.size() );
//  printf("--> removing topoface %d\n", _tface[i]->index());
      for ( int j = 0; j < _tface[i]->topoedge_size(); j++ )
      {
        TopoEdge *te = _tface[i]->get_topoedge ( j );
        for ( int k = 0; k < te->topoface_size(); k++ )
        {
          if ( te->get_topoface ( k ) == _tface[i] )
          {
            te->remove_topoface ( k );
            break;
          }
        }
      }
      _tface[i]->clear_all();
      delete _tface[i];
      _tface.erase ( _tface.begin() +i );;
    }
    inline void remove_topoedge ( int i )
    {
      assert ( i < _tedge.size() );
      delete _tedge[i];
      _tedge.erase ( _tedge.begin() +i );;
    }
    inline void remove_topovertex ( int i )
    {
      assert ( i < _tvx.size() );
      delete _tvx[i];
      _tvx.erase ( _tvx.begin() +i );;
    }
    inline int topovolume_size()
    {
      return _tvol.size();
    }
    inline int topoface_size()
    {
      return _tface.size();
    }
    inline int topoedge_size()
    {
      return _tedge.size();
    }
    inline int topovertex_size()
    {
      return _tvx.size();
    }
    inline int root_topovolume_size()
    {
      return _rtvol.size();
    }
    inline int root_topoface_size()
    {
      return _rtface.size();
    }
    inline int root_topoedge_size()
    {
      return _rtedge.size();
    }
    inline void to_be_updated ( TopoVertex *tv )
    {
      assert ( tv != NULL );
      _vertex_inspection_queue.push ( tv );
    }
    inline void to_be_updated ( TopoEdge *te )
    {
      assert ( te != NULL );
//       assert(te->getFlag() != -1);
      _edge_inspection_queue.push ( te );
    }

    inline void topovertex_map_insert ( int key, TopoVertex *tv )
    {
      _key_vx_map.insert ( std::pair<int, TopoVertex*> ( key, tv ) );
      _key_vx_list.insert ( key );
    }
    inline void topoedge_map_insert ( int key, TopoEdge *te )
    {
      _key_edge_map.insert ( std::pair<int, TopoEdge*> ( key, te ) );
      _key_edge_list.insert ( key );
    }
    inline void topoface_map_insert ( int key, TopoFace *tf )
    {
      _key_face_map.insert ( std::pair<int, TopoFace*> ( key, tf ) );
      _key_face_list.insert ( key );
    }
    inline void topovolume_map_insert ( int key, TopoVolume *tf )
    {
      _key_vol_map.insert ( std::pair<int, TopoVolume*> ( key, tf ) );
      _key_vol_list.insert ( key );
    }
    inline std::set<int> get_topovertex_key_list()
    {
      return _key_vx_list;
    }
    inline std::set<int> get_topoedge_key_list()
    {
      return _key_edge_list;
    }
    inline std::set<int> get_topoface_key_list()
    {
      return _key_face_list;
    }
    inline std::set<int> get_topovolume_key_list()
    {
      return _key_vol_list;
    }
    inline std::set<TopoVertex *> get_topovertex_mapped_set ( int key )
    {
      std::multimap<int, TopoVertex*>::iterator itmap;
      std::pair<std::multimap<int, TopoVertex *>::iterator,std::multimap<int, TopoVertex *>::iterator> retmap;
      std::set<TopoVertex *> tset;
      retmap = _key_vx_map.equal_range ( key );
      for ( itmap=retmap.first; itmap!=retmap.second; ++itmap )
        tset.insert ( itmap->second );
      return tset;
    }
    inline std::set<TopoEdge *> get_topoedge_mapped_set ( int key )
    {
      std::multimap<int, TopoEdge*>::iterator itmap;
      std::pair<std::multimap<int, TopoEdge *>::iterator,std::multimap<int, TopoEdge *>::iterator> retmap;
      std::set<TopoEdge *> tset;
      retmap = _key_edge_map.equal_range ( key );
      for ( itmap=retmap.first; itmap!=retmap.second; ++itmap )
        tset.insert ( itmap->second );
      return tset;
    }
    inline std::set<TopoFace *> get_topoface_mapped_set ( int key )
    {
      std::multimap<int, TopoFace*>::iterator itmap;
      std::pair<std::multimap<int, TopoFace *>::iterator,std::multimap<int, TopoFace *>::iterator> retmap;
      std::set<TopoFace *> tset;
      retmap = _key_face_map.equal_range ( key );
      for ( itmap=retmap.first; itmap!=retmap.second; ++itmap )
        tset.insert ( itmap->second );
      return tset;
    }
    inline std::set<TopoVolume *> get_topovolume_mapped_set ( int key )
    {
      std::multimap<int, TopoVolume*>::iterator itmap;
      std::pair<std::multimap<int, TopoVolume *>::iterator,std::multimap<int, TopoVolume *>::iterator> retmap;
      std::set<TopoVolume *> tset;
      retmap = _key_vol_map.equal_range ( key );
      for ( itmap=retmap.first; itmap!=retmap.second; ++itmap )
        tset.insert ( itmap->second );
      return tset;
    }
    inline void topovertex_map_insert_surf ( TopoVertex *tv )
    {
      for ( int i = 0; i < tv->surf_size(); i++ )
        _key_vx_map.insert ( std::pair<int, TopoVertex*> ( tv->get_surf ( i ), tv ) );
    }
    inline void topoedge_map_insert_surf ( TopoEdge *te )
    {
      for ( int i = 0; i < te->surf_size(); i++ )
        _key_edge_map.insert ( std::pair<int, TopoEdge*> ( te->get_surf ( i ), te ) );
    }
    inline void topoface_map_insert_surf ( TopoFace *tf )
    {
//      printf("surf_size --> %d\n", tf->surf_size());
      for ( int i = 0; i < tf->surf_size(); i++ )
        _key_face_map.insert ( std::pair<int, TopoFace*> ( tf->get_surf ( i ), tf ) );
    }
    inline void topoface_map_remove_surf ( TopoFace *tf )
    {
      std::multimap <int, TopoFace* >::iterator it;
      std::pair<std::multimap <int, TopoFace* >::iterator, std::multimap <int, TopoFace* >::iterator > ret;
      for ( int i = 0; i < tf->surf_size(); i++ )
      {
        _key_face_list.erase ( tf->get_surf ( i ) );
        ret = _key_face_map.equal_range ( tf->get_surf ( i ) );
        for ( it = ret.first; it != ret.second; it++ )
          if ( it->second == tf )
          {
            _key_face_map.erase ( it );
            break;
          }
      }
    }
    inline void topovertex_map_remove_surf ( TopoVertex *tv )
    {
      std::multimap <int, TopoVertex* >::iterator it;
      std::pair<std::multimap <int, TopoVertex* >::iterator, std::multimap <int, TopoVertex* >::iterator > ret;
      for ( int i = 0; i < tv->surf_size(); i++ )
      {
        _key_vx_list.erase ( tv->get_surf ( i ) );
        ret = _key_vx_map.equal_range ( tv->get_surf ( i ) );
        for ( it = ret.first; it != ret.second; it++ )
          if ( it->second == tv )
          {
            _key_vx_map.erase ( it );
            break;
          }
      }
    }
    inline void topoedge_map_remove_surf ( TopoEdge *te )
    {
      std::multimap <int, TopoEdge* >::iterator it;
      std::pair<std::multimap <int, TopoEdge* >::iterator, std::multimap <int, TopoEdge* >::iterator > ret;
      for ( int i = 0; i < te->surf_size(); i++ )
      {
        _key_edge_list.erase ( te->get_surf ( i ) );
        ret = _key_edge_map.equal_range ( te->get_surf ( i ) );
        for ( it = ret.first; it != ret.second; it++ )
          if ( it->second == te )
          {
            _key_edge_map.erase ( it );
            break;
          }
      }
    }
    inline void topovertex_map_clear()
    {
      _key_vx_map.clear();
    }
    inline void topoedge_map_clear()
    {
      _key_edge_map.clear();
    }
    inline void topoface_map_clear()
    {
      _key_face_map.clear();
    }
    inline void topovolume_map_clear()
    {
      _key_vol_map.clear();
    }
    inline void add_existing_face ( int surf )
    {
//    _existing_surf.insert(surf);
    }
    inline void add_existing_edge ( LVertex *v0, LVertex *v1, int edge )
    {
      dbgprintf ( 3, "associate %d -- %d to edge %d\n", v0->getIndex(), v1->getIndex(), edge );
      if ( v0->getIndex() < v1->getIndex() )
        _previous_edge_map.insert ( std::pair<std::pair<int, int>, int> ( std::pair<int, int> ( v0->getIndex(), v1->getIndex() ), edge ) );
      else
        _previous_edge_map.insert ( std::pair<std::pair<int, int>, int> ( std::pair<int, int> ( v1->getIndex(), v0->getIndex() ), edge ) );
    }
    inline void add_existing_vertex ( LVertex *v, int vertex )
    {
//          _vertex_previous_vertex.insert(std::pair<LVertex *, int>(v, vertex));
    }


//     inline int find_existing_edge(LVertex *v0, LVertex *v1)
//     {
//         v0->computeRootParents();
//         v1->computeRootParents();
//
//         if (!v0->getRootParentSize() && !v1->getRootParentSize())
//         {
//      rv0 = ce->get_vertex(0)->getIndex() < ce->get_vertex(1)->getIndex() ? ce->get_vertex(0) : ce->get_vertex(1);
//      rv1 = ce->get_vertex(0)->getIndex() < ce->get_vertex(1)->getIndex() ? ce->get_vertex(1) : ce->get_vertex(0);
//         }
//         else
//  {
//    //      printf("rv00 = %d, rv01 = %d, rv10 = %d, rv11 = %d\n", v0->getRootParent(0)->getIndex(), v0->getRootParent(1)->getIndex(), v1->getRootParent(0)->getIndex(), v1->getRootParent(1)->getIndex());
//             if (((v0->getRootParent(0) == v1->getRootParent(0)) && (v0->getRootParent(1) == v1->getRootParent(1))) ||
//                     ((v0->getRootParent(1) == v1->getRootParent(0)) && (v0->getRootParent(0) == v1->getRootParent(1))))
//             {
//                 rv0 = v0->getRootParent(0)->getIndex() < v0->getRootParent(1)->getIndex() ? v0->getRootParent(0) : v0->getRootParent(1);
//                 rv1 = v0->getRootParent(0)->getIndex() < v0->getRootParent(1)->getIndex() ? v0->getRootParent(1) : v0->getRootParent(0);
//             }
//  }
//     }

    inline EntityManager* get_entity_manager()
    {
      return _em;
    }

    void build_volume ( Mesh *m );
    void build_topo ( Mesh *m, LSurface *s );
    void build_vertex_tree();
    void build_face_tree();
    void build_edge_tree();
    void build_volume_tree();
    void dump_heritage();
    void build_hierarchy ( Mesh *m );
    void init_comparison();
    void export_existing_entities ( char *filename );
    void export_dot_graph ( char *name );
    void build_vertex_comparison_table();
    void build_edge_comparison_table();
    void build_face_comparison_table();
    void ImportIbrep ( IBrep *ib ); // import ibrep
    void get_topo_from_gmodel ( GModel *gm );
    void read_topo_file ( char *name );
    int find_edge_occurrence ( TopoEdge *te, BRepEntity *bv0, BRepEntity *bv1, TopoVertex **tv0, TopoVertex **tv1, int &couple, int &ambiguous );
    void update_all_vertex();
    void update_all_edge();
    void update_topovertex ( TopoVertex *tv );
    void update_topoedge ( TopoEdge *te );
    int merge_edge ( TopoVertex* tv );
    int merge_face ( TopoEdge *te );
    void final_clean_face();
    void loop_detect ( TopoFace *tf );
    void init_clean_edge();
    void init_clean_face();
    void process_edges();
    void process_faces();
    void associate_face ( TopoFace *tf, BRepEntity *bef );
    void associate_edge ( TopoEdge *te, BRepEntity *be, TopoVertex *tv0, BRepEntity *brv0, TopoVertex *tv1, BRepEntity *brv1 );
    void associate_vertex ( TopoVertex *tv, BRepEntity *be );
    BRepEntity *get_closest_vertex ( TopoVertex *tv );
    TopoVertex *get_closest_vertex ( BRepEntity *brv );
//     void associate_vertex_with_geometry();
    int associate_with_geometry ( BRepEntity *bre );
    void check_compatibility ( TopoEdge * te );
    void delete_imposed ( TopoEdge *te );
    void find_best_candidate ( BRepEntity *bee, std::vector<TopoEdge *> te_result, TopoEdge **te, TopoVertex **tv0, TopoVertex **tv1 );
//     TopoEdge *find_best_candidate(BRepEntity *bee, std::vector<TopoEdge *> list);
//     int choose_edge(BRepEntity *bee, std::vector<TopoEdge *> list);
    int choose_edge ( std::vector<BRepEntity *> be_result, std::vector<TopoEdge *> list );
    int find_edge_association ( BRepEntity *be, int nb_clone, std::vector<TopoEdge *> te_result, int &valid );
    int find_face_association ( BRepEntity *bef, std::vector<TopoFace *> tf_result );
    void clean_query_results ( std::vector<TopoEdge *> &te_result );
    int try_edge_association ( BRepEntity *bee );
    int try_face_association ( BRepEntity *bef );
    void clean_topo();
    void topovertex_query ( std::vector<int> vx_surf, std::vector<TopoVertex*> &result );
    void topoedge_query ( std::vector<int> edge_surf, std::vector<TopoEdge*> &result );
    void topoface_query ( int face_surf, std::vector<TopoFace*> &result );

    void dumpVTK ( const char *name );
    void dump();
    void dump_bohren();

};

#endif