<commit_before>/*
 *   CrissCross
 *   A multi-purpose cross-platform library.
 *
 *   A product of Uplink Laboratories.
 *
 *   (c) 2006-2010 <NAME>.
 *   Licensed under the New BSD License.
 *
 */

#ifndef __included_cc_quadtree_h
#define __included_cc_quadtree_h

#include <vector>

#include <crisscross/cc_attr.h>
#include <crisscross/compare.h>
#include <crisscross/mutex.h>
#include <crisscross/vec2.h>

namespace CrissCross
{
	namespace Data
	{
		const unsigned qtMax = 7;

		template <class T>
		struct QtNode
		{
		public:
			float collisionRadius;
			T data;
			vec2 pos;

			QtNode(T const &_data, vec2 const &_pos, float _collisionRadius) : collisionRadius(_collisionRadius), data(_data), pos(_pos)
			{ }
		};

		template <class T>
		class Quadtree
		{
		protected:
			mutable CrissCross::System::ReadWriteLock rwlock;
			vec2 llPosition;
			vec2 trPosition;
			Quadtree<T>             * parent;
			Quadtree<T>             * ll;
			Quadtree<T>             * lr;
			Quadtree<T>             * tl;
			Quadtree<T>             * tr;
			int						descentLevel;
			std::vector<QtNode<T>*>	nodes;

			static bool InRange(float lower_bound, float upper_bound, float point);
			static bool CircleCollision(vec2 circle1, float radius1, vec2 circle2, float radius2);

			void Descend();
			void Ascend();
		public:
			Quadtree(vec2 const &lower_left, vec2 const &upper_right, int _descentLevel = qtMax, Quadtree<T> * _parent = NULL);
			virtual ~Quadtree();
			virtual void InsertObject(T const &_object, vec2 const &position, float _collisionRadius);
			virtual bool RemoveObject(T const &_object, vec2 const &position, float _collisionRadius);
			virtual void ObjectsInCircle(std::vector<T> &array, vec2 const &circle, float radius, size_t limit = (size_t)-1) const;
		};

		template <class T>
		__forceinline bool Quadtree<T>::InRange(float lower_bound, float upper_bound, float point)
		{
			return point > lower_bound && point <= upper_bound;
		}

		template <class T>
		__forceinline bool Quadtree<T>::CircleCollision(vec2 circle1, float radius1, vec2 circle2, float radius2)
		{
			float maximumDistanceSquared = (radius1 + radius2) * (radius1 + radius2);
			float actualDistanceSquared = vec2::DistanceSquared(circle1, circle2);
			return actualDistanceSquared <= maximumDistanceSquared;
		}

		template <class T>
		void Quadtree<T>::ObjectsInCircle(std::vector<T> &array, vec2 const &circle, float radius, size_t limit) const
		{
			RWLockHolder rwlock_holder(&rwlock, RW_LOCK_READ);
<commit_msg>quadtree: don't use __forceinline on InRange/CircleCollision<commit_after>/*
 *   CrissCross
 *   A multi-purpose cross-platform library.
 *
 *   A product of Uplink Laboratories.
 *
 *   (c) 2006-2010 <NAME>.
 *   Licensed under the New BSD License.
 *
 */

#ifndef __included_cc_quadtree_h
#define __included_cc_quadtree_h

#include <vector>

#include <crisscross/cc_attr.h>
#include <crisscross/compare.h>
#include <crisscross/mutex.h>
#include <crisscross/vec2.h>

namespace CrissCross
{
	namespace Data
	{
		const unsigned qtMax = 7;

		template <class T>
		struct QtNode
		{
		public:
			float collisionRadius;
			T data;
			vec2 pos;

			QtNode(T const &_data, vec2 const &_pos, float _collisionRadius) : collisionRadius(_collisionRadius), data(_data), pos(_pos)
			{ }
		};

		template <class T>
		class Quadtree
		{
		protected:
			mutable CrissCross::System::ReadWriteLock rwlock;
			vec2 llPosition;
			vec2 trPosition;
			Quadtree<T>             * parent;
			Quadtree<T>             * ll;
			Quadtree<T>             * lr;
			Quadtree<T>             * tl;
			Quadtree<T>             * tr;
			int						descentLevel;
			std::vector<QtNode<T>*>	nodes;

			static bool InRange(float lower_bound, float upper_bound, float point);
			static bool CircleCollision(vec2 circle1, float radius1, vec2 circle2, float radius2);

			void Descend();
			void Ascend();
		public:
			Quadtree(vec2 const &lower_left, vec2 const &upper_right, int _descentLevel = qtMax, Quadtree<T> * _parent = NULL);
			virtual ~Quadtree();
			virtual void InsertObject(T const &_object, vec2 const &position, float _collisionRadius);
			virtual bool RemoveObject(T const &_object, vec2 const &position, float _collisionRadius);
			virtual void ObjectsInCircle(std::vector<T> &array, vec2 const &circle, float radius, size_t limit = (size_t)-1) const;
		};

		template <class T>
		bool Quadtree<T>::InRange(float lower_bound, float upper_bound, float point)
		{
			return point > lower_bound && point <= upper_bound;
		}

		template <class T>
		bool Quadtree<T>::CircleCollision(vec2 circle1, float radius1, vec2 circle2, float radius2)
		{
			float maximumDistanceSquared = (radius1 + radius2) * (radius1 + radius2);
			float actualDistanceSquared = vec2::DistanceSquared(circle1, circle2);
			return actualDistanceSquared <= maximumDistanceSquared;
		}

		template <class T>
		void Quadtree<T>::ObjectsInCircle(std::vector<T> &array, vec2 const &circle, float radius, size_t limit) const
		{
			RWLockHolder rwlock_holder(&rwlock, RW_LOCK_READ);

{'fraction_non_alphanumeric': 0.104394511831378, 'fraction_numerical': 0.015907735136209984, 'mean_word_length': 3.88824101068999, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 53, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1978708', 'n_tokens_mistral': 1906, 'n_tokens_neox': 1676, 'n_words': 445}