LinkBack URL
About LinkBacks
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
...and here is the aa_tree.cpp fileCode:#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
Some notes: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); } }
- 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.
