//**************************************
// Name: range_map class template
// Description:This is a container class that stores ranges instead of points; otherwise, it works like a map. The ranges are stored as [first, last), where the range includes all the points between first and last, and the point at first, but not the point at last. You can store subranges and superranges as well. The only limitation is that ranges may not "cut into" each other "from outside". For example, you can store 2 separate ranges [3, 5) and [5, 7), as the 5 in the latter does not cut into the former, as 5 does not fall into the range. You can also store [3, 5) inside [2, 6), because the former is not "cutting into" the latter "from outside." However, you can store [10, 15), and then store [12, 17), because the latter would be "cutting into" the former "from outside". Iterators work a little differently, but are explained below, as you iterator begin/end point by begin/end point, rather than range. This container uses a modified red-black tree structure to store ranges and sub-ranges.
This requires C++11. There may be an issue with _ASSERT. If so, then simply add "#define _ASSERT assert" at the top. I've done extensive testing, but it still may be buggy. Please report any bugs that you notice.
It is a class template that with a modified red-black tree (implementation similar to that on the wiki page) that stores ranges as opposed to points. Each range is stored with each point as a key_type, a less-than comparable type in the form of [left, right). The range includes all the points between left and right, and left, but not right. Ranges, if they fall inside a range, will be stored inside other ranges. However, a new range may not be able ot have only one start or end point of an existing range intercept it. That is, if you have a range [3, 5) already stored, you cannot add a new range [4, 6), because it would intercept only one point (5). Note, however, that in this case, adding [5, 6) would be OK, because in the stored range, 5 is not included in the range, so it does not intercept it. There is also a mapped_type attached to it, together creating a range_map_item, or value_type
// By: Erika Butler
//
//This code is copyrighted and has// limited warranties.Please see http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=14209&lngWId=3//for details.//**************************************
/*
The class template follows the following template:
range_map<key_type, mapped_type, key_compare, allocator_type>
key_type: The type that each point in the range is in.
mapped_type: The value/object attached to each range stored.
key_compare: The comparator. Defaults to simple less-than of key_type.
allocator_type: The allocator. Defaults to the standard allocator of the range_map_item.
The range_map_item is as follows:
range_map_item<key_type, mapped_type>
and is also the value_type in the class template container. The range_map_item stores the range along with the mapped item. It can use the following functions:
constructors:
range_map_item(const key_type& left, const key_type& right, const mapped_type& val) ;
range_map_item(key_type&& left, key_type&& right, const mapped_type& val) ;
range_map_item(const key_type& left, const key_type& right, mapped_type&& val) ;
range_map_item(key_type&& left, key_type&& right, mapped_type&& val) ;
Methods (which should be self-explanatory):
const key_type& get_left() const; (returns begin point of range)
const key_type& get_right() const; (returns end point of range)
const mapped_type& get_val() const;
void set_val(const mapped_type& in);
void set_val(mapped_type&& in);
Now for the class itself:
(constructors)
range_map();
range_map(key_compare comp);
range_map(allocator_type all);
range_map(key_compare comp, allocator_type all);
range_map(const range_map& copy);
range_map(range_map&& to_move);
(destructors)
~range_map();
operator=
const range_map& operator=(const range_map& copy);
const range_map& operator=(range_mapy&& to_move);
methods
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
void clear();
size_type size() const; (size_type is same as size_t)
bool empty() const;
size_type max_size() const;
key_compare key_comp() const;
allocator_type get_alloc() const;
std::pair<iterator, bool> insert(const value_type& val);
std::pair<iterator, bool> insert(value_type&& val);
iterator erase(const_iterator iter);
iterator at(const key_type& wher);
const_iterator at(const key_type& wher) const;
This at() method returns an iterator pointing to the begin point of the smallest range that intercepts the point at wher.
iterator upper_bound(const key_type& wher);
const_iterator upper_bound(const key_type& wher) const;
iterator lower_bound(const key_type& wher);
const_iterator lower_bound(const key_type& wher) const;
iterator get_point(const key_type& wher);
const_iterator get_point(const key_type& wher) const;
These functions are important. They return the iterator to the begin point that wher is at, or the begin point or end point of any range that first comes after wher.
The iterators work a little differently from the standard iterators; they are still bidirectional iterators, only that when you increment or decrement, you move from point to point, rather than range to range, in order that they appear. You have the following additional functions (shown for iterator, but can be applied to const_iterator as well):
bool endpt const; (is this at an end point as opposed to a begin point)
const key_type& cur_pt() const; (returns the current point that it's at)
const key_type& opp_pt() const; (returns the point at the opposite end from where it's at)
iterator subtree_parent(); (return a copy of the iterator as it is, and set the iterator to the parent range, which would be equivalent end() if there is no parent range)
iterator opp_end() const; (returns an iterator to the point at the opposite end from where the current iterator is at)
If you have any questions, please feel free to ask.
*/
#include <memory>
#include <utility>
#include <functional>
#include <assert.h>
#ifndef RANGE_MAP_HPP
#define RANGE_MAP_HPP
#define RANGE_MAP_VER_PROP
template<class kty, class ty>
class range_map_item {
public:
range_map_item(const kty& left, const kty& right, const ty& val)
: left(left), right(right), val(val) {}
range_map_item(const kty& left, const kty& right, ty&& val)
: left(left), right(right), val(std::forward(val)) {}
range_map_item(kty&& left, kty&& right, const ty& val)
: left(std::forward<kty>(left)), right(std::forward<kty>(right)), val(val) {}
range_map_item(kty&& left, kty&& right, ty&& val)
: left(std::forward<kty>(left)), right(std::forward<kty>(right)), val(std::forward<ty>(val)) {}
const kty& get_left() const {
return left;
}
const kty& get_right() const {
return right;
}
const ty& get_val() const {
return val;
}
void set_val(const ty& in) {
val = in;
}
void set_val(ty&& in) {
val = std::forward(in);
}
private:
range_map_item() {}
kty left;
kty right;
ty val;
};
template<class kty, class ty, class compare = std::less<kty>, class alloc = std::allocator<range_map_item<kty, ty> > >
class range_map {
public:
typedef range_map<kty, ty, compare, alloc> myt;
typedef kty key_type;
typedef ty mapped_type;
typedef compare key_compare;
typedef alloc allocator_type;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef size_t size_type;
typedef range_map_item<kty, ty> value_type;
private:
struct mydel {
template<class t> void operator()(t* ptr) {
all->destroy(ptr);
all->deallocate(ptr, 1);
}
mydel(allocator_type* all) : all(all) {}
allocator_type* all;
};
struct node {
node(value_type* val, mydel del)
: val(val, del), parent(nullptr), left(nullptr), sub(nullptr), right(nullptr), clr(node::red) {}
node(const node& copy)
: val(doalloc(*copy.val), copy.val.get_deleter()), parent(nullptr), left(nullptr), sub(nullptr), right(nullptr), clr(node::red) {}
node(std::unique_ptr<value_type, mydel>&& ptr)
: val(std::forward<std::unique_ptr<value_type, mydel> >(ptr)), parent(nullptr), left(nullptr), sub(nullptr), right(nullptr), clr(node::red) {}
node* grandparent() {
_ASSERT(this->parent != nullptr);
_ASSERT(this->parent->parent != nullptr);
return this->parent->parent;
}
node* sibling() {
_ASSERT(this->parent != nullptr);
if(this == this->parent->left)
return this->parent->right;
else
return this->parent->left;
}
node* uncle() {
_ASSERT(this->parent != nullptr);
_ASSERT(this->parent->parent != nullptr);
return this->parent->sibling();
}
bool is_root() {
return this->parent == nullptr || this == this->parent->sub;
}
node* leftmost() {
node* ret = this;
while(ret->left != nullptr)
ret = ret->left;
return ret;
}
node* rightmost() {
node* ret = this;
while(ret->right != nullptr)
ret = ret->right;
return ret;
}
node* next() {
node* ret = this;
if(ret->right == nullptr) {
while(!ret->is_root() && ret != ret->parent->left)
ret = ret->parent;
ret = ret->parent;
} else ret = ret->right->leftmost();
return ret;
}
node* prev() {
node* ret = this;
if(ret->left == nullptr) {
node* temp = super();
while(!ret->is_root() && ret != ret->parent->right)
ret = ret->parent;
ret = ret->parent;
} else ret = ret->left->rightmost();
return ret;
}
bool next_iter(bool is_end, node** n) {
bool end = false;
if(!is_end) {
if((*n)->sub == nullptr) {
end = true;
} else {
*n = (*n)->sub->leftmost();
}
} else {
if((*n)->next() == (*n)->super()) {
end = true;
}
*n = (*n)->next();
}
return end;
}
bool prev_iter(bool is_end, node** n) {
bool end = true;
if(is_end) {
if((*n)->sub == nullptr) {
end = false;
} else {
*n = (*n)->sub->rightmost();
}
} else {
if((*n)->prev() == (*n)->super()) {
end = false;
}
*n = (*n)->prev();
}
return end;
}
node* super() {
node *ret = this;
while(!ret->is_root()) {
ret = ret->parent;
}
return ret->parent;
}
node* grandparent() const {
_ASSERT(this->parent != nullptr);
_ASSERT(this->parent->parent != nullptr);
return this->parent->parent;
}
node* sibling() const {
_ASSERT(this->parent != nullptr);
if(this == this->parent->left)
return this->parent->right;
else
return this->parent->left;
}
node* uncle() const {
_ASSERT(this->parent != nullptr);
_ASSERT(this->parent->parent != nullptr);
return this->parent->sibling;
}
bool is_root() const {
return this->parent == nullptr || this == this->parent->sub;
}
node* leftmost() const {
node* ret = this;
while(ret->left != nullptr)
ret = ret->left;
return ret;
}
node* rightmost() const {
node* ret = this;
while(ret->right != nullptr)
ret = ret->right;
return ret;
}
node* next() const {
node* ret = this;
if(ret->right == nullptr) {
while(!is_root() && ret != ret->parent->left)
ret = ret->parent;
ret = ret->parent;
} else ret = ret->right->leftmost();
return ret;
}
node* prev() const {
node* ret = this;
if(ret->left == nullptr) {
while(!is_root() && ret != ret->parent->right)
ret = ret->parent;
ret = ret->parent;
} else ret = ret->left->rightmost();
return ret;
}
bool next_iter(bool is_end, node** n) const {
bool end = false;
if(!is_end) {
if((*n)->sub == nullptr) {
end = true;
} else {
*n = (*n)->sub->leftmost();
}
} else {
if((*n)->next() == (*n)->super()) {
end = true;
}
*n = (*n)->next();
}
return ret;
}
bool prev_iter(bool is_end, node** n) const {
bool end = true;
if(is_end) {
if((*n)->sub == nullptr) {
end = false;
} else {
*n = (*n)->sub->rightmost();
}
} else {
if((*n)->prev() == (*n)->super()) {
end = false;
}
*n = (*n)->prev();
}
return ret;
}
node* super() const {
node *ret = this;
while(!ret->is_root()) {
ret = ret->parent;
}
return ret->parent;
}
std::unique_ptr<value_type, mydel> val;
node* parent;
node* left;
node* sub;
node* right;
int clr;
static const int red = 0;
static const int black = 1;
};
public:
class iterator {
friend class range_map<kty, ty, compare, alloc>;
public:
typedef typename myt::const_pointer const_pointer;
typedef typename myt::const_reference const_reference;
typedef typename myt::pointer pointer;
typedef typename myt::reference reference;
iterator()
: is_end(false), cur_node(nullptr), rootcpy(new node*(nullptr)) {}
iterator(const iterator& copy)
: is_end(copy.is_end), cur_node(copy.cur_node), rootcpy(copy.rootcpy) {}
const iterator& operator=(const iterator& copy) {
this->is_end = copy.is_end;
this->cur_node = copy.cur_node;
this->rootcpy = copy.rootcpy;
return *this;
}
bool operator==(const iterator& right) const {
if(this->cur_node == nullptr) return right.cur_node == nullptr;
return(this->is_end == right.is_end && this->cur_node == right.cur_node);
}
bool operator!=(const iterator& right) const {
return !(*this == right);
}
bool endpt() const {
return is_end;
}
value_type& operator*() const {
return cur_node->val.operator*();
}
value_type* operator->() const {
return cur_node->val.operator->();
}
const key_type& cur_pt() const {
return is_end ? cur_node->val->get_right() : cur_node->val->get_left();
}
const key_type& opp_pt() const {
return is_end ? cur_node->val->get_left() : cur_node->val->get_right();
}
const iterator& operator++() {
if(cur_node == nullptr) {
is_end = false;
cur_node = (*rootcpy)->leftmost();
} else {
is_end = cur_node->next_iter(is_end, &cur_node);
}
return *this;
}
const iterator& operator--() {
if(cur_node == nullptr) {
is_end = true;
cur_node = (*rootcpy)->rightmost();
} else {
is_end = cur_node->prev_iter(is_end, &cur_node);
}
return *this;
}
iterator operator++(int) {
iterator ret = *this;
this->operator++();
return ret;
}
iterator operator--(int) {
iterator ret = *this;
this->operator--();
return ret;
}
iterator subtree_parent() {
iterator ret = *this;
cur_node = cur_node->super();
return ret;
}
iterator opp_end() const {
iterator ret = *this;
ret.is_end = !ret.is_end;
return ret;
}
private:
iterator(bool is_end, node* cur_node, std::shared_ptr<node*>& rootcpy)
: is_end(is_end), cur_node(cur_node), rootcpy(rootcpy) {}
bool is_end;
node* cur_node;
std::shared_ptr<node*> rootcpy;
};
class const_iterator {
friend class range_map<kty, ty, compare, alloc>;
public:
typedef typename myt::const_pointer const_pointer;
typedef typename myt::const_reference const_reference;
typedef typename myt::pointer pointer;
typedef typename myt::reference reference;
const_iterator()
: is_end(false), cur_node(nullptr), rootcpy(new node*(nullptr)) {}
const_iterator(const const_iterator& copy)
: is_end(copy.is_end), cur_node(copy.cur_node), rootcpy(copy.rootcpy) {}
const_iterator(const iterator& copy)
: is_end(copy.is_end), cur_node(copy.cur_node), rootcpy(copy.rootcpy) {}
const const_iterator& operator=(const const_iterator& copy) {
this->is_end = copy.is_end;
this->cur_node = copy.cur_node;
this->rootcpy = copy.rootcpy;
return *this;
}
const const_iterator& operator=(const iterator& copy) {
this->is_end = copy.is_end;
this->cur_node = copy.cur_node;
this->rootcpy = copy.rootcpy;
return *this;
}
bool operator==(const const_iterator& right) const {
if(this->cur_node == nullptr) return right.cur_node == nullptr;
return(this->is_end == right.is_end && this->cur_node == right.cur_node);
}
bool operator!=(const const_iterator& right) const {
return !(*this == right);
}
bool operator==(const iterator& right) const {
if(this->cur_node == nullptr) return right.cur_node == nullptr;
return(this->is_end == right.is_end && this->cur_node == right.cur_node);
}
bool operator!=(const iterator& right) const {
return !(*this == right);
}
bool endpt() const {
return is_end;
}
const value_type& operator*() const {
return cur_node->val.operator*();
}
const value_type* operator->() const {
return cur_node->val.operator->();
}
const key_type& cur_pt() const {
return is_end ? cur_node->val->get_right() : cur_node->val->get_left();
}
const key_type& opp_pt() const {
return is_end ? cur_node->val->get_left() : cur_node->val->get_right();
}
const const_iterator& operator++() {
if(cur_node == nullptr) {
is_end = false;
cur_node = (*rootcpy)->leftmost();
} else {
is_end = cur_node->next_iter(is_end, &cur_node);
}
return *this;
}
const const_iterator& operator--() {
if(cur_node == nullptr) {
is_end = true;
cur_node = (*rootcpy)->rightmost();
} else {
is_end = cur_node->prev_iter(is_end, &cur_node);
}
return *this;
}
const_iterator operator++(int) {
iterator ret = *this;
this->operator++();
return ret;
}
const_iterator operator--(int) {
iterator ret = *this;
this->operator--();
return ret;
}
const_iterator subtree_parent() {
const_iterator ret = *this;
cur_node = cur_node->super();
return ret;
}
const_iterator opp_end() const {
const_iterator ret = *this;
ret.is_end = !ret.is_end;
return ret;
}
private:
const_iterator(bool is_end, node* cur_node, const std::shared_ptr<node*>& rootcpy)
: is_end(is_end), cur_node(cur_node), rootcpy(rootcpy) {}
bool is_end;
node* cur_node;
std::shared_ptr<node*> rootcpy;
};
range_map()
: cur_size(0), comp(key_compare()), all(allocator_type()), root(new node*(nullptr)) {}
range_map(key_compare comp)
: cur_size(0), comp(comp), all(allocator_type()), root(new node*(nullptr)) {}
range_map(allocator_type all)
: cur_size(0), comp(key_compare()), all(all), root(new node*(nullptr)) {}
range_map(key_compare comp, allocator_type all)
: cur_size(0), comp(comp), all(all), root(new node*(nullptr)) {}
range_map(const myt& copy)
: comp(copy.comp), all(copy.all), cur_size(0), root(new node*(nullptr)) {
copy_range_map(copy);
}
const myt& operator=(const myt& copy) {
clear();
comp = copy.comp;
all = copy.all;
copy_range_map(copy);
return *this;
}
range_map(myt&& right)
: comp(right.comp), all(right.all), cur_size(right.cur_size) {
root = std::move(right.root);
right.root = std::shared_ptr<node*>(new node*(nullptr));
right.cur_size = 0;
}
const myt& operator=(myt&& right) {
clear();
comp = right.comp;
all = right.all;
root = std::move(right.root);
right.root = std::shared_ptr<node*>(new node*(nullptr));
cur_size = right.cur_size;
right.cur_size = 0;
return *this;
}
~range_map() {
clear();
}
iterator begin() {
if(*root == nullptr) return end();
return iterator(false, (*root)->leftmost(), root);
}
const_iterator begin() const {
if(*root == nullptr) return end();
return const_iterator(false, (*root)->leftmost(), root);
}
iterator end() {
return iterator(false, nullptr, root);
}
const_iterator end() const {
return const_iterator(false, nullptr, root);
}
void clear() {
while(*root != nullptr) {
delete2(*root);
verify_properties();
}
}
size_type size() const {
return cur_size;
}
bool empty() const {
return (*root == nullptr);
}
size_type max_size() const {
return all.max_size();
}
key_compare key_comp() const {
return comp;
}
allocator_type get_alloc() const {
return all;
}
std::pair<iterator, bool> insert(const value_type& val) {
if(!comp(val.get_left(), val.get_right())) return std::pair<iterator, bool>(end(), false);
_ASSERT(!comp(val.get_right(), val.get_left()));
node* n = insert1(val);
return std::pair<iterator, bool>(iterator(false, n, root), n != nullptr);
}
std::pair<iterator, bool> insert(value_type&& val) {
if(!comp(val.get_left(), val.get_right())) return std::pair<iterator, bool>(end(), false);
_ASSERT(!comp(val.get_right(), val.get_left()));
node* n = insert1(std::forward<value_type>(val));
return std::pair<iterator, bool>(iterator(false, n, root), n != nullptr);
}
iterator erase(const_iterator iter) {
return iterator(false, delete2(iter.cur_node), root);
}
iterator at(const key_type& wher) {
return iterator(false, nodelookup(wher), root);
}
const_iterator at(const key_type& wher) const {
return const_iterator(false, nodelookup(wher), root);
}
iterator upper_bound(const key_type& wher) {
return iterator(false, ubound(wher), root);
}
const_iterator upper_bound(const key_type& wher) const {
return const_iterator(false, ubound(wher), root);
}
iterator lower_bound(const key_type& wher) {
return iterator(false, lbound(wher), root);
}
const_iterator lower_bound(const key_type& wher) const {
return const_iterator(false, lbound(wher), root);
}
iterator get_point(const key_type& wher) {
iterator ret = lower_bound(wher);
if(ret == end()) return ret;
if(!comp(ret.cur_pt(), wher)) return ret;
return ret.opp_end();
}
const_iterator get_point(const key_type& wher) const {
const_iterator ret = lower_bound(wher);
if(ret == end()) return ret;
if(!comp(ret.cur_pt(), wher)) return ret;
return ret.opp_end();
}
private:
value_type* doalloc(const value_type& val) {
value_type* ret = nullptr;
try {
ret = all.allocate(1);
} catch(std::bad_alloc&) {return nullptr;}
all.construct(ret, val);
return ret;
}
value_type* doalloc(value_type&& val) {
value_type* ret = nullptr;
try {
ret = all.allocate(1);
} catch(std::bad_alloc&) {return nullptr;}
all.construct(ret, std::forward<value_type>(val));
return ret;
}
bool are_equal(const value_type& left, const value_type& right) const {
return !comp(left.get_left(), right.get_left()) && !comp(left.get_right(), right.get_right()) &&
!comp(right.get_left(), left.get_left()) && !comp(right.get_right(), left.get_right());
}
bool in_range(const key_type& key, const value_type& range) const {
return !comp(range.get_left(), key) && comp(key, range.get_right());
}
node* nodelookup(const key_type& key) const {
node* ret = *root, * last = nullptr;
while(1) {
if(ret == nullptr) {
ret = last;
break;
}
if(comp(key, ret->val->get_left())) {
_ASSERT(comp(key, ret->val->get_left()));
ret = ret->left;
} else if(!comp(key, ret->val->get_right())) {
ret = ret->right;
} else {
last = ret;
ret = ret->sub;
}
}
return ret;
}
bool nodelookup(const value_type& val, node** left, node** right) const {
node* ret = *root, * last = nullptr;
while(1) {
if(ret == nullptr) {
ret = last;
return ret;
}
if(!comp((*root)->val->get_left(), val.get_right())) {
ret = ret->left;
} else if(!comp(val.get_left(), ret->val->get_right())) {
_ASSERT(!comp(val.get_right(), ret->get_left()));
ret = ret->right;
} else {
_ASSERT(!comp(val.get_right(), ret->val->get_left()));
_ASSERT(!comp(ret->val->get_right(), val.get_left()));
if(!comp(val.get_left(), ret->val->get_left()) && !comp(ret->val->get_right(), val.get_right())) {
last = ret;
ret = ret->sub;
continue;
}
_ASSERT(!comp(ret->val->get_left(), val.get_left()));
_ASSERT(!comp(val.get_right(), ret->val->get_right()));
break;
}
}
*left = *right = ret;
if(ret == nullptr) return true;
return nodelookup2(val, left, right);
}
bool nodelookup2(const value_type& val, node** left, node** right) const {
while((*left)->prev() != nullptr &&
(*left)->prev() != (*left)->super() &&
comp(val.get_left(), (*left)->prev()->val->get_right())) {
_ASSERT(!comp((*left)->prev()->val->get_right(), val.get_left()));
*left = (*left)->prev();
}
while((*right)->prev() != nullptr &&
(*right)->next() != (*right)->super() &&
comp((*right)->next()->val->get_left(), val.get_right())) {
_ASSERT(!comp(val.get_right(), (*right)->next()->val->get_left()));
*right = (*right)->next();
}
if(comp((*left)->val->get_left(), val.get_left())) {
_ASSERT(!comp(val.get_left(), (*left)->val->get_left()));
return false;
}
if(comp(val.get_right(), (*right)->val->get_right())) {
_ASSERT(!comp((*right)->val->get_right(), val.get_right()));
return false;
}
return true;
}
node* ubound(const key_type& key) const {
if(*root == nullptr) return nullptr;
node* ret = *root;
while(1) {
if(!comp(key, ret->val->get_right())) {
if(ret->right == nullptr) {
if(ret->next() == ret->super()) ret = ret->next();
if(ret != nullptr) ret = ret->next();
break;
}
ret = ret->right;
continue;
}
_ASSERT(!comp(ret->val->get_right(), key));
if(comp(key, ret->val->get_left())) {
_ASSERT(!comp(ret->val->get_left(), key));
if(ret->left == nullptr) {
break;
}
ret = ret->left;
continue;
}
if(ret->sub == nullptr) {
if(ret->next() == ret->super()) ret = ret->next();
if(ret != nullptr) ret = ret->next();
break;
}
ret = ret->sub;
}
return ret;
}
node* lbound(const key_type& key) const {
if(*root == nullptr) return nullptr;
node* ret = *root;
while(1) {
if(!comp(key, ret->val->get_right())) {
if(ret->right == nullptr) {
ret = ret->next();
break;
}
ret = ret->right;
continue;
}
_ASSERT(!comp(ret->val->get_right(), key));
if(comp(key, ret->val->get_left())) {
_ASSERT(!comp(ret->val->get_left(), key));
if(ret->left == nullptr) {
break;
}
ret = ret->left;
continue;
}
if(!comp(ret->val->get_left(), key)) {
break;
}
if(ret->sub == nullptr) {
break;
}
ret = ret->sub;
}
return ret;
}
void node_replace(node* old, node* n) {
if(old->parent == nullptr) {
*root = n;
} else {
if(old == old->parent->left) {
old->parent->left = n;
} else if(old == old->parent->right) {
old->parent->right = n;
} else {
old->parent->sub = n;
}
}
if(n != nullptr) {
n->parent = old->parent;
}
}
void node_rot_left(node* n) {
node* z = n->right;
node_replace(n, z);
n->right = z->left;
if(z->left != nullptr) {
z->left->parent = n;
}
z->left = n;
n->parent = z;
}
void node_rot_right(node* n) {
node* z = n->left;
node_replace(n, z);
n->left = z->right;
if(z->right != nullptr) {
z->right->parent = n;
}
z->right = n;
n->parent = z;
}
int node_color(node* n) const {
return n == nullptr ? node::black : n->clr;
}
void verify_properties() {
#ifdef RANGE_MAP_VER_PROP
verify_property1(*root);
verify_property2(*root);
verify_property4(*root);
verify_property5(*root);
#endif
}
void verify_property1(node* n) {
_ASSERT(node_color(n) == node::red || node_color(n) == node::black);
if(n == nullptr) return;
verify_property1(n->left);
verify_property1(n->right);
verify_property1(n->sub);
verify_property2(n->sub);
}
void verify_property2(node* n) {
_ASSERT(node_color(n) == node::black);
}
void verify_property4(node* n) {
if(node_color(n) == node::red) {
_ASSERT(node_color(n->left) == node::black);
_ASSERT(node_color(n->right) == node::black);
_ASSERT(node_color(n->parent) == node::black);
}
if(n == nullptr) return;
verify_property4(n->left);
verify_property4(n->right);
verify_property4(n->sub);
}
void verify_property5(node* n) {
int black_count_path = -1;
verify_property5_helper(n, 0, &black_count_path);
}
void verify_property5_helper(node* n, int black_count, int* path_black_count) {
if(node_color(n) == node::black) {
black_count++;
}
if(n == nullptr) {
if(*path_black_count = -1) {
*path_black_count = black_count;
} else {
_ASSERT(black_count = *path_black_count);
}
return;
}
verify_property5_helper(n->left, black_count, path_black_count);
verify_property5_helper(n->right, black_count, path_black_count);
verify_property5(n->sub);
}
node* insert1(const value_type& val) {
return insert2(new node(doalloc(val), mydel(&all)), &*root);
}
node* insert1(value_type&& val) {
return insert2(new node(doalloc(std::forward<value_type>(val)), mydel(&all)), &*root);
}
node* insert2(node* ins, node** start) {
if(*start == nullptr) {
*start = ins;
++cur_size;
} else {
node* n = *start;
while(1) {
if(!comp(n->val->get_left(), ins->val->get_right())) {
if(n->left == nullptr) {
n->left = ins;
ins->parent = n;
++cur_size;
break;
}
n = n->left;
continue;
}
_ASSERT(!comp(ins->val->get_right(), n->val->get_left()));
if(!comp(ins->val->get_left(), n->val->get_right())) {
if(n->right == nullptr) {
n->right = ins;
ins->parent = n;
++cur_size;
break;
}
n = n->right;
continue;
}
_ASSERT(!comp(n->val->get_right(), ins->val->get_left()));
if(comp(ins->val->get_left(), n->val->get_left()) || comp(n->val->get_right(), ins->val->get_right())) {
ins = insert3(ins, n);
if(ins == nullptr)
return nullptr;
break;
}
if(n->sub == nullptr) {
n->sub = ins;
ins->parent = n;
++cur_size;
break;
}
n = n->sub;
}
}
inscase1(ins);
verify_properties();
return ins;
}
node* insert3(node* ins, node* n) {
node* left = n, * right = n;
if(!nodelookup2(*(ins->val), &left, &right)) {
return nullptr;
delete ins;
}
node* endpt = right->next();
while(left != nullptr && left != endpt) {
node* next = left->next();
node* copy = new node(std::move(left->val));
copy->sub = left->sub;
left->sub = nullptr;
if(copy->sub != nullptr) copy->sub->parent = copy;
delete2(left);
copy->parent = ins;
insert2(copy, &ins->sub);
left = next;
}
return insert2(ins, &*root);
}
void inscase1(node* n) {
if(n->is_root()) {
n->clr = node::black;
} else {
inscase2(n);
}
}
void inscase2(node* n) {
if(node_color(n->parent) == node::black)
return;
else
inscase3(n);
}
void inscase3(node* n) {
if(node_color(n->uncle()) == node::red) {
n->parent->clr = node::black;
n->uncle()->clr = node::black;
n->grandparent()->clr = node::red;
inscase1(n->grandparent());
} else {
inscase4(n);
}
}
void inscase4(node* n) {
if(n == n->parent->right && n->parent == n->grandparent()->left) {
node_rot_left(n->parent);
n = n->left;
} else if(n == n->parent->left && n->parent == n->grandparent()->right) {
node_rot_right(n->parent);
n = n->right;
}
inscase5(n);
}
void inscase5(node* n) {
n->parent->clr = node::black;
n->grandparent()->clr = node::red;
if(n == n->parent->left && n->parent == n->grandparent()->left) {
node_rot_right(n->grandparent());
} else {
_ASSERT(n == n->parent->right && n->parent == n->grandparent()->right);
node_rot_left(n->grandparent());
}
}
node* delete2(node* n) {
if(n == nullptr) return nullptr;
node* ret = n->next();
if(n->left != nullptr && n->right != nullptr) {
node* pred = n->left->rightmost();
n->val = std::move(pred->val);
std::swap(n->sub, pred->sub);
if(n->sub != nullptr && pred->sub != nullptr) {
std::swap(n->sub->parent, pred->sub->parent);
} else if(n->sub != nullptr) {
n->sub->parent = n;
} else if(pred->sub != nullptr) {
pred->sub->parent = pred;
}
n = pred;
}
_ASSERT(n->left == nullptr || n->right == nullptr);
node* child = n->right == nullptr ? n->left : n->right;
if(node_color(n) == node::black) {
n->clr = node_color(child);
delcase1(n);
}
node_replace(n, child);
if(n->is_root() && child != nullptr)
child->clr = node::black;
while(n->sub != nullptr) {
node* copy = new node(std::move(n->sub->val));
copy->sub = n->sub->sub;
n->sub->sub = nullptr;
if(copy->sub != nullptr) copy->sub->parent = copy;
delete2(n->sub);
insert2(copy, &*root);
}
--cur_size;
delete n;
verify_properties();
return ret;
}
void delcase1(node* n) {
if(n->is_root())
return;
else
delcase2(n);
}
void delcase2(node* n) {
if(node_color(n->sibling()) == node::red) {
n->parent->clr = node::red;
n->sibling()->clr = node::black;
if(n == n->parent->left)
node_rot_left(n->parent);
else
node_rot_right(n->parent);
}
delcase3(n);
}
void delcase3(node* n) {
_ASSERT(n->sibling() != nullptr);
if(node_color(n->parent) == node::black &&
node_color(n->sibling()) == node::black &&
node_color(n->sibling()->left) == node::black &&
node_color(n->sibling()->right) == node::black) {
n->sibling()->clr = node::red;
delcase1(n->parent);
} else {
delcase4(n);
}
}
void delcase4(node* n) {
_ASSERT(n->sibling() != nullptr);
if(node_color(n->parent) == node::red &&
node_color(n->sibling()) == node::black &&
node_color(n->sibling()->left) == node::black &&
node_color(n->sibling()->right) == node::black) {
n->sibling()->clr = node::red;
n->parent->clr = node::black;
} else {
delcase5(n);
}
}
void delcase5(node* n) {
_ASSERT(n->sibling() != nullptr);
if(n == n->parent->left &&
node_color(n->sibling()) == node::black &&
node_color(n->sibling()->left) == node::red &&
node_color(n->sibling()->right) == node::black) {
n->sibling()->clr = node::red;
n->sibling()->left->clr = node::black;
node_rot_right(n->sibling());
} else if(n == n->parent->right &&
node_color(n->sibling()) == node::black &&
node_color(n->sibling()->left) == node::black &&
node_color(n->sibling()->right) == node::red) {
n->sibling()->clr = node::red;
n->sibling()->right->clr = node::black;
node_rot_left(n->sibling());
}
delcase6(n);
}
void delcase6(node* n) {
n->sibling()->clr = n->parent->clr;
n->parent->clr = node::black;
if(n == n->parent->left) {
_ASSERT(node_color(n->sibling()->right) == node::red);
n->sibling()->right->clr = node::black;
node_rot_left(n->parent);
} else {
_ASSERT(node_color(n->sibling()->left) == node::red);
n->sibling()->left->clr = node::black;
node_rot_right(n->parent);
}
}
void copy_range_map(const myt& copy) {
copy_ranges(copy.begin(), copy.end());
}
void copy_ranges(const_iterator left, const_iterator right) {
while(left != right) {
if(left.endpt()) {
++left;
continue;
}
insert(*left);
++left;
}
}
size_type cur_size;
key_compare comp;
allocator_type all;
std::shared_ptr<node*> root;
};
#endif
|
6/25/2013 5:23:51 PM: 
