// ToolsLib Project

/* CryptLib library for RusRoute firewall and other projects of
* Andrey A. Moiseenko and MaaSoftware (LLC, Russia)
* e-mail: support@maasoftware.ru, maa2002@mail.ru
* web: http://maasoftware.ru, http://maasoftware.com
* Author's full name: Andrey Alekseevitch Moiseenko
* (russian name: Моисеенко Андрей Алексеевич)
*/

// ToolsLib/rbtree.h

/* Copyright (C) 2002-2015 Andrey A. Moiseenko (support@maasoftware.ru)
* All rights reserved.
*
* This library contains cross-platform templates for working heap
* sutable for using them in sockets' timers.
* The library implementation written
* by Andrey A. Moiseenko (support@maasoftware.ru).
* This library and applications are
* FREE FOR COMMERCIAL AND NON-COMMERCIAL USE
* as long as the following conditions are adhered to.
*
* Copyright remains Andrey A. Moiseenko's, and as such any Copyright notices in
* the code are not to be removed. If this code is used in a product,
* Andrey A. Moiseenko should be given attribution as the author of the parts used.
* This can be in the form of a textual message at program startup or
* in documentation (online or textual) provided with the package.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by Andrey A. Moiseenko (support@maasoftware.ru)
*
* THIS SOFTWARE IS PROVIDED BY ANDREY A. MOISEENKO ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* The licence and distribution terms for any publically available version or
* derivative of this code cannot be changed. i.e. this code cannot simply be
* copied and put under another distribution licence
* [including the GNU Public Licence.]
*/

// Red-Black balanced tree
// Keys can be duplicated

// fixed algo from book
// Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн
// "Алгоритмы: построение и анализ. 3-е издание"
// and from 1st or second edition

