//#####################################################################
// Copyright 2004, Ron Fedkiw, Andrew Selle, Joseph Teran.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Class BOX_HIERARCHY
//#####################################################################
#ifndef __BOX_HIERARCHY__
#define __BOX_HIERARCHY__

#include "../Arrays/ARRAY.h"
#include "../Arrays/LIST_ARRAY.h"
#include "../Arrays/LIST_ARRAYS.h"
#include "../Geometry/BOX_3D.h"
#include "../Geometry/ORIENTED_BOX_3D.h"
#include "../Geometry/IMPLICIT_SURFACE.h"
#include "../Geometry/PLANE.h"
#include "../Data_Structures/STACK.h"
namespace PhysBAM
{

template<class T> class VECTOR_2D;
template<class T> class KD_TREE_NODE_3D;

template<class T>
class BOX_HIERARCHY
{
public:
	int leaves, root;
	LIST_ARRAY<int> parents;
	LIST_ARRAYS<int> children;
	ARRAY<BOX_3D<T> > box_hierarchy;
	mutable STACK<int> traversal_stack;
	mutable STACK<VECTOR_2D<int> > dual_traversal_stack;
	ARRAY<T> box_radius;

	BOX_HIERARCHY()
		: children (2, 0)
	{}

	virtual ~BOX_HIERARCHY()
	{}

	bool Leaf (const int box) const
	{
		return box <= leaves;
	}

	void Thicken_Leaf_Boxes (const T extra_thickness)
	{
		for (int k = 1; k <= leaves; k++) box_hierarchy (k).Change_Size (extra_thickness);
	}

	void Thicken_Leaf_Boxes (const T extra_thickness, const VECTOR_2D<int>& range)
	{
		for (int k = range.x; k <= range.y; k++) box_hierarchy (k).Change_Size (extra_thickness);
	}

	void Update_Box_Radii()
	{
		Update_Leaf_Box_Radii();
		Update_Nonleaf_Box_Radii();
	}

	void Update_Leaf_Box_Radii()
	{
		Calculate_Bounding_Box_Radii (box_hierarchy, box_radius);
	}

	void Dual_Intersection_List_Against_Self (LIST_ARRAY<VECTOR_2D<int> >& dual_intersection_list, const T thickness_over_two = 0) const
	{
		Dual_Intersection_List_Against_Self (root, dual_intersection_list, thickness_over_two);
	}

	void Dual_Intersection_List_Against_Other (BOX_HIERARCHY<T>* other_hierarchy, LIST_ARRAY<VECTOR_2D<int> >& dual_intersection_list, const T thickness_over_two = 0) const
	{
		Dual_Intersection_List_Against_Other (root, other_hierarchy, dual_intersection_list, thickness_over_two);
	}

	void Intersection_List (const VECTOR_3D<T>& point, LIST_ARRAY<int>& intersection_list, const T thickness_over_two = 0) const
	{
		Intersection_List (root, point, intersection_list, thickness_over_two);
	}

	void Intersection_List (const BOX_3D<T>& test_box, LIST_ARRAY<int>& intersection_list, const T thickness_over_two = 0) const
	{
		Intersection_List (root, test_box, intersection_list, thickness_over_two);
	}

	void Intersection_List (const ORIENTED_BOX_3D<T>& test_box, LIST_ARRAY<int>& intersection_list) const
	{
		Intersection_List (root, test_box, intersection_list);
	}

	void Intersection_List (const PLANE<T>& test_plane, LIST_ARRAY<int>& intersection_list, const T thickness_over_two = 0) const
	{
		Intersection_List (root, test_plane, intersection_list, thickness_over_two);
	}

	void Intersection_List (const IMPLICIT_SURFACE<T>& implicit_surface, const MATRIX_3X3<T>& rotation, const VECTOR_3D<T>& translation, LIST_ARRAY<int>& intersection_list, const T contour_value = 0) const
	{
		Intersection_List (root, implicit_surface, rotation, translation, intersection_list, contour_value);
	}

//#####################################################################
public:
	virtual void Initialize_Hierarchy_Using_KD_Tree();
	void Set_Leaf_Boxes (const ARRAY<BOX_3D<T> >& boxes, const bool reinitialize = false);
	void Update_Nonleaf_Boxes();
	virtual void Calculate_Bounding_Box_Radii (const ARRAY<BOX_3D<T> >& bounding_boxes, ARRAY<T>& radius);
	void Update_Nonleaf_Box_Radii();
	// for internal use - but octrees use them as well so they're not private
	void Dual_Intersection_List_Against_Self (const int box, LIST_ARRAY<VECTOR_2D<int> >& dual_intersection_list, const T thickness_over_two) const;
	static void Dual_Intersection_List_Against_Self_Helper (long thread_id, void* helper_raw);
	void Dual_Intersection_List_Against_Self_Parallel (const int box, LIST_ARRAY<VECTOR_2D<int> >& dual_intersection_list, const T thickness_over_two) const;
	void Dual_Intersection_List_Against_Self_Serial (const int box, LIST_ARRAY<VECTOR_2D<int> >& dual_intersection_list, const T thickness_over_two) const;
	void Dual_Intersection_List_Against_Other (const int box, BOX_HIERARCHY<T>* other_hierarchy, LIST_ARRAY<VECTOR_2D<int> >& dual_intersection_list, const T thickness_over_two) const;
	static void Dual_Intersection_List_Against_Other_Helper (long thread_id, void* helper_raw);
	void Dual_Intersection_List_Against_Other_Parallel (const int box, BOX_HIERARCHY<T>* other_hierarchy, LIST_ARRAY<VECTOR_2D<int> >& dual_intersection_list, const T thickness_over_two) const;
	void Dual_Intersection_List_Against_Other_Serial (const int box, BOX_HIERARCHY<T>* other_hierarchy, LIST_ARRAY<VECTOR_2D<int> >& dual_intersection_list, const T thickness_over_two) const;
	void Intersection_List (const int box, const VECTOR_3D<T>& point, LIST_ARRAY<int>& intersection_list, const T thickness_over_two) const;
	void Intersection_List (const int box, const BOX_3D<T>& test_box, LIST_ARRAY<int>& intersection_list, const T thickness_over_two) const;
	void Intersection_List (const int box, const ORIENTED_BOX_3D<T>& test_box, LIST_ARRAY<int>& intersection_list) const;
	void Intersection_List (const int box, const PLANE<T>& test_plane, LIST_ARRAY<int>& intersection_list, const T thickness_over_two) const;
	void Intersection_List (const int box, const IMPLICIT_SURFACE<T>& implicit_surface, const MATRIX_3X3<T>& rotation, const VECTOR_3D<T>& translation, LIST_ARRAY<int>& intersection_list,
				const T contour_value) const;
//#####################################################################
};
}
#endif