#ifndef QUADTREE_H
#define QUADTREE_H

#include "vector.h"

#include <boost/thread.hpp>

class Quadtree {
	public:

		struct UpdateThread {
			Quadtree *tree;
			float *buffer;
			UpdateThread(Quadtree *t, float *b);
			void operator()();
		};

		struct QuadNode {
			Quadtree *tree;
			QuadNode *parent;
			QuadNode *children[4];
			int elems;
			float x, y, width, height;
			int level;
			float *vertex_array;

			QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf);
			virtual ~QuadNode();

			float distance(float px, float pz);
			void fill();
			void fix_cracks();
			void subdivide(bool leaf = true);
			void merge();
			void draw();
			void draw_grid();
			float get_height(float px, float py);
			Vector3 get_normal(int index);
		};

		float *heights;
		float *thread_buffer;
		size_t buf_size;
		bool thread_done, thread_running;
		boost::mutex vbo_lock;
		boost::mutex node_lock;
		int width, height, levels;
		float init_time;
		QuadNode *root;
		unsigned int temp_vbo;
		unsigned int vbo_object;
		unsigned int nodes;
		unsigned int vertices;
		Quadtree(int width, int height, float *heightmap, int levels);
		virtual ~Quadtree();

		void update(float x, float z);
		void fix_cracks();
		void create_nodes(int levels);
		unsigned int count_nodes();
		void make_vbo();
		void update_vbo();
		QuadNode *find(float x, float y, int level = -1);
		QuadNode *get_left(QuadNode *node);
		QuadNode *get_right(QuadNode *node);
		QuadNode *get_up(QuadNode *node);
		QuadNode *get_down(QuadNode *node);
};

#endif