/*
 *  sweepTris.cpp
 *  VSweep
 *
 *  Created by Chema on 8/12/10.
 *  Copyright 2010 __MyCompanyName__. All rights reserved.
 *
 */

#include <set>
#include <utility>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <sys/time.h>

#include "vec.h"
#include "draw.h"
#include "GLInclude.h"
#include "basicas.h"
#include "segment.h"
#include "triangle.h"
#include "sweepline.h"
#include "sweepTris.h"

using namespace std;
using namespace Draw;


namespace {

    struct timeval start, end;
    float lapse;
    float average0,average1,average2;
    unsigned cc0,cc1,cc2;

    void printEvent(const ST::Event& e) {
        cout << "event: "<< e.type_ << ":"<< e.p_<<" "<<e.tri_;
        cout<< endl;
    }

    void printEvents(const ST::Event::vector& events, int limit=-1) {
        ST::Event::vector::const_iterator itr = events.begin();
        while(limit--!=0 && itr!=events.end()) {
            printEvent(*itr);
            ++itr;
        }
    }

    void printAET(const Edge::list& aet) {
        Edge::list::const_iterator aetitr = aet.begin();
        while (aetitr!=aet.end()) {
            cout<<*(*aetitr)->vx_[0]<<*(*aetitr)->vx_[1]<<endl;
            aetitr++;
        }
    }

    template<typename Compare, typename T>
    void shellsort(std::vector<T>& A, Compare comp)
    {
        int i, j, incrmnt;


        size_t size = A.size();
        incrmnt = size/2;
        while (incrmnt > 0)
        {
            for (i=incrmnt; i < size; i++)
            {
                j = i;
                T temp = A[i];
                while ((j >= incrmnt) && comp(temp, (A[j-incrmnt] )) )
                {
                    A[j] = A[j - incrmnt];
                    j = j - incrmnt;
                }
                A[j] = temp;
            }
            incrmnt /= 2;
        }
    }


} // namespace


bool ST::Event::Compare::operator()(const ST::Event& lhs, const ST::Event& rhs) const {
    bool ret = false;
    // order first less y coordinate then less x coordinate
    ret = lessLexicoOrderYX(lhs.p_,rhs.p_);
    return ret;
}

void ST::init(std::vector<Triangle>& tris, std::vector<std::string>& console) {

    gettimeofday(&start, 0);
    clear();


    events_.reserve(tris.size()*3);
    for (unsigned i=0;i<tris.size();++i) {
        const Triangle& tri = tris[i];
        const DReal3& b = *tri.vx_[0];
        const DReal3& m = *tri.vx_[1];
        const DReal3& t = *tri.vx_[2];
        events_.push_back( Event(b,&tris[i], ST::Event::eBottom) );
        events_.push_back( Event(m,&tris[i], ST::Event::eMiddle) );
        events_.push_back( Event(t,&tris[i], ST::Event::eTop) );
    }

    gettimeofday(&end, 0);
    lapse = (end.tv_sec - start.tv_sec)* (1e03f) + (end.tv_usec - start.tv_usec)*(1e-03f);
    char txt[128];
    sprintf(txt," events: n %3.3fms", lapse);
    console.push_back(txt);
//    printEvents(events_);

    gettimeofday(&start, 0);

    Event::Compare cmp;
    sort(events_.begin(),events_.end(),cmp);
    //shellsort(events_,cmp);

    gettimeofday(&end, 0);
    lapse = (end.tv_sec - start.tv_sec)* (1e03f) + (end.tv_usec - start.tv_usec)*(1e-03f);
    sprintf(txt," sort: n %3.3fms", lapse);
    console.push_back(txt);
    //cout<< endl;
    //printEvents(events_);
    //printSegments(segments_);
}


