#ifndef _DCEL_H
#define _DCEL_H

#include <ostream>
#include <vector>
#include <list>
#include "nutil.h"


class dcel_halfedge;
class dcel_face;
class dcel_vertex;

class dcel_entity
{
public:
  dcel_entity(void) {}
  virtual ~dcel_entity() {}
  long num; // user defined number
};

class dcel;

class dcelcallbacks : public ncallbacks
{
public:
  dcelcallbacks(): picked(NULL),select(-1),drag(false) {}
  virtual ~dcelcallbacks() {}
  virtual int pick_callback(int,pickinfo[]);
  virtual int drag_callback(npoint3,npoint3,pickinfo);
  virtual int release_callback(npoint3,npoint3,pickinfo);
  virtual int key_callback(const char* txt);
  virtual void draw(void); //redraw everything
  virtual void draw(int i); //redraw just one part
  virtual int add_entity(dcel* ent) {objects.push_back(ent);prop_objects.push_back(properties());datas.push_back(data_container()); return (objects.size()-1);}
  virtual int add_entity(dcel* ent,properties p) {objects.push_back(ent);prop_objects.push_back(p);datas.push_back(data_container()); return (objects.size()-1);}
  virtual const std::vector<data_container>* get_data() {return &datas;}
  std::vector<dcel*> objects;
  std::vector<properties> prop_objects;
  std::vector<data_container> datas;
  std::vector<npoint3> listp;
  dcel* picked;
  int select;
  bool drag;
};


template<class T> class handle
{
public:
  handle():it(0) {} // null "pointer"
  handle(typename std::list<T*>::iterator it_): it(it_) {}
  T& operator *(void) {return **it;}
  T* operator ->() { return *it ;}
  typename std::list<T*>::iterator Base() {return it;}
  bool valid(void) {return (it != typename std::list<T*>::iterator(0));}
  bool operator ==(const handle<T> &other) const {return it==other.it;}
  bool operator !=(const handle<T> &other) const {return it!=other.it;}
  handle<T>& operator ++(void) {it++;return *this;}
  handle<T> operator ++(int) {handle<T> cur=*this;it++;return cur;}
  handle<T>& operator --(void) {it--;return *this;}
  handle<T> operator --(int) {handle<T> cur=*this;it--;return cur;}
private :
  typename std::list<T*>::iterator it;
};

typedef handle<dcel_halfedge> halfedge_handle;
typedef handle<dcel_vertex> vertex_handle;
typedef handle<dcel_face> face_handle;

typedef handle<const dcel_halfedge> halfedge_const_handle;
typedef handle<const dcel_vertex> vertex_const_handle;
typedef handle<const dcel_face> face_const_handle;

class dcel_vertex : public dcel_entity
{
public:  
  dcel_vertex(void): pt(),inc(),dcel_entity() {}
  virtual ~dcel_vertex() {}
  halfedge_handle incident_halfedge(void) const { return inc ;}
  void set_incident_halfedge(halfedge_handle inc_) { inc=inc_ ;}
  npoint3& point(void) { return pt ;}
  const npoint3& point(void) const { return pt ;}
private:
  npoint3 pt;
  halfedge_handle inc;
};
  
class dcel_halfedge : public dcel_entity
{
public:  
  dcel_halfedge(void) : ori(),tw(),inc(),prev(),next(),dcel_entity() {}
  virtual ~dcel_halfedge() {}
  vertex_handle origin(void) const { return ori ;}
  void set_origin(vertex_handle ori_) { ori=ori_;}
  halfedge_handle twin(void) const { return tw ;}
  void set_twin(halfedge_handle tw_) { tw=tw_;}
  face_handle incident_face(void) const { return inc;}
  void set_incident_face(face_handle inc_) { inc=inc_;}
  halfedge_handle next_halfedge(void) const { return next ;}
  void set_next_halfedge(halfedge_handle next_) { next=next_;}
  halfedge_handle prev_halfedge(void) const { return prev ;}
  void set_prev_halfedge(halfedge_handle prev_) { prev=prev_;}
private:
  vertex_handle ori;
  halfedge_handle tw;
  face_handle inc;
  halfedge_handle prev;
  halfedge_handle next;
};

