Skip to content

Instantly share code, notes, and snippets.

@realazthat

realazthat/corner_traverser.hpp

Created October 8, 2014 20:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save realazthat/e6ad2eb073812407c771 to your computer and use it in GitHub Desktop.
Save realazthat/e6ad2eb073812407c771 to your computer and use it in GitHub Desktop.
Download ZIP
octree
Raw
corner_traverser.hpp
/*
Copyright (c) 2012 Azriel Fasten azriel.fasten@gmail.com
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef OCTREE_CORNER_TRAVERSER_H
#define OCTREE_CORNER_TRAVERSER_H
#include <cube/cube.hpp>
#include <tree/traverser.hpp>
#include <boost/concept/assert.hpp>
namespace tree{
template<typename tree_type>
struct corner_traverser{
corner_traverser();
explicit corner_traverser(tree_type* node);
template<typename>
friend class corner_traverser;
//template<typename other_tree_type>
//corner_traverser(const other_tree_type& other);
bool has_children() const;
bool is_child_of(const corner_traverser& other) const;
bool is_last_sibling() const;
corner_traverser first_child() const;
corner_traverser next_sibling() const;
corner_traverser parent() const;
void reset();
bool valid() const;
tree_type& operator*() const;
bool operator==(const corner_traverser& other) const;
bool operator!=(const corner_traverser& other) const;
private:
tree_type* node;
};
} // namespace tree
#include "corner_traverser.inl.hpp"
#endif
Raw
corner_traverser.inl.hpp
/*
Copyright (c) 2012 Azriel Fasten azriel.fasten@gmail.com
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/
#include <tree/corner_traverser.hpp>
namespace tree{
template<typename tree_type>
inline
corner_traverser<tree_type>::
corner_traverser()
: node(NULL)
{
}
template<typename tree_type>
inline
corner_traverser<tree_type>::
corner_traverser(tree_type* node)
: node(node)
{
}
/*
template<typename tree_type>
template<typename other_tree_type>
inline
corner_traverser<tree_type>::
corner_traverser(const other_tree_type& other)
: node(other.node)
{
}
*/
template<typename tree_type>
inline
tree_type&
corner_traverser<tree_type>::
corner_traverser::operator*() const
{
BOOST_ASSERT(valid());
return *node;
}
template<typename tree_type>
inline
bool
corner_traverser<tree_type>::
operator!=(const corner_traverser& other) const
{
return node != other.node;
}
template<typename tree_type>
inline
bool
corner_traverser<tree_type>::operator==(const corner_traverser& other) const
{
return node == other.node;
}
template<typename tree_type>
inline
corner_traverser<tree_type>
corner_traverser<tree_type>::
parent() const
{
if (node)
{
if (node->is_child())
{
corner_traverser result(node->parent());
BOOST_ASSERT(result.valid());
BOOST_ASSERT(result.node->is_parent_of(*node));
BOOST_ASSERT(node->is_child_of(*result.node));
return result;
}
}
return corner_traverser(NULL);
}
template<typename tree_type>
inline
bool
corner_traverser<tree_type>::
has_children() const
{
if (node)
if (node->has_children())
return true;
return false;
}
template<typename tree_type>
inline
corner_traverser<tree_type>
corner_traverser<tree_type>::
first_child() const
{
corner_traverser result(NULL);
if (node)
{
if (node->has_children())
{
result = corner_traverser(&(node->child(cube::corner_t::get(0))));
BOOST_ASSERT(result.valid());
BOOST_ASSERT(result.node->is_child_of(*node));
BOOST_ASSERT(node->is_parent_of(*result.node));
return result;
}
}
BOOST_ASSERT(!result.valid());
return result;
}
template<typename tree_type>
inline
bool
corner_traverser<tree_type>::
is_last_sibling() const
{
if (!node)
///This is really an error, but we will return true, since this function is
///usually used to terminate an iterative loop when true
return true;
return (node->corner() == cube::corner_t::all().back());
}
template<typename tree_type>
inline
corner_traverser<tree_type>
corner_traverser<tree_type>::next_sibling() const
{
if (!node)
///This is an error
return corner_traverser(NULL);
if (!node->is_child())
///This is an error
return corner_traverser(NULL);
BOOST_ASSERT(node->parent());
const cube::corner_t& next_corner = cube::corner_t::get(node->corner().index() + 1);
return corner_traverser( &(node->parent()->child(next_corner)) );
}
template<typename tree_type>
inline
void
corner_traverser<tree_type>::
reset(){
node = NULL;
}
template<typename tree_type>
inline
bool
corner_traverser<tree_type>::
valid() const
{
return node != NULL;
}
template<typename tree_type>
inline
bool
corner_traverser<tree_type>::
is_child_of(const corner_traverser& other) const
{
if (node && other.node)
{
BOOST_ASSERT(other.valid());
return (node->is_child_of(*other.node));
}
return false;
}
} // namespace tree
Raw
face_traverser.hpp
/*
Copyright (c) 2012 Azriel Fasten azriel.fasten@gmail.com
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef OCTREE_FACE_TRAVERSER_H
#define OCTREE_FACE_TRAVERSER_H
#include <cube/cube.hpp>
#include <tree/traverser.hpp>
#include <boost/concept/assert.hpp>
namespace tree{
template<typename tree_type>
struct face_traverser{
face_traverser();
face_traverser(tree_type* node, const cube::face_t& face);
template<typename>
friend class face_traverser;
template<typename other_tree_type>
face_traverser(const other_tree_type& other);
bool has_children() const;
bool is_child_of(const face_traverser& other) const;
bool is_last_sibling() const;
face_traverser first_child() const;
face_traverser next_sibling() const;
face_traverser parent() const;
void reset();
bool valid() const;
tree_type& operator*() const;
bool operator==(const face_traverser& other) const;
bool operator!=(const face_traverser& other) const;
private:
tree_type* node;
cube::face_t face;
typedef boost::array<cube::corner_t, 4> face_corners_t;
};
} // namespace tree
#include "face_traverser.inl.hpp"
#endif
Raw
face_traverser.inl.hpp
/*
Copyright (c) 2012 Azriel Fasten azriel.fasten@gmail.com
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/
#include <tree/face_traverser.hpp>
namespace tree{
template<typename tree_type>
inline
face_traverser<tree_type>::
face_traverser()
: node(NULL), face(cube::face_t::get(0))
{
}
template<typename tree_type>
inline
face_traverser<tree_type>::
face_traverser(tree_type* node, const cube::face_t& face)
: node(node), face(face)
{
}
template<typename tree_type>
template<typename other_tree_type>
inline
face_traverser<tree_type>::
face_traverser(const other_tree_type& other)
: node(other.node), face(other.face)
{
}
template<typename tree_type>
inline
tree_type&
face_traverser<tree_type>::
face_traverser::operator*() const
{
BOOST_ASSERT(valid());
return *node;
}
template<typename tree_type>
inline
bool
face_traverser<tree_type>::
operator!=(const face_traverser& other) const
{
return node != other.node;
}
template<typename tree_type>
inline
bool
face_traverser<tree_type>::operator==(const face_traverser& other) const
{
return node == other.node;
}
template<typename tree_type>
inline
face_traverser<tree_type>
face_traverser<tree_type>::
parent() const
{
if (node)
{
if (node->is_child())
{
face_traverser result(node->parent(), face);
BOOST_ASSERT(result.valid());
BOOST_ASSERT(result.node->is_parent_of(*node));
BOOST_ASSERT(node->is_child_of(*result.node));
return result;
}
}
return face_traverser(NULL, face);
}
template<typename tree_type>
inline
bool
face_traverser<tree_type>::
has_children() const
{
if (node)
if (node->has_children())
return true;
return false;
}
template<typename tree_type>
inline
face_traverser<tree_type>
face_traverser<tree_type>::
first_child() const
{
const face_corners_t& face_corners = face.corners();
if (node)
{
if (node->has_children())
{
face_traverser result(&(node->child(face_corners[0])), face);
BOOST_ASSERT(result.valid());
BOOST_ASSERT(result.node->is_child_of(*node));
BOOST_ASSERT(node->is_parent_of(*result.node));
return result;
}
}
return face_traverser(NULL, face);
}
template<typename tree_type>
inline
bool
face_traverser<tree_type>::
is_last_sibling() const
{
if (!node)
///This is really an error, but we will return true, since this function is
///usually used to terminate an iterative loop when true
return true;
const face_corners_t& face_corners = face.corners();
return node->corner() == face_corners[3];
}
template<typename tree_type>
inline
face_traverser<tree_type>
face_traverser<tree_type>::next_sibling() const
{
if (!node)
///This is an error
return face_traverser(NULL, face);
if (!node->is_child())
///This is an error
return face_traverser(NULL, face);
const face_corners_t& face_corners = face.corners();
face_corners_t::const_iterator w = std::find(face_corners.begin(), face_corners.end(), node->corner());
if (w == face_corners.end())
///This is an error
return face_traverser(NULL, face);
++w;
if (w == face_corners.end())
///This is an error
return face_traverser(NULL, face);
BOOST_ASSERT(node->parent());
return face_traverser(&(node->parent()->child(*w)), face);
}
template<typename tree_type>
inline
void
face_traverser<tree_type>::
reset(){
node = NULL;
}
template<typename tree_type>
inline
bool
face_traverser<tree_type>::
valid() const
{
return node != NULL;
}
template<typename tree_type>
inline
bool
face_traverser<tree_type>::
is_child_of(const face_traverser& other) const
{
if (node && other.node)
{
BOOST_ASSERT(other.valid());
return (node->is_child_of(*other.node));
}
return false;
}
} // namespace tree
Raw
traverser.hpp
/*
Copyright (c) 2012 Azriel Fasten azriel.fasten@gmail.com
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef OCTREE_TRAVERSER_H
#define OCTREE_TRAVERSER_H
#include <boost/concept_check.hpp>
#include <boost/concept/usage.hpp>
#include <boost/ref.hpp>
namespace tree{
/**
* Traverser concept
*
* @param X
* The traverser class
* @param
* The value type the traverser returns
*/
template<typename X, typename V>
struct Traverser
: boost::Assignable<X>,
boost::EqualityComparable<X>,
boost::CopyConstructible<X>,
boost::DefaultConstructible<X>
{
BOOST_CONCEPT_USAGE(Traverser)
{
is_traverser(boost::cref(child_traveser).get().parent());
is_traverser(boost::cref(child_traveser).get().first_child());
is_traverser(boost::cref(child_traveser).get().next_sibling());
is_boolean(boost::cref(child_traveser).get().is_child_of(parent_traverser));
is_boolean(boost::cref(child_traveser).get().is_child_of(X()));
is_boolean(boost::cref(parent_traverser).get().has_children());
is_boolean(boost::cref(parent_traverser).get().is_last_sibling());
is_boolean(boost::cref(parent_traverser).get().valid());
is_boolean(boost::cref(parent_traverser).get().operator==(X()));
is_boolean(boost::cref(parent_traverser).get().operator==(parent_traverser));
is_boolean(boost::cref(parent_traverser).get().operator!=(X()));
is_boolean(boost::cref(parent_traverser).get().operator!=(child_traveser));
is_value(boost::cref(child_traveser).get().operator*());
parent_traverser.reset();
}
void is_boolean(bool);
void is_traverser(X);
void is_value(V&);
X parent_traverser;
X child_traveser;
};
} // namespace tree
#endif
Raw
tree.hpp
/*
Copyright (c) 2012 Azriel Fasten azriel.fasten@gmail.com
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef OCTREE_TREE_H
#define OCTREE_TREE_H
#include <cube/cube.hpp>
#include <boost/iterator/indirect_iterator.hpp>
#include <boost/scoped_ptr.hpp>
#include <boost/ref.hpp>
#include <boost/concept_check.hpp>
#include <boost/concept/assert.hpp>
#include <boost/static_assert.hpp>
#include <tree/face_traverser.hpp>
#include <tree/corner_traverser.hpp>
namespace tree{
template<typename T>
struct root_t;
template<typename T>
struct branch_t;
template<typename T>
struct leaf_t;
template<typename T>
struct none_t;
/*
template<typename T>
struct leaf_t
: private boost::noncopyable
{
typedef boost::variant< branch_t<T>*, root_t<T>* > parent_ptr_type;
leaf_t(const parent_ptr_type& parent_ptr, const T& value, std::size_t level, const cube::corner_t& corner);
//boost::iterator_range< parent_iterator > parents();
//boost::iterator_range< neighbor_iterator > neighbors();
//boost::iterator_range< adjacent_iterator > adjacent();
typedef boost::variant<leaf_t<T>, branch_t<T>, none_t<T> > adjacent_type;
adjacent_type& adjacent(const cube::direction_t& direction);
const adjacent_type& adjacent(const cube::direction_t& direction) const;
T& value();
root_t<T>& root();
private:
///No slicing
leaf_t(const branch_t<T>& branch);
root_t<T>& mroot;
T mvalue;
std::size_t level;
cube::corner_t corner;
parent_ptr_type parent_ptr;
};
*/
namespace detail{
template<typename value_type, typename traverser_type>
struct dual_pointer_traversal_iterator
: public boost::iterator_facade<dual_pointer_traversal_iterator<value_type, traverser_type>,
value_type,
boost::forward_traversal_tag>
{
BOOST_CONCEPT_ASSERT((Traverser<traverser_type, value_type>));
private:
struct enabler {}; // a private type avoids misuse
public:
dual_pointer_traversal_iterator()
: root(), current(), last()
{
BOOST_ASSERT(!valid());
}
dual_pointer_traversal_iterator(const traverser_type& root, bool end)
: root(root), current(root), last(root)
{
if (end)
current.reset();
BOOST_ASSERT(valid());
}
template <class OtherValue, class OtherTraverser>
dual_pointer_traversal_iterator(
dual_pointer_traversal_iterator<OtherValue, OtherTraverser> const& other
///This parameter is ignored; its just here to make sure that @c other is convertable to this
, typename boost::enable_if<
boost::is_convertible<OtherValue*,value_type*>
, enabler
>::type = enabler()
)
: root(other.root), current(other.current), last(other.last)
{
BOOST_ASSERT(other.valid());
BOOST_ASSERT(valid());
}
template<typename T>
dual_pointer_traversal_iterator& operator=(const T& other)
{
assign(other);
return *this;
}
private:
template <class, class>
friend class dual_pointer_traversal_iterator;
friend class boost::iterator_core_access;
void increment() {
BOOST_ASSERT(valid());
BOOST_ASSERT(dereferencable());
traverser_type old_current = current;
{
///TODO think through what happens when root is actually the root of the tree and it has no children
// up/right traversal loop
while(true){
if (on_my_way_down())
{
BOOST_ASSERT(current.is_child_of(last));
BOOST_ASSERT(current != root);
if (current.has_children())
{
last = current;
current = current.first_child();
break;
} else if (!current.is_last_sibling()){
BOOST_ASSERT(!current.has_children());
last = current;
current = current.next_sibling();
break;
} else {
BOOST_ASSERT(!current.has_children());
BOOST_ASSERT(current.is_last_sibling());
last = current;
current = current.parent();
BOOST_ASSERT(on_my_way_up());
continue;
}
} else if (on_my_way_up()) {
if (current == root)
{
last = current;
current.reset();
break;
} else if(!current.is_last_sibling() ) {
BOOST_ASSERT(current != root);
BOOST_ASSERT(!current.is_last_sibling());
last = current;
current = current.next_sibling();
break;
} else {
last = current;
current = current.parent();
BOOST_ASSERT(on_my_way_up());
continue;
}
} // on_my_way_up()
else
{ // !on_my_way_up(), !on_my_way_down
BOOST_ASSERT(!on_my_way_down() && !on_my_way_down());
if (current == root)
{
BOOST_ASSERT(last == current);
if ( current.has_children() )
{
last = current;
current = current.first_child();
break;
} else {
last = current;
current.reset();
break;
}
}
else
{
BOOST_ASSERT(last.parent() == current.parent());
BOOST_ASSERT(!last.is_last_sibling());
BOOST_ASSERT(last.next_sibling() == current);
if (current.has_children())
{
last = current;
current = current.first_child();
BOOST_ASSERT(on_my_way_down());
break;
} else if (!current.is_last_sibling()){
last = current;
current = current.next_sibling();
BOOST_ASSERT(!on_my_way_down() && !on_my_way_up());
break;
} else {
last = current;
current = current.parent();
BOOST_ASSERT(on_my_way_up());
continue;
}
}
}
BOOST_ASSERT(false && "Something is wrong");
} // up/right traversal loop
}
BOOST_ASSERT(current != old_current);
BOOST_ASSERT(valid());
BOOST_ASSERT(!on_my_way_up());
BOOST_ASSERT(on_my_way_down() || !on_my_way_up());
}
value_type& dereference() const {
BOOST_ASSERT(valid());
BOOST_ASSERT(dereferencable());
return *current;
}
template<typename T>
bool equal(const T& other) const
{
return equal_internal(other);
}
private:
bool valid() const{
///TODO: triple check this
return root.valid() && last.valid();
}
bool dereferencable() const{
///TODO: triple check this
return valid() && current.valid();
}
template <class OtherValue, class OtherTraverser>
void
assign(dual_pointer_traversal_iterator<OtherValue, OtherTraverser> const& other,
///This parameter is ignored; its just here to make sure that @c other is convertable to this
typename boost::enable_if<
boost::is_convertible<OtherValue*,value_type*>
, enabler
>::type = enabler() )
{
BOOST_ASSERT(other.valid());
bool other_is_derefable = other.dereferencable();
///TODO: double check this is all members before giving green light
this->root = other.root;
this->current = other.current;
this->last = other.last;
BOOST_ASSERT(valid());
BOOST_ASSERT(liff(other_is_derefable, dereferencable()));
}
template <class OtherValue, class OtherTraverser>
bool equal_internal(dual_pointer_traversal_iterator<OtherValue, OtherTraverser> const& other,
///This parameter is ignored; its just here to make sure that @c other is convertable to this
typename boost::enable_if<
boost::is_convertible<OtherValue*,value_type*>
, enabler
>::type = enabler()
) const
{
return (this->root == other.root) && (this->current == other.current) && (this->last == other.last);
}
bool on_my_way_down() const{
BOOST_ASSERT(valid());
return current.is_child_of(last);
}
bool on_my_way_up() const{
BOOST_ASSERT(valid());
return last.is_child_of(current);
}
traverser_type root;
traverser_type current;
traverser_type last;
};
} // namespace detail
/**
*
* stack based traversal
* (best/average/worst): O(n)/O(n)/O(n) traversal,
* O(1)/O(1)/O(1) increment time,
* O(depth of tree) memory
*
* dual pointer based
* (best/average/worst/[amortized constant]):
* O(n)/O(n)/O(n) traversal,
* O(1)/O(1)/O(depth of tree)/O(1) increment time
* O(1)/O(1)/O(1) memory
* left-most-leaf-link:
* O(n)/O(n)/O(n) traversal,
* O(1)/O(1)/O(1) increment time
* O(1)/O(1)/O(1) memory
* Features TODO:
*
* node-counter
* ordered-face traverser
* clockwise vs counter clockwise
* leaf-to-root traverser
* leaf-first traverser so one can modify the nodes
* leaf-to-root face-traverser
* leaf-traverser
* level-traverser
* Traversal of all nodes on a level (or closest possible to that level)
* octree-web
* A web of linked non-overlapping nodes on different levels that define some depth of an octree.
* An example use would be all visible nodes in a view dependent octree.
* back-to-front traversal
* back-to-front traversal of a web
*
* destruct iteratively leaf-to-root otherwise stack might not like the destructor recursion
*
* scaffolding to search the tree
* some sort of bounded-box info:
* ~ allows for easy is_descendant checking
* ~ can be used to search the tree
*
* other functionality:
* ~ is_descendant_of(other)
* ~ is_ancestor_of(other)
* ~ is_adjacent_to(other)/is_on_face_of(other)
*
* helper classes
* ~ heirarchical occluder tracking
* ~ occlusion checking
* ~ occluder detector
*
* mixouts
* make these separate optional mixins:
* ~ adjacency policy
* nodes should keep track of their adjacent facing out-of-parent neighbors
* ~ parent policy
* nodes should know their parent
* ~ sibling policy
* how nodes find their sibling
* methods:
* ~ using the parent, keeping track of node's child id, finding the other children
* ~ keeping neihbor links
* ~ implicitly in a constant depth tree
* ~ root policy
* how nodes can find the root
* methods:
* ~ keep a pointer to the root, obtained upon creation
* ~ climbing the tree until the root, worst case O(depth of tree)
* ~ implicitly in a constant depth tree
* ~ node counting policy
* how the root should be able to count the nodes in the tree
* methods:
* ~ nodes keep the root informed of their creation and destruction, worst case O(1) to count
* ~ the root traverses the tree counting the nodes, an O(n) operation to count
* how nodes should be able to count the number of children they have
* methods:
* ~ the node traverses the tree counting the nodes, an O(n) worst case operation to count
* ~ each node keeps a count of their desendents, insertion and deletion would now cost >= O(depth of tree) worst case
* ~ level policy
* each node keeps track of its level
* methods:
* ~ each node keeps its own level, consequently requires storing an extra integer, obtained upon creation,
* O(1) to find the level
* ~ recursively climb to the root, consequently an O(depth of tree) worst case operation
* ~ constant depth policy
* All nodes can be preallocated and disallow growth of the tree
* consquences:
* ~ adjacency is implicit and O(1)
* ~ locating parent is implicitly trivial
* ~ locating siblings is implicitly trivial
* ~ locating the root is trival O(1)
* ~ finding the level of a node is trival
*
* ~ memory requirement of n nodes
* ~ left-most-leaf-node-tracker policy
* all nodes should keep track of their left most leaf nodes
* consequences:
* ~ insertion possibly requires informing O(depth of three) nodes of their new left-most-leaf
* ~ deletion possibly requires informing O(depth of three) nodes of their new left-most-leaf
* ~ now dual-pointer leaf-to-root traversal can be done in O(1)/O(1)/O(1)
* ~ corner policy
* make use of cube::corner_t a policy that decides how many children each node has (make it no longer an octree but an N?-tree)
*/
template<typename T>
struct branch_t
: private boost::noncopyable
{
public:
typedef branch_t<T> child_type;
typedef branch_t<T> adjacent_type;
typedef std::pair<adjacent_type*, adjacent_type*> adjacent_link;
typedef boost::array<boost::scoped_ptr<child_type>, 8> children_type;
typedef boost::indirect_iterator< typename children_type::iterator > child_iterator;
typedef boost::indirect_iterator< typename children_type::const_iterator > const_child_iterator;
typedef detail::dual_pointer_traversal_iterator<branch_t, face_traverser<branch_t> > face_iterator;
typedef detail::dual_pointer_traversal_iterator<const branch_t, face_traverser<const branch_t> > const_face_iterator;
typedef detail::dual_pointer_traversal_iterator<branch_t, corner_traverser<branch_t> > traversal_iterator;
typedef detail::dual_pointer_traversal_iterator<const branch_t, corner_traverser<const branch_t> > const_traversal_iterator;
typedef T value_type;
branch_t(root_t<T>& root, branch_t* parent, T value, std::size_t level, const cube::corner_t& corner);
~branch_t();
boost::iterator_range< child_iterator > children();
boost::iterator_range< const_child_iterator > children() const;
boost::iterator_range< traversal_iterator > traversal();
boost::iterator_range< const_traversal_iterator > traversal() const;
void split();
void join();
child_type& child(const cube::corner_t& corner);
const child_type& child(const cube::corner_t& corner) const;
//adjacent_type* adjacent(const cube::direction_t& direction);
//const adjacent_type* adjacent(const cube::direction_t& direction) const;
boost::iterator_range< face_iterator > face_traversal(const cube::face_t& face);
boost::iterator_range< const_face_iterator > face_traversal(const cube::face_t& face) const;
boost::iterator_range< const_face_iterator > cface_traversal(const cube::face_t& face) const;
//boost::iterator_range< parent_iterator > parents();
//boost::iterator_range< neighbor_iterator > neighbors();
//boost::iterator_range< adjacent_iterator > adjacent();
//typedef branch_t<T> adjacent_type;
const cube::corner_t& corner() const;
T& value();
const T& value() const;
root_t<T>& root();
const root_t<T>& root() const;
bool is_root() const;
bool has_children() const;
bool is_child() const;
bool is_child_of(const branch_t& other) const;
bool is_parent_of(const branch_t& other) const;
const branch_t<T>* previous_brother() const;
const branch_t<T>* next_brother() const;
const branch_t<T>* first_child() const;
const branch_t<T>* last_child() const;
branch_t<T>* parent();
const branch_t<T>* parent() const;
std::size_t level() const;
private:
//No slicing
branch_t(const root_t<T>&);
root_t<T>& mroot;
branch_t<T>* mparent;
T mvalue;
std::size_t mlevel;
cube::corner_t mcorner;
private:
#if 0
void set_adjacent_link(const cube::direction_t& direction, adjacent_type* adjacent_node);
adjacent_type* get_adjacent_link(const cube::direction_t& direction);
const adjacent_type* get_adjacent_link(const cube::direction_t& direction) const;
template<typename cv_tree_type>
static cv_tree_type* get_adjacent_link(cv_tree_type& tree_node, const cube::direction_t& direction);
///This code was getting to complicated to duplicate for const and non-const functions
template<typename cv_tree_type>
static
cv_tree_type*
adjacent(cv_tree_type& from_node, const cube::direction_t& direction);
boost::array<adjacent_type*, 6> adjacent_links;
void initialize_adjacencies();
void uninitialize_adjacencies();
#endif
private:
boost::scoped_ptr< children_type > mchildren;
};
template<typename T>
struct root_t
: public branch_t<T>
{
typedef branch_t<T> super;
root_t(T value);
root_t();
};
} // namespace tree
#include "tree.inl.hpp"
#endif // TREE_H
Raw
tree.inl.hpp
/*
Copyright (c) 2012 Azriel Fasten azriel.fasten@gmail.com
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/
#include <tree/tree.hpp>
#include <cube/logic_utility.hpp>
#include <boost/range.hpp>
#include <boost/assert.hpp>
namespace tree{
template<typename T>
inline
root_t<T>::
root_t(T value)
: super(*this, NULL, value, 0, cube::corner_t::get(0))
{
}
template<typename T>
inline
root_t<T>::
root_t()
: super(*this, NULL, T(), 0, cube::corner_t::get(0))
{
}
#if 0
template<typename T>
inline
void
branch_t<T>::
initialize_adjacencies()
{
//TODO: make sure this adjacency thingy works for the root
//TODO: make sure this adjacency thingy works in destruction too
//TODO: optimize adjacency in destruction of parent with lots of children
//TODO: make sure the destructor iteratively destroys its children, bottom up
///@note don't use any member functions here, some things haven't finished initializing yet
///@note don't depend on parent knowing its children yet; and we cannot yet know our siblings either
/// as we are being just now created and haven't yet been inserted into our parents
BOOST_FOREACH(const cube::face_t& face, corner().faces())
{
set_adjacent_link(face.direction(), NULL);
}
if (!mparent)
return;
///For each adjacent node (possibly non-existent),
BOOST_FOREACH(const cube::face_t& face, mcorner.faces())
{
const cube::direction_t& adjacent_direction = face.direction();
/*
///Link me to adjacent node or closest parent of adjacent node
branch_t* adjacent_node_parent_closest_ptr = NULL;
if (mparent->corner().face_set().contains(face))
{
adjacent_node_parent_closest_ptr = mparent->adjacent(adjacent_direction);
///If parent has no adjacent, we are at the edge of the tree, and we don't either
if (!adjacent_node_parent_closest_ptr)
continue;
} else if(mparent->is_child()) {
const cube::corner_t& parent_corner = mparent->corner();
const cube::corner_t& ungle_corner = parent_corner.adjacent(adjacent_direction);
adjacent_node_parent_closest_ptr = &(mparent->mparent->child(ungle_corner));
} else {
///We are close to the root, and thus the edge, no adjacency
continue;
}
*/
branch_t* adjacent_node_parent_closest_ptr = mparent->adjacent(adjacent_direction);
if (!adjacent_node_parent_closest_ptr)
{
///We are close to the root, or the edge, and have no adjacency
continue;
}
BOOST_ASSERT(!!adjacent_node_parent_closest_ptr);
branch_t& adjacent_node_parent_closest = *adjacent_node_parent_closest_ptr;
///My parent's adjacent node in this direction is at least as low as my parent's level
BOOST_ASSERT(adjacent_node_parent_closest.level() <= mparent->level());
///My parent's adjacent node in this direction is definitely lower than my level
BOOST_ASSERT(adjacent_node_parent_closest.level() < level());
bool adjacent_node_parent_closest_has_children = adjacent_node_parent_closest.has_children();
bool parent_links_same = (adjacent_node_parent_closest.level() == level() - 1);
bool parent_links_lower = (adjacent_node_parent_closest.level() < level() - 1);
///If my parent's adjacent link is not on my parent's level
///Then my parent's adjacent doesn't have children (otherwise my parent would point to them)
BOOST_ASSERT( lif(!parent_links_same, adjacent_node_parent_closest_has_children) );
///Same as above, just sanity testing
BOOST_ASSERT( lif(parent_links_lower, adjacent_node_parent_closest_has_children) );
///If my parent's adjacent link has children,
///Then my parent must be on the same level as it, otherwise my parent would point lower to its children.
BOOST_ASSERT( lif(adjacent_node_parent_closest_has_children, parent_links_same) );
if (!adjacent_node_parent_closest_has_children)
{
///If the parent adjacent has no children
///Link to the parent adjacent
set_adjacent_link(adjacent_direction, &adjacent_node_parent_closest);
} // !adjacent_node_parent_closest_has_children
else
{ // adjacent_node_parent_closest_has_children
///If the parent adjacent has children
///If my parent's adjacent link has children,
///Then my parent must be on the same level as it, otherwise my parent would point lower to its children.
BOOST_ASSERT(parent_links_same);
///If there is an existing node on my level, that is adjacent to me
const cube::corner_t& facing_adjacent_corner = corner().adjacent(adjacent_direction.opposite());
///TODO
branch_t& adjacent_node = adjacent_node_parent_closest.child(facing_adjacent_corner);
///Set this node as facing @c adjacent_node
set_adjacent_link(adjacent_direction, &adjacent_node);
///Adjacent node should be linked to my parent
BOOST_ASSERT((adjacent_node.adjacent(adjacent_direction.opposite())) == mparent);
///Adjacent node might have children, those facing me would be linked to my parent
///They should be relinked to me
BOOST_FOREACH(branch_t& facing_node, adjacent_node.face_traversal(adjacent_direction.opposite().face()))
{
///For each facing node that is inside of the node adjacent to me (includes the adjacent node itself)
///The facing node would have been facing my parent
///Therefore if my parent is NULL, it should think that *it's* adjacent neighbor in *my* direction
/// is NULL.
///If my parent is not NULL. it should think that *it's* adjacent neighbor in *my* direction
/// is my parent
BOOST_ASSERT(
(mparent == NULL && facing_node.adjacent(adjacent_direction.opposite()) == NULL)
|| (facing_node.adjacent(adjacent_direction.opposite()) == mparent));
///Inform the facing node of it's new adjacent neighbor, *me*
facing_node.set_adjacent_link(adjacent_direction.opposite(), this);
}
} // adjacent_node_parent_closest_has_children
} // foreach adjacent face to this corner
}
template<typename T>
inline
void
branch_t<T>::
uninitialize_adjacencies()
{
if (!mparent)
return;
///TODO
}
template<typename T>
inline
void
branch_t<T>::
set_adjacent_link(const cube::direction_t& direction, adjacent_type* adjacent_node)
{
BOOST_ASSERT((direction.index() < adjacent_links.size()) && "Invalid direction");
BOOST_ASSERT(corner().face_set().contains(direction.face()) && "Adjacent links do not include siblings");
adjacent_links[direction.index()] = adjacent_node;
}
#endif
template<typename T>
inline
branch_t<T>::
branch_t(root_t<T>& root, branch_t* parent, T value, std::size_t level, const cube::corner_t& corner)
: mroot(root), mparent(parent), mvalue(value), mlevel(level), mcorner(corner), mchildren()
{
///Make sure our iterator is convertable to const_iterator
BOOST_STATIC_ASSERT((boost::is_convertible<face_iterator, const_face_iterator>::value));
}
template<typename T>
inline
branch_t<T>::
~branch_t()
{
join();
}
template<typename T>
inline
boost::iterator_range< typename branch_t<T>::const_child_iterator >
branch_t<T>::
children() const
{
if (mchildren)
{
return boost::make_iterator_range(const_child_iterator(mchildren->begin()), const_child_iterator(mchildren->end()));
}
return boost::make_iterator_range(const_child_iterator(), const_child_iterator());
}
template<typename T>
inline
boost::iterator_range< typename branch_t<T>::child_iterator >
branch_t<T>::
children()
{
if (mchildren)
{
return boost::make_iterator_range(child_iterator(mchildren->begin()), child_iterator(mchildren->end()));
}
return boost::make_iterator_range(child_iterator(), child_iterator());
}
template<typename T>
inline
T&
branch_t<T>::
value()
{
return mvalue;
}
template<typename T>
inline
const T&
branch_t<T>::
value() const
{
return mvalue;
}
template<typename T>
const root_t< T >&
branch_t<T>::
root() const
{
return mroot;
}
template<typename T>
root_t< T >&
branch_t<T>::
root()
{
return mroot;
}
template<typename T>
inline
void branch_t<T>::
split()
{
if (!mchildren)
{
mchildren.reset( new children_type() );
BOOST_FOREACH(const cube::corner_t& c, cube::corner_t::all() )
{
boost::scoped_ptr<child_type>& child_ptr = (*mchildren)[c.index()];
child_ptr.reset( new child_type(root(), this, T(), mlevel + 1, c) );
BOOST_ASSERT(!child_ptr->is_root());
BOOST_ASSERT(child_ptr->is_child());
BOOST_ASSERT(this->is_parent_of(*child_ptr));
BOOST_ASSERT(child_ptr->is_child_of(*this));
}
}
}
template<typename T>
inline
void
branch_t<T>::
join()
{
///FIXME: this will make a recursive destructor call all the way down the tree,
///we should do this with a receding-depth-first traversal to destroy the highest levels of the tree first iteratively
mchildren.reset();
}
template<typename T>
inline
const cube::corner_t&
branch_t<T>::
corner() const
{
return mcorner;
}
template<typename T>
inline
typename branch_t<T>::child_type&
branch_t<T>::
child(const cube::corner_t& corner)
{
BOOST_ASSERT(mchildren);
return *(*mchildren)[corner.index()];
}
template<typename T>
inline
const typename branch_t<T>::child_type&
branch_t<T>::
child(const cube::corner_t& corner) const
{
BOOST_ASSERT(mchildren);
return *(*mchildren)[corner.index()];
}
template<typename T>
inline
std::size_t
branch_t<T>::level() const
{
return mlevel;
}
template<typename T>
inline
branch_t< T >*
branch_t<T>::parent()
{
if (mparent) {
BOOST_ASSERT(mparent != this);
BOOST_ASSERT(mparent->has_children());
BOOST_ASSERT(mparent->is_parent_of(*this));
}
return mparent;
}
template<typename T>
inline
const branch_t< T >*
branch_t<T>::parent() const
{
if (mparent) {
BOOST_ASSERT(mparent != this);
BOOST_ASSERT(mparent->has_children());
BOOST_ASSERT(mparent->is_parent_of(*this));
}
return mparent;
}
template<typename T>
inline
bool
branch_t<T>::is_root() const
{
return &mroot == this;
}
#if 0
template<typename T>
template<typename cv_tree_type>
cv_tree_type*
branch_t<T>::
get_adjacent_link(cv_tree_type& from_node, const cube::direction_t& direction)
{
BOOST_ASSERT(direction.index() < from_node.adjacent_links.size());
if (from_node.mcorner.face_set().contains(direction.face()))
return from_node.adjacent_links[direction.index()];
if (from_node.mparent)
{
const cube::corner_t& sibling_corner = from_node.mcorner.adjacent(direction);
return &(from_node.mparent->child(sibling_corner));
}
return NULL;
}
template<typename T>
typename branch_t<T>::adjacent_type*
branch_t<T>::
get_adjacent_link(const cube::direction_t& direction)
{
return get_adjacent_link(*this, direction);
}
template<typename T>
const typename branch_t<T>::adjacent_type*
branch_t<T>::
get_adjacent_link(const cube::direction_t& direction) const
{
return get_adjacent_link(*this, direction);
}
template<typename T>
template<typename cv_tree_type>
inline
cv_tree_type*
branch_t<T>::
adjacent(cv_tree_type& from_node, const cube::direction_t& direction)
{
cv_tree_type* result = from_node.get_adjacent_link(direction);
if (!result)
return result;
///I only point to nodes that are on my level, or lower
BOOST_ASSERT(result->level() <= from_node.level());
///If I am adjacent to a node, they must be adjacent to *a* node in the opposite direction
/// (a sibling of it's, me, or one of my ancestors) FIXME:
//BOOST_ASSERT(!!result->adjacent(direction.opposite()));
#ifndef NDEBUG
///Find my ancestor that is on the same level as my adjacent node
cv_tree_type* reverse_adjacent_ancestor_or_self = &from_node;
///Sanity
BOOST_ASSERT(reverse_adjacent_ancestor_or_self);
{
for (std::size_t i = 0; i < from_node.level() - result->level(); ++i)
{
BOOST_ASSERT(reverse_adjacent_ancestor_or_self->is_child());
BOOST_ASSERT(reverse_adjacent_ancestor_or_self->mparent);
reverse_adjacent_ancestor_or_self = reverse_adjacent_ancestor_or_self->mparent;
BOOST_ASSERT(reverse_adjacent_ancestor_or_self);
}
}
///My ancestor, on the same level as *my* "adjacent node", should be the "adjacent node" of *my* "adjacent node"
///FIXME:this is recursion ...
//BOOST_ASSERT(reverse_adjacent_ancestor_or_self == result->adjacent(direction.opposite()));
#endif
return result;
}
template<typename T>
inline
typename branch_t<T>::adjacent_type*
branch_t<T>::
adjacent(const cube::direction_t& direction)
{
return adjacent(*this, direction);
}
template<typename T>
inline
const typename branch_t<T>::adjacent_type*
branch_t<T>::
adjacent(const cube::direction_t& direction) const
{
return adjacent(*this, direction);
}
#endif
template<typename T>
inline
bool
branch_t<T>::
has_children() const
{
return !!mchildren;
}
template<typename T>
inline
boost::iterator_range< typename branch_t<T>::const_traversal_iterator >
branch_t<T>::
branch_t::traversal() const
{
typedef corner_traverser<const branch_t> traverser_t;
traverser_t me(this);
return boost::make_iterator_range( const_traversal_iterator(me, false),
const_traversal_iterator(me, true) );
}
template<typename T>
inline
boost::iterator_range< typename branch_t<T>::traversal_iterator >
branch_t<T>::
branch_t::traversal()
{
typedef corner_traverser<branch_t> traverser_t;
traverser_t me(this);
return boost::make_iterator_range( traversal_iterator(me, false),
traversal_iterator(me, true) );
}
template<typename T>
inline
boost::iterator_range< typename branch_t<T>::face_iterator >
branch_t<T>::
face_traversal(const cube::face_t& face)
{
typedef face_traverser<branch_t> traverser_t;
traverser_t me(this, face);
return boost::make_iterator_range( face_iterator(me, false),
face_iterator(me, true) );
}
template<typename T>
inline
boost::iterator_range< typename branch_t<T>::const_face_iterator >
branch_t<T>::
face_traversal(const cube::face_t& face) const
{
typedef face_traverser<const branch_t> traverser_t;
traverser_t me(this, face);
return boost::make_iterator_range( const_face_iterator(me, false),
const_face_iterator(me, true) );
}
template<typename T>
inline
boost::iterator_range< typename branch_t<T>::const_face_iterator >
branch_t<T>::
cface_traversal(const cube::face_t& face) const
{
return face_traversal(face);
}
template<typename T>
inline
bool
branch_t<T>::
branch_t::is_child() const
{
return !!mparent;
}
template<typename T>
inline
bool
branch_t<T>::
branch_t::is_child_of(const branch_t<T>& other) const
{
if (!!mparent && (mparent == &other))
{
BOOST_ASSERT(other.mchildren);
BOOST_ASSERT(&*(*other.mchildren)[corner().index()] == this);
return true;
}
return false;
}
template<typename T>
inline
bool
branch_t<T>::
branch_t::is_parent_of(const branch_t<T>& other) const
{
if ( !!other.mparent && (other.mparent == this) )
{
BOOST_ASSERT(has_children());
BOOST_ASSERT(other.is_child());
BOOST_ASSERT(!!mchildren);
BOOST_ASSERT(!!(*mchildren)[other.corner().index()]);
BOOST_ASSERT(&*(*mchildren)[other.corner().index()] == &other);
return true;
}
return false;
}
} // namespace tree
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment