I wrote a C++ implementation of a segment tree (I wrote it for an arbitrary function, "lazy" version) and I want so much to ask for a review. I'd like to know how I can make it better, especially the consistency of the code and the design.
template<typename T_Type, typename Function, typename Multiple_Function>
class LazySegmentTree {
struct TreeNode;
typedef std::unique_ptr<TreeNode> uniqueNodePtr_;
typedef TreeNode *nodePtr_;
struct TreeNode {
T_Type val_;
bool has_changed_;
uniqueNodePtr_ left_;
uniqueNodePtr_ right_;
TreeNode(T_Type val, bool has_changed = true) : val_(val), has_changed_(has_changed), left_(
nullptr), right_(nullptr) {
}
};
private:
uniqueNodePtr_ root_;
size_t real_size_;
T_Type default_val_;
Function func_;
Multiple_Function multiple_func_;
inline void push(nodePtr_ node) {
if (node->has_changed_) {
if (node->left_ == nullptr) {
node->left_ = uniqueNodePtr_(new TreeNode(node->val_, true));
node->right_ = uniqueNodePtr_(new TreeNode(node->val_, true));
} else {
node->left_->val_ = node->right_->val_ = node->val_;
node->left_->has_changed_ = node->right_->has_changed_ = true;
}
node->has_changed_ = false;
}
}
inline T_Type getData(nodePtr_ node, size_t left, size_t right) const {
if (node->has_changed_) {
return multiple_func_(node->val_, right - left);
} else {
return node->val_;
}
}
// makes a change from the position "from" to the position "to"
// STL style: [left, right), [from, to)
inline void setRecursive(nodePtr_ node, size_t left, size_t right, size_t from, size_t to,
T_Type val) {
if (from >= right || left >= to) {
return;
}
if (left == from && right == to) {
node->val_ = val;
node->has_changed_ = true;
} else {
push(node);
size_t mid = (left + right) / 2;
setRecursive(node->left_.get(), left, mid, from, std::min(to, mid), val);
setRecursive(node->right_.get(), mid, right, std::max(from, mid), to, val);
node->val_ = func_(getData(node->left_.get(), left, mid),
getData(node->right_.get(), mid, right));
}
}
inline const T_Type getRecursive(nodePtr_ node, size_t left, size_t right, size_t from,
size_t to) {
if (from >= right || left >= to) {
return default_val_;
}
if (left == from && right == to) {
return getData(node, left, right);
} else {
push(node);
size_t mid = (left + right) / 2;
T_Type left_ans = getRecursive(node->left_.get(), left, mid, from, std::min(to, mid));
T_Type right_ans = getRecursive(node->right_.get(), mid, right, std::max(from, mid),
to);
node->val_ = func_(getData(node->left_.get(), left, mid),
getData(node->right_.get(), mid, right));
return func_(left_ans, right_ans);
}
}
public:
LazySegmentTree(const std::vector<T_Type> &data, T_Type default_val = T_Type(0), Function func = Function(),
Multiple_Function multiple_func = Multiple_Function()) :
root_(uniqueNodePtr_(new TreeNode(default_val))), real_size_(data.size()),
default_val_(default_val), func_(func), multiple_func_(multiple_func) {
for (size_t i = 0; i < real_size_; ++i) {
set(i, data[i]);
}
}
inline void set(size_t left, size_t right, T_Type val) {
setRecursive(root_.get(), 0, real_size_, left, right, val);
}
inline void set(size_t pos, T_Type val) {
set(pos, pos + 1, val);
}
inline const T_Type get(size_t left, size_t right) {
return getRecursive(root_.get(), 0, real_size_, left, right);
}
inline const T_Type get(size_t pos) {
return get(pos, pos + 1);
}
inline const T_Type get() {
return get(0, real_size_);
}
};
An example:
LazySegmentTree<int, std::plus<int>, std::multiplies<int>> tree({5, 7, 3});
std::cout << tree.get(0, 2) << std::endl;
return 0;