#ifndef __TYPETRAIT__H__
#define __TYPETRAIT__H__
#include <cstddef>
namespace stc{
class trueType{};
class falseType{};
template <typename type>
class typeTrait{
public:
typedef trueType thisDummyMemberMustBeFirst;
typedef falseType hasTrivalDefaultCtor;
typedef falseType hasTrivalCopyCtor;
typedef falseType hasTrivalAssignmentOperator;
typedef falseType hasTrivalDtor;
typedef falseType isPODType;
};
template <> class typeTrait < signed char > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < unsigned char > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < wchar_t > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < short > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < unsigned short > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < int > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < unsigned int > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < long > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < long long> {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < unsigned long > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < float > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < double > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < long double > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <class type> class typeTrait < type* > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < bool > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
}
#endif
#ifndef __ITERATOR__TRAIT__H__
#define __ITERATOR__TRAIT__H__
#include <cstddef>
namespace stc{
class inputIteratorTag{};
class outputIteratorTag{};
class forwardIteratorTag{};
class bidirectionalIteratorTag{};
class randomAccessIteratorTag{};
template < typename type,
typename category = forwardIteratorTag,
typename distance = std::ptrdiff_t,
typename pointer = type*,
typename reference = type& >
class iterator{
public:
typedef type valueType;
typedef category iteratorCategory;
typedef distance differenceType;
typedef pointer pointer;
typedef reference reference;
};
template <typename iterator>
class iteratorTrait{
public:
typedef typename iterator::iteratorCategory
iteratorCategory;
typedef typename iterator::valueType
valueType;
typedef typename iterator::differenceType
differenceType;
typedef typename iterator::pointer
pointer;
typedef typename iterator::reference
reference;
};
template <> class iteratorTrait < signed char > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef signed char valueType;
typedef std::ptrdiff_t differenceType;
typedef signed char* pointer;
typedef signed char& reference;
};
template <> class iteratorTrait < const signed char > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const signed char valueType;
typedef std::ptrdiff_t differenceType;
typedef const signed char* pointer;
typedef const signed char& reference;
};
template <> class iteratorTrait < unsigned char > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef unsigned char valueType;
typedef std::ptrdiff_t differenceType;
typedef unsigned char* pointer;
typedef unsigned char& reference;
};
template <> class iteratorTrait < const unsigned char > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const unsigned char valueType;
typedef std::ptrdiff_t differenceType;
typedef const unsigned char* pointer;
typedef const unsigned char& reference;
};
template <> class iteratorTrait < wchar_t > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef wchar_t valueType;
typedef std::ptrdiff_t differenceType;
typedef wchar_t* pointer;
typedef wchar_t& reference;
};
template <> class iteratorTrait < const wchar_t > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const wchar_t valueType;
typedef std::ptrdiff_t differenceType;
typedef const wchar_t* pointer;
typedef const wchar_t& reference;
};
template <> class iteratorTrait < short > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef short valueType;
typedef std::ptrdiff_t differenceType;
typedef short* pointer;
typedef short& reference;
};
template <> class iteratorTrait < const short > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const short valueType;
typedef std::ptrdiff_t differenceType;
typedef const short* pointer;
typedef const short& reference;
};
template <> class iteratorTrait < unsigned short > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef unsigned short valueType;
typedef std::ptrdiff_t differenceType;
typedef unsigned short* pointer;
typedef unsigned short& reference;
};
template <> class iteratorTrait < const unsigned short > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const unsigned short valueType;
typedef std::ptrdiff_t differenceType;
typedef const unsigned short* pointer;
typedef const unsigned short& reference;
};
template <> class iteratorTrait < int > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef int valueType;
typedef std::ptrdiff_t differenceType;
typedef int* pointer;
typedef int& reference;
};
template <> class iteratorTrait < const int > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const int valueType;
typedef std::ptrdiff_t differenceType;
typedef const int* pointer;
typedef const int& reference;
};
template <> class iteratorTrait < unsigned int > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef unsigned int valueType;
typedef std::ptrdiff_t differenceType;
typedef unsigned int* pointer;
typedef unsigned int& reference;
};
template <> class iteratorTrait < const unsigned int > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const unsigned int valueType;
typedef std::ptrdiff_t differenceType;
typedef const unsigned int* pointer;
typedef const unsigned int& reference;
};
template <> class iteratorTrait < long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef long valueType;
typedef std::ptrdiff_t differenceType;
typedef long* pointer;
typedef long& reference;
};
template <> class iteratorTrait < const long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const long valueType;
typedef std::ptrdiff_t differenceType;
typedef const long* pointer;
typedef const long& reference;
};
template <> class iteratorTrait < long long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef long long valueType;
typedef std::ptrdiff_t differenceType;
typedef long long * pointer;
typedef long long & reference;
};
template <> class iteratorTrait < const long long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const long long valueType;
typedef std::ptrdiff_t differenceType;
typedef const long long * pointer;
typedef const long long & reference;
};
template <> class iteratorTrait < unsigned long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef unsigned long valueType;
typedef std::ptrdiff_t differenceType;
typedef unsigned long* pointer;
typedef unsigned long& reference;
};
template <> class iteratorTrait < const unsigned long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const unsigned long valueType;
typedef std::ptrdiff_t differenceType;
typedef const unsigned long* pointer;
typedef const unsigned long& reference;
};
template <> class iteratorTrait < float > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef float valueType;
typedef std::ptrdiff_t differenceType;
typedef float* pointer;
typedef float& reference;
};
template <> class iteratorTrait < const float > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const float valueType;
typedef std::ptrdiff_t differenceType;
typedef const float* pointer;
typedef const float& reference;
};
template <> class iteratorTrait < double > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef double valueType;
typedef std::ptrdiff_t differenceType;
typedef double* pointer;
typedef double& reference;
};
template <> class iteratorTrait < const double > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const double valueType;
typedef std::ptrdiff_t differenceType;
typedef const double* pointer;
typedef const double& reference;
};
template <> class iteratorTrait < long double > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef long double valueType;
typedef std::ptrdiff_t differenceType;
typedef long double* pointer;
typedef long double& reference;
};
template <> class iteratorTrait < const long double > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const long double valueType;
typedef std::ptrdiff_t differenceType;
typedef const long double* pointer;
typedef const long double& reference;
};
template <> class iteratorTrait < bool > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef bool valueType;
typedef std::ptrdiff_t differenceType;
typedef bool* pointer;
typedef bool& reference;
};
template <> class iteratorTrait < const bool > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const bool valueType;
typedef std::ptrdiff_t differenceType;
typedef const bool* pointer;
typedef const bool& reference;
};
}
#endif
#ifndef __RBTREENODE__H__
#define __RBTREENODE__H__
namespace stc{
typedef char RBTreeNodeColorType;
template <typename type>
class RBTreeNode{
typedef RBTreeNode<type>* pointer;
public:
static const RBTreeNodeColorType red = 'r';
static const RBTreeNodeColorType black = 'b';
RBTreeNode();
RBTreeNode(const type&,pointer = NULL,pointer = NULL,pointer = NULL,RBTreeNodeColorType = red);
~RBTreeNode() = default;
type& getVal() { return mVal; }
pointer getParent() const { return mParent; }
pointer getLeft() const{ return mLeft; }
pointer getRight() const{ return mRight; }
RBTreeNodeColorType getColor() const{ return mColor; }
void setVal(const type& val) { mVal = val; }
void setParent(pointer p) { mParent = p; }
void setLeft(pointer p) { mLeft = p; }
void setRight(pointer p) { mRight = p; }
void setColor(RBTreeNodeColorType color){ mColor = color; }
private:
type mVal;
pointer mParent;
pointer mLeft;
pointer mRight;
RBTreeNodeColorType mColor;
};
template <typename type>
RBTreeNode<type>::RBTreeNode()
:mParent(NULL),
mLeft(NULL),
mRight(NULL),
mColor(red)
{
}
template <typename type>
RBTreeNode<type>::RBTreeNode(const type& val,pointer parent,pointer left,pointer right,RBTreeNodeColorType color)
:mVal(val),
mParent(parent),
mLeft(left),
mRight(right),
mColor(color)
{
}
template <typename type>
inline RBTreeNode<type>* parent(RBTreeNode<type>* item)
{
assert(item);
return item->getParent();
}
template <typename type>
inline RBTreeNode<type>* brother(RBTreeNode<type>* item)
{
RBTreeNode<type>* par = parent(item);
assert(par);
return item == par->getLeft() ?
par->getRight() : par->getLeft();
}
template <typename type>
inline RBTreeNode<type>* grand_parent(RBTreeNode<type>* item)
{
RBTreeNode<type>* temp = parent(item);
return parent(temp);
}
template <typename type>
inline RBTreeNode<type>* uncle(RBTreeNode<type>* item)
{
RBTreeNode<type>* temp = parent(item);
return brother(temp);
}
template <typename type>
inline bool isBlackNode(RBTreeNode<type>* item){
if (item == NULL || item->getColor() == RBTreeNode<type>::black)
return true;
return false;
}
template <typename type>
inline bool isRedNode(RBTreeNode<type>* item){
if (item != NULL && item->getColor() == RBTreeNode<type>::red)
return true;
return false;
}
}
#endif
#ifndef __RBTREE__H__
#define __RBTREE__H__
#include <memory>
#include <cstddef>
#include <stdexcept>
#include <cassert>
#include <memory>
#include <functional>
#include <utility>
#include "typeTrait.h"
#include "RBTreeNode.h"
#include "iteratorTrait.h"
namespace stc{
template <typename type,
typename ref,
typename ptr>
class RBTreeIterator{
typedef RBTreeNode<type>* basePtr;
typedef RBTreeIterator<type, type&, type*> self;
public:
typedef stc::bidirectionalIteratorTag
iteratorCategory;
typedef type valueType;
typedef ref reference;
typedef ptr pointer;
typedef std::ptrdiff_t differenceType;
RBTreeIterator() :mNode(NULL){}
explicit RBTreeIterator(basePtr n) :mNode(n){}
ref operator *()const { return mNode->getVal(); }
ptr operator ->()const { return &(mNode->getVal()); }
const self& operator ++();
const self operator ++(int);
const self& operator --();
const self operator --(int);
const bool operator ==(const self& rhs) { return mNode == rhs.mNode; }
const bool operator !=(const self& rhs) { return !(*this == rhs); }
basePtr getBasePtr()const { return mNode; }
private:
basePtr mNode;
};
template <typename type,
typename ref,
typename ptr>
typename const RBTreeIterator<type,ref,ptr>::self&
RBTreeIterator<type,ref,ptr>::
operator ++(){
assert(mNode);
basePtr parent = NULL;
if (mNode->getRight()){
mNode = mNode->getRight();
while (mNode->getLeft())
mNode = mNode->getLeft();
}else{
parent = mNode->getParent();
while (parent && mNode == parent->getRight()){///哨兵的左孩子右孩子都是指向一个地方的！
mNode = parent;
parent = parent->getParent();
}
}
if (parent && mNode != parent->getRight())
mNode = parent;
return *this;
}
template <typename type,
typename ref,
typename ptr>
typename const RBTreeIterator<type,ref,ptr>::self
RBTreeIterator<type,ref,ptr>::
operator ++(int){
assert(mNode);
self res = *this;
++(*this);
return res;
}
template <typename type,
typename ref,
typename ptr>
typename const RBTreeIterator<type,ref,ptr>::self&
RBTreeIterator<type,ref,ptr>::
operator --(){
assert(mNode);
basePtr parent = NULL;
if (mNode->getLeft()){
mNode = mNode->getLeft();
while (mNode->getRight())
mNode = mNode->getRight();
}else{
parent = mNode->getParent();
while (parent && mNode == parent->getLeft()){
mNode = parent;
parent = parent->getParent();
}
}
if (parent && mNode != parent->getLeft())
mNode = parent;
return *this;
}
template <typename type,
typename ref,typename ptr>
typename const RBTreeIterator<type,ref,ptr>::self
RBTreeIterator<type,ref,ptr>::
operator --(int){
assert(mNode);
self res = *this;
--(*this);
return res;
}
template <typename key,
typename type,
class keyOfValue = std::identity<type>,
class Compare = std::less<type>,
class Alloc = std::allocator<stc::RBTreeNode<type> > >
class rb_tree{
typedef rb_tree<key, type, keyOfValue, Compare, Alloc> self;
typedef RBTreeNode<type> node;
enum insertWay { unique = 0,equal };
typedef std::pair<RBTreeIterator<type,type&,type*>, bool> pair_result;
typedef RBTreeNode<type>* linkType;
static const std::size_t default_node_size = 1;
public:
typedef type valueType;
typedef std::ptrdiff_t differenceType;
typedef std::size_t sizeType;
typedef RBTreeIterator<type, type&, type*> iterator;
typedef type& reference;
typedef type* pointer;
public:
rb_tree();
rb_tree(const self&);
rb_tree(self&&);
~rb_tree();
sizeType size() const{ return mSize; }
sizeType max_size() const{ return sizeType(-1); }
bool empty() const{return mSize ? false : true; }
Compare key_comp() const { mCompare; }
pair_result insert_unique(const type&);
iterator insert_equal(const type&);
self& operator =(const self&);
self& operator =(self&&);
self& copymem(const self&);
self& copymem(self&&);
iterator begin();
iterator end() { return iterator(&mNil); }
iterator erase(iterator);
void clear();
private:
pair_result insert(const type&, insertWay);
void insert_fix_up(linkType);
linkType root()const { return mNil.getLeft(); }
linkType creatNode(const type&);
void destroyNode(linkType&);
void left_rotate(linkType);
void right_rotate(linkType);
linkType find_min(linkType)const;
void transplant(linkType, linkType);
void erase_fix_up(linkType, linkType);
void clear(linkType);
void unite(linkType);
private:
node mNil;
sizeType mSize;
Compare mCompare;
Alloc mAlloc;
};
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
rb_tree<key,type,keyOfValue,Compare,Alloc>::
rb_tree() :mSize(0),
mNil(type(),NULL,NULL,NULL,RBTreeNode<type>::black){}
template <typename key, typename type,
class keyOfValue, class Compare,
class Alloc>
rb_tree<key, type, keyOfValue, Compare, Alloc>::
rb_tree(const rb_tree& rhs) : mSize(0),
mNil(type(), NULL,NULL,NULL,RBTreeNode<type>::black){
copymem(rhs);
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
rb_tree<key,type,keyOfValue,Compare,Alloc>::
rb_tree(rb_tree&& rhs) :mSize(0),
mNil(type(), RBTreeNode<type>::black){
copymem(std::move(rhs));
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
rb_tree<key, type, keyOfValue, Compare, Alloc>::
~rb_tree(){
this->clear();
}
template <typename key, typename type,
class keyOfValue, class Compare,
class Alloc>
typename std::pair<typename stc::RBTreeIterator<type,type&,type*>,bool>
rb_tree<key,type, keyOfValue, Compare, Alloc>::
insert_unique(const type& val){
return insert(val, unique);
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
typename stc::rb_tree<key,type,keyOfValue,Compare,Alloc>::iterator
rb_tree<key,type,keyOfValue,Compare,Alloc>::
insert_equal(const type& val){
return insert(val, equal).first;
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
typename std::pair<typename stc::RBTreeIterator<type, type&, type*>, bool>
rb_tree < key, type, keyOfValue, Compare, Alloc>::
insert(const type& val, insertWay way){
type elem = keyOfValue()(val);
linkType root_node = root();
if (empty()){
root_node = creatNode(val);
mNil.setLeft(root_node);
mNil.setRight(root_node);
root_node->setParent(&mNil);
root_node->setColor(RBTreeNode<type>::black);
++mSize;
return pair_result(iterator(root_node),true);
}
assert(root_node);
linkType prev = root_node;
linkType scan = prev;
while (scan){
if (val == scan->getVal() && way == unique)
return pair_result(iterator(scan), false);
prev = scan;
scan = mCompare(val, scan->getVal()) ?
scan->getLeft() : scan->getRight();
}
linkType new_node = creatNode(val);
if (mCompare(val, prev->getVal()))
prev->setLeft(new_node);
else prev->setRight(new_node);
new_node->setParent(prev);
++mSize;
if (isRedNode(prev))
insert_fix_up(new_node);
return pair_result(iterator(new_node), true);
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
RBTreeNode<type>* rb_tree<key,type,keyOfValue,Compare,Alloc>::
creatNode(const type& val){
linkType res = mAlloc.allocate(default_node_size);
mAlloc.construct(res,val);
return res;
}
template <typename key, typename type,
class keyOfValue, class Compare,
class Alloc>
void rb_tree<key,type,keyOfValue,Compare,Alloc>::
destroyNode(linkType& item){
if (item == nullptr)
throw std::runtime_error("item is a nullptr");
mAlloc.destroy(item);
mAlloc.deallocate(item, default_node_size);
item = nullptr;
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
void rb_tree<key,type,keyOfValue,Compare,Alloc>::
insert_fix_up(linkType ptr){
assert(ptr);
linkType parent_node = parent(ptr);
linkType grand_node = grand_parent(ptr);
linkType uncle_node = uncle(ptr);
linkType brother_node = brother(ptr);
#ifndef __RED__COLOR__
#define __RED__COLOR__ RBTreeNode<type>::red
#endif
#ifndef __BLACK__COLOR__
#define __BLACK__COLOR__ RBTreeNode<type>::black
#endif
while (ptr != root() && isRedNode(parent(ptr)))
{
uncle_node = uncle(ptr);
parent_node = parent(ptr);
grand_node = grand_parent(ptr);
if (isRedNode(uncle_node))
{
parent_node->setColor(__BLACK__COLOR__);
uncle_node->setColor(__BLACK__COLOR__);
grand_node->setColor(__RED__COLOR__);
ptr = grand_node;
}
else if (grand_node->getLeft() == parent_node)
{//左子树
if (ptr == parent_node->getRight())
{
ptr = parent_node;
left_rotate(ptr);
continue;
}
parent_node->setColor(__BLACK__COLOR__);
grand_node->setColor(__RED__COLOR__);
right_rotate(grand_node);
parent_node = parent(ptr);
}
else
{//右子树
if (ptr == parent_node->getLeft())
{
ptr = parent_node;
right_rotate(ptr);
continue;
}
parent_node->setColor(__BLACK__COLOR__);
grand_node->setColor(__RED__COLOR__);
left_rotate(grand_node);
}
}
linkType root_node = root();
root_node->setColor(__BLACK__COLOR__);
#undef __RED__COLOR__
#undef __BLACK__COLOR__
}
template <typename key, typename type,
class keyOfValue, class Compare,
class Alloc>
typename rb_tree<key,type,keyOfValue,Compare,Alloc>::iterator
rb_tree<key, type, keyOfValue, Compare, Alloc>::
erase(iterator item){
assert(!empty());
#ifndef __RED__COLOR__
#define __RED__COLOR__ RBTreeNode<type>::red
#endif
#ifndef __BLACK__COLOR__
#define __BLACK__COLOR__ RBTreeNode<type>::black
#endif
assert(item != end());
linkType erase_node = item.getBasePtr();
assert(erase_node);
linkType parent_node = parent(erase_node);
linkType res = NULL;
if (erase_node->getLeft() != NULL &&
erase_node->getRight() != NULL){
linkType min_node = find_min(erase_node->getRight());
std::swap(erase_node->getVal(), min_node->getVal());
erase_node = min_node;
}
if (erase_node->getLeft() == NULL)
res = erase_node->getRight();
else
res = erase_node->getLeft();
transplant(erase_node, res);
if (isBlackNode(erase_node))
erase_fix_up(res, parent_node);
destroyNode(erase_node);
--mSize;
#undef __BLACK__COLOR__
#undef __RED__COLOR__
return iterator(res);
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
void rb_tree<key, type, keyOfValue, Compare, Alloc>::
left_rotate(linkType item){
linkType parent_node = parent(item);
linkType child = item->getRight();
linkType new_child = child->getLeft();
if (parent_node->getLeft() == item)
parent_node->setLeft(child);
else parent_node->setRight(child);
child->setParent(parent_node);
child->setLeft(item);
item->setParent(child);
item->setRight(new_child);
if (new_child != NULL)
new_child->setParent(item);
if (parent_node == &mNil)
{
parent_node->setLeft(child);
parent_node->setRight(child);
}
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
void rb_tree<key,type,keyOfValue,Compare,Alloc>::
right_rotate(linkType item){
linkType parent_node = parent(item);
linkType child = item->getLeft();
linkType new_child = child->getRight();
if (parent_node->getLeft() == item)
parent_node->setLeft(child);
else parent_node->setRight(child);
child->setParent(parent_node);
child->setRight(item);
item->setParent(child);
item->setLeft(new_child);
if (new_child != NULL)
new_child->setParent(item);
if (parent_node == &mNil)
{
parent_node->setLeft(child);
parent_node->setRight(child);
}
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
void rb_tree<key, type, keyOfValue, Compare, Alloc>::
erase_fix_up(linkType new_node, linkType parent_node){
#ifndef __RED__COLOR__
#define __RED__COLOR__ RBTreeNode<type>::red
#endif
#ifndef __BLACK__COLOR__
#define __BLACK__COLOR__ RBTreeNode<type>::black
#endif
linkType brother_node = NULL;
linkType brother_left = NULL;
linkType brother_right = NULL;
while (new_node != root() && isBlackNode(new_node)){
if (new_node != NULL)
parent_node = parent(new_node);
if (new_node == parent_node->getLeft()){
brother_node = parent_node->getRight();
if (isRedNode(brother_node)){
parent_node->setColor(__RED__COLOR__);
brother_node->setColor(__BLACK__COLOR__);
left_rotate(parent_node);
brother_node = parent_node->getRight();
}
brother_left = brother_node->getLeft();
brother_right = brother_node->getRight();
if (isBlackNode(brother_right)){
if (isBlackNode(brother_left)){
brother_node->setColor(__RED__COLOR__);
new_node = parent_node;
continue;
}
if (isRedNode(brother_left)){
brother_node->setColor(__RED__COLOR__);
brother_left->setColor(__BLACK__COLOR__);
right_rotate(brother_node);
brother_node = parent_node->getRight();
brother_left = brother_node->getLeft();
brother_right = brother_node->getRight();
}
}
if (isRedNode(brother_right)){
brother_node->setColor(parent_node->getColor());
parent_node->setColor(__BLACK__COLOR__);
brother_right->setColor(__BLACK__COLOR__);
left_rotate(parent_node);
break;
}
}
else{
brother_node = parent_node->getLeft();
if (isRedNode(brother_node)){
parent_node->setColor(__RED__COLOR__);
brother_node->setColor(__BLACK__COLOR__);
right_rotate(parent_node);
brother_node = parent_node->getLeft();
}
brother_left = brother_node->getLeft();
brother_right = brother_node->getRight();
if (isBlackNode(brother_left)){
if (isBlackNode(brother_right)){
brother_node->setColor(__RED__COLOR__);
new_node = parent_node;
continue;
}
if (isRedNode(brother_right)){
brother_node->setColor(__RED__COLOR__);
brother_right->setColor(__BLACK__COLOR__);
left_rotate(brother_node);
brother_node = parent_node->getLeft();
brother_left = brother_node->getLeft();
brother_right = brother_node->getRight();
}
}
if (isRedNode(brother_left)){
brother_node->setColor(parent_node->getColor());
parent_node->setColor(__BLACK__COLOR__);
brother_left->setColor(__BLACK__COLOR__);
right_rotate(parent_node);
break;
}
}
}
linkType root_node = root();
if (root_node != NULL)
root_node->setColor(__BLACK__COLOR__);
#undef __RED__COLOR__
#undef __BLACK__COLOR__
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
void rb_tree<key, type, keyOfValue, Compare, Alloc>::
transplant(linkType old_node, linkType new_node){
assert(old_node);
linkType parent_node = parent(old_node);
if (parent_node->getLeft() == old_node)
parent_node->setLeft(new_node);
else parent_node->setRight(new_node);
if (new_node != NULL)
new_node->setParent(parent_node);
if (parent_node == &mNil)
{
parent_node->setLeft(new_node);
parent_node->setRight(new_node);
}
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
void rb_tree<key, type, keyOfValue, Compare, Alloc>::clear(){
if (empty()) return;
clear(root());
mNil.setLeft(NULL);
mNil.setRight(NULL);
mSize = 0;
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
void rb_tree<key, type, keyOfValue, Compare, Alloc>::
clear(linkType node){
if (node == NULL) return;
clear(node->getLeft());
clear(node->getRight());
destroyNode(node);
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
rb_tree<key,type,keyOfValue,Compare,Alloc>&
rb_tree<key, type, keyOfValue, Compare, Alloc>::
copymem(const self& item){
self temp;
temp.unite(item.root());
copymem(std::move(temp));
return *this;
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
void rb_tree<key, type, keyOfValue, Compare, Alloc>::
unite(linkType node){
if (node == NULL) return;
insert_equal(node->getVal());
unite(node->getLeft());
unite(node->getRight());
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
rb_tree<key, type, keyOfValue, Compare, Alloc>&
rb_tree<key, type, keyOfValue, Compare, Alloc>::
copymem(self&& item){
this->clear();
linkType root_node = item.root();
this->mSize = item.mSize;
this->mNil.setLeft(root_node);
this->mNil.setRight(root_node);
if (root_node != NULL)
root_node->setParent(&mNil);
item.mSize = 0;
item.mNil.setLeft(NULL);
item.mNil.setRight(NULL);
return *this;
}
template <typename key, typename type,
class keyOfValue, class Compare,
class Alloc>
rb_tree<key, type, keyOfValue, Compare, Alloc>&
rb_tree<key, type, keyOfValue, Compare, Alloc>::
operator =(const self& item){
return copymem(item);
}
template <typename key, typename type,
class keyOfValue, class Compare,
class Alloc>
rb_tree<key, type, keyOfValue, Compare, Alloc>&
rb_tree<key, type, keyOfValue, Compare, Alloc>::
operator =(self&& item){
return copymem(std::move(item));
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
typename rb_tree<key,type,keyOfValue,Compare,Alloc>::iterator
rb_tree<key,type,keyOfValue,Compare,Alloc>::
begin(){
if (empty()) return end();
linkType res = find_min(root());
return iterator(res);
}
template <typename key,typename type,
class keyOfValue,class Compare,
class Alloc>
RBTreeNode<type>*
rb_tree<key, type, keyOfValue, Compare, Alloc>::
find_min(linkType node)const{
assert(node);
while (node->getLeft())
node = node->getLeft();
return node;
}
}
#endif