template <class Key, class Data> class CMaaRBTree
{
protected:
class Node
{
public:
char color;
Node * p, * left, * right;
Key k;
Data d;

Node(const Key &_k, const Data &_d, int _c = 0)
: p(nullptr),
left(nullptr),
right(nullptr),
color(_c),
k(_k),
d(_d)
{
}
Key key()
{
return k;
}
Data & data()
{
return d;
}
const Key & c_key() const
{
return k;
}
const Data & c_data() const
{
return d;
}
ADD_UL_ALLOCATOR(Node)
};
public:
typedef Node * Handle;
static Key key(Handle x)
{
return x->key();
}
static Data & data(Handle x)
{
return x->data();
}
static const Key & c_key(Handle x)
{
return x->c_key();
}
static const Data & c_data(Handle x)
{
return x->c_data();
}
Key k(Handle x)
{
return x->key();
}
Data & d(Handle x)
{
return x->data();
}
/*
Handle GetHandle(const Key &k) const
{
return FindNode(k);
}
*/

protected:
size_t N;
Node * _nil, * root;
bool m_bMulti;

public:
CMaaRBTree(bool Multi = true)
: m_bMulti(Multi)
{
N = 0;
_nil = (Node *) TL_NEW char[sizeof(Node)];
if (!_nil)
{
throw "CMaaRBTree(): allocation error";
}
memset(_nil, 0, sizeof(Node));
_nil->color = 'B';
root = _nil;
}
void SimpleFree(Node * x)
{
if (x != _nil)
{
if (x->left != _nil)
{
SimpleFree(x->left);
}
if (x->right != _nil)
{
SimpleFree(x->right);
}
delete x;
}
}
~CMaaRBTree()
{
SimpleFree(root);
delete [] (char *)_nil;
}
void RemoveAll()
{
SimpleFree(root);
root = _nil;
N = 0;
_nil->color = 'B';
}
size_t GetCount() const
{
return N;
}
protected:
//
// | <--LeftRotate(x)-- |
// Y --RightRotate(y)--> X
// / \ / \ .
// X g a Y
// / \ / \ .
// a b b g
//
void LeftRotate(Node * x)
{
if (x->right == _nil)
{
throw "CMaaRBTree::LeftRotate(): x->right == _nil";
}
// x->right != nullptr
Node * y = x->right;
x->right = y->left;
if (y->left != _nil)
{
y->left->p = x;
}
y->p = x->p;
if (x->p == _nil)
{
root = y;
}
else if (x == x->p->left)
{
x->p->left = y;
}
else
{
x->p->right = y;
}
y->left = x;
x->p = y;
}
void RightRotate(Node * y)
{
if (y->left == _nil)
{
throw "CMaaRBTree::RightRotate(): y->left == _nil";
}
// y->left != nullptr
Node * x = y->left;
y->left = x->right;
if (x->right != _nil)
{
x->right->p = y;
}
x->p = y->p;
if (y->p == _nil)
{
root = x;
}
else if (y == y->p->right)
{
y->p->right = x;
}
else
{
y->p->left = x;
}
x->right = y;
y->p = x;
}
public:
// 0 - ok
int Add(const Key& k, const Data& d)
{
return RBInsert(k, d, m_bMulti) ? 0 : 1;
}
// Handle != nullptr - ok
Handle AddNode(const Key& k, const Data& d)
{
return RBInsert(k, d, m_bMulti);
}
// Handle != nullptr - ok
Node* Insert(const Key& k, const Data& d)
{
return RBInsert(k, d, m_bMulti);
}

// specific multi
// 0 - ok
int Add(const Key& k, const Data& d, bool bMulti)
{
return RBInsert(k, d, bMulti) ? 0 : 1;
}
// Handle != nullptr - ok
Handle AddNode(const Key& k, const Data& d, bool bMulti)
{
return RBInsert(k, d, bMulti);
}
// Handle != nullptr - ok
Node * Insert(const Key &k, const Data &d, bool bMulti)
{
return RBInsert(k, d, bMulti);
}

int GetHeightSlow(Node* x = nullptr) const
{
if (!x)
{
x = root;
}
if (x == _nil)
{
return 0;
}
int l = GetHeightSlow(x->left);
int r = GetHeightSlow(x->right);
return 1 + (l > r ? l : r);
}
// RB-Insert(T,z)
Node * RBInsert(const Key &k, const Data &d, bool bMulti)
{
/*
if (!bMulti)
{
Handle r = FindNode(k);
if (r)
{
return nullptr;
}
}
*/
Node * y = _nil;
Node * x = root;
if (!bMulti)
{
while (x != _nil)
{
y = x;
if (k < x->k)
{
x = x->left;
}
else if (x->k == k)
{
return nullptr;
}
else
{
x = x->right;
}
}
}
else
{
while (x != _nil)
{
y = x;
if (k < x->k)
{
x = x->left;
}
else
{
x = x->right;
}
}
}
//Node * z = TL_NEW Node(k, d, 'R');
Node* z = new Node(k, d, 'R');
//z->p = z->left = z->right =_nil;
z->p = y;
if (y == _nil)
{
root = z;
}
else if (z->k < y->k)
{
y->left = z;
}
else
{
y->right = z;
}
z->left = _nil;
z->right = _nil;
z->color = 'R';
N++;
//Print();
RBInsertFixup(z);
return z;
}
protected:
void RBInsertFixup(Node *z)
{
while(z->p->color == 'R')
{
if (z->p == root)
{
//throw "CMaaRBTree::RBInsertFixup(): (z->p == root)";
break;
}
if (z->p == z->p->p->left)
{
Node * y = z->p->p->right;
if (y->color == 'R') // wiki: if (y != nullptr && y->color == 'R')
{
z->p->color = 'B';
y->color = 'B';
z->p->p->color = 'R';
z = z->p->p;
//__utf8_printf(">1<\n");
//Print();
continue;
}
if (z == z->p->right) // wiki: if (z == z->p->right && z->p == z->p->p->left)
{
z = z->p;
LeftRotate(z);
//__utf8_printf(">2<\n");
//Print();
}
z->p->color = 'B';
z->p->p->color = 'R';
// wiki: if (z == z->p->left && z->p == z->p->p->left)
RightRotate(z->p->p);
// wiki: else
// wiki: LeftRotate(z->p->p);

//__utf8_printf(">3<\n");
//Print();
//break;
}
else //if (z->p == z->p->p->right)
{
Node * y = z->p->p->left;
if (y->color == 'R')
{
z->p->color = 'B';
y->color = 'B';
z->p->p->color = 'R';
z = z->p->p;
//__utf8_printf(">1<\n");
//Print();
continue;
}
if (y->color == 'B' && z == z->p->left)
{
z = z->p;
RightRotate(z);
//__utf8_printf(">2<\n");
//Print();
}
z->p->color = 'B';
z->p->p->color = 'R';
LeftRotate(z->p->p);
//__utf8_printf(">3<\n");
//Print();
//break;
}
//else
//{
//throw "CMaaRBTree::RBInsertFixup(): (z->p != z->p->p->left) && (z->p != z->p->p->right)";
//}
break;
}
root->color = 'B';
}
protected:
Node * grandparent(Node *n)
{
if (n != _nil && n->p != _nil)
{
return n->p->p;
}
else
{
return _nil;
}
}
Node * uncle(Node *n)
{
Node * g = grandparent(n);
if (g == _nil)
{
return _nil; // No grandparent means no uncle
}
if (n->p == g->left)
{
return g->right;
}
else
{
return g->left;
}
}
void rotate_left(Node *n)
{
Node *pivot = n->right;

pivot->p = n->p; // при этом, возможно, pivot становится корнем дерева
if (n->p != _nil)
{
if (n->p->left == n)
{
n->p->left = pivot;
}
else
{
n->p->right = pivot;
}
}
else
{
root = pivot;
}

n->right = pivot->left;
if (pivot->left != _nil)
{
pivot->left->p = n;
}

n->p = pivot;
pivot->left = n;
}

void rotate_right(Node *n)
{
Node *pivot = n->left;

pivot->p = n->p; // при этом, возможно, pivot становится корнем дерева
if (n->p != _nil)
{
if (n->p->left == n)
{
n->p->left = pivot;
}
else
{
n->p->right = pivot;
}
}
else
{
root = pivot;
}

n->left = pivot->right;
if (pivot->right != _nil)
{
pivot->right->p = n;
}
n->p = pivot;
pivot->right = n;
}
void insert_case1(Node *n)
{
if (n->p == _nil)
{
n->color = 'B';
}
else
{
insert_case2(n);
}
}
void insert_case2(Node *n)
{
if (n->p->color == 'B')
{
return; // Tree is still valid
}
else
{
insert_case3(n);
}
}
void insert_case3(Node *n)
{
Node *u = uncle(n), * g;

if (u != _nil && u->color == 'R')
{
// && (n->parent->color == RED) Второе условие проверяется в insert_case2, то есть родитель уже является красным.
n->p->color = 'B';
u->color = 'B';
g = grandparent(n);
g->color = 'R';
insert_case1(g);
}
else
{
insert_case4(n);
}
}
void insert_case4(Node *n)
{
Node *g = grandparent(n);

if (n == n->p->right && n->p == g->left)
{
rotate_left(n->p);

/*
* rotate_left может быть выполнен следующим образом, учитывая что уже есть *g = grandparent(n)
*
* struct node *saved_p=g->left, *saved_left_n=n->left;
* g->left=n;
* n->left=saved_p;
* saved_p->right=saved_left_n;
*
*/

n = n->left;
}
else if (n == n->p->left && n->p == g->right)
{
rotate_right(n->p);

/*
* rotate_right может быть выполнен следующим образом, учитывая что уже есть *g = grandparent(n)
*
* struct node *saved_p=g->right, *saved_right_n=n->right;
* g->right=n;
* n->right=saved_p;
* saved_p->left=saved_right_n;
*
*/

n = n->right;
}
insert_case5(n);
}

void insert_case5(Node *n)
{
Node *g = grandparent(n);

n->p->color = 'B';
g->color = 'R';
if (n == n->p->left && n->p == g->left)
{
rotate_right(g);
}
else
{
// (n == n->p->right) && (n->p == g->right)
rotate_left(g);
}
}

// ins_fixup() is iterative version of insert_case1() - insert_case5(), written by Moiseenko A.A.
void ins_fixup(Node *n)
{
while (1)
{
if (n->p == _nil)
{
n->color = 'B';
break;
}
if (n->p->color == 'B')
{
break; // Tree is still valid
}

Node *u = uncle(n), * g;

if (u != _nil && u->color == 'R')
{
// && (n->parent->color == RED) Второе условие проверяется в insert_case2, то есть родитель уже является красным.
n->p->color = 'B';
u->color = 'B';
g = grandparent(n);
g->color = 'R';
n = g;
continue;
}
g = grandparent(n);

if (n == n->p->right && n->p == g->left)
{
rotate_left(n->p);

/*
* rotate_left может быть выполнен следующим образом, учитывая что уже есть *g = grandparent(n)
*
* struct node *saved_p=g->left, *saved_left_n=n->left;
* g->left=n;
* n->left=saved_p;
* saved_p->right=saved_left_n;
*
*/

n = n->left;
}
else if (n == n->p->left && n->p == g->right)
{
rotate_right(n->p);

/*
* rotate_right может быть выполнен следующим образом, учитывая что уже есть *g = grandparent(n)
*
* struct node *saved_p=g->right, *saved_right_n=n->right;
* g->right=n;
* n->right=saved_p;
* saved_p->left=saved_right_n;
*
*/

n = n->right;
}
g = grandparent(n);

n->p->color = 'B';
g->color = 'R';
if (n == n->p->left && n->p == g->left)
{
rotate_right(g);
}
else
{
// (n == n->p->right) && (n->p == g->right)
rotate_left(g);
}
break;
}
}

public:
Node * RBInsertWiki(const Key &k, const Data &d, bool bMulti)
{
/*
if (!bMulti)
{
Handle r = FindNode(k);
if (r)
{
return nullptr;
}
}
*/
Node * y = _nil;
Node * x = root;
if (!bMulti)
{
while (x != _nil)
{
y = x;
if (k < x->k)
{
x = x->left;
}
else if (x->k == k)
{
return nullptr;
}
else
{
x = x->right;
}
}
}
else
{
while (x != _nil)
{
y = x;
if (k < x->k)
{
x = x->left;
}
else
{
x = x->right;
}
}
}
//Node * z = TL_NEW Node(k, d, 'R');
Node* z = new Node(k, d, 'R');
//z->p = z->left = z->right =_nil;
z->p = y;
if (y == _nil)
{
root = z;
}
else if (z->k < y->k)
{
y->left = z;
}
else
{
y->right = z;
}
z->left = _nil;
z->right = _nil;
z->color = 'R';
N++;
//RBInsertFixup(z);
//insert_case1(z);
ins_fixup(z);
return z;
}

protected:
void RBTransplant(Node * u, Node * v)
{
if (u->p == _nil)
{
root = v;
}
else if (u == u->p->left)
{
u->p->left = v;
}
else
{
u->p->right = v;
}
v->p = u->p;
}
public:
Node * begin() const
{
return root != _nil ? TreeMinimum(root) : _nil;
}
// next: p = rb.TreeSuccessor(p);
// for (CMaaRBTree<int, int>::Handle p = r.begin(); p != r.end(); p = r.TreeSuccessor(p))
Node * end() const
{
return _nil;
}
Node * rbegin() const
{
return root != _nil ? TreeMaximum(root) : _nil;
}
// prev: p = rb.TreePredecessor(p);
// for (CMaaRBTree<int, int>::Handle p = r.begin(); p != r.end(); p = r.TreePredecessor(p))
Node * rend() const
{
return _nil;
}
Node * TreeMinimum(Node * x) const
{
while(x->left != _nil)
{
x = x->left;
}
return x;
}
Node * TreeMaximum(Node * x) const
{
while(x->right != _nil)
{
x = x->right;
}
return x;
}
Node * TreeSuccessor(Node * x) const
{
if (x->right != _nil)
{
return TreeMinimum(x->right);
}
Node * y = x->p;
while(y != _nil && x == y->right)
{
x = y;
y = y->p;
}
return y;
}
Node * TreePredecessor(Node * x) const
{
if (x->left != _nil)
{
return TreeMaximum(x->left);
}
Node * y = x->p;
while(y != _nil && x == y->left)
{
x = y;
y = y->p;
}
return y;
}
Node * RecursiveTreeSearch(Node * x, const Key &k) const
{
if (x == _nil || k == x->k)
{
return x;
}
if (k < x->k)
{
return TreeSearch(x->left, k);
}
else
{
return TreeSearch(x->right, k);
}
}
Node * IteractiveTreeSearch(Node * x, const Key &k) const
{
while(x != _nil && k != x->k)
{
if (k < x->k)
{
x = x->left;
}
else
{
x = x->right;
}
}
return x;
}
Node * TreeSearchLQ(const Key &k, bool bRetEq = true, Node * x = nullptr) const
{
x = x ? x : root;
Node * y;
if (bRetEq)
{
y = IteractiveTreeSearch(x, k);
if (y != _nil)
{
return y;
}
}
y = _nil;

while(x != _nil)
{
if (k == x->k)
{
x = x->left;
}
else if (k < x->k)
{
x = x->left;
}
else
{
y = x;
x = x->right;
}
}
return y;
}
Node * TreeSearchGQ(const Key &k, bool bRetEq = true, Node * x = nullptr) const
{
x = x ? x : root;
Node * y;
if (bRetEq)
{
y = IteractiveTreeSearch(x, k);
if (y != _nil)
{
return y;
}
}
y = _nil;

while(x != _nil)
{
if (k == x->k)
{
x = x->right;
}
else if (k < x->k)
{
y = x;
x = x->left;
}
else
{
x = x->right;
}
}
return y;
}
/*
Node * TreeSearchLQ1(const Key &k, bool bRetEq = true)
{
Node * x = root, * y = _nil;

while(x != _nil)
{
if (k == x->k)
{
if (bRetEq)
{
return x;
}
while(x != _nil && x->k == k)
{
x = TreePredecessor(x);
}
return x;
}
if (k < x->k)
{
x = x->left;
}
else
{
y = x;
x = x->right;
}
}
return y;
}
Node * TreeSearchGQ1(const Key &k, bool bRetEq = true)
{
Node * x = root, * y = _nil;

while(x != _nil)
{
if (k == x->k)
{
if (bRetEq)
{
return x;
}
while(x != _nil && x->k == k)
{
x = TreeSuccessor(x);
}
return x;
}
if (k < x->k)
{
y = x;
x = x->left;
}
else
{
x = x->right;
}
}
return y;
}
*/
int Find(const Key &k, Data *d = nullptr)
{
Node * x = IteractiveTreeSearch(root, k);
if (x != _nil)
{
if (d)
{
*d = x->d;
}
return 0;
}
return 1;
}
Handle FindNode(const Key &k) const
{
Node * x = IteractiveTreeSearch(root, k);
return x != _nil ? x : nullptr;
}
int Remove(const Key &k, Data *d = nullptr)
{
Node * x = IteractiveTreeSearch(root, k);
if (x != _nil)
{
if (d)
{
*d = x->d;
}
RBDelete(x);
return 0;
}
return 1;
}
int FindMin(Key *k = nullptr, Data *d = nullptr) const
{
Node * x = TreeMinimum(root);
if (x != _nil)
{
if (k)
{
*k = x->k;
}
if (d)
{
*d = x->d;
}
return 0;
}
return 1;
}
int FindMax(Key *k = nullptr, Data *d = nullptr) const
{
Node * x = TreeMaximum(root);
if (x != _nil)
{
if (k)
{
*k = x->k;
}
if (d)
{
*d = x->d;
}
return 0;
}
return 1;
}
int FindSucc(const Key &_k, Key *k = nullptr, Data *d = nullptr) const
{
Node * x = IteractiveTreeSearch(root, _k);
if (x != _nil)
{
x = TreeSuccessor(x);
if (x != _nil)
{
if (k)
{
*k = x->k;
}
if (d)
{
*d = x->d;
}
return 0;
}
return 2;
}
return 1;
}
int FindPred(const Key &_k, Key *k = nullptr, Data *d = nullptr) const
{
Node * x = IteractiveTreeSearch(root, _k);
if (x != _nil)
{
x = TreePredecessor(x);
if (x != _nil)
{
if (k)
{
*k = x->k;
}
if (d)
{
*d = x->d;
}
return 0;
}
return 2;
}
return 1;
}
Handle FindSucc(Handle x) const
{
if (x && x != _nil)
{
x = TreeSuccessor(x);
return x != _nil ? x : nullptr;
}
return nullptr;
}
Handle FindPred(Handle x) const
{
if (x && x != _nil)
{
x = TreePredecessor(x);
return x != _nil ? x : nullptr;
}
return nullptr;
}
// 0 - ok
int FindLQ(const Key &_k, bool bRetEq, Key *k = nullptr, Data *d = nullptr) const
{
Node * x = TreeSearchLQ(_k, bRetEq, root);
if (x != _nil)
{
if (k)
{
*k = x->k;
}
if (d)
{
*d = x->d;
}
return 0;
}
return 1;
}
// 0 - ok
int FindGQ(const Key &_k, bool bRetEq, Key *k = nullptr, Data *d = nullptr) const
{
Node * x = TreeSearchGQ(_k, bRetEq, root);
if (x != _nil)
{
if (k)
{
*k = x->k;
}
if (d)
{
*d = x->d;
}
return 0;
}
return 1;
}
// 0 - ok
int FindLQ(const Key &_k, Key *k = nullptr, Data *d = nullptr) const
{
return FindLQ(_k, true, k, d);
}
// 0 - ok
int FindGQ(const Key &_k, Key *k = nullptr, Data *d = nullptr) const
{
return FindGQ(_k, true, k, d);
}
// 0 - ok
int FindLnQ(const Key &_k, Key *k = nullptr, Data *d = nullptr) const
{
return FindLQ(_k, false, k, d);
}
// 0 - ok
int FindGnQ(const Key &_k, Key *k = nullptr, Data *d = nullptr) const
{
return FindGQ(_k, false, k, d);
}
protected:
public:
void RBDelete(Node * z)
{
//RBDelete1(z);
RBDeleteWiki(z);
}
// 3rd edition
void RBDelete3(Node * z)
{
Node * y = z;
Node * x;
char y_original_color = y->color;
if (z->left == _nil)
{
x = z->right;
RBTransplant(z, z->right);
/*
if (y_original_color == 'B' && x == _nil && z->p != _nil && z->p->p != _nil)
{
LeftRotate(z->p->p);
root->color = 'B';
}
*/
}
else if (z->right == _nil)
{
x = z->left;
RBTransplant(z, z->left);
/*
if (y_original_color == 'B' && x == _nil && z->p != _nil && z->p->p != _nil)
{
RightRotate(z->p->p);
root->color = 'B';
}
*/
}
else
{
y = TreeMinimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->p == z)
{
x->p = y;
}
else
{
RBTransplant(y, y->right);
y->right = z->right;
y->right->p = y;
}
RBTransplant(z, y);
y->left = z->left;
y->left->p = y;
y->color = z->color;
}
if (y_original_color == 'B' && x != _nil)
{
RBDeleteFixup(x);
}
N--;
delete z;
}
// 1st edition
void RBDelete1(Node * z)
{
Node * y;
if (z->left == _nil || z->right == _nil)
{
y = z;
}
else
{
y = TreeSuccessor(z);
}
Node * x;
if (y->left != _nil)
{
x = y->left;
}
else
{
x = y->right;
}
x->p = y->p;
if (y->p == _nil)
{
root = x;
}
else if (y == y->p->left)
{
y->p->left = x;
}
else
{
y->p->right = x;
}
char y_orig_color = y->color;
if (y != z)
{
y->p = z->p;
y->left = z->left;
y->right = z->right;
y->color = z->color;
y->left->p = y;
y->right->p = y;
if (z == root)
{
root = y;
root->color = 'B';
}
else if (z->p->left == z)
{
z->p->left = y;
}
else
{
z->p->right = y;
}
}
if (y_orig_color == 'B' && x != _nil)
{
//__utf8_printf("fixup...\n");
RBDeleteFixup(x);
}
N--;
delete z;
}
// Wiki 26-27.12.2017
// https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
Node * Sibling(Node * n)
{
if (n == n->p->left)
{
return n->p->right;
}
else
{
return n->p->left;
}
}
void RBDeleteWiki(Node * z)
{
if (z->left != _nil && z->right != _nil)
{
Node * y = TreeSuccessor(z);
//swap(*y, *z);
CMaaSwap(y->p, z->p);
if (y->p == _nil)
{
root = y;
}
else
{
if (y->p->left == z)
{
y->p->left = y;
}
else
{
y->p->right = y;
}
}
if (z->p->left == y)
{
z->p->left = z;
}
else
{
z->p->right = z;
}
CMaaSwap(y->left, z->left);
CMaaSwap(y->right, z->right);
CMaaSwap(y->color, z->color);
y->left->p = y;
y->right->p = y;
z->left->p = z;
z->right->p = z;
//root->color = 'B';
}
if (z->left != _nil && z->right != _nil)
{
throw "if (z->left != _nil && z->right != _nil)";
}
//rm0(z); // recursive fixup
rm_fixup(z); // iterative fixup
N--;
delete z;
}
protected:
// rm0() - rm6() - wiki source
void rm0(Node *n)
{
if (n->left != _nil && n->right != _nil)
{
throw "if (n->left != _nil && n->right != _nil)";
}
Node * c = n->left != _nil ? n->left : n->right;
//replace_node(n, c); // n <== c
c->p = n->p;
if (c->p == _nil)
{
root = c;
}
else
{
if (c->p->left == n)
{
c->p->left = c;
}
else
{
c->p->right = c;
}
}
n->left = n->right = n->p = _nil;
if (n->color == 'B')
{
if (c->color == 'R')
{
c->color = 'B';
}
else
{
rm1(c);
}
}
// delete n;
}
void rm1(Node * n)
{
if (n->p != _nil)
{
rm2(n);
}
}
void rm2(Node * n)
{
Node * s = Sibling(n);
if (s->color == 'R')
{
n->p->color = 'R';
s->color = 'B';
if (n == n->p->left)
{
LeftRotate(n->p);
}
else
{
RightRotate(n->p);
}
}
rm3(n);
}
void rm3(Node * n)
{
Node *s = Sibling(n);

if (n->p->color == 'B' && s->color == 'B' &&
s->left->color == 'B' && s->right->color == 'B')
{
s->color = 'R';
rm1(n->p);
}
else
{
rm4(n);
}
}
void rm4(Node *n)
{
Node *s = Sibling(n);

if (n->p->color == 'R' && s->color == 'B' &&
s->left->color == 'B' && s->right->color == 'B')
{
s->color = 'R';
n->p->color = 'B';
}
else
{
rm5(n);
}
}
void rm5(Node *n)
{
Node *s = Sibling(n);

if (s->color == 'B')
{
/* this if statement is trivial,
due to case 2 (even though case 2 changed the sibling to a sibling's child,
the sibling's child can't be red, since no red parent can have a red child). */
/* the following statements just force the red to be on the left of the left of the parent,
or right of the right, so case six will rotate correctly. */
if (n == n->p->left && s->right->color == 'B' && s->left->color == 'R')
{
/* this last test is trivial too due to cases 2-4. */
s->color = 'R';
s->left->color = 'B';
RightRotate(s);
}
else if (n == n->p->right && s->left->color == 'B' && s->right->color == 'R')
{
/* this last test is trivial too due to cases 2-4. */
s->color = 'R';
s->right->color = 'B';
LeftRotate(s);
}
}
rm6(n);
}
void rm6(Node *n)
{
Node *s = Sibling(n);

s->color = n->p->color;
n->p->color = 'B';

if (n == n->p->left)
{
s->right->color = 'B';
LeftRotate(n->p);
}
else
{
s->left->color = 'B';
RightRotate(n->p);
}
}

