// Description: header for classes implementing D-CEL

// Revision history: 25/6/99/LY



#ifndef DCEL

#define DCEL



#include "decl.h"

#include <iostream>

#include <cstring>

#include "structs.h"

#include "sweep.h"



using namespace std;



class D_CEL

{

	friend class OverlayWindow;

	public:

		D_CEL();

		~D_CEL();

		void build_d_cel(InputVertices& vertices1, InputEdges& edges1, InputFaces& faces1, char subdiv1_text = 'A', 

				InputVertices& vertices2 = InputVertices(0), InputEdges& edges2 = InputEdges(0), 

				InputFaces& faces2 = InputFaces(0), char subdiv2_text = 'B');

		void overlay();

	private:

		// nested class forward declaration

		class EqKeyCmp;

		// class scope enumeration

		enum EventType {upper_endpoint, lower_endpoint, edge_edge_intersection, edge_vertex_intersection, 

							 vertex_vertex_intersection, error_event};

		enum Orientation {left, right, error};

		enum Subdivision {intersection_between_halfedges, endpoint_from_subdiv1, 

								endpoint_from_subdiv2, intersection_between_vertices};

		// class scope typedefs

		typedef pair<HalfEdge*,HalfEdge*>									QueueElementValue;

		typedef multimap<Coordinates, QueueElementValue, EqKeyCmp>	EventQueue;

		// nested function object class used in event queue key comparison operations

		class EqKeyCmp

		{

			public:

				bool operator() (const Coordinates& x, const Coordinates& y)

				{	return ((x.second < y.second) || (x.second == y.second && x.first <= y.first));	}

		};

		// private member data

		VertexList			vertex_records;

		HalfEdgeList		half_edge_records;

		FaceList				face_records;

		EventQueue			event_queue;

		SweepStatus			sweep_status;

		// minor utility functions

		HalfEdgeListKey	calc_key(long origin, long destination) const;

		EventType event_type(const QueueElementValue& qev, const Coordinates& event_point) const;

		void build_inner_components(vector<BCGraphNode*>::iterator first, vector<BCGraphNode*>::iterator last, Face* fPtr);

		Orientation turn(const Coordinates& p0, const Coordinates& p1, const Coordinates& p2) const;

		double	calc_slope(const Coordinates& p0, const Coordinates& p1) const;

		void set_incident_face(HalfEdge* hePtr, Face* fPtr);

		void label_new_vertex(EventQueue::iterator ep_iter, string& face1, string& face2);

		// core sub-functions

		bool find_new_event(	SweepStatus::iterator sw_iter1, SweepStatus::iterator sw_iter2, 

									Coordinates& event_point, Coordinates& new_event);

		void validate_vertex_vertex(HalfEdge* old_hePtr_first, Vertex* vPtr);

		void validate_edge_vertex(HalfEdge* old_hePtr_first, HalfEdge* old_hePtr_second, 

										  HalfEdge* new_hePtr_first, HalfEdge* new_hePtr_first_twin, Vertex* vPtr);

		void validate_edge_edge(HalfEdge* old_hePtr_first, HalfEdge* old_hePtr_second, 

										HalfEdge* new_hePtr_first, HalfEdge* new_hePtr_first_twin, Vertex* vPtr);

		void validate_d_cel(EventType event, EventQueue::iterator ep_iter, Vertex* vPtr);

		void plane_sweep();

		void build_bc_graph_and_label();

};



#endif DCEL