/*
 *  sweepLine.cpp
 *  Bentley
 *
 *  Created by Chema on 7/14/10.
 *  Copyright 2010 __MyCompanyName__. All rights reserved.
 *
 */
#include <sys/time.h>
#include <set>
#include <utility>
#include <iostream>
#include <sstream>

#include "vec.h"
#include "GLInclude.h"
#include "basicas.h"
#include "segment.h"
#include "triangle.h"
#include "sweepLineDg.h"
#include "sweepLine.h"

using namespace std;

namespace {

    struct timeval start, end;
    float lapse;
    
    pair<Event::queue::iterator,bool> checkInterx(
            Segment* s, 
            Segment* t,
            Event::queue& events,
            SL::Interx::set& interxs) 
    {
        pair<Event::queue::iterator,bool> ret;
        ret.second=false;

        Edge* sel = (*s).aeg_[Edge::eLeft];
        Edge* ser = (*s).aeg_[Edge::eRight];
        Edge* tel = (*t).aeg_[Edge::eLeft];
        Edge* ter = (*t).aeg_[Edge::eRight];
        
        // avoiding same edge starts and ends         
        if (sel==tel || sel==ter || ser==tel || ser==ter) {
            return ret;
        }

        if(testIntersecxSegs((*sel).p_,(*ser).p_,(*tel).p_,(*ter).p_)) {
            dreal ua=0, ub=0;
            DReal2 p;
            bool overlap = false;
            if (intersecxRectas((*sel).p_,(*ser).p_,(*tel).p_,(*ter).p_,overlap, p, ua, ub) ) {
                if (!overlap) {
                    SL::Interx ix (s,t,p);
                    Event e (s,t,p);
                    if (interxs.count(ix)==0) {
                        Event::queue::iterator eitr = events.insert(e);
                        pair<SL::Interx::set::iterator,bool> iret;
                        iret=interxs.insert(ix);
                        (*const_cast<SL::Interx*>(&*iret.first)).eitr_=eitr;
                    }
//                    if (interxs.count(ix)==0) {
//                        events.push_front(e);
//                        pair<SL::Interx::set::iterator,bool> iret;
//                        iret=interxs.insert(ix);
//                        (*const_cast<SL::Interx*>(&*iret.first)).eitr_=events.begin();
//                        events.sort();
//                    }
                }
            }
        }
        return ret;
    }
}


void SL::cleanInterxEvents() {
    Interx::set::iterator itr = interxs_.begin();
    while(itr!=interxs_.end()) {
        events_.erase((*itr).eitr_);
        ++itr;
    }
}


pair<Segment::tree::iterator,bool> SL::addSegment(Segment* s) {
    pair<Segment::tree::iterator,bool> ret;
    (*s).hot_=true;
    (*s).titr_=tree_.insert(s);
    (*s).hot_=false;
    ret= make_pair((*s).titr_,true);
    return ret;
}

void SL::removeSegment(Segment* s) {
    tree_.erase((*s).titr_);
    (*s).titr_=tree_.end();
}

// segment end or start
Event::Event(Segment* seg, const eType& type) :
    p_((*(*seg).aeg_[type]).p_),
    type_(type),
    sa_(seg) 
    {;}

// intersection
Event::Event(Segment* sa, Segment* sb, const DReal2& p) :
    p_(p),
    type_(eInterx),
    sa_(sa),
    sb_(sb) {;}

    
// lexicographical ordering (first x, then y)
bool Event::operator<(const Event& ref) const {
    return lessLexicoOrder(p_,ref.p_);
}


bool Segment::Compare::operator()(const Segment* lhs, const Segment* rhs) const
{
    bool ret=false;
    
    if (lhs==rhs) return ret;
    
    bool lhshot = (*lhs).hot_;
    const Segment* hseg=lhshot?lhs:rhs;
    const Segment* cseg=lhshot?rhs:lhs;
    const DReal2& p=(*(*hseg).aeg_[Edge::eLeft]).p_;
    const DReal2& l=(*(*cseg).aeg_[Edge::eLeft]).p_;
    const DReal2& r=(*(*cseg).aeg_[Edge::eRight]).p_;

    dreal pgarea = pgArea(l,r,p);
    if (pgarea == 0) {
        const DReal2& o=(*(*hseg).aeg_[Edge::eRight]).p_;
        pgarea = pgArea(l,r,o);
    }
    ret=lhshot? pgarea>0:pgarea<0;
    

    return ret;
}

