Newer
Older
#ifndef TREE_NODE_HPP
#define TREE_NODE_HPP
#include <cstdlib>
// utilities for reverse iteration
template <typename T>
struct reversion_wrapper { T& iterable; };
template <typename T>
auto begin(reversion_wrapper<T> w) { using std::rbegin; return rbegin(w.iterable); }
template <typename T>
auto end(reversion_wrapper<T> w) { using std::rend; return rend(w.iterable); }
template <typename T>
reversion_wrapper<T> reverse(T&& iterable) { return{ iterable }; }
class Node {
friend class Tree;
friend class NodeIterator;
friend class BarnesHutTree;
protected:
Node* prev{ this };
Node* next{ this };
Node* nextSibling{ nullptr };
Node* prevSibling{ nullptr };
Node* afterSubtree{ nullptr };
bool leaf{ true };
Tree* tree{ nullptr };
Body representative;
Node(const Box& bb_, std::vector<Body> bodies_, Tree* tree_);
Node(std::vector<Body> bodies_, Tree* tree_);
~Node() = default;
bool isSplitable() const;
void extendBBforBodies();
void extendBBtoCube();
Box getBB() const;
std::vector<Body> getBodies() const;
void insertBefore(Node* node);
void insertAfter(Node* node);
void unlink();
void update();
double getL() const;
bool isCorrect() const;
void print(std::size_t parallelId) const;
bool sufficientForBody(const Body& body) const;
bool sufficientForBox(const Box& box) const;
void extractLocalBodiesTo(std::vector<Body>& result);
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// iterator classes for traversing of pointered node data structures
template<typename Derived>
class BaseNodeIterator {
protected:
Node* node_{ nullptr };
BaseNodeIterator(Node * node) :node_(node) {};
public:
typedef std::ptrdiff_t difference_type;
typedef Node value_type;
typedef Node& reference;
typedef Node* pointer;
typedef std::bidirectional_iterator_tag iterator_category;
const BaseNodeIterator& operator++() {
return static_cast<Derived*>(this)->operator++();
}
BaseNodeIterator operator++(int) {
auto result = *this; ++(*this); return result;
}
BaseNodeIterator& operator--() {
return static_cast<Derived*>(this)->operator--();
}
BaseNodeIterator operator--(int) {
auto result = *this; --(*this); return result;
}
reference operator*() const { return *node_; }
pointer operator->() const { return node_; }
friend bool operator==(const BaseNodeIterator& lhs, const BaseNodeIterator& rhs) { return lhs.node_ == rhs.node_; }
friend bool operator!=(const BaseNodeIterator& lhs, const BaseNodeIterator& rhs) { return !(lhs == rhs); }
};
struct NodeIterator : BaseNodeIterator<NodeIterator>{
NodeIterator(Node * node) : BaseNodeIterator(node) {};
const BaseNodeIterator& operator++() { node_ = node_->next; return *this; }
BaseNodeIterator& operator--() { node_ = node_->prev; return *this; }
};
struct SiblingNodeIterator : BaseNodeIterator<SiblingNodeIterator>{
SiblingNodeIterator(Node * node) : BaseNodeIterator(node) {};
const BaseNodeIterator& operator++() { node_ = node_->nextSibling; return *this; }
BaseNodeIterator& operator--() { node_ = node_->prevSibling; return *this; }
};