Splay - An Array mainly used to "Flip"

Splay.cpp

//Splay Tree
//An array mainly used to do "Flip" action
//You can build Splay Tree by running 'SplayTree::Create(TreeSize)', and then you'll have an array with numbers '1 2 3 ... n'
//You can flip a block of numbers by running 'Tree->Flip(L,R)'. Notice, L and R are counted from 0.
//You can print all the numbers in Tree by running 'Tree->TryPrint()'. Also you can get the Nth number by running 'Tree->FindNth(pos)'
//This is an incomplete example.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;

typedef int SplayTreeData;
typedef vector<SplayTreeData> SplayTreeDataArray;
class SplayTree;
class SplayTreeNode;


SplayTreeData NullTreeData = -1;
SplayTreeNode *NullTreeNode;

class SplayTreeNode
{
public:
	int Size;
	SplayTreeNode *Left, *Right;
	SplayTreeNode *Parent;
	SplayTreeData Data;
	bool Reverse;

	SplayTreeNode()
	{
		Reverse = false;
		Left = Right = Parent = NullTreeNode;
		Data = 0;
		Size = 1;
	}
	void UpdateSize()
	{
		if (!this->isNullNode())this->Size = Left->Size + Right->Size + 1;
	}

	static SplayTreeNode *CreateNode()
	{
		SplayTreeNode *Node = new SplayTreeNode();
		return Node;
	}

	static SplayTreeNode *CreateNullNode()
	{
		SplayTreeNode *Node = new SplayTreeNode();
		Node = new SplayTreeNode();
		Node->Left = NullTreeNode;
		Node->Right = NullTreeNode;
		Node->Parent = NullTreeNode;
		Node->Data = NullTreeData;
		Node->Size = 0;
		return Node;
	}

	bool isNullNode()
	{
		return this->Data == NullTreeData;
	}

	void __SetReverseFlag()
	{
		if (!isNullNode())this->Reverse = !this->Reverse;
	}

	bool isLeft(SplayTreeNode *Node)
	{
		return (this->Left == Node);
	}

	void SetReverseFlag()
	{
		if (!this->isNullNode())
		{
			this->Reverse = !this->Reverse;
		}
	}

	void PushDown()
	{
		if (this->isNullNode())return;
		if (Reverse)
		{
			swap(this->Left, this->Right);
			this->Left->SetReverseFlag();
			this->Right->SetReverseFlag();
			Reverse = false;
		}
	}

	void Flip()
	{
		Reverse = true;
		PushDown();
	}
};

class SplayTree
{
public:
	SplayTreeNode *Root;
	vector<SplayTreeNode*> Nodes;
	static void SplayTreeInitNullNode()
	{
		NullTreeNode = new SplayTreeNode();
		NullTreeNode->Left = NullTreeNode;
		NullTreeNode->Right = NullTreeNode;
		NullTreeNode->Parent = NullTreeNode;
		NullTreeNode->Data = NullTreeData;
		NullTreeNode->Size = 0;
	}
	static void SplayTreeInit()
	{
		SplayTreeInitNullNode();
	}

	static SplayTree* CreateTree(int Size)
	{
		SplayTree *Tree = new SplayTree();
		int M = Size / 2;
		SplayTreeNode *RootNode = SplayTreeNode::CreateNode();
		RootNode->Data = (SplayTreeData)M;
		RootNode->Parent = NullTreeNode;
		Tree->PushNode(RootNode);
		Tree->SetRoot(RootNode);
		RootNode->Left = RootNode->Right = NullTreeNode;

		SplayTreeNode *__lstNode;
		__lstNode = RootNode;
		for (SplayTreeData i = M - 1; i >= 0; i--)
		{
			SplayTreeNode *__Node = SplayTreeNode::CreateNode();

			__Node->Data = i;
			__Node->Parent = __lstNode;
			__Node->Left = __Node->Right = NullTreeNode;
			__lstNode->Left = __Node;

			__lstNode = __Node;
			Tree->PushNode(__Node);
		}

		__lstNode = RootNode;
		for (SplayTreeData i = M + 1; i < Size; i++)
		{
			SplayTreeNode *__Node = SplayTreeNode::CreateNode();

			__Node->Data = i;
			__Node->Parent = __lstNode;
			__Node->Left = __Node->Right = NullTreeNode;
			__lstNode->Right = __Node;

			__lstNode = __Node;
			Tree->PushNode(__Node);
		}
		Tree->UpdateSize();
		return Tree;
	}

	SplayTree()
	{
		Nodes.clear();
	}

	void SetRoot(SplayTreeNode *Node)
	{
		Root = Node;
	}

	void PushNode(SplayTreeNode *Node)
	{
		Nodes.push_back(Node);
	}