// rm_fixup() is iterative version of rm0() - rm6(), written by Moiseenko A.A.
void rm_fixup(Node *n)
{
if (n->left != _nil && n->right != _nil) // assert
{
throw "if (n->left != _nil && n->right != _nil)";
}
Node * c = n->left != _nil ? n->left : n->right;
//replace_node(n, c); // n <== c
c->p = n->p;
if (c->p == _nil)
{
root = c;
}
else
{
if (c->p->left == n)
{
c->p->left = c;
}
else
{
c->p->right = c;
}
}
n->left = n->right = n->p = _nil;
if (n->color == 'B')
{
if (c->color == 'R')
{
c->color = 'B';
}
else
{
//rm1(c);
n = c;
while(n->p != _nil)
{
//rm2(n);

Node * s = Sibling(n);
if (s->color == 'R')
{
n->p->color = 'R';
s->color = 'B';
if (n == n->p->left)
{
LeftRotate(n->p);
}
else
{
RightRotate(n->p);
}
}
//rm3(n);
s = Sibling(n);

if (n->p->color == 'B' && s->color == 'B' && s->left->color == 'B' && s->right->color == 'B')
{
s->color = 'R';
//rm1(n->p);
n = n->p;
continue;
}
//rm4(n);
//s = Sibling(n);

if (n->p->color == 'R' && s->color == 'B' && s->left->color == 'B' && s->right->color == 'B')
{
s->color = 'R';
n->p->color = 'B';
}
else
{
//rm5(n);
//Node *s = Sibling(n);

if (s->color == 'B')
{
/* this if statement is trivial,
due to case 2 (even though case 2 changed the sibling to a sibling's child,
the sibling's child can't be red, since no red parent can have a red child). */
/* the following statements just force the red to be on the left of the left of the parent,
or right of the right, so case six will rotate correctly. */
if (n == n->p->left && s->right->color == 'B' && s->left->color == 'R')
{
/* this last test is trivial too due to cases 2-4. */
s->color = 'R';
s->left->color = 'B';
RightRotate(s);
}
else if (n == n->p->right && s->left->color == 'B' && s->right->color == 'R')
{
/* this last test is trivial too due to cases 2-4. */
s->color = 'R';
s->right->color = 'B';
LeftRotate(s);
}
}
//rm6(n);
s = Sibling(n);

s->color = n->p->color;
n->p->color = 'B';

if (n == n->p->left)
{
s->right->color = 'B';
LeftRotate(n->p);
}
else
{
s->left->color = 'B';
RightRotate(n->p);
}
}
break;
}
}
}
// delete orig n in called fn;
}
void RBDeleteFixup(Node * x)
{
while(x != root && x->color == 'B')
{
if (x == x->p->left)
{
Node * w = x->p->right;
if (w->color == 'R')
{
w->color = 'B'; // 1
x->p->color = 'R'; // 1
LeftRotate(x->p); // 1
w = x->p->right; // 1
}
if (w == _nil)
{
break; // wiki: none
}
// wiki: if (x->p->color == 'B' && w->color == 'B' && w->left->color == 'B' && w->right->color == 'B')
if (w->left->color == 'B' && w->right->color == 'B')
{
w->color = 'R'; // 2
x = x->p; // 2
}
else
{
// далее несоответствие
if (w->right->color == 'B')
{
w->left->color = 'B'; // n // 3
// nw.color = 'R'
w->color = 'R'; // 3
RightRotate(w); // 3
w = x->p->right; // 3
}
w->color = x->p->color; // 4
x->p->color = 'B'; // 4
w->right->color = 'B'; // 4
LeftRotate(x->p); // 4
x = root; // 4
}
}
else if (x == x->p->right)
{
Node * w = x->p->left;
if (w->color == 'R')
{
w->color = 'B'; // 1
x->p->color = 'R'; // 1
RightRotate(x->p); // 1
w = x->p->left; // 1
}
if (w == _nil)
{
break;
}
if (w->right->color == 'B' && w->left->color == 'B')
{
w->color = 'R'; // 2
x = x->p; // 2
}
else
{
if (w->left->color == 'B')
{
w->right->color = 'B'; // n // 3
// nw.color = 'R'
w->color = 'R'; // 3
LeftRotate(w); // 3
w = x->p->left; // 3
}
w->color = x->p->color; // 4
x->p->color = 'B'; // 4
w->left->color = 'B'; // 4
RightRotate(x->p); // 4
x = root; // 4
}
}
}
x->color = 'B';
}
public:
void Swap(CMaaRBTree<Key, Data> &That)
{
CMaaSwap(N, That.N);
CMaaSwap(_nil, That._nil);
CMaaSwap(root, That.root);
CMaaSwap(m_bMulti, That.m_bMulti);
}
CMaaString Node2Text(Node* x);
//{
// return CMaaString::sFormat("%d%c", x->k, (char)x->color);
//}
void Print(Node * x = nullptr, int w = 79, int ll = 10)
{
x = x ? x : root;
for (int l = 0; l < ll; l++)
{
bool e = false;
CMaaString str = Print(x, w, l, &e);
if (e)
{
break;
}
__utf8_printf("%S\n", &str);
}
}
CMaaString Print(Node * x, int w = 79, int l = 0, bool *e = nullptr)
{
if (e)
{
*e = false;
}
if (x == _nil)
{
CMaaString sp(nullptr, w);
sp.Fill(' ');
if (e)
{
*e = true;
}
return sp;
}
if (l == 0)
{
CMaaString Ret = Node2Text(x);
//Ret.Format("%d%c", x->k, (char)x->color);
int w2 = w - Ret.Length();
if (w2 < 2)
{
w2 = 2;
}
int w1 = w2 / 2;
w2 -= w1;
CMaaString sp1(nullptr, w1), sp2(nullptr, w2);
sp1.Fill(' ');
sp2.Fill(' ');
return sp1 + Ret + sp2;
}
if (x->left != _nil && x->left->p != x)
{
static char err[512];
sprintf(err, "chk: %d->left error", x->k);
throw err;
}
if (x->right != _nil && x->right->p != x)
{
static char err[512];
sprintf(err, "chk: %d->right error", x->k);
throw err;
}
bool ee[2];
CMaaString Ret =
Print(x->left, w / 2, l - 1, &ee[0]) +
Print(x->right, w - w / 2, l - 1, &ee[1]);
if (e)
{
*e = ee[0] && ee[1];
}
return Ret;
}
};

