Boost Intrusive/binary search trees

Question

I'm looking for a binary search tree for a Voronoi tessellation algorithm (Fortune's algorithm; a darned non-trivial task in itself, methinks), so of course, I thought I'd have a look at Boost.

Boost has the Intrusive header file, which seems to contain a wealth of BSTs (such as AVL, Splay trees, and Scapegoat trees - ha, I had to make sure of that name there!) and at first sight looked to be just what I needed.

1: Am I missing something or is there no way to directly access the root node of a tree?

2: Is an AVL tree appropriate for the Fortune algorithm beachline structure?

Damn, I thought this was going to be easy.

Update: Perhaps it's better to state what I aim to achieve: I'd like to implement the parabola search that is part of the Fortune algorithm, the part where a new site is detected and we need to find the parabola directly overhead. I thought I would traverse the tree starting from the root, in order to find the correct arc.

Answer 1

In the end I implemented my own AVL tree. The complexity of the Voronoi algorithm seemed to demand it, and the Boost version had no access to the nodes, anyway (if I'm mistaken, please point it out; it's possible, given the obscurity of Boost).

An AVL tree seems to be doing the job perfectly.

Answer 2

 iterator begin();
 const_iterator begin() const;
 const_iterator cbegin() const;

It is a bit unclear, based on the documentation, but it looks like begin() will return the first header node (aka root node).

http://www.dcs.gla.ac.uk/~samm/trees.html

Update

 #include <iostream>
 #include <algorithm>
 #include <boost/intrusive/rbtree.hpp>

 using namespace boost::intrusive;

 struct X  : public set_base_hook<optimize_size<true> > {
    X(int x) : _x{x} { }

    int _x;

    friend inline std::ostream& operator<<(std::ostream&, const X&);
    friend bool operator<(const X&, const X&);
    friend bool operator>(const X&, const X&);
    friend bool operator==(const X&, const X&);
 };

 std::ostream& operator<<( std::ostream& os, const X& x) {
    os << x._x;
    return os;
 }

 bool operator<(const X&  lhs, const X& rhs) { return lhs._x < rhs._x; }
 bool operator>(const X&  lhs, const X& rhs) { return lhs._x > rhs._x; }
 bool operator==(const X& lhs, const X& rhs) { return lhs._x == rhs._x; }

 int main()
 {
    typedef rbtree<X> tree_t;

    tree_t tree;
    X x0(0);
    X x1(1);
    X x2(2);

    /*! Output is the same for the following
    * X x1(1);
    * X x0(0);
    * X x2(2);
    */

    tree.insert_unique(x1);
    tree.insert_unique(x0);
    tree.insert_unique(x2);

    std::for_each(
          tree.begin(), tree.end(),
          [](const X& xx) { std::cout << "x: " << xx << std::endl; });
 }

Output

x: 0 x: 1 x: 2

I noticed that push_back/push_front does not invoke tree re-ordering. Perhaps I missed that in the docs.

Answer 3

Actually looking up root is easier than it sounds.

First, you have to write the usual stuff for using boost::intrusive like hooks, etc.

boost::intrusive::avltree<Object> avl;

If you want to lookup a node in any boost::intrusive, you have to use find(). Now, the find() function requires an overloaded () operator that basically checks if $a>b$ or $b < a$ (very much like the boolean output of strcmp), you want this operator to fail at the root node so it will return the root as the results. One way of doing this would be

class RootComp{
 bool operator () (const Object &a, const int b) const {
        return false;
    }

    bool operator () (int b, const Object &a) const{
        return false;
    }
};

Then using find() is straightforward:

 int data=0;
 boost::intrusive::avltree<Object>::iterator it = avl.find(data, RootComp());
    if( it != avl.end() ){
        //*it is the root
    }else{
       // the tree is empty
    }

Answer 4

Boost.Intrusive tree-like containers have a root() member that returns an iterator to the root node or end() if there is no root node. Those functions were committed a long time ago. The following commit:

https://github.com/boostorg/intrusive/commit/6d38384e369697894bb71fb81132ad60b796c70c

documents those functions, so they are now official. The following code shows how to use it:

#include <boost/intrusive/set.hpp>
#include <cassert>

using namespace boost::intrusive;

struct MyClass : public set_base_hook<>
{
   friend bool operator<(const MyClass&, const MyClass&)
   {  return true;   }
};

int main()
{
   set<MyClass> set;
   //end() is returned when the tree is empty
   assert(set.root()  == set.end() );

   //insert myobject, must be root
   MyClass myobject;
   set.insert(myobject);
   assert(&*set.root() == &myobject);

   //erase and check root is again end()
   set.erase(set.root());
   assert(set.croot() == set.cend());

   return 0;   
}