Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;
share|improve this question
    
Possible duplicate of Segment tree implementation in C++ – DarthGizka May 3 '16 at 6:56
    
The code is different in the other question. – mdfst13 May 3 '16 at 7:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.