<commit_before>#ifndef OMPL_DATASTRUCTURES_PDF_
#define OMPL_DATASTRUCTURES_PDF_

#include <vector>

namespace ompl
{
	template <typename _T>
	class PDF
	{
		public:

		PDF(void) : normalization(0.0);
		{
		}

		virtual ~PDF(void)
		{
		}

		virtual void add(_T d, const double w)
		{
			data.push_back(d);
			weights.push_back(w);
			normalization += w;
		}

		virtual _T sample(double r) const
		{
			r *= normalization;
			//TODO
		}

		protected:
		std::vector<double> weights;
		double normalization;
		std::vector<_T> data;
	};
}

#endif<commit_msg>added initial impl of pdf, still need to finish removals<commit_after>#ifndef OMPL_DATASTRUCTURES_PDF_
#define OMPL_DATASTRUCTURES_PDF_

#include <vector>

namespace ompl
{
	template <typename _T>
	class PDF
	{
		public:

		PDF(void) : root(NULL), normalization(0.0)
		{
		}

		virtual ~PDF(void)
		{
			if (root != NULL)
				clearTree(root);
		}

		virtual void add(const _T d, const double w)
		{
			Node* n = new Node(data.size(), w);
			data.push_back(d);
			normalization += w;
			if (root == NULL)
				root = n;
			else if (root->isLeaf())
			{
				Node* parent = new Node(-1, w + root->weight);
				parent->left = root;
				parent->right = n;
				root = parent;
			}
			else
			{
				Node* sibling = root;
				Node* parent = NULL;
				while (!sibling->isLeaf())
				{
					sibling->weight += w;
					parent = sibling;
					if (sibling->left->weight <= sibling->right->weight)
						sibling = sibling->left;
					else
						sibling = sibling->right;
				}
				Node* newParent = new Node(-1, w + sibling->weight);
				newParent->left = sibling;
				newParent->right = n;
				if (parent->left == sibling)
					parent->left = newParent;
				else
					parent->right = newParent;
			}
			printTree(root);
		}

		/* The value r must be between 0 and 1. */
		virtual _T sample(double r) const
		{
			//TODO throw exception if tree is empty
			r *= normalization;
			Node* current = root;
			while (!current->isLeaf())
			{
				if (r < current->left->weight)
					current = current->left;
				else
				{					
					r -= current->left->weight;
					current = current->right;
				}
			}
			return data[current->dataIndex];
		}

		protected:

		struct Node
		{
			Node* left;
			Node* right;
			//If this is a leaf node, dataIndex contains index into data vector
			int dataIndex;			
			double weight;

			Node(const int index, const double w) : left(NULL), right(NULL), dataIndex(index), weight(w)
			{
			}

			Node(void) : Node(-1, 0.0)
			{
			}

			inline bool isLeaf()
			{
				return (left == NULL && right == NULL);		
			}
		};

		void clearTree(Node* n)
		{
			if (!n->isLeaf())
			{
				clearTree(n->left);	
				clearTree(n->right);
			}
			delete n;
		}

		void printTree(Node* n, const int level = 0)
		{
			for (int i = 0; i < level; ++i)
				std::cout << " ";
			std::cout << n->weight;
			if (n->isLeaf())
				std::cout << " " << n->dataIndex << std::endl;
			else
			{
				std::cout << std::endl;
				printTree(n->left, level+2);
				printTree(n->right, level+2);
			}
		}

		Node* root;
		double normalization;
		std::vector<_T> data;
	};
}

#endif
{'fraction_non_alphanumeric': 0.14675658317276816, 'fraction_numerical': 0.004816955684007707, 'mean_word_length': 2.5317460317460316, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 44, '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': '1529340', 'n_tokens_mistral': 1437, 'n_tokens_neox': 1121, 'n_words': 281}