//template<> CMaaFixedAllocator<CMaaRBTree<int, int>::Node> * CMaaRBTree<int, int>::Node::s_pAllocator = nullptr;
//opt:
//template<> CMaaString CMaaRBTree<int, int>::Node2Text(CMaaRBTree<int, int>::Node* x)
//{
// return CMaaString::sFormat("%d%c", x->k, (char)x->color);
//}

#if 0
template<> CMaaFixedAllocator<CMaaRBTree<int, int>::Node> * CMaaRBTree<int, int>::Node::s_pAllocator = nullptr;
int gii = 0;
int test2()
{
try
{
for (int c = 0; c < 1; c++)
{
//__utf8_printf("%79s\rc=%d ", "", c);
__utf8_printf("\rc=%d ", c);
const int N = 10000;
const int VMax = 2 * N - N + N / 2;
const int Dups = 1000;
CMaaPtr<int> x(N);
CMaaUnivHash<int, int> h;
int i, j;
__utf8_printf("gen ");
for (i = 0; i < N; i++)
{
while(1)
{
unsigned r = -1;
GetRnd(&r, sizeof(r));
//x[i] = rand() % VMax;
x[i] = i;//r % VMax;
//if (!h.Add(x[i], i))
{
break;
}
}
}
__utf8_printf("shuff ");
for (i = 0; i < N; i++)
{
unsigned r = 0;
GetRnd(&r, sizeof(r));
r %= N;
int tmp = x[i];
x[i] = x[(int)r];
x[(int)r] = tmp;
}
CMaaRBTree<int, int> t;
__utf8_printf("ins ");
for (j = 0; j < Dups; j++)
for (i = 0; i < N; i++)
{
if (i % 1000 == 0)
{
//__utf8_printf("\ri[%d]=%d:", i, x[i]);
}
/*
if (i >= 4)
{
gii++;
}
*/
t.Insert(x[i],i);

if (i % 10 == 0 && i > 0 && false)
{
int xx = t.Remove(x[i - 10]);
x[i - 10] = -1;
//__utf8_printf("\ri[%d]=%d:", i, x[i]);
}
//t.Print();
//getch();
}

__utf8_printf("LQ ");

for (i = -1; i <= N; i++)
{
/*if (x[i] == -1)
{
continue;
}*/
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int k = -1, d = -1, r = -1;
if ((r = t.FindLQ(i, &k, &d)) || k != i)
{
if (i == -1 && r == 1)
{
}
else if (i == N && r == 0 && k == N - 1)
{
}
else
{
__utf8_printf("fLQ[%d]:%d %d ", i, r, k);
}
//__utf8_printf("-err\n");
}
}

__utf8_printf("GQ ");

for (i = -1; i <= N; i++)
{
/*if (x[i] == -1)
{
continue;
}*/
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int k = -1, d = -1, r = -1;
if ((r = t.FindGQ(i, &k, &d)) || k != i)
{
if (i == N && r == 1)
{
}
else if (i == -1 && r == 0 && k == 0)
{
}
else
{
__utf8_printf("fGQ[%d]:%d %d ", i, r, k);
}
}
}

__utf8_printf("LnQ ");

for (i = -1; i <= N + 1; i++)
{
/*if (x[i] == -1)
{
continue;
}*/
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int k = -1, d = -1, r = -1;
if ((r = t.FindLnQ(i, &k, &d)) || k != i - 1)
{
if ((i == -1 || i == 0) && r == 1)
{
}
else if (i == N + 1 && r == 0 && k == N - 1)
{
}
else
{
__utf8_printf("fLnQ[%d]:%d %d ", i, r, k);
}
}
}

__utf8_printf("GnQ ");

for (i = -2; i <= N; i++)
{
/*if (x[i] == -1)
{
continue;
}*/
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int k = -1, d = -1, r = -1;
if ((r = t.FindGnQ(i, &k, &d)) || k != i + 1)
{
if ((i == N -1 || i == N) && r == 1)
{
}
else if (i == -2 && r == 0 && k == 0)
{
}
else
{
__utf8_printf("fGnQ[%d]:%d %d ", i, r, k);
}
}
}

__utf8_printf("Succ ");

for (i = -1; i <= N; i++)
{
/*if (x[i] == -1)
{
continue;
}*/
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int k = -1, d = -1, r = -1;
if ((r = t.FindSucc(i, &k, &d)) || (k != i + 1 && Dups == 1) || (k != i + 1 && k != i && Dups > 1))
{
if ((i == -1 || i == N) && r == 1)
{
}
else if (i == N - 1 && r == 2)
{
}
else
{
__utf8_printf("Succ[%d]:%d ", i, r);
}
}
}

__utf8_printf("Pred ");

for (i = -1; i <= N; i++)
{
/*if (x[i] == -1)
{
continue;
}*/
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int k = -1, d = -1, r = -1;
if ((r = t.FindPred(i, &k, &d)) || (k != i - 1 && Dups == 1) || (k != i - 1 && k != i && Dups > 1))
{
if ((i == -1 || i == N) && r == 1)
{
}
else if (i == 0 && r == 2)
{
}
else
{
__utf8_printf("Pred[%d]:%d ", i, r);
}
}
}

if (0)
{
__utf8_printf("\n");
int a = N / 2;
// a = 0;
// a = N - 1;
CMaaRBTree<int, int>::Handle h = t.FindNode(a), h1, h2;
__utf8_printf("%p %d %d\n", h, t.k(h), t.d(h));
h1 = h2 = h;
for (i = 0; i < Dups + 1; i++)
{
h1 = t.FindSucc(h1);
__utf8_printf("Succ %p %d %d\n", h1, h1 ? t.k(h1) : -9999, h1 ? t.d(h1) : -8888);
}
for (i = 0; i < Dups + 1; i++)
{
h2 = t.FindPred(h2);
__utf8_printf("Pred %p %d %d\n", h2, h2 ? t.k(h2) : -9999, h2 ? t.d(h2) : -8888);
}
}

//__utf8_printf("\n");
//t.Print();
__utf8_printf("find ");
for (i = 0; i < N; i++)
{
if (x[i] == -1)
{
continue;
}
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int ii = -1;
if (t.Find(x[i], &ii))// || ii != i)
{
__utf8_printf("\rf[%d]=%d:", i, x[i]);
__utf8_printf("-err\n");
}
}
//__utf8_printf("\n");
__utf8_printf("shuff ");
for (i = 0; i < N; i++)
{
unsigned r = 0;
GetRnd(&r, sizeof(r));
r %= N;
int tmp = x[i];
x[i] = x[(int)r];
x[(int)r] = tmp;
}
__utf8_printf("find ");
for (i = 0; i < N; i++)
{
if (x[i] == -1)
{
continue;
}
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int ii = -1;
if (t.Find(x[i], &ii))// || ii != i)
{
__utf8_printf("\rf[%d]=%d:", i, x[i]);
__utf8_printf("-err\n");
}
}
__utf8_printf("rem ");
for (j = 0; j < Dups; j++)
for (i = 0; i < N; i++)
{
if (x[i] == -1)
{
continue;
}
//__utf8_printf("r %d: ", i);
if (i % 1000 == 0)
{
//__utf8_printf("\rr[%d]=%d:", i, x[i]);
}
if (i >= 3)
{
gii++;
}
int xx = t.Remove(x[i]);
//__utf8_printf("%d\n", x);
if (xx)
{
__utf8_printf("\rr[%d]=%d:", i, x[i]);
__utf8_printf("-err\n");
}
else
{
//__utf8_printf("\n");
}

//t.Print();
//getch();
}
//__utf8_printf("\n");
//__utf8_printf("delete array\n");
//delete [] x;
__utf8_printf("Empty:\r");
t.Print();
//__utf8_printf("\n");
}
__utf8_printf("\n");
return 0;
}
catch(CMaaString e)
{
__utf8_printf("Error: %s\n", (const char *)e);
}
catch(const char * e)
{
__utf8_printf("Error: %s\n", e);
}
catch(...)
{
__utf8_printf("catch(...)\n");
}
return 1;
}

