/********************************************************************************
*                                                                               *
*   Copyright (C) Golaem S.A.  All Rights Reserved.                             *
*                                                                               *
*   Original code & license:                                                    *
*                                                                               *
*   OpenSteer -- Steering Behaviors for Autonomous Characters                   *
*                                                                               *
*   Copyright (c) 2002-2003, Sony Computer Entertainment America                *
*   Original author: Craig Reynolds <craig_reynolds@playstation.sony.com>       *
*                                                                               *
*   Permission is hereby granted, free of charge, to any person obtaining a     *
*   copy of this software and associated documentation files (the "Software"),  *
*   to deal in the Software without restriction, including without limitation   *
*   the rights to use, copy, modify, merge, publish, distribute, sublicense,    *
*   and/or sell copies of the Software, and to permit persons to whom the       *
*   Software is furnished to do so, subject to the following conditions:        *
*                                                                               *
*   The above copyright notice and this permission notice shall be included in  *
*   all copies or substantial portions of the Software.                         *
*                                                                               *
*   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR  *
*   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,    *
*   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL    *
*   THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER  *
*   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING     *
*   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER         *
*   DEALINGS IN THE SOFTWARE.                                                   *
*                                                                               *
********************************************************************************/

/* ------------------------------------------------------------------ */
/*                                                                    */
/*                   Locality Query (LQ) Facility                     */
/*                                                                    */
/* ------------------------------------------------------------------ */
/*

This utility is a spatial database which stores objects each of
which is associated with a 3d point (a location in a 3d space).
The points serve as the "search key" for the associated object.
It is intended to efficiently answer "sphere inclusion" queries,
also known as range queries: basically questions like:

Which objects are within a radius R of the location L?

In this context, "efficiently" means significantly faster than the
naive, brute force O(n) testing of all known points.  Additionally
it is assumed that the objects move along unpredictable paths, so
that extensive preprocessing (for example, constructing a Delaunay
triangulation of the point set) may not be practical.

The implementation is a "bin lattice": a 3d rectangular array of
brick-shaped (rectangular parallelepipeds) regions of space.  Each
region is represented by a pointer to a (possibly empty) doubly-
linked list of objects.  All of these sub-bricks are the same
size.  All bricks are aligned with the global coordinate axes.

Terminology used here: the region of space associated with a bin
is called a sub-brick.  The collection of all sub-bricks is called
the super-brick.  The super-brick should be specified to surround
the region of space in which (almost) all the key-points will
exist.  If key-points move outside the super-brick everything will
continue to work, but without the speed advantage provided by the
spatial subdivision.  For more details about how to specify the
super-brick's position, size and subdivisions see lqCreateDatabase
below.

Overview of usage: an application using this facility would first
create a database with lqCreateDatabase.  For each client object
the application wants to put in the database it creates a
lqClientProxy and initializes it with lqInitClientProxy.  When a
client object moves, the application calls lqUpdateForNewLocation.
To perform a query lqMapOverAllObjectsInLocality is passed an
application-supplied call-back function to be applied to all
client objects in the locality.  See lqCallBackFunction below for
more detail.  The lqFindNearestNeighborWithinRadius function can
be used to find a single nearest neighbor using the database.

Note that "locality query" is also known as neighborhood query,
neighborhood search, near neighbor search, and range query.  For
additional information on this and related topics see:
http://www.red3d.com/cwr/boids/ips.html

For some description and illustrations of this database in use,
see this paper: http://www.red3d.com/cwr/papers/2000/pip.html

*/

#pragma once

#include "glmAbstractProximityDatabase.h"
#include <glmAtomic.h>
#include <glmSimuEntityHandle.h>
#include <glmPODArray.h>

namespace glm
{
	class Vector3;

	struct LocalityQueryData
	{
		float radiusSquared;
		glm::Array<SimuEntityHandle>* neighbors;
	};

	/// A AbstractProximityDatabase-style wrapper for the LQ bin lattice system
	class LocalityQueryProximityDatabase : public AbstractProximityDatabase
	{
	public:

		GLM_CLASS_STAT_ID( glm::MemoryStatIds::Simulation);

		LocalityQueryProximityDatabase(Simulation* simulation, const Vector3& center, const Vector3& dimensions, const Vector3& divisions);
		virtual ~LocalityQueryProximityDatabase();
		virtual void allocateTokens(int typeIndex, int64_t count);
		virtual AbstractTokenType* getToken(int typeIndex, int64_t index);


		// "token" to represent objects stored in the database
		class TokenType : public AbstractProximityDatabase::AbstractTokenType
		{
			friend class LocalityQueryProximityDatabase;

		public:

			GLM_CLASS_STAT_ID( glm::MemoryStatIds::Simulation);

			//TokenType(SimuEntityHandle parentObject, LocalityQueryProximityDatabase& lqsd) ;
			TokenType();
			virtual ~TokenType();

		private:
			void removeFromBin();

			/// previous object in this bin, or NULL
			TokenType*  _prev;

			/// next object in this bin, or NULL
			TokenType*  _next;

			/// bin ID (pointer to pointer to bin contents list)
			TokenType** _bin;
		};

		static atomic32_t _tokenCount;

		void addToBin(TokenType* token, TokenType** bin);

		// the client object calls this each time its position changes
		void updateForNewPosition(AbstractTokenType* token);

        virtual void registerToken(AbstractTokenType* token);
        virtual void unregisterToken(AbstractTokenType* token);

		// find all neighbors within the given sphere (as center and radius). 
		void findNeighbors(const Vector3& position, const float radius, glm::Array< SimuEntityHandle >& neighbors);

		// Given a bin's list of client proxies, traverse the list and adds the ones that falls within the search radius
		void traverseBinClientObjectList(const Vector3& p0, LocalityQueryData& data, TokenType* co);

		// This subroutine of lqMapOverAllObjectsInLocality efficiently traverses of subset of bins specified by max and min bin coordinates
		void mapOverAllObjectsInLocalityClipped(const Vector3& p0, LocalityQueryData& data, int minBinX, int minBinY, int minBinZ, int maxBinX, int maxBinY, int maxBinZ);

	private:

		/* the origin is the super-brick corner minimum coordinates */
		float _originx, _originy, _originz;

		/* length of the edges of the super-brick */
		float _sizex, _sizey, _sizez;

		/* number of sub-brick divisions in each direction */
		int _divx, _divy, _divz;

		/* pointer to an array of pointers, one for each bin */
		TokenType** _bins;

		/* extra bin for "everything else" (points outside super-brick) */
		TokenType* _other;

		glm::PODArray<TokenType*> _allocatedTokens;
	};
}
