#ifndef AUGMENTEDBALANCEDBINARYTREE_HEADER_INCLUDED
#define AUGMENTEDBALANCEDBINARYTREE_HEADER_INCLUDED

#include <stdint.h>
#include <set>

#pragma pack(1) // fuck you visual studio without this it will crash, to no fault of the code, but what appears to be a bug in VS
// wikipedia: Balance factors can be kept up-to-date by knowing the previous balance factors and the change in height –
// it is not necessary to know the absolute height. For holding the AVL balance information, two bits per node are sufficient.
std::set<uint64_t> niggerSet;
struct treeNode
{
	treeNode()
	{
		headAddress = 0;
		tailAddress = 0;
		height = 0;
		leftChild = 0;
		rightChild = 0;
		tailInstructionLength = 0;
	}

	~treeNode()
	{
		std::set<uint64_t>::iterator it = niggerSet.find(headAddress);
		if (it != niggerSet.end())
		{
			int asdfasdf = 324532452354;
		}

		niggerSet.insert(headAddress);
	}
	uint64_t headAddress;
	uint64_t tailAddress;

	treeNode* leftChild;
	treeNode* rightChild;

	uint16_t tailInstructionLength;

	unsigned char height;

};

/*
	modified avl instead of red-black because we want faster lookup.
	a node will store a range (eg. 7-15) and will operate like a normal avl tree (19-23) goes to the right of (7-15); as there will be no range overlaps ever.
	nodes will automatically merge together if they "hug", to use the tree for general purpose ranges just set the tailInstructionLength to 1 so 5-12 and 13-200 will hug
	while not overlapping. Pointers are meaningless here, for example when you go to delete a node, instead you delete a range because nodes will merge and be deleted
	automatically behind the scenes, so that node pointer you have in the outside world may be meaningless, stay safe.
*/
class rangedAVLTree
{
public:
	rangedAVLTree();
	~rangedAVLTree();

	// the node MAY be deleted, consider this function to insert the range into the tree, the internal tree may shift and merge nodes assume the pointer is trash after the call.
	// instead of merging nodes from inside, nodes will be flaged during insertion and then merging will take place outside to ensure tree balancing functions normally.
	void
	insertRange(treeNode* node);

	//  delete a range, just fill out the node and this will remove that range from the tree.
	void
	removeRange(treeNode* node);

	void
	deleteTree();

	void
	inOrder(treeNode* node, void(*func)(void*));

	void
	preOrder(treeNode* node, void(*func)(void*));

	void
	postOrder(treeNode* node, void(*func)(void*));

	void
	breadthFirst(treeNode* node, void(*func)(void*));

	uint32_t
	getTreeHeight();

	treeNode*
	isValueInRange(uint64_t value);

	treeNode* treeRoot;

	uint64_t numberOfItems;

private:
private:
private:

	unsigned char
	height(treeNode* node);

	int
	balanceFactor(treeNode* node);

	void
	fixHeight(treeNode* node);

	treeNode*
	rotateRight(treeNode* node);

	treeNode*
	rotateLeft(treeNode* node);

	treeNode*
	balance(treeNode* node);

	treeNode*
	findMin(treeNode* node);

	treeNode*
	removeMin(treeNode* node);

	// insert and remove return the root.
	treeNode*
	internalInsertRange(treeNode* root, treeNode* node);

	void
	internalRemoveRange(treeNode* root, treeNode* node, treeNode** mergedNodes);

	// this should be internal only because we dont know if nodes have been merged so hanging onto that tree pointer in the outside world and trying to remove it is dangerous.
	void
	remove(treeNode* node);

	treeNode*
	internalRemove(treeNode* root, treeNode* node);

	//void deleteNodes(treeNode* node);
};


/*
1
5
9
13
... space width from start of row to end (including the end)

left to begin of number 2 + 2 + 2.....

       5
     /   \
    3     6
   / \   / \
  2   7     8
 / \       / \
1   2     5   9
*/
#endif