void SL::init(Triangle::list& tris) {

    gettimeofday(&start, 0);
    clear();
    gettimeofday(&end, 0);
    lapse = (end.tv_sec - start.tv_sec)* (1e03f) + (end.tv_usec - start.tv_usec)*(1e-03f);
    average0_+=lapse;

    gettimeofday(&start, 0);    
    Triangle::list::iterator itr = tris.begin();
    while(itr!=tris.end()) {
        Segment* s = (*itr)->seg_;
        Event eleft(s,Event::eLeft);
        Event eright(s,Event::eRight);

        events_.insert(eleft);
        events_.insert(eright);
        ++itr;
    }

    gettimeofday(&end, 0);
    lapse = (end.tv_sec - start.tv_sec)* (1e03f) + (end.tv_usec - start.tv_usec)*(1e-03f);
    average1_+=lapse;
    //DBUG::printEvents(events_);
    //printSegments(segments_);
}

        
void SL::run(int& debug, Font& font) {

    //DBUG::DEBUG_DRAW(events_,interxs_,tree_, font);
 
    gettimeofday(&start, 0);
    //DBUG::printEvents(events_);
    Event::queue::iterator ie = events_.begin();
    
    //while(debug  && itr != events_.end()
    while(ie != events_.end()) {
        //debug--;

        switch((*ie).type_) {

            case Event::eLeft:
                {
                    // insert incoming segment(s) 
                    Segment* s = (*ie).sa_;
//                    (*s).d_=Edge::eLeft;
                    pair<Segment::tree::iterator,bool> ret;
                    ret = addSegment(s);

                    // intersect incoming segment with above, below
                    if (ret.second) {
                        Segment::tree::iterator is=ret.first;
                        Segment::tree::iterator isa=is; ++isa;
                        if (isa!=tree_.end()) {
                            checkInterx(*isa,*is,events_,interxs_);
                        }
                        if (is!=tree_.begin()) {
                            Segment::tree::iterator isb=is; --isb; 
                            checkInterx(*is,*isb,events_,interxs_);
                        }

                        // envolvente inferior
                        if (ret.first==tree_.begin()) {

                            if (isa!=tree_.end()) {
                                Segment* t =(*isa); 
                                dreal xn = (*(*s).aeg_[Edge::eLeft]).p_[0];
                                dreal x0 = (*(*t).aeg_[Edge::eLeft]).p_[0];
                                dreal yn = (*(*t).aeg_[Edge::eLeft]).p_[1] + (*t).m_*(xn-x0);
                                
                                spans_[spans_.size()-1].r_=DReal2(xn,yn);
                            }
                            spans_.push_back(Span((*s).tri_,(*(*s).aeg_[Edge::eLeft]).p_));
                        }
                    }
                }
                break;

            case Event::eRight:
                {
                    Segment* s = ((*ie).sa_);
                    Segment::tree::iterator is = (*s).titr_;
                    
                    if (is==tree_.end()) break;

                    // intersect above with below of leaving segment
                    if (is!=tree_.begin()) {
                        Segment::tree::iterator isa=is; ++isa;
                        if (isa!=tree_.end()) {
                            Segment::tree::iterator isb=is; --isb; 
                            checkInterx(*isa,*isb,events_,interxs_);
                        }
                    }
                    else { // envolvente inferior
                        Segment::tree::iterator isa=is; ++isa;

                        spans_[spans_.size()-1].r_=(*(*s).aeg_[Edge::eRight]).p_;

                        if (isa!=tree_.end()) {
                            Segment* t =(*isa); 
                            
                            dreal xn = (*(*s).aeg_[Edge::eRight]).p_[0];
                            dreal x0 = (*(*t).aeg_[Edge::eLeft]).p_[0];
                            dreal yn = (*(*t).aeg_[Edge::eLeft]).p_[1] + (*t).m_*(xn-x0);
                           
                            spans_.push_back(Span( (*t).tri_,DReal2(xn,yn) ) );
                        }
                    }
                    removeSegment(s);

                }
                break;

            case Event::eInterx:
                {

                    cc_++;
                    // swap order of intersecting segments in tree
                    DReal2 p = (*ie).p_;

                    Segment* oldt= ((*ie).sa_);
                    Segment* oldb= ((*ie).sb_);
                                        
                    Segment::tree::iterator isa=(*oldt).titr_!=tree_.end()?(*oldt).titr_:(*oldb).titr_;
                    Segment::tree::iterator isb=(*oldb).titr_!=tree_.end()?(*oldb).titr_:(*oldt).titr_; 
                    
                    if (isa!=tree_.end()) {  ++isa;  }
                    if (isb!=tree_.begin()) {  --isb;  }
                    else {    isb == tree_.end();   }

                    if ((*oldb).titr_==tree_.begin()) {
                        spans_[spans_.size()-1].r_=p;
                        spans_.push_back( Span( (*oldt).tri_,p) );
                    }
                    
//                    (*oldb).d_=Edge::eRight;
  //                  (*oldt).d_=Edge::eRight;

                    if ((*oldb).titr_!=tree_.end() && (*oldt).titr_!=tree_.end()) {
                        Segment** ppb =  (const_cast<Segment**>(&*(*oldb).titr_));
                        Segment** ppt =  (const_cast<Segment**>(&*(*oldt).titr_));
                        
                        swap(*ppb,*ppt);
                        swap((*oldb).titr_,(*oldt).titr_);
                    }
                                            
                    Segment::tree::iterator st = (*oldb).titr_!=tree_.end()?(*oldb).titr_:(*oldt).titr_;
                    Segment::tree::iterator sb = (*oldt).titr_!=tree_.end()?(*oldt).titr_:(*oldb).titr_;

                    if (st!=tree_.end()) {
                        if (isa!=tree_.end()) {
                            checkInterx(*isa,*st,events_,interxs_);
                        }
                    }                                      
                    if (sb!=tree_.end()) {
                        if (sb!=tree_.begin()) {
                            checkInterx(*sb,*isb,events_,interxs_);
                        }
                    }

                }
                break;
        }
        ++ie;
    }
    
    gettimeofday(&end, 0);
    lapse = (end.tv_sec - start.tv_sec)* (1e03f) + (end.tv_usec - start.tv_usec)*(1e-03f);
    average2_+=lapse;
}