	void TryPrint(SplayTreeNode *Node)
	{
		Node->PushDown();
		if (Node->isNullNode())return;
		TryPrint(Node->Left);
		//cout << Node->Data << " L" << Node->Left->Data << " R" << Node->Right->Data << " " << Node->Size << " ";
		cout << Node->Data << Node->Size << " ";
		TryPrint(Node->Right);
	}

	void __UpdateSize(SplayTreeNode *Node)
	{
		if (Node->isNullNode())return;
		__UpdateSize(Node->Left);
		__UpdateSize(Node->Right);
		Node->UpdateSize();
	}
	void UpdateSize()
	{
		__UpdateSize(Root);
	}

	void RotateL(SplayTreeNode *CurrentNode)
	{
		SplayTreeNode *Par = CurrentNode->Parent;
		SplayTreeNode *Y = CurrentNode;
		SplayTreeNode *X = Y->Left;
		SplayTreeNode *A = X->Left;
		SplayTreeNode *B = X->Right;
		SplayTreeNode *C = Y->Right;

		Y->PushDown();
		X->PushDown();
		C->PushDown();

		if (X->isNullNode() || Y->isNullNode())
		{
			cerr << "Rotate Failed: Found Null Node." << endl;
			return;
		}
		if (!Par->isNullNode())
		{
			if (Par->isLeft(Y))Par->Left = X;
			else Par->Right = X;
			X->Parent = Par;
		}
		else
		{
			X->Parent = NullTreeNode;
			this->SetRoot(X);
		}

		X->Right = Y; Y->Parent = X;
		Y->Left = B; B->Parent = Y;

		Y->UpdateSize();
		X->UpdateSize();
	}

	void RotateR(SplayTreeNode *CurrentNode)
	{
		SplayTreeNode *Par = CurrentNode->Parent;
		SplayTreeNode *X = CurrentNode;
		SplayTreeNode *Y = X->Right;
		SplayTreeNode *A = X->Left;
		SplayTreeNode *B = Y->Left;
		SplayTreeNode *C = Y->Right;

		X->PushDown();
		A->PushDown();
		Y->PushDown();

		if (X->isNullNode() || Y->isNullNode())
		{
			cerr << "Rotate Failed: Found Null Node." << endl;
			return;
		}
		if (!Par->isNullNode())
		{
			if (Par->isLeft(X))Par->Left = Y;
			else Par->Right = Y;
			Y->Parent = Par;
		}
		else
		{
			Y->Parent = NullTreeNode;
			this->SetRoot(Y);
		}


		Y->Left = X; X->Parent = Y;
		X->Right = B; B->Parent = X;

		X->UpdateSize();
		Y->UpdateSize();
		Par->UpdateSize();
	}
	void Splay(SplayTreeNode *Node, SplayTreeNode *Target)
	{
		SplayTreeNode *Current = Node;
		SplayTreeNode *CurrentRoot = Node->Parent;
		while (CurrentRoot != Target)
		{
			if (CurrentRoot->isLeft(Current))
				RotateL(CurrentRoot);
			else
				RotateR(CurrentRoot);
			CurrentRoot = Current->Parent;
		}
	}

	SplayTreeNode* FindNth(int n)
	//0Base
	{
		SplayTreeNode *CurrentNode = Root;
		CurrentNode->PushDown();
		int Current = CurrentNode->Left->Size;
		while (Current != n)
		{
			if (n < Current)
			{
				CurrentNode = CurrentNode->Left;
				CurrentNode->PushDown();
				Current = CurrentNode->Left->Size;
			}
			else
			{
				n -= Current + 1;
				CurrentNode = CurrentNode->Right;
				CurrentNode->PushDown();
				Current = CurrentNode->Left->Size;
			}
		}
		return CurrentNode;
	}

	void Filp(int L, int R)
	{
		SplayTreeNode *Node;
		SplayTreeNode *Current;
		if (L == 0 && (R + 1 == Nodes.size()))
		{
			Current = this->Root;
		}
		else if (L == 0)
		{
			Node = this->FindNth(R + 1);
			this->Splay(Node, NullTreeNode);
			Current = this->Root->Left;
		}
		else if (R + 1 == Nodes.size())
		{
			Node = this->FindNth(L - 1);
			this->Splay(Node, NullTreeNode);
			Current = this->Root->Right;
		}
		else
		{
			Node = this->FindNth(L - 1);
			this->Splay(Node, NullTreeNode);
			Node = this->FindNth(R + 1);
			this->Splay(Node, this->Root);
			Current = this->Root->Right->Left;
		}
		Current->Flip();
	}
};

int main()
{
	SplayTree::SplayTreeInit();
	SplayTree *Tree=SplayTree::CreateTree(9);

	Tree->Filp(0, 8);
	Tree->Filp(2, 7);
	//Tree->TryPrint(Tree->Root); cout << endl;
	for (int i = 0; i < 9; i++)cout << Tree->FindNth(i)->Data << endl;

	system("PAUSE");
	return 0;
}