Thread: Help with STL-like AA-tree, skew()/split() problems

Hi,

I wanted to ask for some help regarding my skew() and split() functions.
I am testing this by inserting the numbers 0 through 49, in order, into the tree.
The loop containing the skew() and split() functions goes into an infinite loop at number
6. I have been pulling my hair out trying to figure out what is wrong. When the loop is omitted a correct unbalanced binary search tree is the result. I have attached my code below. I am guessing there is a problem when setting the parent nodes in the skew() and split() functions and possibly a problem when dealing with the null_node when manipulating the parent nodes.

The code:

Here is the aa_tree.hpp file

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:

• The comp function is the same as std::less<int>.
• anchor.p_parent points to the root
• anchor.p_child[0] and anchor.p_child[1] aren't being used yet. I'm trying to get this fixed first.

Any help would be greatly appreciated.