Page MenuHomec4science
Files F92283484

aka_tree.hh
No OneTemporary
Actions

File Metadata

Created
Tue, Nov 19, 02:19

aka_tree.hh
View Options

/**
* @file aka_tree.hh
*
* @author Alejandro M. Aragón <alejandro.aragon@epfl.ch>
*
* @date creation: Fri Jan 04 2013
* @date last modification: Sun Oct 19 2014
*
* @brief bounding volume hierarchies
*
* @section LICENSE
*
* Copyright (©) 2014, 2015 EPFL (Ecole Polytechnique Fédérale de Lausanne)
* Laboratory (LSMS - Laboratoire de Simulation en Mécanique des Solides)
*
* Akantu is free software: you can redistribute it and/or modify it under the
* terms of the GNU Lesser General Public License as published by the Free
* Software Foundation, either version 3 of the License, or (at your option) any
* later version.
*
* Akantu is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
* A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
* details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with Akantu. If not, see <http://www.gnu.org/licenses/>.
*
*/
/* -------------------------------------------------------------------------- */
#ifndef __AKANTU_TREE_HH__
#define __AKANTU_TREE_HH__
#include <cassert>
#include <queue>
#include <set>
#include <iomanip>
//#include <limits>
#include "aka_ball.hh"
#include "aka_bounding_box.hh"
#include "aka_array.hh"
//#define DEBUG_TREE 1
__BEGIN_AKANTU__
using std::cout;
using std::endl;
struct Tree_node_base
{
typedef Tree_node_base* base_ptr;
typedef const Tree_node_base* const_base_ptr;
base_ptr parent_;
base_ptr left_;
base_ptr right_;
static base_ptr _minimum(base_ptr x) {
while (x->left_ != 0) x = x->left_;
return x;
}
static const_base_ptr _minimum(const_base_ptr x) {
while (x->left_ != 0) x = x->left_;
return x;
}
static base_ptr _maximum(base_ptr x) {
while (x->right_ != 0) x = x->right_;
return x;
}
static const_base_ptr _maximum(const_base_ptr x) {
while (x->right_ != 0) x = x->right_;
return x;
}
};
template<typename T>
struct Tree_node : public Tree_node_base
{
typedef T value_tpe;
typedef Tree_node<value_tpe>* link_type;
value_tpe value_;
template<typename... Args>
Tree_node(Args&&... args)
: Tree_node_base(), value_(std::forward<Args>(args)...) { }
};
// iterators
static Tree_node_base* local_leaf_increment(Tree_node_base* x) throw () {
Tree_node_base* y = x->parent_;
if (y->parent_ == x)
return y;
while (x == y->right_) {
x = y;
y = y->parent_;
}
if (y->parent_ == x)
return y;
if (x->right_ != y)
x = y;
if (x->right_ != 0) {
x = x->right_;
while (x->left_ != 0)
x = x->left_;
}
return x;
}
template <class tree_pointer>
tree_pointer* _tree_leaf_increment(tree_pointer* x) throw ()
{ return local_leaf_increment(x); }
template <class tree_pointer>
const tree_pointer* _tree_leaf_increment(const tree_pointer* x) throw ()
{ return local_leaf_increment(const_cast<tree_pointer*>(x)); }
template<typename _Tp>
struct Tree_leaf_iterator
{
typedef _Tp value_type;
typedef _Tp& reference;
typedef _Tp* pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
typedef Tree_leaf_iterator<_Tp> self_type;
typedef Tree_node_base::base_ptr base_ptr;
typedef Tree_node<_Tp>* link_type;
Tree_leaf_iterator() : node_() { }
explicit Tree_leaf_iterator(link_type x) : node_(x) { }
reference operator*() const
{ return static_cast<link_type>(node_)->value_; }
pointer operator->() const
{ return std::__addressof(static_cast<link_type>(node_)->value_); }
self_type& operator++() {
node_ = _tree_leaf_increment(node_);
return *this;
}
self_type operator++(int) {
self_type tmp = *this;
node_ = _tree_leaf_increment(node_);
return tmp;
}
bool operator==(const self_type& x) const
{ return node_ == x.node_; }
bool operator!=(const self_type& x) const
{ return node_ != x.node_; }
bool operator<(const self_type& x) const
{ return node_ < x.node_; }
base_ptr node_;
};
template<typename _Tp>
struct Tree_leaf_const_iterator
{
typedef _Tp value_type;
typedef const _Tp& reference;
typedef const _Tp* pointer;
typedef Tree_leaf_iterator<_Tp> iterator;
typedef std::bidirectional_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
typedef Tree_leaf_const_iterator<_Tp> self_type;
typedef Tree_node_base::const_base_ptr base_ptr;
typedef const Tree_node<_Tp>* link_type;
Tree_leaf_const_iterator() : node_() { }
explicit Tree_leaf_const_iterator(link_type x) : node_(x) { }
Tree_leaf_const_iterator(const iterator& it) : node_(it.node_) { }
iterator _const_cast() const
{ return iterator(static_cast<typename iterator::link_type>(const_cast<typename iterator::base_ptr>(node_))); }
reference operator*() const
{ return static_cast<link_type>(node_)->value_; }
pointer operator->() const
{ return std::__addressof(static_cast<link_type>
(node_)->value_); }
self_type& operator++() {
node_ = _tree_leaf_increment(node_);
return *this;
}
self_type operator++(int) {
self_type tmp = *this;
node_ = _tree_leaf_increment(node_);
return tmp;
}
bool operator==(const self_type& x) const
{ return node_ == x.node_; }
bool operator!=(const self_type& x) const
{ return node_ != x.node_; }
bool operator<(const self_type& x) const
{ return node_ < x.node_; }
base_ptr node_;
};
template<typename _Val>
inline bool operator==(const Tree_leaf_iterator<_Val>& x,
const Tree_leaf_const_iterator<_Val>& y)
{ return x.node_ == y.node_; }
template<typename _Val>
inline bool operator!=(const Tree_leaf_iterator<_Val>& x,
const Tree_leaf_const_iterator<_Val>& y)
{ return x.node_ != y.node_; }
template <class tree_pointer>
static tree_pointer*
local_tree_increment(tree_pointer* x) throw ()
{
if (x->right_ != 0)
{
x = x->right_;
while (x->left_ != 0)
x = x->left_;
}
else
{
tree_pointer* y = x->parent_;
while (x == y->right_)
{
x = y;
y = y->parent_;
}
if (x->right_ != y)
x = y;
}
return x;
}
template <class tree_pointer>
tree_pointer* _tree_increment(tree_pointer* x) throw ()
{ return local_tree_increment(x); }
template <class tree_pointer>
const tree_pointer*
_tree_increment(const tree_pointer* x) throw ()
{ return local_tree_increment(const_cast<tree_pointer*>(x)); }
template <class tree_pointer>
static tree_pointer*
local_tree_decrement(tree_pointer* x) throw () {
if (x->parent_->parent_ == x)
x = x->right_;
else if (x->left_ != 0) {
Tree_node_base* y = x->left_;
while (y->right_ != 0)
y = y->right_;
x = y;
}
else {
tree_pointer* y = x->parent_;
while (x == y->left_) {
x = y;
y = y->parent_;
}
x = y;
}
return x;
}
template <class tree_pointer>
tree_pointer* _tree_decrement(tree_pointer* x) throw ()
{ return local_tree_decrement(x); }
template <class tree_pointer>
const tree_pointer* _tree_decrement(const tree_pointer* x) throw ()
{ return local_tree_decrement(const_cast<tree_pointer*>(x)); }
// iterators
template<typename _Tp>
struct Tree_iterator
{
typedef _Tp value_type;
typedef _Tp& reference;
typedef _Tp* pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
typedef Tree_iterator<_Tp> self_type;
typedef Tree_node_base::base_ptr base_ptr;
typedef Tree_node<_Tp>* link_type;
typedef Tree_leaf_iterator<value_type> leaf_iterator;
Tree_iterator() : node_() { }
explicit Tree_iterator(link_type x) : node_(x) { }
Tree_iterator(const leaf_iterator& it) : node_(it.node_) { }
reference operator*() const
{ return static_cast<link_type>(node_)->value_; }
pointer operator->() const
{ return std::__addressof(static_cast<link_type>(node_)->value_); }
self_type& operator++() {
node_ = _tree_increment(node_);
return *this;
}
self_type operator++(int) {
self_type tmp = *this;
node_ = _tree_increment(node_);
return tmp;
}
self_type& operator--() {
node_ = _tree_decrement(node_);
return *this;
}
self_type operator--(int) {
self_type tmp = *this;
node_ = _tree_decrement(node_);
return tmp;
}
self_type left()
{ return self_type(static_cast<link_type>(node_->left_)); }
self_type right()
{ return self_type(static_cast<link_type>(node_->right_)); }
self_type parent()
{ return self_type(static_cast<link_type>(node_->parent_)); }
bool is_leaf() {
assert(node_ != nullptr);
return node_->left_ == nullptr && node_->right_ == nullptr;
}
bool operator==(const self_type& x) const
{ return node_ == x.node_; }
bool operator!=(const self_type& x) const
{ return node_ != x.node_; }
bool operator<(const self_type& x) const
{ return node_ < x.node_; }
base_ptr node_;
};
template<typename _Tp>
struct Tree_const_iterator
{
typedef _Tp value_type;
typedef const _Tp& reference;
typedef const _Tp* pointer;
typedef Tree_iterator<_Tp> iterator;
typedef std::bidirectional_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
typedef Tree_const_iterator<_Tp> self_type;
typedef Tree_node_base::const_base_ptr base_ptr;
typedef const Tree_node<_Tp>* link_type;
Tree_const_iterator() : node_() { }
explicit Tree_const_iterator(link_type x) : node_(x) { }
Tree_const_iterator(const iterator& it) : node_(it.node_) { }
iterator _const_cast() const
{ return iterator(static_cast<typename iterator::link_type>(const_cast<typename iterator::base_ptr>(node_))); }
reference operator*() const
{ return static_cast<link_type>(node_)->value_; }
pointer operator->() const
{ return std::__addressof(static_cast<link_type>
(node_)->value_); }
self_type& operator++() {
node_ = _tree_increment(node_);
return *this;
}
self_type operator++(int) {
self_type tmp = *this;
node_ = _tree_increment(node_);
return tmp;
}
self_type& operator--() {
node_ = _tree_decrement(node_);
return *this;
}
self_type operator--(int) {
self_type tmp = *this;
node_ = _tree_decrement(node_);
return tmp;
}
self_type left()
{ return self_type(static_cast<link_type>(node_->left_)); }
self_type right()
{ return self_type(static_cast<link_type>(node_->right_)); }
self_type parent()
{ return self_type(static_cast<link_type>(node_->parent_)); }
bool is_leaf() {
assert(node_ != nullptr);
return node_->left_ == nullptr && node_->right_ == nullptr;
}
bool operator==(const self_type& x) const
{ return node_ == x.node_; }
bool operator!=(const self_type& x) const
{ return node_ != x.node_; }
bool operator<(const self_type& x) const
{ return node_ < x.node_; }
base_ptr node_;
};
template<typename _Val>
inline bool operator==(const Tree_iterator<_Val>& x,
const Tree_const_iterator<_Val>& y)
{ return x.node_ == y.node_; }
template<typename _Val>
inline bool operator!=(const Tree_iterator<_Val>& x,
const Tree_const_iterator<_Val>& y)
{ return x.node_ != y.node_; }
// traversal
template <class iterator_type, class functor_type>
void inorder(iterator_type it, functor_type& fn) {
if (it.node_ == nullptr)
return;
inorder(it.left(), fn);
fn(it);
inorder(it.right(), fn);
}
template <class iterator_type, class functor_type>
void preorder(iterator_type it, functor_type& fn) {
if (it.node_ == nullptr)
return;
fn(it);
preorder(it.left(), fn);
preorder(it.right(), fn);
}
template <class iterator_type, class functor_type>
void postorder(iterator_type it, functor_type& fn) {
if (it.node_ == nullptr)
return;
postorder(it.left(), fn);
postorder(it.right(), fn);
fn(it);
}
//! Tree class
template<typename T, template <class> class _Cost, typename _Alloc = std::allocator<T> >
class Tree
{
typedef typename _Alloc::template rebind<Tree_node<T> >::other
_Node_allocator;
protected:
typedef Tree_node_base* base_ptr;
typedef const Tree_node_base* const_base_ptr;
public:
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef Tree_node<T>* link_type;
typedef const Tree_node<T>* const_link_type;
typedef size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef _Cost<value_type> cost_functor;
typedef _Alloc allocator_type;
_Node_allocator& _get_Node_allocator()
{ return *static_cast<_Node_allocator*>(&this->impl_); }
const _Node_allocator& _get_Node_allocator() const
{ return *static_cast<const _Node_allocator*>(&this->impl_); }
allocator_type
get_allocator() const
{ return allocator_type(_get_Node_allocator()); }
private:
link_type _get_node()
{ return impl_._Node_allocator::allocate(1); }
void _put_node(link_type p)
{ impl_._Node_allocator::deallocate(p, 1); }
void _destroy_node(link_type p) {
_get_Node_allocator().destroy(p);
_put_node(p);
}
link_type _clone_node(const_link_type x) {
link_type tmp = _create_node(x->value_);
tmp->left_ = 0;
tmp->right_ = 0;
return tmp;
}
template<typename... _Args>
link_type _create_node(_Args&&... args) {
link_type tmp = _get_node();
try {
_get_Node_allocator().construct(tmp, std::forward<_Args>(args)...);
tmp->left_ = 0;
tmp->right_ = 0;
tmp->parent_ = 0;
}
catch(...) {
_put_node(tmp);
throw;
}
return tmp;
}
private:
template<typename _Cost_functor>
struct Tree_impl : public _Node_allocator
{
_Cost_functor cost_;
Tree_node_base header_;
size_type node_count_; // Keeps track of size of tree.
Tree_impl()
: _Node_allocator(), cost_(), header_(),
node_count_(0)
{ _M_initialize(); }
Tree_impl(const _Cost_functor& comp, const _Node_allocator& a)
: _Node_allocator(a), cost_(comp), header_(),
node_count_(0)
{ _M_initialize(); }
Tree_impl(const _Cost_functor& comp, _Node_allocator&& a)
: _Node_allocator(std::move(a)), cost_(comp),
header_(), node_count_(0)
{ _M_initialize(); }
private:
void
_M_initialize()
{
this->header_.parent_ = 0;
this->header_.left_ = &this->header_;
this->header_.right_ = &this->header_;
}
};
private:
Tree_impl<cost_functor> impl_; //!< Tree implementation instance
base_ptr& _root()
{ return this->impl_.header_.parent_; }
const_base_ptr _root() const
{ return this->impl_.header_.parent_; }
base_ptr& _leftmost()
{ return this->impl_.header_.left_; }
const_base_ptr _leftmost() const
{ return this->impl_.header_.left_; }
base_ptr& _rightmost()
{ return this->impl_.header_.right_; }
const_base_ptr _rightmost() const
{ return this->impl_.header_.right_; }
link_type _begin()
{ return static_cast<link_type>(this->impl_.header_.parent_); }
const_link_type _begin() const
{ return static_cast<const_link_type>(this->impl_.header_.parent_); }
link_type _end()
{ return static_cast<link_type>(&this->impl_.header_); }
const_link_type _end() const
{ return static_cast<const_link_type>(&this->impl_.header_); }
static reference _value(link_type x)
{ return x->value_; }
static const_reference _value(const_link_type x)
{ return x->value_; }
static reference _value(base_ptr x)
{ return static_cast<link_type>(x)->value_; }
static const_reference _value(const_base_ptr x)
{ return static_cast<const_link_type>(x)->value_; }
static link_type _left(base_ptr x)
{ return static_cast<link_type>(x->left_); }
static const_link_type _left(const_base_ptr x)
{ return static_cast<const_link_type>(x->left_); }
static link_type _right(base_ptr x)
{ return static_cast<link_type>(x->right_); }
static const_link_type _right(const_base_ptr x)
{ return static_cast<const_link_type>(x->right_); }
static link_type _parent(base_ptr x)
{ return static_cast<link_type>(x->parent_); }
static const_link_type _parent(const_base_ptr x)
{ return static_cast<const_link_type>(x->parent_); }
void _erase(link_type x) {
while (x != 0)
{
#ifdef DEBUG_TREE
cout<<"pointer x -> "<<x<<endl;
cout<<"calling erase on right -> "<<_right(x)<<endl;
cout<<"destroying node -> "<<_value(x)<<endl;
cout<<"setting x to left -> "<<_left(x)<<endl;
#endif
_erase(_right(x));
link_type y = _left(x);
_destroy_node(x);
--impl_.node_count_; // decrement nodes
x = y;
}
}
link_type _copy(const_link_type x, link_type p) {
link_type top = _clone_node(x);
top->parent_ = p;
try
{
if (x->right_)
top->right_ = _copy(_right(x), top);
p = top;
x = _left(x);
while (x != 0)
{
link_type y = _clone_node(x);
p->left_ = y;
y->parent_ = p;
if (x->right_)
y->right_ = _copy(_right(x), y);
p = y;
x = _left(x);
}
}
catch(...)
{
_erase(top);
throw;
}
return top;
}
void _check_integrity(link_type x) {
while (x != 0) {
link_type r = _right(x);
if (r)
if (r->parent_ != x) {
cout<<"*** ERROR *** Integrity check failed"<<endl;
cout<<"Right child parent mismatch"<<endl;
exit(1);
}
link_type l = _left(x);
if (l)
if (l->parent_ != x) {
cout<<"*** ERROR *** Integrity check failed"<<endl;
cout<<"Left child parent mismatch"<<endl;
exit(1);
}
_check_integrity(r);
x = _left(x);
}
}
public:
typedef Tree_iterator<value_type> iterator;
typedef Tree_const_iterator<value_type> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef Tree_leaf_iterator<value_type> leaf_iterator;
typedef Tree_leaf_const_iterator<value_type> const_leaf_iterator;
// allocation/deallocation
Tree() {}
Tree(const cost_functor& cost, const allocator_type& a = allocator_type())
: impl_(cost, _Node_allocator(a)) { }
Tree(const Tree& x) : impl_(x.impl_.cost_, x._get_Node_allocator())
{
if (x._root() != 0)
{
_root() = _copy(x._begin(), _end());
_leftmost() = Tree_node_base::_minimum(_root());
_rightmost() = Tree_node_base::_maximum(_root());
impl_.node_count_ = x.impl_.node_count_;
}
}
//! construct a tree from link type, defined by the user in any way
Tree(link_type x) {
// integrity check
_check_integrity(x);
if (x) _insert(0,x);
}
~Tree() noexcept
{ _erase(_begin()); }
const cost_functor& cost() const
{ return impl_.cost_; }
void clear() noexcept
{
_erase(_begin());
_leftmost() = _end();
_root() = 0;
_rightmost() = _end();
// assert count == 0, _erase should take care of decrementing the node count
assert(impl_.node_count_ == 0);
// impl_.node_count_ = 0;
}
iterator begin()
{ return iterator(static_cast<link_type>(this->impl_.header_.left_)); }
const_iterator begin() const
{ return const_iterator(static_cast<const_link_type>(this->impl_.header_.left_)); }
iterator end()
{ return iterator(static_cast<link_type>(&this->impl_.header_)); }
const_iterator end() const
{ return const_iterator(static_cast<const_link_type>(&this->impl_.header_)); }
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()); }
leaf_iterator leaves_begin()
{ return leaf_iterator(static_cast<link_type>(impl_.header_.left_)); }
const_leaf_iterator leaves_begin() const
{ return const_leaf_iterator(static_cast<const_link_type>(impl_.header_.left_)); }
leaf_iterator leaves_end()
{ return leaf_iterator(static_cast<link_type>(&impl_.header_)); }
const_leaf_iterator leaves_end() const
{ return const_leaf_iterator(static_cast<const_link_type>(&impl_.header_)); }
iterator root()
{ return iterator(static_cast<link_type>(impl_.header_.parent_)); }
const_iterator root() const
{ return const_iterator(static_cast<const_link_type>(impl_.header_.parent_)); }
bool empty() const
{ return impl_.node_count_ == 0; }
size_type size() const
{ return impl_.node_count_; }
size_type max_size() const
{ return _get_Node_allocator().max_size(); }
std::tuple<size_t, size_t, size_t> height() const {
size_t count = 0;
size_t min = std::numeric_limits<size_t>::max();
size_t max = 0;
size_t h = 0;
for (const_leaf_iterator it = leaves_begin(); it != leaves_end(); ++it) {
const_base_ptr x = it.node_;
size_t h1 = 0;
while (x->parent_ != _end()) {
++h1;
x = x->parent_;
}
min = std::min(min, h1);
max = std::max(max, h1);
++count;
h += h1;
}
return std::make_tuple(h/count, min, max);
}
private:
void _add_level(std::queue<link_type>& q, base_ptr x, size_t h, size_t level) {
if (h < level) {
if (x->left_ != 0) _add_level(q, x->left_, h+1, level);
if (x->right_ != 0) _add_level(q, x->right_, h+1, level);
}
else if (h == level)
q.push(static_cast<link_type>(x));
else
return;
}
iterator _insert(base_ptr l, base_ptr r, bool count = true) {
#ifdef DEBUG_TREE
cout<<"inside inserting two for iterators"<<endl;
cout<<"left pointer "<<l<<endl;
if (l)
cout<<"left "<<_value(l)<<endl;
cout<<"right pointer "<<r<<endl;
cout<<"right "<<_value(r)<<endl;
#endif
// set parent to header to count nodes
link_type p = _end();
r->parent_ = p;
// get left most
base_ptr lt = r;
while (lt->left_ != 0)
lt = lt->left_;
#ifdef DEBUG_TREE
cout<<"left most -> "<<_value(lt)<<endl;
#endif
// count nodes
if (count)
for (iterator it(static_cast<link_type>(lt)); it != end(); ++it)
++impl_.node_count_;
// get right most
base_ptr rt = r;
while (rt->right_ != 0)
rt = rt->right_;
// if l is not null, create a new node
link_type lr = static_cast<link_type>(r);
if (l) {
auto vp = impl_.cost_(_value(l),_value(r));
lr = _create_node(vp);
++impl_.node_count_;
p = _parent(l);
lr->parent_ = p;
lr->right_ = r;
lr->left_ = l;
r->parent_ = lr;
l->parent_ = lr;
} else
_leftmost() = lt;
// fix header
if (lr->parent_ == _end()) {
_root() = lr;
_rightmost() = rt;
} else {
// fix parent pointers
if (p->right_ == l)
p->right_ = lr;
else if (p->left_ == l)
p->left_ = lr;
}
// recursively fix parents
auto fix = _value(lr);
while (lr->parent_ != _end()) {
p = _parent(lr);
fix = impl_.cost_(_value(p), fix);
p->value_ = fix;
lr = p;
}
return iterator(static_cast<link_type>(r));
}
bool _is_leaf(const_base_ptr x) const
{ assert(x != nullptr); return (_right(x) == nullptr) && (_left(x) == nullptr); }
public:
struct _Queue_compare {
// pointer - ancestor expansion - best cost tuples
typedef std::tuple<link_type, Real, Real> tuple_type;
bool operator()(const tuple_type& t1, const tuple_type& t2) const
{ return std::get<1>(t1) > std::get<1>(t2); }
};
//! Adapted from Omohundro:89 routine best_sib
template <typename Arg>
iterator best_sibling(Arg&& v) {
#ifdef DEBUG_TREE
cout<<"--------------------"<<endl;
cout<<"inserting "<<v<<endl;
#endif
typedef typename _Queue_compare::tuple_type tuple_type;
typedef typename std::priority_queue<tuple_type, std::vector<tuple_type>, _Queue_compare> queue_type;
// set result to root
link_type result = _begin();
// check for empty tree
if (!result)
return iterator(nullptr);
// check for leaf node
else if (_is_leaf(result))
return iterator(result);
// compute combined cost
Real bcost = impl_.cost_(impl_.cost_(v, _value(result)));
#ifdef DEBUG_TREE
cout<<"root -> "<<_value(result)<<endl;
cout<<"bcost -> "<<bcost<<endl;
#endif
// start the queue
queue_type q;
decltype(impl_.cost_(v)) e, c;
q.push(std::make_tuple(result, 0., bcost));
// while queue is not empty
while (!q.empty()) {
// best candidate
auto t = q.top();
auto nd = std::get<0>(t);
auto aexp = std::get<1>(t);
auto ndvol = std::get<2>(t);
// remove top most element
q.pop();
#ifdef DEBUG_TREE
cout<<" inside while"<<endl;
cout<<" top queue item "<<_value(nd)<<endl;
#endif
// no way to get better than bnd
if (aexp >= bcost) {
#ifdef DEBUG_TREE
cout<<"*** BREAKING"<<endl;
#endif
break;
}
// new ancestor expansion
e = aexp + ndvol - impl_.cost_(_value(nd));
#ifdef DEBUG_TREE
cout<<" a exp "<<e<<endl;
cout<<" bcost "<<bcost<<endl;
cout<<" cost x "<<impl_.cost_(_value(nd))<<endl;
cout<<" e -> "<<e<<endl;
#endif
// do left node
c = impl_.cost_(impl_.cost_(v, _value(nd->left_)));
#ifdef DEBUG_TREE
cout<<" c left -> "<<c<<endl;
#endif
if (c+e <= bcost) {
bcost = c+e;
result = _left(nd);
#ifdef DEBUG_TREE
cout<<" c+e < bcost!!! result set to left "<<_value(result)<<endl;
#endif
}
if(!_is_leaf(nd->left_))
q.push(std::make_tuple(_left(nd), e, c));
// do right node
c = impl_.cost_(impl_.cost_(v, _value(nd->right_)));
#ifdef DEBUG_TREE
cout<<" c right -> "<<c<<endl;
#endif
if (c+e <= bcost) {
bcost = c+e;
result = _right(nd);
#ifdef DEBUG_TREE
cout<<" c+e < bcost!!! result set to right "<<_value(result)<<endl;
#endif
}
if(!_is_leaf(nd->right_))
q.push(std::make_tuple(_right(nd), e, c));
} // while queue is not empty
#ifdef DEBUG_TREE
cout<<"best sibling -> "<<_value(result)<<endl;
#endif
return iterator(result);
}
//! Adapted from Omohundro:89 routine cheap_best_sib
template <typename Arg>
iterator cheap_best_sibling(Arg&& v) {
#ifdef DEBUG_TREE
cout<<"--------------------"<<endl;
cout<<"inserting "<<v<<endl;
#endif
link_type x = _begin();
if (!x)
return iterator(nullptr);
#ifdef DEBUG_TREE
cout<<"root -> "<<_value(x)<<endl;
#endif
link_type result = x;
// compute combined cost
Real wv = impl_.cost_(v, _value(x));
// node vol + ancestor expansion
Real bcost = wv;
// ancestor expansion starts at zero
Real ae = 0;
#ifdef DEBUG_TREE
cout<<"bcost -> "<<bcost<<endl;
#endif
// while not a leaf node
while (x->left_ && x->right_) {
#ifdef DEBUG_TREE
cout<<" inside while"<<endl;
#endif
auto nd = impl_.cost_(_value(x));
// correct for both children
ae += wv - nd;
#ifdef DEBUG_TREE
cout<<" top queue item "<<_value(x)<<endl;
cout<<" a exp "<<ae<<endl;
cout<<" bcost "<<bcost<<endl;
cout<<" cost x "<<nd<<endl;
cout<<" e -> "<<ae<<endl;
#endif
// cannot do any better, insert the volumes in the tree
if (ae >= bcost)
break;
else {
auto lv = impl_.cost_(v, _value(x->left_));
auto rv = impl_.cost_(v, _value(x->right_));
#ifdef DEBUG_TREE
cout<<" c left -> "<<lv<<endl;
#endif
if (ae + lv <= bcost) {
bcost = ae + lv;
result = _left(x);
#ifdef DEBUG_TREE
cout<<" c+e < bcost!!! result set to left "<<_value(_left(x))<<endl;
#endif
}
#ifdef DEBUG_TREE
cout<<" c right -> "<<rv<<endl;
#endif
if (ae + rv <= bcost) {
bcost = ae + rv;
result = _right(x);
#ifdef DEBUG_TREE
cout<<" c+e < bcost!!! result set to right "<<_value(_right(x))<<endl;
#endif
}
// if left branch expands less
if (lv - impl_.cost_(_value(x->left_)) <=
rv - impl_.cost_(_value(x->right_))) {
wv = lv;
x = _left(x);
} else {
wv = rv;
x = _right(x);
}
}
} // while loop
#ifdef DEBUG_TREE
cout<<"best sibling -> "<<_value(result)<<endl;
#endif
return iterator(result);
}
private:
template <class functor_type>
void _execute_at_leaves(iterator x, std::set<base_ptr>& visited, functor_type& fn) {
auto it = visited.find(x.node_);
if (it != visited.end())
return;
visited.insert(x.node_);
if (x.is_leaf())
fn(x);
else {
if (x.node_->left_ != 0) _execute_at_leaves(iterator(static_cast<link_type>(x.node_->left_)), visited, fn);
if (x.node_->right_ != 0) _execute_at_leaves(iterator(static_cast<link_type>(x.node_->right_)), visited, fn);
}
}
public:
//! Collect neighbors
/*! This function is used to collect neighbors from a tree given a functor.
* The functor should implement a parameterless and a one-parameter operator() overloads.
* The first load is used as the predicate to finish the search of neighbors, whereas
* the second one is executed at leaves.
*/
template <class functor_type>
void collect_neighbors(iterator it, functor_type& fn) {
// check for null ptr
if (it.node_ == nullptr)
return;
std::set<base_ptr> visited;
base_ptr p = it.node_;
// execute while predicate is not true
while (!fn()) {
p = p->parent_;
// root node
if (p == _root()->parent_)
break;
_execute_at_leaves(iterator(static_cast<link_type>(p)), visited, fn);
}
}
template <typename Arg>
std::pair<iterator,bool> cheap_insert(Arg&& v) {
iterator it = cheap_best_sibling(v);
link_type r = _create_node(v);
return std::pair<iterator, bool>(_insert(it.node_, r), true);
}
template <typename Arg>
std::pair<iterator,bool> insert(Arg&& v) {
iterator it = best_sibling(v);
link_type r = _create_node(v);
return std::pair<iterator, bool>(_insert(it.node_, r), true);
}
std::pair<iterator,bool> insert(link_type x)
{ return insert(iterator(x)); }
std::pair<iterator,bool> insert(iterator vit) {
iterator it = best_sibling(_value(vit.node_));
return std::pair<iterator, bool>(_insert(it.node_, vit.node_), true);
}
iterator sibling(iterator it) {
base_ptr x = it.node_;
if (!x)
return iterator(nullptr);
if (x == _root())
return end();
base_ptr p = x->parent_;
assert (p != 0);
if (p->left_ == x)
return iterator(_right(p));
return iterator(_left(p));
}
public:
iterator relocate_parent(iterator it) {
#if DEBUG_TREE
if (it.node_)
cout<<"relocating node "<<_value(it.node_)<<endl;
#endif
link_type x = static_cast<link_type>(it.node_);
// null pointer
if (!x)
return end();
// get parent
link_type p = _parent(x);
// if parent is header return root
if (p == _end())
return iterator(_begin());
// get grand-parent
link_type gp = _parent(p);
// no need to recompute volume as the parent has
// the enclosing volume of its children
// sibling
link_type s = x == p->left_ ? _right(p) : _left(p);
#ifdef DEBUG_TREE
cout<<"relocating x -> "<<_value(x)<<endl;
cout<<"parent of node -> "<<_value(p)<<endl;
cout<<"sibling -> "<<_value(s)<<endl;
#endif
if (gp == _end()) {
#ifdef DEBUG_TREE
cout<<"*** WARNING *** sibling new parent is the header!"<<endl;
#endif
_root() = s;
} else if (gp->left_ == p) {
gp->left_ = s;
#ifdef DEBUG_TREE
cout<<"setting parent->parent->left to sibling"<<endl;
#endif
}
else if (gp->right_ == p) {
gp->right_ = s;
#ifdef DEBUG_TREE
cout<<"setting parent->parent->right to sibling"<<endl;
#endif
} else
assert(false);
// set parent of sibling
s->parent_ = p->parent_;
// recursively fix parents
link_type r = _parent(s);
while (r != _end()) {
r->value_ = impl_.cost_(_value(r->right_), _value(r->left_));
r = _parent(r);
}
// destroy parent node p and reinsert x into the tree
x->parent_ = 0;
p->parent_ = 0;
p->left_ = 0;
p->right_ = 0;
_erase(p);
// get the best sibling
iterator bit = best_sibling(_value(x));
#ifdef DEBUG_TREE
cout<<"best sibling for relocation -> "<<bit.node_<<endl;
if (it.node_)
cout<<" best sibling value -> "<<_value(bit.node_)<<endl;
#endif
iterator result = _insert(bit.node_, x, false);
// set leftmost and rightmost
base_ptr lt = _root();
while (lt->left_ != 0)
lt = lt->left_;
_leftmost() = lt;
base_ptr rt = _root();
while (rt->right_ != 0)
rt = rt->right_;
_rightmost() = rt;
return result;
}
iterator erase(iterator it) {
link_type x = static_cast<link_type>(it.node_);
// null pointer
if (!x)
return end();
// root node
else if (x == _root()) {
clear();
return end();
}
link_type p = _parent(x);
link_type s; // sibling
if (x == p->left_) {
s = _right(p);
p->right_ = 0; // set to zero to use erase
} else {
s = _left(p);
p->left_ = 0;
}
#ifdef DEBUG_TREE
cout<<"erasing x -> "<<_value(x)<<endl;
cout<<"parent of node -> "<<_value(p)<<endl;
cout<<"sibling -> "<<_value(s)<<endl;
#endif
if (_leftmost() == x) {
base_ptr l = s;
while (l->left_ != 0)
l = l->left_;
_leftmost() = l;
#ifdef DEBUG_TREE
cout<<"x is leftmost, so setting leftmost to "<<_value(l)<<endl;
#endif
} if (_rightmost() == x) {
base_ptr r = s;
while (r->right_ != 0)
r = r->right_;
_rightmost() = r;
#ifdef DEBUG_TREE
cout<<"x is rightmost, so setting rightmost to "<<_value(r)<<endl;
#endif
}
s->parent_ = p->parent_;
if (p->parent_ == _end()) {
#ifdef DEBUG_TREE
cout<<"*** WARNING *** sibling new parent is the header!"<<endl;
#endif
_root() = s;
} else if (p->parent_->left_ == p) {
p->parent_->left_ = s;
#ifdef DEBUG_TREE
cout<<"setting parent->parent->left to sibling"<<endl;
#endif
}
else {
p->parent_->right_ = s;
#ifdef DEBUG_TREE
cout<<"setting parent->parent->right to sibling"<<endl;
#endif
}
#ifdef DEBUG_TREE
cout<<"p right -> "<<p->right_<<endl;
cout<<"p left -> "<<p->left_<<endl;
if (p->right_)
cout<<"p right value -> "<<_value(p->right_)<<endl;
if (p->left_)
cout<<"p left value -> "<<_value(p->left_)<<endl;
#endif
// recursively fix parents
link_type r = _parent(s);
while (r != _end()) {
r->value_ = _value(r->right_) + _value(r->left_);
r = _parent(r);
}
// erase subtree rooted at p
_erase(p);
return iterator(s);
}
Real volume() const {
Real v = 0;
for (const_iterator it = begin(); it != end(); ++it)
v += it->measure();
return v;
}
friend std::ostream& operator<<(std::ostream& os, const Tree& t) {
os<<"Tree: count "<<t.impl_.node_count_<<endl;
os<<" header: "<<&t.impl_.header_<<endl;
if (t.impl_.header_.parent_)
os<<" ROOT: "<<t.impl_.header_.parent_<<", value "<<_value(t.impl_.header_.parent_)<<endl;
os<<" left: "<<t.impl_.header_.left_<<endl;
os<<" right: "<<t.impl_.header_.right_<<endl;
size_t c = 0;
Real v = 0;
os<<endl;
for (Tree::const_iterator it = t.begin(); it != t.end(); ++it, ++c) {
Real cost = t.impl_.cost_(*it);
if (it.node_ == t.impl_.header_.parent_) {
os<<" ROOT "<<it.node_;
if (it.node_ == t._leftmost())
os<<" [LEFTMOST]";
if (it.node_ == t._rightmost())
os<<" [RIGHTMOST]";
os<<"\n value: "<<*it<<endl;
os<<" parent: "<<it.node_->parent_<<endl;
} else {
os<<" pointer "<<it.node_;
if (it.node_ == t._leftmost())
os<<" [LEFTMOST]";
if (it.node_ == t._rightmost())
os<<" [RIGHTMOST]";
os<<"\n value: "<<*it<<endl;
os<<" parent: "<<it.node_->parent_<<", value "<<_value(it.node_->parent_)<<endl;
}
if (it.node_->left_)
os<<" left: "<<it.node_->left_<<", value "<<_value(it.node_->left_)<<endl;
if (it.node_->right_)
os<<" right: "<<it.node_->right_<<", value "<<_value(it.node_->right_)<<endl;
if (!it.node_->left_ && !it.node_->right_)
os<<" leaf"<<endl;
os<<" cost: "<<cost<<endl;
os<<endl;
v += cost;
}
cout<<"total cost -> "<<v<<endl;
if (c != t.impl_.node_count_)
cout<<"*** WARNING *** Tree node count mismatch "<<t.impl_.node_count_<<" != "<<c<<endl;
return os;
}
template <class functor_type>
functor_type execute_at_level(size_t level, functor_type fn) {
link_type x = _begin();
if (x == nullptr)
return fn;
std::queue<link_type> q;
_add_level(q, x, 0, level);
while (!q.empty()) {
link_type l = q.front();
assert(l != 0);
fn(iterator(l));
q.pop();
}
return fn;
}
};
template <class object_type>
struct Cost_functor {
auto operator()(const object_type& o) const -> decltype(o.measure())
{ return o.measure(); }
auto operator()(const object_type& o1, const object_type& o2) const -> decltype(o1+o2)
{ return (o1+o2); }
};
template <class link_type>
struct Tuple_compare {
typedef std::tuple<link_type, link_type, Real> tuple_type;
bool operator()(const tuple_type& t1, const tuple_type& t2) const
{ return std::get<2>(t1) > std::get<2>(t2); }
};
// bottom up tree construction
template <class tree_type, class volume_container>
tree_type* construct_tree_bottom_up(const volume_container& volumes)
{
// online tree type definitions
typedef typename tree_type::value_type volume_type;
typedef typename tree_type::cost_functor cost_functor;
typedef typename tree_type::iterator iterator_type;
// queue type definitions
typedef std::tuple<iterator_type, iterator_type, Real> tuple_type;
typedef typename std::priority_queue<tuple_type, std::vector<tuple_type>, Tuple_compare<iterator_type> > queue_type;
// already paired container type definitions
typedef std::set<iterator_type> paired_set;
typedef typename paired_set::iterator paired_iterator;
size_t numVolumes = volumes.size();
assert(numVolumes != 0);
tree_type* tp = new tree_type();
const cost_functor& cost = tp->cost();
tree_type& t = *tp;
queue_type q;
paired_set s;
std::vector<iterator_type> links(numVolumes);
// insert volumes into online tree
for (size_t i=0; i<numVolumes; ++i) {
std::pair<iterator_type, bool> p = t.insert(volumes[i]);
assert(p.second);
links[i] = p.first;
}
iterator_type ii,jj;
for (size_t i=0; i<numVolumes-1; ++i) {
Real merged = std::numeric_limits<Real>::infinity();
for (size_t j=i+1; j<numVolumes; ++j) {
volume_type v = cost(*links[i], *links[j]);
Real measure = cost(v);
if (measure < merged) {
ii = links[i];
jj = links[j];
merged = measure;
}
}
q.push(std::make_tuple(ii,jj,merged));
}
while (!q.empty()) {
// best candidate
auto tuple = q.top();
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
q.pop();
paired_iterator it = s.find(node);
if (it != s.end())
continue;
it = s.find(pair);
if (it != s.end())
continue;
#if DEBUG_TREE
cout<<t<<endl;
cout<<"node -> "<<node.node_<<endl;
cout<<"node value -> "<<*node<<endl;
cout<<"pair -> "<<pair.node_<<endl;
cout<<"pair value -> "<<*pair<<endl;
cout<<"volume -> "<<std::get<2>(tuple)<<endl;
#endif
// obtain best pair from online tree
iterator_type best = t.sibling(node);
#if DEBUG_TREE
cout<<"best sibling -> "<<*best<<endl;
#endif
if (pair == best) {
iterator_type parent = t.relocate_parent(node);
assert(parent != t.end());
#if DEBUG_TREE
cout<<"BEST SIBLING MATCHES! relocating..."<<endl;
cout<<" parent -> "<<*parent<<endl;
#endif
// add paired nodes to container
s.insert(node);
s.insert(pair);
// compute best pair for the parent
best = t.sibling(parent);
if (best != t.end()) {
tuple_type tuple = std::make_tuple(parent, best, cost(cost(*parent, *best)));
q.push(tuple);
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
#if DEBUG_TREE
cout<<" pushing new tuple "<<endl;
cout<<" node -> "<<*node<<endl;
cout<<" pair -> "<<*pair<<endl;
cout<<" volume -> "<<std::get<2>(tuple)<<endl;
#endif
}
}
// else enqueue new pair
else {
if (best != t.end()) {
tuple_type tuple = std::make_tuple(node,best, cost(cost(*node, *best)));
q.push(tuple);
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
#if DEBUG_TREE
cout<<"BEST SIBLING DOES NOT MATCH!"<<endl;
cout<<" pushing new tuple "<<endl;
cout<<" node -> "<<*node<<endl;
cout<<" pair -> "<<*pair<<endl;
cout<<" volume -> "<<std::get<2>(tuple)<<endl;
#endif
}
}
}
return tp;
}
template <class volume_type>
class Volume_creator;
template<int d>
struct Volume_creator<Ball<d> > {
typedef typename Ball<d>::point_type point_type;
template <class coord_array>
static Ball<d> create(const coord_array& coord) {
std::vector<point_type> pts;
size_t nnodes = coord.size();
pts.reserve(nnodes);
for (size_t i=0; i<nnodes; ++i)
pts.push_back(point_type(coord[i]));
return bounding_ball<d>(pts);
}
};
template <int d>
struct Volume_creator<BoundingBox<d> > {
typedef typename BoundingBox<d>::point_type point_type;
template <class coord_array>
static Sphere create(const coord_array& coord) {
std::vector<point_type> pts;
size_t nnodes = coord.size();
pts.reserve(nnodes);
for (size_t i=0; i<nnodes; ++i)
pts.push_back(point_type(coord[i]));
return BoundingBox<d>(pts.begin(), pts.end());
}
};
// bottom up tree construction
template <class tree_type, class model_type, class element_type>
tree_type* construct_tree_bottom_up(model_type& model) {
// online tree type definitions
typedef typename tree_type::value_type volume_type;
typedef typename tree_type::cost_functor cost_functor;
typedef typename tree_type::iterator iterator_type;
// queue type definitions
typedef std::tuple<iterator_type, iterator_type, Real> tuple_type;
typedef typename std::priority_queue<tuple_type, std::vector<tuple_type>, Tuple_compare<iterator_type> > queue_type;
// already paired container type definitions
typedef std::set<iterator_type> paired_set;
typedef typename paired_set::iterator paired_iterator;
tree_type* tp = new tree_type();
tree_type& t = *tp;
const cost_functor& cost = t.cost();
std::vector<iterator_type> links;
typedef typename model_type::mesh_type mesh_type;
mesh_type& mesh = model.getMesh();
int dim = mesh.getSpatialDimension();
// iterate over elements of lower dimension
typename mesh_type::type_iterator it = mesh.firstType(dim-1);
typename mesh_type::type_iterator end = mesh.lastType(dim-1);
size_t numVolumes = 0;
for(; it != end; ++it) {
// add elements to corresponding surface
for(UInt e = 0; e < mesh.getNbElement(*it); ++e) {
// create solid mechanics element
element_type el(model, *it, e);
// vector of coordinates for update
std::vector<const Real*> coord = el.coordinates();
// create leaf volume
volume_type v = Volume_creator<volume_type>::create(coord);
// do not add zero measure volumes
if (v.measure() == 0 && dim != 1)
continue;
std::pair<iterator_type, bool> p = t.insert(v);
assert(p.second);
links.push_back(p.first);
++numVolumes;
// save leaf data
if (!t.add_data(p.first,el)) {
cout<<"*** ERROR *** Could not add data. Aborting..."<<endl;
exit(1);
}
} // loop over elements
} // loop over types of element
if (numVolumes == 0) {
cout<<"*** ERROR *** No volumes were created. Aborting..."<<endl;
exit(1);
}
queue_type q;
paired_set s;
iterator_type ii,jj;
for (size_t i=0; i<numVolumes-1; ++i) {
Real merged = std::numeric_limits<Real>::infinity();
for (size_t j=i+1; j<numVolumes; ++j) {
volume_type v = cost(*links[i], *links[j]);
Real measure = v.measure();
if (measure < merged) {
ii = links[i];
jj = links[j];
merged = measure;
}
}
q.push(std::make_tuple(ii,jj,merged));
}
while (!q.empty()) {
// best candidate
auto tuple = q.top();
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
q.pop();
paired_iterator it = s.find(node);
if (it != s.end())
continue;
it = s.find(pair);
if (it != s.end())
continue;
#if DEBUG_TREE
cout<<t<<endl;
cout<<"node -> "<<node.node_<<endl;
cout<<"node value -> "<<*node<<endl;
cout<<"pair -> "<<pair.node_<<endl;
cout<<"pair value -> "<<*pair<<endl;
cout<<"volume -> "<<std::get<2>(tuple)<<endl;
#endif
// obtain best pair from online tree
iterator_type best = t.sibling(node);
#if DEBUG_TREE
cout<<"best sibling -> "<<*best<<endl;
#endif
if (pair == best) {
iterator_type parent = t.relocate_parent(node);
assert(parent != t.end());
#if DEBUG_TREE
cout<<"BEST SIBLING MATCHES! relocating..."<<endl;
cout<<" parent -> "<<*parent<<endl;
#endif
// add paired nodes to container
s.insert(node);
s.insert(pair);
// compute best pair for the parent
best = t.sibling(parent);
if (best != t.end()) {
tuple_type tuple = std::make_tuple(parent, best, cost(cost(*parent,*best)));
q.push(tuple);
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
#if DEBUG_TREE
cout<<" pushing new tuple "<<endl;
cout<<" node -> "<<*node<<endl;
cout<<" pair -> "<<*pair<<endl;
cout<<" volume -> "<<std::get<2>(tuple)<<endl;
#endif
}
}
// else enqueue new pair
else {
if (best != t.end()) {
tuple_type tuple = std::make_tuple(node,best, cost(cost(*node, *best)));
q.push(tuple);
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
#if DEBUG_TREE
cout<<"BEST SIBLING DOES NOT MATCH!"<<endl;
cout<<" pushing new tuple "<<endl;
cout<<" node -> "<<*node<<endl;
cout<<" pair -> "<<*pair<<endl;
cout<<" volume -> "<<std::get<2>(tuple)<<endl;
#endif
}
}
}
return tp;
}
// bottom up tree construction
template <class tree_type, class element_container>
tree_type* construct_tree_bottom_up(element_container& elems) {
// element type
typedef typename element_container::value_type element_type;
// online tree type definitions
typedef typename tree_type::value_type volume_type;
typedef typename tree_type::cost_functor cost_functor;
typedef typename tree_type::iterator iterator_type;
// queue type definitions
typedef std::tuple<iterator_type, iterator_type, Real> tuple_type;
typedef typename std::priority_queue<tuple_type, std::vector<tuple_type>, Tuple_compare<iterator_type> > queue_type;
// already paired container type definitions
typedef std::set<iterator_type> paired_set;
typedef typename paired_set::iterator paired_iterator;
tree_type* tp = new tree_type();
tree_type& t = *tp;
const cost_functor& cost = t.cost();
std::vector<iterator_type> links;
size_t numVolumes = 0;
for (typename element_container::iterator it = elems.begin();
it != elems.end(); ++it) {
element_type &el = *it;
// vector of coordinates for update
std::vector<const Real*> coord = el.coordinates();
// create leaf volume
volume_type v = Volume_creator<volume_type>::create(coord);
// do not add zero measure volumes
if (v.measure() == 0)
continue;
std::pair<iterator_type, bool> p = t.insert(v);
assert(p.second);
links.push_back(p.first);
++numVolumes;
// save leaf data
if (!t.add_data(p.first,el)) {
cout<<"*** ERROR *** Could not add data. Aborting..."<<endl;
exit(1);
}
} // loop over elements in container
if (numVolumes == 0) {
cout<<"*** ERROR *** No volumes were created. Aborting..."<<endl;
exit(1);
}
queue_type q;
paired_set s;
iterator_type ii,jj;
for (size_t i=0; i<numVolumes-1; ++i) {
Real merged = std::numeric_limits<Real>::infinity();
for (size_t j=i+1; j<numVolumes; ++j) {
volume_type v = cost(*links[i], *links[j]);
Real measure = v.measure();
if (measure < merged) {
ii = links[i];
jj = links[j];
merged = measure;
}
}
q.push(std::make_tuple(ii,jj,merged));
}
while (!q.empty()) {
// best candidate
auto tuple = q.top();
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
q.pop();
paired_iterator it = s.find(node);
if (it != s.end())
continue;
it = s.find(pair);
if (it != s.end())
continue;
#if DEBUG_TREE
cout<<t<<endl;
cout<<"node -> "<<node.node_<<endl;
cout<<"node value -> "<<*node<<endl;
cout<<"pair -> "<<pair.node_<<endl;
cout<<"pair value -> "<<*pair<<endl;
cout<<"volume -> "<<std::get<2>(tuple)<<endl;
#endif
// obtain best pair from online tree
iterator_type best = t.sibling(node);
#if DEBUG_TREE
cout<<"best sibling -> "<<*best<<endl;
#endif
if (pair == best) {
iterator_type parent = t.relocate_parent(node);
assert(parent != t.end());
#if DEBUG_TREE
cout<<"BEST SIBLING MATCHES! relocating..."<<endl;
cout<<" parent -> "<<*parent<<endl;
#endif
// add paired nodes to container
s.insert(node);
s.insert(pair);
// compute best pair for the parent
best = t.sibling(parent);
if (best != t.end()) {
tuple_type tuple = std::make_tuple(parent, best, cost(cost(*parent,*best)));
q.push(tuple);
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
#if DEBUG_TREE
cout<<" pushing new tuple "<<endl;
cout<<" node -> "<<*node<<endl;
cout<<" pair -> "<<*pair<<endl;
cout<<" volume -> "<<std::get<2>(tuple)<<endl;
#endif
}
}
// else enqueue new pair
else {
if (best != t.end()) {
tuple_type tuple = std::make_tuple(node,best, cost(cost(*node, *best)));
q.push(tuple);
iterator_type node = std::get<0>(tuple);
iterator_type pair = std::get<1>(tuple);
#if DEBUG_TREE
cout<<"BEST SIBLING DOES NOT MATCH!"<<endl;
cout<<" pushing new tuple "<<endl;
cout<<" node -> "<<*node<<endl;
cout<<" pair -> "<<*pair<<endl;
cout<<" volume -> "<<std::get<2>(tuple)<<endl;
#endif
}
}
}
return tp;
}
template <class tree_type>
void print_mathematica(tree_type& t) {
typedef typename tree_type::value_type volume_type;
int d = volume_type::dim();
cout<<std::fixed;
cout.precision(2);
if (d == 2)
cout<<"Graphics[{";
else
cout<<"Graphics3D[{";
for (typename tree_type::const_leaf_iterator it = t.leaves_begin(); it != t.leaves_end(); ++it)
cout<<*it<<", ";
cout<<"}];"<<endl;
}
template <typename T>
std::string stringify(const T& x) {
std::stringstream o;
if (!(o << x)) {
cout<<"*** ERROR *** Bad argument to stringity function"<<endl;
exit(1);
}
return o.str();
}
template <class tree>
void export_video(tree& t, Real duration, Real min_opacity, std::string pre = "", std::string post = "") {
typedef typename tree::value_type volume_type;
typedef typename volume_type::aabb_type aabb_type;
typedef typename aabb_type::point_type point_type;
typedef typename point_type::value_type value_type;
typedef typename tree::iterator iterator;
int d = volume_type::dim();
cout<<std::fixed;
cout.precision(2);
std::tuple<size_t, size_t, size_t> h = t.height();
typename tree::iterator it = t.begin();
aabb_type bb = it->bounding_box();
// get bounding box
for (; it != t.end(); ++it)
bb += it->bounding_box();
std::string figs;
int H = std::get<2>(h);
int k = 0;
for (int l = H; l>=0; --l) {
std::string g = "g";
g += stringify(k);
++k;
// compute opacity for figure
Real opacity = (1 - min_opacity)*static_cast<double>(l)/H + min_opacity;
if (d == 2)
cout<<g<<" = Graphics[{Opacity["<<stringify(opacity)<<"],"<<pre;
else
cout<<g<<" = Graphics3D[{Opacity["<<stringify(opacity)<<"],"<<pre;
t.execute_at_level(l, [](iterator it){ cout<<*it<<", ";});
figs += figs.empty() ? g : (','+g);
cout<<"}];\nShow["<<figs<<", PlotRange-> {{";
const point_type &m = bb.min();
const point_type &M = bb.max();
for (int i=0; i<d; ++i) {
value_type l = 0.05*(M[i] - m[i]);
cout<<(m[i]-l)<<','<<(M[i]+l)<<(i < d-1 ? "},{" : "}}");
}
cout<<post<<"];\n";
cout<<"Export[\""<<g<<".png\", %, ImageResolution -> 300];"<<endl;
}
cout<<"files = Last /@ Sort[{Characters@#, #} & /@ FileNames[\"*.png\"]]"<<endl;
cout<<"images = Map[Import, files];"<<endl;
cout<<"Export[\"video.mov\", images, \"FrameRate\" -> "<<stringify(static_cast<double>(k)/duration)<<"];"<<endl;
}
//// bottom up tree construction
//template <class volume_container>
//Tree<typename volume_container::value_type, Cost_functor<typename volume_container::value_type> >
//construct_tree_bottom_up2(const volume_container& volumes)
//{
//
// typedef typename volume_container::value_type volume_type;
//
// // online tree type definitions
// typedef Tree<volume_type, Cost_functor<volume_type> > tree_type;
//
// typedef Tree_node<volume_type> node_type;
// typedef typename tree_type::link_type link_type;
//
// size_t numVolumes = volumes.size();
// assert(numVolumes != 0);
//
// // allocate leafs of the tree
// link_type* leafs = new link_type[numVolumes];
//
// for (size_t i=0; i<numVolumes; ++i)
// leafs[i] = new node_type(volumes[i]);
//
// while (numVolumes > 1) {
//
// // find indices of the two "nearest" nodes, based on some criterion
// size_t ii,jj;
// Real merged = std::numeric_limits<Real>::infinity();
// for (size_t i=0; i<numVolumes; ++i)
// for (size_t j=i+1; j<numVolumes; ++j) {
//
// volume_type v = leafs[i]->value_ + leafs[j]->value_;
// if (v.measure() < merged) {
// ii = i;
// jj = j;
// merged = v.measure();
// }
// }
//
// volume_type v = leafs[ii]->value_ + leafs[jj]->value_;
// link_type parent = new node_type(v);
//
//#if DEBUG_TREE
// cout<<"best volume found -> "<<v<<endl;
// cout<<"measure -> "<<v.measure()<<endl;
// cout<<"parent -> "<<parent->value_<<endl;
// cout<<"left -> "<<leafs[ii]->value_<<endl;
// cout<<"right -> "<<leafs[jj]->value_<<endl;
//#endif
//
// parent->left_ = leafs[ii];
// parent->right_ = leafs[jj];
// leafs[ii]->parent_ = parent;
// leafs[jj]->parent_ = parent;
//
// // remove the two nodes from the active set and add in the new node.
// leafs[ii] = parent;
// leafs[jj] = leafs[numVolumes - 1];
// --numVolumes;
// }
//
// link_type root = leafs[0];
//
// tree_type t(root);
//
// delete leafs;
//
// return t;
//}
__END_AKANTU__
#endif /* __AKANTU_TREE_HH__ */

Event Timeline

c4science · Help