#include "stdafx.h"
#include "kd.h"
#include <list>


template<int i> class min_sort {
    public: 
        static bool sort(Primitive* obj1, Primitive* obj2) {
            obj1->getBBox().min[i] < obj2->getBBox().min[i];
        }
};
template<int i> class max_sort {
    public: 
        static bool sort(Primitive* obj1, Primitive* obj2) {
            obj1->getBBox().max[i] < obj2->getBBox().max[i];
        }
};


void KD::build(const std::vector<Primitive*> &_objects)
{
    BBox bbox = BBox::empty();
    size_t n = _objects.size();
    // O(n)
    for (size_t i; i < n; i++) {
        bbox.extend(_objects[i]->getBBox());
    }

    float surfaceArea = 0.0f;
    for (size_t i; i < n; i++) {
        surfaceArea += _objects[i]->getSurfaceArea();
    }

    int splitDim = 0;
    if (bbox.max[0] - bbox.min[0] > bbox.max[1] - bbox.min[1]) {
        if (bbox.max[0] - bbox.min[0] < bbox.max[2] - bbox.min[2]) {
            splitDim = 2;
        }
    } else {
        if (bbox.max[1] - bbox.min[1] > bbox.max[2] - bbox.min[2]) {
            splitDim = 1;
        }    
        else {
            splitDim = 2;
        }
    }
    std::vector<Primitive*> minsort(_objects.begin(), _objects.end());
    std::vector<Primitive*> maxsort(_objects.begin(), _objects.end());
    printf("%u %u %u\n", _objects.size(), (maxsort.size()), (minsort.size()));
    for (size_t i=0; i < n; i++) {
        maxsort[i]->getBBox(); 
        minsort[i]->getBBox(); 
    }
    minsort.resize(3);
    std::stable_sort(minsort.begin(), minsort.end(), min_sort<2>::sort);




/*
my compare functions (named sort, sorry for the confusion!) are called with invalid pointers, even though all pointers in _objects, minsort (and maxsort) are valid.
it looks like std::stable_sort tries to access the -1st element of minsort.
gdb:
Program received signal SIGSEGV, Segmentation fault.
0x08054a02 in min_sort<2>::sort (obj1=0xb6f2c038, obj2=0x22041) at src/rt/kd.cpp:9
9	            obj1->getBBox().min[i] < obj2->getBBox().min[i];

(gdb) frame 7
#7  0x08053d2f in KD::build (this=0xbffff3a0, _objects=...) at src/rt/kd.cpp:55
55	    std::stable_sort(minsort.begin(), minsort.end(), min_sort<2>::sort);

(gdb) print minsort[-1]
$1 = (Primitive *&) @0x8169bfc: 0x22041
(gdb) print minsort[0]
$2 = (Primitive *&) @0x8169c00: 0xb6f2c008
(gdb) print minsort[1]
$3 = (Primitive *&) @0x8169c04: 0xb6f2c008
(gdb) print minsort[2]
$4 = (Primitive *&) @0x8169c08: 0xb6f2c068
(gdb) print minsort.size()
$5 = 3


*/