/*
	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License version 2 
	as published by the Free Software Foundation.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA


	Copyright (C) 2006  Thierry Berger-Perrin <tbptbp@gmail.com>
*/
#ifndef KDLIB_INTERNAL_H_
#define KDLIB_INTERNAL_H_

#include "sys_log.h"
#include "sys_mem.h"

#include "kdlib.h"			// aabb_t & co

#ifdef USE_CLIPPER
	#include "kdlib_clipper.h"
#endif


#include "rt_sah.h" //FIX:

//FIX: our rptr_t typedef is too broad in some cases
#ifdef __ICC__
	#pragma warning(disable : 858) // remark #858: type qualifier on return type is meaningless
#endif


namespace kdlib {
	namespace cst {
		extern const float32_t inf_plus, inf_minus;
	}
	static int remap_other_axis[4] = { 1,2,0,1 };
	static FINLINE int get_other_axis(const int axis) { return remap_other_axis[axis]; }
	template <int axis> static int get_other_axis() { return remap_other_axis[axis]; }


	// save some typing/qualification. plz.
	enum sideness_t { side_left = 0, side_right = 1 };


	/*
		Stores ordered lists of intervals/segments for 3 axis, some state
		and a reference to the underlying triangle.

		Can be seen either as linked boxes, ordered boundaries etc...


		That structure isn't sufficiently aligned so we can't directly use one of those pointer in there
		to point explicitely into either a left or right side and then infer from that what is really the
		linked_box_t it's pointing to.

		Instead we encode the sideness into pointers, into the lowest bits,
		so we're then able to reconstruct everything, that is the triplet linked_box_t/axis/side.
	*/
	struct list3d_t;
	template <typename T> class sided_pointer_t {
		friend 	struct list3d_t;			// needed because we do really ugly things.
		typedef T * const __restrict rptr_t;	// sorry too much typing.
	public:
	
		// try to catch as many missuses as possible
		//sided_pointer_t() {}
		//explicit sided_pointer_t(rptr_t p, const sideness_t s) : ptr(compose(p,s)) {}

		static rptr_t compose(rptr_t base, const sideness_t s) {
			const ptrdiff_t p(reinterpret_cast<ptrdiff_t>(base));
			return (rptr_t) (p | s);
		}

		void set(rptr_t base, const sideness_t s) { ptr = compose(base, s); }
		void set_null() { ptr = 0; }

		rptr_t extract(sideness_t &side) const {
			const ptrdiff_t p(reinterpret_cast<ptrdiff_t>(ptr));
			side = sideness_t(p & 1);
			return (rptr_t) (p & ~1);
		}

		sideness_t get_side() const {
			const ptrdiff_t p(reinterpret_cast<ptrdiff_t>(ptr));
			return sideness_t(p & 1);
		}

		/*
		operator rptr_t() const { 
			const ptrdiff_t p(reinterpret_cast<ptrdiff_t>(ptr));
			return (rptr_t) (p & ~1);
		}
		*/
		rptr_t get() const { 
			const ptrdiff_t p(reinterpret_cast<ptrdiff_t>(ptr));
			return (rptr_t) (p & ~1);
		}

		bool_t is_null() const { return get() == 0; }
	private:
		T *ptr;
	};




	/*
	struct linked_box_t {
		typedef sided_pointer_t<linked_box_t> ptr_t;
		struct boundary_t {
			sided_pointer_t<linked_box_t>	next, prev;
			float							pos;
		} bounds[3][2];	// 2 boundaries (left/right) per axis.

		uint_t triangle_id;
		template <uint_t axis> const float &get_coord(const sideness_t s) const { return bounds[axis][s].pos; }
	};
	*/

	struct lbox_t {
		typedef sided_pointer_t<lbox_t> ptr_t;
		struct boundary_t {
			float	pos;
			ptr_t	next;
		} dim[3][2];

		uint_t triangle_id;
		union flags_t {
			uint32_t bits;
			struct {
				// mutable.
				uint_t		tag_clipped : 1;
				uint_t		tag_planar : 1;		// debug
				sideness_t	tag_side : 2;

				uint_t	dummy_padding: 14;


				// constant part.
				uint_t	planarity : 3;	// planar flag for each axis.
			};
		} flags;

		//char padding[8];	// 64-56 -> 
		// we need some temp storage for when we clip-split; as we're padding to 64 bytes anyway...
		// should try to pack flags & tmp storage on x86-64, so we end up with a 80 bytes structure.
		lbox_t * __restrict clone;
		char padding[4];


		lbox_t() {}
		explicit lbox_t(const aabb_t &bbox, const uint_t id) : triangle_id(id) {
			dim[0][0].pos = bbox.pmin.x; dim[0][1].pos = bbox.pmax.x;
			dim[1][0].pos = bbox.pmin.y; dim[1][1].pos = bbox.pmax.y;
			dim[2][0].pos = bbox.pmin.z; dim[2][1].pos = bbox.pmax.z;

			flags.bits = 0;
			flags.planarity |= (dim[0][0].pos == dim[0][1].pos) ? 1 : 0;
			flags.planarity |= (dim[1][0].pos == dim[1][1].pos) ? 2 : 0;
			flags.planarity |= (dim[2][0].pos == dim[2][1].pos) ? 4 : 0;
		}

