/**
 * \file
 * \author Thomas Fischer
 * \date   2012-02-27
 * \brief  Implementation of the OctTree class.
 *
 * \copyright
 * Copyright (c) 2012-2015, OpenGeoSys Community (http://www.opengeosys.org)
 *            Distributed under a Modified BSD License.
 *              See accompanying file LICENSE.txt or
 *              http://www.opengeosys.org/project/license
 *
 */

#ifndef OCTTREE_H_
#define OCTTREE_H_

#include <cstdint>

#include "MathLib/Point3d.h"
#include "MathLib/MathTools.h"

namespace GeoLib {

/// @tparam POINT point data type the OctTree will use
/// @tparam MAX_POINTS maximum number of pointers of POINT in a leaf
template <typename POINT, std::size_t MAX_POINTS>
class OctTree {
public:
	/// Create an OctTree object. The arguments ll and ur are used to compute a
	/// cube domain the OctTree will living in.
	/// @attention This cubic domain can not be resized during the life time of
	/// the OctTree.
	/// @param ll lower left front point, used for computation of cubic domain
	/// @param ur upper right back point, used for computation of cubic domain
	/// @param eps the euclidean distance as a threshold to make objects unique
	/// [default std::numeric_limits<double>::epsilon()]
	/// Adding a new item to an already "filled" OctTree node results in a
	/// split of the OctTree node. The smaller this number is the more leaves
	/// the OctTree will have, i.e. it needs more memory and more time to walk
	/// through the OctTree, but the search inside a leaf is fast. In
	/// contrast a big value results into a smaller number of OctTree leaves,
	/// the memory requirements for the OctTree may be lower but the search
	/// inside a OctTree leaf may be more expensive. The value should be
	/// choosen application dependend. [default 8]
	template <typename T>
	static OctTree<POINT, MAX_POINTS>* createOctTree(T ll, T ur,
		double eps = std::numeric_limits<double>::epsilon());

	/// Destroys the children of this node. @attention Does not destroy the
	/// pointers to the managed objects.
	virtual ~OctTree();

	/// This method adds the given point to the OctTree. If necessary,
	/// new OctTree nodes will be inserted deploying a split of the
	/// corresponding OctTree node.
	/// @param pnt the pointer to a point that should be inserted
	/// @param ret_pnt the pointer to a point in the OctTree. Three cases can
	/// occure:
	/// (1) ret_pnt is nullptr: the given point (pnt) is outside of the OctTree
	/// domain
	/// (2) ret_pnt is equal to pnt: the point is added to the OctTree
	/// (3) In case ret_pnt is neither equal to pnt nor equal to nullptr,
	/// another item within the eps distance is already in the OctTree and the
	/// pointer to this object is returned.
	/// @return If the point can be inserted the method returns true, else false.
	bool addPoint(POINT * pnt, POINT *& ret_pnt);

	/// range query - returns all points inside the range [min[0], max[0]) x
	/// [min[1], max[1]) x [min[2], max[2])
	template <typename T>
	void
	getPointsInRange(T const& min, T const& max, std::vector<POINT*> &pnts) const;

#ifndef NDEBUG
	MathLib::Point3d const& getLowerLeftCornerPoint() const { return _ll; }
	MathLib::Point3d const& getUpperRightCornerPoint() const { return _ur; }
	OctTree<POINT, MAX_POINTS> const* getChild(std::size_t i) const
	{
		return _children[i];
	}
	std::vector<POINT*> const& getPointVector() const { return _pnts; }
#endif

private:
	/// private constructor
	/// @param ll lower left point
	/// @param ur upper right point
	OctTree(MathLib::Point3d const& ll, MathLib::Point3d const& ur, double eps);

	enum class Quadrant : std::int8_t {
		NEL = 0, //!< north east lower
		NWL, //!< north west lower
		SWL, //!< south west lower
		SEL, //!< south east lower
		NEU, //!< south west upper
		NWU, //!< south west upper
		SWU, //!< south west upper
		SEU //!< south east upper
	};

	/// This method tries to add the given point to the OctTree. If necessary
	/// for adding the point, new nodes will be inserted into the OctTree.
	/// @param pnt, ret_pnt see documentation of addPoint()
	/// @return If the point can be inserted the method returns true, else false.
	bool addPoint_(POINT * pnt, POINT *& ret_pnt);

	/**
	 * This method adds the given point to the OctTree. If necessary,
	 * the OctTree will be extended.
	 * @param pnt the point
	 * @return If the point can be inserted the method returns true, else false.
	 */
	bool addPointToChild(POINT* pnt);

	/// Creates the child nodes of this leaf and distribute the points stored
	/// in _pnts to the children.
	/// @param pnt the pointer to the points that is responsible for the split
	void splitNode(POINT * pnt);

	/// checks if the given point pnt is outside of the OctTree node.
	/// @param pnt the point that check is performed on
	/// @return true if the point is outside of the OctTree node.
	bool isOutside(POINT * pnt) const;

	/// children are sorted:
	///   _children[0] is north east lower child
	///   _children[1] is north west lower child
	///   _children[2] is south west lower child
	///   _children[3] is south east lower child
	///   _children[4] is north east upper child
	///   _children[5] is north west upper child
	///   _children[6] is south west upper child
	///   _children[7] is south east upper child
	std::array<OctTree<POINT, MAX_POINTS>*, 8> _children;
	/// lower left front face point of the cube
	MathLib::Point3d const _ll;
	/// upper right back face point of the cube
	MathLib::Point3d const _ur;
	/// vector of pointers to POINT objects
	std::vector<POINT*> _pnts;
	/// flag if this OctTree is a leaf
	bool _is_leaf;
	/// threshold for point uniqueness
	double const _eps;
};

} // end namespace GeoLib

#include "OctTree-impl.h"

#endif /* OCTTREE_H_ */