void ST::run(int height, int& debug, Font& font, std::vector<string>& console) {

    //DEBUG_DRAW(segments_,events_,interxs_,tree_, envinf_,font);

    std::vector<SL::Span::vector> spanlines;
    spanlines.resize(height);

    ST::Event::vector::iterator itr = events_.begin();
    average0=0;average1=0;average2=0;cc0=0;cc1=0;cc2=0;
    sweepline_.average0_ =0;
    sweepline_.average1_ =0;
    sweepline_.average2_ =0;

    dreal dy = 1./height;
    dreal level =0.;
    //while(debug && itr != events_.end() ) {
    for (unsigned i=0;i<height;++i) {

        gettimeofday(&start, 0);

        level+=dy;

        //debug--;

        while(itr != events_.end() && (*itr).p_[1]<level ) {

//            printEvent(*itr);
            Triangle& t = *(*itr).tri_;

            if (dotProd(*t.normal_,DReal3(0,0,1)) <= 0) {
                ++itr;
                continue;
            }

            // add or remove to list
            switch((*itr).type_) {
                case Event::eBottom:
                    {
                        if ( t.setlevel(level) ) {
                            (*t.seg_).activateEdges(aet_);
                            at_.push_front(&t);
                            t.aitr_= at_.begin();
                        }
                    }
                    break;

                case Event::eMiddle:
                    {
                        (*t.seg_).deActivateEdges(aet_);
                        if ( t.setlevel(level) ) {
                            (*t.seg_).activateEdges(aet_);
                        }
                    }
                    break;

                case Event::eTop:
                    {
                        if ( t.aitr_!= at_.end() ) {
                            (*t.seg_).deActivateEdges(aet_);
                            at_.erase(t.aitr_);
                            t.aitr_ = at_.end();

                        }
                    }
                    break;
            }
            ++itr;
        }

//        printAET(aet_);
        // increment all active edges
        Edge::list::iterator etr = aet_.begin();
        while(etr!=aet_.end()) {
            (*etr)->inc(level);
            ++etr;
        }


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

        gettimeofday(&start, 0);

        sweepline_.init(at_);
        sweepline_.run(debug,font);

        unsigned atsize = at_.size();
        cc0+=sweepline_.interxs_.size();
        cc1+=atsize;
        cc2+=atsize>0?1:0;

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

        spanlines[i].assign(sweepline_.spans_.begin(),sweepline_.spans_.end());
    }

    // remove leftover triangles
    while(itr != events_.end() ) {
        Triangle& t = *(*itr).tri_;
        switch((*itr).type_) {
            case Event::eTop:
            {
                if ( t.aitr_!= at_.end() ) {
                    (*t.seg_).deActivateEdges(aet_);
                    at_.erase(t.aitr_);
                    t.aitr_ = at_.end();
                }
            }
            break;
        }
        ++itr;
    }

    gettimeofday(&start, 0);

    level =0.;
    glBegin(GL_LINES) ;
    for (unsigned i=0;i<height;i++) {
        level+=dy;
        for(unsigned j=0;j<spanlines[i].size();++j) {
            const SL::Span& span = spanlines[i][j];
            const Color3& rgb = *(*span.tri_).rgb_;
            glColor3ubv(&rgb[0]);

            drawSegment2D(DReal3(min(1.,max(0.,span.l_[0])), level, +1),DReal3(min(1.,max(0.,span.r_[0])), level, +1));
            drawSegment2D(DReal3(min(1.,max(0.,span.l_[0])), level+dy/2, +1),DReal3(min(1.,max(0.,span.r_[0])), level+dy/2, +1));

//            drawSegment2D(DReal3(min(1.,max(0.,span.l_[0])), level, min(1.,max(0.,span.l_[1]))),
//            DReal3(min(1.,max(0.,span.r_[0])), level, min(1.,max(0.,span.r_[1]))));
        }

    }
    glEnd();

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

    char txt[128];
    sprintf(txt," while:%3.3fms", average0);
    console.push_back(txt);
    sprintf(txt," SL: %3.3f",average1);
    console.push_back(txt);
    sprintf(txt,"  intersections:%d segs:%d av:%3.3f ava:%3.3f", cc0,cc1,static_cast<dreal>(cc1)/height,static_cast<dreal>(cc1)/cc2);
    console.push_back(txt);
    sprintf(txt,"  clear:%3.3fms", sweepline_.average0_);
    console.push_back(txt);
    sprintf(txt,"  events:%3.3fms", sweepline_.average1_);
    console.push_back(txt);
    sprintf(txt,"  run:%3.3fms", sweepline_.average2_);
    console.push_back(txt);
    sprintf(txt," Draw: n %3.3fms", average2);
    console.push_back(txt);
}