class dcel_face : public dcel_entity
{
public:  
  dcel_face(void) : out(),dcel_entity()  {}
  virtual ~dcel_face() {}
  halfedge_handle outer_loop(void) const { return out ;}
  halfedge_handle inner_loop(int i) const { return in[i] ;}
  int nb_inner_loop(void) const { return in.size() ;}
  void set_outer_loop(halfedge_handle out_) { out=out_ ;}
  void add_inner_loop(halfedge_handle in_) { in.push_back(in_);}
  void set_inner_loop(int i, halfedge_handle in_) { in[i]=in_;};
  void clear_inner_loops(void) { in.clear();}
private:
  halfedge_handle out;
  std::vector<halfedge_handle> in;
};

class dcel : public ndrawable
{
public:
  dcel(void) : nh(0),nf(0),nv(0) {}
  dcel(const dcel & other) {*this=other;}; // deep copy
  dcel& operator =(const dcel & other); // deep copy
  virtual ~dcel(void);
  template < class T > vertex_handle add_vertex(const T &v);
  template < class T > face_handle add_face(const T &f);
  template < class T > halfedge_handle add_halfedge(const T &he);
  void del_vertex(vertex_handle v) { delete *(v.Base());vertices.erase(v.Base());nv--;}
  void del_face(face_handle f) { delete *(f.Base());faces.erase(f.Base());nf--;}
  void del_halfedge(halfedge_handle he) { delete *(he.Base()); halfedges.erase(he.Base());nh--;}
  void clear(void); // empties the datastructure
  vertex_handle begin_vertices() const {return vertex_handle(vertices.begin());}
  face_handle begin_faces() const {return face_handle(faces.begin());}
  halfedge_handle begin_halfedges() const {return halfedge_handle(halfedges.begin());}
  vertex_handle end_vertices() const {return vertex_handle(vertices.end());}
  face_handle end_faces() const {return face_handle(faces.end());}
  halfedge_handle end_halfedges() const {return halfedge_handle(halfedges.end());}
  int nb_vertices() const {return nv;}
  int nb_halfedges() const {return nh;}
  int nb_faces() const {return nf;}
  void _display(data_container &data, bool vertices=true,bool lines=true, bool faces=false) const; // for display purposes
  void print(std::ostream &os,int prec=5) const ;    
  virtual void Display(data_container &data) const  { _display(data,true,true,true);}
  virtual dcel* clone(void) const;
  virtual int dim(void) const {return 3;}

private:

  int nh;
  int nf;
  int nv;
  mutable std::list<dcel_halfedge *> halfedges;
  mutable std::list<dcel_face *> faces;
  mutable std::list<dcel_vertex *>  vertices;
//  std::vector<halfedge_handle> active_loops;
};


template < class T > vertex_handle dcel::add_vertex(const T &v) 
{ 
  T* ptr=new T(v) ; 
  vertices.push_back(ptr); 
  std::list<dcel_vertex *>::iterator it=vertices.end();
  it--;
  nv++;
  return vertex_handle(it);
}

template < class T > face_handle dcel::add_face(const T &f)
{  
  T* ptr=new T(f) ;
  faces.push_back(ptr);
  std::list<dcel_face *>::iterator it=faces.end();
  it--;
  nf++;
  return face_handle(it);
}

template < class T > halfedge_handle dcel::add_halfedge(const T &he)
{ 
  T* ptr=new T(he) ; 
  halfedges.push_back(ptr);
  std::list<dcel_halfedge *>::iterator it=halfedges.end();
  it--;
  nh++;
  return halfedge_handle(it);
}


// build dcel from list of points and faces (no internal loops). faces described by ordered point id as list (nbpt / pt1... ptX / etc...)
// point list begins with id 0 and is dense
void build_dcel_from_mesh(std::vector<npoint3> vp,std::vector<int> vf,dcel& graph);

// perform one step of the Doo-Sabin subdivision
// graph should contain only simple faces (no internal loops)
void doo_sabin_subdivision(dcel& graph, dcel& subd_graph);

// perform one step of the Catmull-Clark subdivision
// graph should contain only simple faces (no internal loops)
void catmull_clark_subdivision(dcel& graph, dcel& subd_graph);


// perform one step of Loop's subdivision algorithm
// graph should contain only simple faces (no internal loops)
void loop_subdivision(dcel& graph, dcel& subd_graph);

#endif