<commit_before>/*******************************************************************************
 * DANIEL'S ALGORITHM IMPLEMENTAIONS
 *
 *  /\  |  _   _  ._ o _|_ |_  ._ _   _ 
 * /--\ | (_| (_) |  |  |_ | | | | | _> 
 *         _|                      
 *
 * DYNAMIC ORDER STATISTIC
 *
 * Features:
 * 1. based on red-black tree
 * 2. O(logn) lookup time 
 * 3. Select the i-th largest element
 *
 * http://en.wikipedia.org/wiki/Order_statistic
 *
 ******************************************************************************/

#ifndef __DOS_TREE_H__
#define __DOS_TREE_H__

#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include "generic.h"
#include "stack.h"
#include "double_linked_list.h"
#include "rbtree.h"

namespace alg
{
	class DosTree:public RBTreeAbstract
	{
	public:
		/**
		 * dynamic order stat node structure definition
		 */
		typedef struct dostree_node_t : public rbtree_node_t {
			int key;	// the key	
			int size;	// the size of this subtree
		} *dostree_node;

#define DOSNODE(rbnode) static_cast<dostree_node>(rbnode)
#define DOSNODE_SIZE(rbnode) (rbnode?DOSNODE(rbnode)->size:0)

	public:
		DosTree() { }
		~DosTree() {
			destruct(DOSNODE(get_root()));
		}
	private:
		DosTree(const DosTree&);
		DosTree& operator=(const DosTree&);

		void destruct(dostree_node n)
		{
			if (n==NULL) return;
			destruct(DOSNODE(n->left));
			destruct(DOSNODE(n->right));
			delete n;
		}

	public:

		dostree_node index(int index)
		{
			return lookup_node(get_root(),index);
		}

		/**
		 * dostree_insert
		 * insert a new key into the dos tree
		 */
		void insert(int key) 
		{
			dostree_node inserted_node = new_node(key, RED, NULL, NULL);

			if (get_root() == NULL) {
				set_root(inserted_node);
			}
			else {
				rbtree_node n = DOSNODE(get_root());
				while (1) {
					// incr 1 for each node on the path traversed from the root
					DOSNODE(n)->size+=1;
					if (key < DOSNODE(n)->key) {
						if (n->left == NULL) {
							n->left = inserted_node;
							break;
						} else {
							n = n->left;
						}
					} else {
						if (n->right == NULL) {
							n->right = inserted_node;
							break;
						} else {
							n = n->right;
						}
					}
				}
				inserted_node->parent = n;	
			}

			// fix red-black properties
			insert_case1(inserted_node);
		}

		/**
		 * delete the key in the red-black tree
		 */
		void delete_key(dostree_node n)
		{
			rbtree_node child;

			/* Copy key/value from predecessor and then delete it instead */
			if (n->left != NULL && n->right != NULL) {
				dostree_node pred = DOSNODE(maximum_node(n->left));
				DOSNODE(n)->key = DOSNODE(pred)->key;
				DOSNODE(n)->size = DOSNODE(pred)->size;
				n = pred;
			}

			// fix up size from pred
			fixup_size(n);

			assert(n->left == NULL || n->right == NULL);
			child = n->right == NULL ? n->left  : n->right;
			if (node_color(n) == BLACK) {
				n->color = node_color(child);
				delete_case1(n);
			}
			replace_node(n, child);
			if (n->parent == NULL && child != NULL)
				child->color = BLACK;

			delete (DOSNODE(n));
		}

		void print() {
			print_helper(get_root(), 0);
			puts("");
		}