		template <uint_t axis> bool_t is_planar(const float coord) const { return (dim[axis][0].pos == dim[axis][1].pos) & (dim[axis][0].pos == coord); }

		// update our tags according to this axis/split.
		void set_category(const uint_t axis, const float split, const sideness_t planar_side) {
			const float &min(dim[axis][0].pos), &max(dim[axis][1].pos);
			const bool_t 
				planar	= (min == max) & (min == split),
				cross	= (min < split) & (max > split);

			// if crossing, the clipped bit is raised and this lbox put on the left side.
			flags.tag_clipped	= cross ? true : false;
			flags.tag_planar	= planar;

			flags.tag_side		= min >= split ? side_right : side_left;
			flags.tag_side		= planar ? planar_side : flags.tag_side;

			// if (flags.tag_clipped) BREAKPOINT();
		}
	};

	// used to park lbox on one axis for which we know the sideness upfront.
	template <sideness_t side> struct sided_list_t {
		static lbox_t dummy;	// geez, i'm a punk.
		lbox_t 
			* __restrict head,
			* __restrict tail;	// don't use it.

		sided_list_t() : head(0), tail(&dummy) {}

		void append(const uint_t axis, lbox_t * __restrict l) {
			head = head ? head : l;
			tail->dim[axis][side].next.set(l, side);
			tail = l;
		}
		void stopgap(const uint_t axis) {
			tail->dim[axis][side].next.set_null();
		}
	};


	// we'll need to pass around something like that.
	struct list3d_t {
		lbox_t::ptr_t 
			heads[3],
			tails[3];

		void append(const uint_t axis, lbox_t * __restrict p, const sideness_t side) {
			heads[axis].ptr = heads[axis].ptr ? heads[axis].ptr : lbox_t::ptr_t::compose(p, side);
			if (!tails[axis].is_null()) {
				sideness_t tail_side;
				lbox_t * __restrict q = tails[axis].extract(tail_side);
				q->dim[axis][tail_side].next.set(p, side);
			}

			tails[axis].set(p, side);				
		}

		void stopgap(const uint_t axis) {
			if (!tails[axis].is_null()) {
				sideness_t tail_side;
				lbox_t * __restrict q = tails[axis].extract(tail_side);
				q->dim[axis][tail_side].next.set_null();
			}
		}
	};



	//debug: walks a list.
	static NOINLINE int walk(lbox_t * __restrict p, const uint_t axis, sideness_t side) {
		int pop = 0, pop_l = 0, pop_r = 0;

		while (p) {
			pop_l += side == side_left  ? 1 : 0;
			pop_r += side == side_right ? 1 : 0;
			++pop;
			p = p->dim[axis][side].next.extract(side);
		}

		return pop;
	}




	// anonymous struct/union abuse.
	// 16 bytes.
	struct node_t {
		union {
			struct { // leaf
				lbox_t::ptr_t	items;			// list of elements forming that leaf
				int				count;
			};
			struct { // splitter
				float32_t	split_coord;	// not very good for alignment, but useful for debugging (same slot as items).
				node_t		*left;
				node_t		*right;
			};
		};

		struct {
			struct {
				uint32_t split_axis	: 2;
				uint32_t padding	: 29;
				uint32_t is_leaf	: 1;
			};
		};
		//uint_t	split_axis;
		//bool_t space_cut;
		//int	num_l, num_r;
		//float	score;

		aabb_t cell;						// bloat, but easier to get // build right this way.
	};

	struct stats_t {
		int
			num_nodes,			// total number of nodes (inner & leaf).
			num_leaves,			// number of leaves.
			num_leaves_empty,	// number of empty leaves.
			num_ids,			// total number of triangle referenced in leaves.
			num_max_ids,		// max triangles per leaf.
			num_space_cuts,		// how many times we cut emptyness away.
			max_lvl;			// how deep we went.
	};

	struct state_t {
		const triangle_t	*tris;
		int					tcount;
		list3d_t			l3;
		aabb_t				scene_bbox;
	};

	struct pools_t {
		lbox_t	*initial_lboxen;

		sys::mem::growing_pool_t<node_t>	nodes;
		sys::mem::growing_pool_t<lbox_t>	lboxen;

		void purge() {
			// sys::log("kdlib::pools_t::purge: purging all pools.\n");
			lboxen.purge();
			nodes.purge();

			sys::mem::liberate(initial_lboxen);
		}
	};


	struct compiler_t {
		int injection(const kdlib::triangle_t * const __restrict soup, const int_t tcount);
		int compile(const SAH::heuristic_t &sah);
		int dispose();

		pools_t		pools;	//FIXSMP: nope. per thread/cpu.
		stats_t		stats;

		#ifdef USE_CLIPPER
			clipper_t	clippy;	//FIXSMP: nope. per thread/cpu.
		#endif

		node_t		root;
	//private:
		state_t		state;
	};
}

#endif