int test1()
{
try
{
for (int c = 0; c < 10000; c++)
{
__utf8_printf("%79s\rc=%d ", "", c);
const int N = 100;
const int VMax = 2 * N - N + N / 2;
CMaaPtr<int> x(N);
CMaaUnivHash<int, int> h;
int i;
__utf8_printf("gen rand ");
for (i = 0; i < N; i++)
{
while(1)
{
unsigned r = -1;
GetRnd(&r, sizeof(r));
//x[i] = rand() % VMax;
x[i] = r % VMax;
//if (!h.Add(x[i], i))
{
break;
}
}
}
CMaaRBTree<int, int> t;
__utf8_printf("insert/remove ");
for (i = 0; i < N; i++)
{
if (i % 1000 == 0)
{
//__utf8_printf("\ri[%d]=%d:", i, x[i]);
}
/*
if (i >= 4)
{
gii++;
}
*/
t.Insert(x[i],i);

if (i % 10 == 0 && i > 0)
{
int xx = t.Remove(x[i - 10]);
x[i - 10] = -1;
//__utf8_printf("\ri[%d]=%d:", i, x[i]);
}
//t.Print();
//getch();
}
//__utf8_printf("\n");
//t.Print();
__utf8_printf("find ");
for (i = 0; i < N; i++)
{
if (x[i] == -1)
{
continue;
}
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int ii = -1;
if (t.Find(x[i], &ii))// || ii != i)
{
__utf8_printf("\rf[%d]=%d:", i, x[i]);
__utf8_printf("-err\n");
}
}
//__utf8_printf("\n");
__utf8_printf("shuffle ");
for (i = 0; i < N; i++)
{
unsigned r = 0;
GetRnd(&r, sizeof(r));
r %= N;
int tmp = x[i];
x[i] = x[(int)r];
x[(int)r] = tmp;
}
__utf8_printf("find ");
for (i = 0; i < N; i++)
{
if (x[i] == -1)
{
continue;
}
if (i % 1000 == 0)
{
//__utf8_printf("\rf[%d]=%d:", i, x[i]);
}
int ii = -1;
if (t.Find(x[i], &ii))// || ii != i)
{
__utf8_printf("\rf[%d]=%d:", i, x[i]);
__utf8_printf("-err\n");
}
}
__utf8_printf("remove ");
for (i = 0; i < N; i++)
{
if (x[i] == -1)
{
continue;
}
//__utf8_printf("r %d: ", i);
if (i % 1000 == 0)
{
//__utf8_printf("\rr[%d]=%d:", i, x[i]);
}
if (i >= 3)
{
gii++;
}
int xx = t.Remove(x[i]);
//__utf8_printf("%d\n", x);
if (xx)
{
__utf8_printf("\rr[%d]=%d:", i, x[i]);
__utf8_printf("-err\n");
}
else
{
//__utf8_printf("\n");
}

//t.Print();
//getch();
}
//__utf8_printf("\n");
//__utf8_printf("delete array\n");
//delete [] x;
__utf8_printf("Empty:\r");
t.Print();
//__utf8_printf("\n");
}
__utf8_printf("\n");
return 0;
}
catch(CMaaString e)
{
__utf8_printf("Error: %s\n", (const char *)e);
}
catch(const char * e)
{
__utf8_printf("Error: %s\n", e);
}
catch(...)
{
__utf8_printf("catch(...)\n");
}
return 1;
}


#endif

//template<> CMaaFixedAllocator<CMaaRBTree<int, int>::Node> * CMaaRBTree<int, int>::Node::s_pAllocator = nullptr;