Code:
#ifndef POWERSTL_AA_TREE__
#define POWERSTL_AA_TREE__
#include "impl_defs.hpp"
#ifndef POWERSTD_DEBUG_ENABLED__
#define NDEBUG //turn off assertions
#else
#include <cassert>
#endif
#include <boost/move.hpp>
#include <boost/type_traits.hpp>
#include "helper_functions.hpp"
#include "impl_types.hpp"
#include "functional.hpp"
#include "algorithm.hpp"
#include "memory.hpp"
#include "iterator.hpp"
#include "utility.hpp"
#include <cstdint>
namespace powerstd_aa_tree //hide implementation details
{
class aa_node_base
{
public:
aa_node_base *p_parent;
aa_node_base *p_child[2];
int level;
};
template <typename T>
class aa_node : public aa_node_base
{
public:
T value;
};
static aa_node_base null_node = { &null_node, &null_node, &null_node, 0 }; //Is there a way to make this local to each object instance and have iterators work without taking a reference to the null_node?
void skew(aa_node_base *&p_tree, aa_node_base *p_anchor); //modifies p_root
void split(aa_node_base *&p_tree, aa_node_base *p_anchor); //modifies p_root
template <typename Key, typename Value, typename Compare, class Allocator = powerstd::allocator>
class aa_tree
{
public:
typedef Key key_type;
typedef Value value_type;
typedef Allocator allocator_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef powerstl_size_t size_type;
typedef ptrdiff_t difference_type;
typedef aa_tree<Key, Value, Compare, Allocator> this_type;
typedef aa_node_base base_type;
typedef aa_node<value_type> node_type;
static const powerstl_size_t k_node_alignment = DEFAULT_MEMORY_ALIGNMENT; //memory alignment constant
template <typename T, typename Pointer, typename Reference>
class aa_iterator
{
friend class aa_iterator<T, Pointer, Reference>;
friend class aa_tree<Key, Value, Compare, Allocator>;
public:
typedef powerstd::bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
typedef aa_iterator<T, Pointer, Reference> this_type;
typedef T value_type;
typedef Reference reference;
typedef Pointer pointer;
typedef aa_iterator <T, T*, T&> iterator;
typedef aa_iterator <T, const T*, const T&> const_iterator;
typedef aa_node<T> node_type;
typedef aa_node_base base_type;
aa_iterator() : p_node(static_cast<node_type *>(&null_node))
{
}
aa_iterator(node_type *x) : p_node(x)
{
}
aa_iterator(const this_type &x) : p_node(x.p_node)
{
}
reference operator*() const { return p_node->value; }
pointer operator->() const { return &(p_node->value); }
this_type& operator=(const this_type &x)
{
p_node = x.p_node;
return *this;
}
this_type& operator++()
{
if(p_node->p_child[1] != &powerstd_aa_tree::null_node) {
p_node = static_cast<node_type *>(p_node->p_child[1]);
while(p_node->p_child[0] != &powerstd_aa_tree::null_node)
p_node = static_cast<node_type *>(p_node->p_child[0]);
return *this;
}
base_type *p_temp = p_node->p_parent;
while(p_node == p_temp->p_child[1]) {
p_node = static_cast<node_type *>(p_temp);
p_temp = p_temp->p_parent;
}
if(p_node->p_child[1] != p_temp)
p_node = static_cast<node_type *>(p_temp);
return *this;
}
this_type operator++(int32_t )
{
assert(p_node != &null_node);
this_type temp(*this);
++temp;
return temp;
}
this_type& operator--()
{
if(p_node->p_child[0] != &powerstd_aa_tree::null_node) {
p_node = static_cast<node_type *>(p_node->p_child[0]);
while(p_node->p_child[1] != &powerstd_aa_tree::null_node)
p_node = static_cast<node_type *>(p_node->p_child[1]);
return *this;
}
base_type *p_temp = p_node->p_parent;
while(p_node == p_temp->p_child[0]) {
p_node = static_cast<node_type *>(p_temp);
p_temp = p_temp->p_parent;
}
p_node = static_cast<node_type *>(p_temp);
return *this;
}
this_type operator--(int32_t )
{
assert(p_node != NULL);
this_type temp(*this);
--temp;
return temp;
}
bool operator==(const this_type &x) const { return (p_node == x.p_node); }
bool operator!=(const this_type &x) const { return (p_node != x.p_node); }
node_type *p_node;
};
typedef aa_iterator<value_type, value_type*, value_type&> iterator;
typedef aa_iterator<value_type, const value_type*, const value_type&> const_iterator;
typedef powerstd::reverse_iterator<iterator> reverse_iterator;
typedef powerstd::reverse_iterator<const_iterator> const_reverse_iterator;
//Construct/Copy/Destroy
aa_tree()
{
reset();
}
//End Construct/Copy/Destroy
//**********************************************************
//Iterators:
iterator begin() { return iterator(static_cast<node_type *>(anchor.p_child[0])); }
const_iterator begin() const { return const_iterator(static_cast<node_type *>(anchor.p_child[0])); }
iterator end() { return iterator(static_cast<node_type *>(&anchor)); }
const_iterator end() const { return const_iterator(static_cast<node_type *>(&anchor)); }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
const_iterator cbegin() const { return const_iterator(static_cast<node_type *>(anchor.p_child[0])); }
const_iterator cend() const { return const_iterator(static_cast<node_type *>(&anchor)); }
const_reverse_iterator crbegin() const;
const_reverse_iterator crend() const;
//End Iterators
//**********************************************************
//Container modifier methods
iterator find_by_value(const value_type &value)
{
node_type *p_trv = static_cast<node_type *>(anchor.p_parent);
node_type *p_parent = static_cast<node_type *>(&anchor);
//NOTE: TODO: this is a hack for the initial node
if(p_trv->value == value)
return iterator(p_trv);
while(p_trv != &null_node) {
p_parent = p_trv;
p_trv = static_cast<node_type *>(p_trv->p_child[comp(p_trv->value, value)]);
}
if(p_parent != static_cast<node_type *>(&anchor) && p_parent->value == value)
return iterator(p_parent);
return iterator(static_cast<node_type *>(&anchor));
}
iterator insert_duplicate(const value_type &value);
iterator insert_duplicate(iterator position, const value_type &value);
template <class InputIterator> void insert_duplicate(InputIterator first, InputIterator last);
void reset()
{
anchor.level = 0;
anchor.p_parent = &null_node;
anchor.p_child[0] = anchor.p_child[1] = &null_node;
tree_size = 0;
}
protected:
base_type anchor;
Allocator ct_alloc;
Compare comp;
size_type tree_size;
//we don't set p->p_parent here
node_type *create_node()
{
node_type *p = static_cast<node_type *>(ct_alloc.allocate(sizeof(node_type), k_node_alignment));
p->level = 1;
p->p_child[0] = p->p_child[1] = &null_node;
return p;
}
};
//Inserts value into a tree regardless of whether there are duplicates
template <typename Key, typename Value, typename Compare, class Allocator>
typename aa_tree<Key, Value, Compare, Allocator>::iterator
aa_tree<Key, Value, Compare, Allocator>::insert_duplicate(const value_type &value)
{
if(anchor.p_parent != &null_node) {
node_type *p_trv = static_cast<node_type *>(anchor.p_parent);
node_type *p_parent = static_cast<node_type *>(&null_node);
while(p_trv != &null_node) {
p_parent = p_trv;
p_trv = static_cast<node_type *>(p_trv->p_child[comp(p_trv->value, value)]); //>= move to the right
}
node_type *p_node = create_node();
powerstd_helper::construct(&(p_node->value), value);
p_node->p_parent = p_parent;
p_parent->p_child[comp(p_parent->value, value)] = p_node; // >= goes to the right
//The problem is here with the skew and split functions. Chopping this out gives a correct unbalanced BST.
base_type *p_trv2 = static_cast<base_type *>(p_parent);
while(p_trv2 != &null_node) {
skew(p_trv2, &anchor);
split(p_trv2, &anchor);
p_trv2 = p_trv2->p_parent;
}
return iterator(p_node);
}
node_type *p_node = create_node();
powerstd_helper::construct(&(p_node->value), value);
p_node->p_parent = &null_node;
++tree_size;
//set root (p_parent), leftmost (p_child[0]), rightmost (p_child[1])
anchor.p_child[0] = anchor.p_child[1] = anchor.p_parent = static_cast<base_type *>(p_node);
return iterator(p_node);
}
}
#endif
...and here is the aa_tree.cpp file
Code:
#include "aa_tree.hpp"
//maintaining the leftmost and rightmost not done yet
void powerstd_aa_tree::skew(aa_node_base *&p_tree, aa_node_base *p_anchor) //modifies p_root
{
if(p_tree->p_child[0] != &null_node && p_tree->p_child[0]->level == p_tree->level) {
aa_node_base *p_left = p_tree->p_child[0];
//Set the parents of each node
p_left->p_child[1]->p_parent = p_tree;
p_left->p_parent = p_tree->p_parent;
p_tree->p_parent = p_left;
if(p_tree == p_anchor->p_parent)
p_anchor->p_parent = p_left;
//set the nodes
p_tree->p_child[0] = p_left->p_child[1];
p_left->p_child[1] = p_tree;
p_tree = p_left;
}
}
void powerstd_aa_tree::split(aa_node_base *&p_tree, aa_node_base *p_anchor) //modifies p_root
{
if(p_tree != &null_node && p_tree->p_child[1]->p_child[1]->level == p_tree->level) {
aa_node_base *p_right = p_tree->p_child[1];
//Set the parents of each node
p_right->p_child[0]->p_parent = p_tree;
p_right->p_parent = p_tree->p_parent;
p_tree->p_parent = p_right;
if(p_tree == p_anchor->p_parent)
p_anchor->p_parent = p_right;
//set the nodes
p_right->p_child[1] = p_right->p_child[0];
p_right->p_child[0] = p_tree;
p_tree = p_right;
++(p_right->level);
}
}
Some notes: