#ifndef KDTREE_H

#define KDTREE_H

#include <vector>

#include "scene.h"

using namespace std;

class ShapeList: public vector<Shape*>

{

};

class SortableShape

{

public:

	Shape *shape;

	BBox bbox;

	short axis;

	short mark;

	SortableShape(Shape *aShape, short &aAxis): shape(aShape), axis(aAxis), mark(0)

		{ bbox = shape->get_bbox(); };

	friend bool operator<(const SortableShape& a, const SortableShape& b)

		{ return a.bbox.L.cell[a.axis] < b.bbox.L.cell[b.axis]; };

	void setAxis(short aAxis) { axis = aAxis; };

	void setMark() { mark = 1; };

	short hasMark() { return mark; };

};

class SortableShapeList: public vector<SortableShape>

{

public:

	SortableShapeList(ShapeList &shapes, short axis)

	{

		ShapeList::iterator shape;

		for (shape = shapes.begin(); shape != shapes.end(); shape++)

			push_back(SortableShape(*shape, axis));

	};

};

class SplitPos

{

public:

	float pos;

	int lnum, rnum;

	SplitPos(float &aPos): pos(aPos) {};

	friend bool operator<(const SplitPos& a, const SplitPos& b)

		{ return a.pos < b.pos; };

};

class SplitList: public vector<SplitPos>

{

};

class Container

{

protected:

	ShapeList shapes;

	BBox bbox;

public:

	Container(): shapes(), bbox() {};

	void addShape(Shape* aShape);

	//void addShapeNoExtend(Shape* aShape) { shapes.push_back(aShape); };

};

class KdNode

{

	float split;

	bool leaf; /* is this node a leaf? */

public:

	ShapeList shapes;

	KdNode() : leaf(true), axis(0), shapes() {};

	void setSplit(float aSplit) { split = aSplit; };

	float getSplit() { return split; };

	void setLeaf(bool aLeaf) { leaf = aLeaf; };

	bool isLeaf() { return leaf; };

	void addShape(Shape* aShape) { shapes.push_back(aShape); };

};

class KdTree: public Container

{

	KdNode *root;

public:

	KdTree() {};

	void build();

};

#endif