		void print_helper(rbtree_node n, int indent) {
			int i;
			if (n == NULL) {
				fputs("<empty tree>", stdout);
				return;
			}
			if (n->right != NULL) {
				print_helper(n->right, indent + INDENT_STEP);
			}
			for(i=0; i<indent; i++)
				fputs(" ", stdout);<commit_msg>fixed a bug in leaf node delete<commit_after>/*******************************************************************************
 * DANIEL'S ALGORITHM IMPLEMENTAIONS
 *
 *  /\  |  _   _  ._ o _|_ |_  ._ _   _ 
 * /--\ | (_| (_) |  |  |_ | | | | | _> 
 *         _|                      
 *
 * DYNAMIC ORDER STATISTIC
 *
 * Features:
 * 1. based on red-black tree
 * 2. O(logn) lookup time 
 * 3. Select the i-th largest element
 *
 * http://en.wikipedia.org/wiki/Order_statistic
 *
 ******************************************************************************/

#ifndef __DOS_TREE_H__
#define __DOS_TREE_H__

#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include "generic.h"
#include "stack.h"
#include "double_linked_list.h"
#include "rbtree.h"

namespace alg
{
	class DosTree:public RBTreeAbstract
	{
	public:
		/**
		 * dynamic order stat node structure definition
		 */
		typedef struct dostree_node_t : public rbtree_node_t {
			int key;	// the key	
			int size;	// the size of this subtree
		} *dostree_node;

#define DOSNODE(rbnode) static_cast<dostree_node>(rbnode)
#define DOSNODE_SIZE(rbnode) (rbnode?DOSNODE(rbnode)->size:0)

	public:
		DosTree() { }
		~DosTree() {
			destruct(DOSNODE(get_root()));
		}
	private:
		DosTree(const DosTree&);
		DosTree& operator=(const DosTree&);

		void destruct(dostree_node n)
		{
			if (n==NULL) return;
			destruct(DOSNODE(n->left));
			destruct(DOSNODE(n->right));
			delete n;
		}

	public:

		dostree_node index(int index)
		{
			return lookup_node(get_root(),index);
		}

		/**
		 * dostree_insert
		 * insert a new key into the dos tree
		 */
		void insert(int key) 
		{
			dostree_node inserted_node = new_node(key, RED, NULL, NULL);

			if (get_root() == NULL) {
				set_root(inserted_node);
			}
			else {
				rbtree_node n = DOSNODE(get_root());
				while (1) {
					// incr 1 for each node on the path traversed from the root
					DOSNODE(n)->size+=1;
					if (key < DOSNODE(n)->key) {
						if (n->left == NULL) {
							n->left = inserted_node;
							break;
						} else {
							n = n->left;
						}
					} else {
						if (n->right == NULL) {
							n->right = inserted_node;
							break;
						} else {
							n = n->right;
						}
					}
				}
				inserted_node->parent = n;	
			}

			// fix red-black properties
			insert_case1(inserted_node);
		}

		/**
		 * delete the key in the red-black tree
		 */
		void delete_key(dostree_node n)
		{
			rbtree_node child;

			/* Copy key/value from predecessor and then delete it instead */
			if (n->left != NULL && n->right != NULL) {
				dostree_node pred = DOSNODE(maximum_node(n->left));
				DOSNODE(n)->key = DOSNODE(pred)->key;
				DOSNODE(n)->size = DOSNODE(pred)->size;
				n = pred;
			}

			// fix up size from pred
			fixup_size(n);

			assert(n->left == NULL || n->right == NULL);
			child = n->right == NULL ? n->left  : n->right;
			if (node_color(n) == BLACK) {
				n->color = node_color(child);
				delete_case1(n);
			}
			replace_node(n, child);
			// copy child value if exists
			if (child != NULL) {
				DOSNODE(n)->key = DOSNODE(child)->key;
				DOSNODE(n)->size = DOSNODE(child)->size;
			}
			if (n->parent == NULL && child != NULL)
				child->color = BLACK;

			delete (DOSNODE(n));
		}

		void print() {
			print_helper(get_root(), 0);
			puts("");
		}

		void print_helper(rbtree_node n, int indent) {
			int i;
			if (n == NULL) {
				fputs("<empty tree>", stdout);
				return;
			}
			if (n->right != NULL) {
				print_helper(n->right, indent + INDENT_STEP);
			}
			for(i=0; i<indent; i++)
				fputs(" ", stdout);
{'fraction_non_alphanumeric': 0.19213095921883974, 'fraction_numerical': 0.0031591039632395176, 'mean_word_length': 2.693001060445387, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 77, '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': '3554913', 'n_tokens_mistral': 3131, 'n_tokens_neox': 2522, 'n_words': 557}