VectorFuncRange

/**
    Author: Djeefther Souza Albuquerque (djeefther@gmail.com)
    Created at 20/09/2015
    Version 0.2
*/

#ifndef VECTOR_FUNC_RANGE_H_
#define VECTOR_FUNC_RANGE_H_

#include <vector>
#include <functional>
#include <assert.h>

inline size_t div2ceil(size_t n) {
    return (n >> 1) + (n & 1);
}

template<class T, class Func = std::function<T(const T&, const T&)>>
class VectorFuncRange {
    std::vector<std::vector<T>> data_;
    size_t last_level_;
    Func func_;
    T neutral_element_;

    //last_level_ is the index of last valid level in data_.
    //After that index are just levels keeped to avoid reallocations.
    //data_ should always have at least last_level_ allocated, and when reduced the number of levels
    //should not reduce its size, but just clear the folling do not used levels
    //the size of data_ (or levels allocated) should be reduced just in shring_to_fit method.

public:
    class GetSetT {
    protected:
        VectorFuncRange * p_container_;
        size_t index_;
        GetSetT(VectorFuncRange * p_container, size_t index) : p_container_(p_container), index_(index) {
        }
        GetSetT(const GetSetT&) = delete;
        GetSetT(const GetSetT&& obj) : p_container_(obj.p_container_), index_(index_) {}
    public:
        inline operator const T&() const {
            return p_container_->get(index_);
        }
        inline const T& get() const {
            return this->operator const T &();
        }
        inline typename const T& operator=(const T& data) {
            p_container_->set(index_, data);
            return p_container_->get(index_);
        }
        friend VectorFuncRange;
    };

    VectorFuncRange() : data_(1), last_level_(0), neutral_element_() {
    }
    ~VectorFuncRange() {
    }
    const Func& func() const {
        return func_;
    }
    const Func& func(const Func& func) {
        func_ = func;
        _update(0, 0, size());
        return func_;
    }
    const Func& func(Func&& func) {
        func_ = func;
        _update(0, 0, size());
        return func_;
    }
    inline const T& neutral_element() const {
        return neutral_element_;
    }
    inline void neutral_element(const T& neutral_element) {
        neutral_element_ = neutral_element;
    }
    inline void neutral_element(T&& neutral_element) {
        neutral_element_ = neutral_element;
    }
    void push_back(const T& obj) {
        data_.front().push_back(obj);
        _update_and_resize(0, data_.front().size() - 1);
    }
    void push_back(T&& obj) {
        data_.front().push_back(obj);
        _update_and_resize(0, data_.front().size() - 1);
    }
    void set(size_t index, const T& obj) {
        data_.front()[index] = obj;
        _update(0, index);
    }
    void set(size_t index, T&& obj) {
        data_.front()[index] = obj;
        updata(0, index);
    }
    inline size_t size() const {
        return data_.front().size();
    }
    void resize(const size_t size) {
        size_t old_size = data_.front().size();

        if (old_size == size) {
            return;
        }

        data_.front().resize(size);

        _base_resize(old_size,size);
    }
    void resize(const size_t size, const T& value) {
        size_t old_size = data_.front().size();

        if (old_size == size) {
            return;
        }

        data_.front().resize(size, value);

        _base_resize(old_size,size);
    }
    inline GetSetT operator[](size_t index) {
        return GetSetT(this, index);
    }
    inline const T& operator[](size_t index) const {
        return get(index);
    }
    inline const T& get(size_t index) const {
        return data_.front()[index];
    }
    T range_func(size_t first_index, size_t last_index) const {
        if (first_index == last_index) {
            return neutral_element_;
        }

        T accumulate_element_left = neutral_element_;
        T accumulate_element_right = neutral_element_;

        last_index--;
        //the intern process of this function is considering a close range [first_index, last_index],
        //but the usage of this function follows the C++ idiomatic of [first_index,last_index)
        size_t level = 0;

        while (true) {
            if (first_index < last_index) {
                //Need some elements
                //will have a next level with diferent bounders

                //first_index
                if (_is_right_children(first_index)) {
                    //If this index is a right children his _father accumulate one element outside the range, so accumulate this one and change the _father
                    accumulate_element_left = func_(accumulate_element_left, data_[level][first_index]);
                    first_index = _father(first_index) + 1;
                }
                else {
                    //His _father just accumulate the range
                    first_index = _father(first_index);
                }

                //last index
                if (_is_left_children(last_index)) {
                    //In oposite direction the same  as above
                    accumulate_element_right = func_(data_[level][last_index], accumulate_element_right);
                    last_index = _father(last_index) - 1;
                }
                else {
                    //In oposite direction the same  as above
                    last_index = _father(last_index);
                }

                //next_level
                level++;
            }
            else if (first_index == last_index) {
                //Just one element
                accumulate_element_left = func_(accumulate_element_left, data_[level][first_index]);
                break;
            }
            else {
                //Do not need any other accumulation
                break;
            }


        }

        return func_(accumulate_element_left, accumulate_element_right);
    }
    T range_func_dumb(size_t first_index, size_t last_index) const {
        T accumulate_element = neutral_element_;
        for (size_t i = first_index; i < last_index; i++) {
            accumulate_element = func_(accumulate_element, data_.front()[i]);
        }
        return accumulate_element;
    }
    inline const T& all_range_func() const {
        if (size() == 0) {
            return neutral_element_;
        }
        return data_[last_level_].front();
    }
    void shrink_to_fit() {
        data_.resize(last_level_+1);
        data_.shrink_to_fit();
        for (auto &i : data_) {
            i.shrink_to_fit();
        }
    }
    void clear() {
        _num_levels(1);
        data_.front().clear();
    }
    void pop_back() {
        for (size_t level_index = 0; level_index <= last_level_; level_index++) {
            size_t current_back_index = data_[level_index].size() - 1;

            data_[level_index].pop_back();

            if (data_[level_index].size() == 1) {
                //if this level now have size of one, it is the new root (final level)
                _num_levels(level_index + 1);
                break;
            }
            else if (_is_right_children(current_back_index)) {
                _update(level_index, current_back_index - 1);
                break;
                //this level is a right_children, so the next level still have a other children (left one)
                //after the pop_back and all the next levels should be keeped
            }
        }
    }
private:
    static inline size_t _father(size_t index) {
        return index / 2;
    }
    static inline bool _is_left_children(size_t index) {
        return !(index & 1);
    }
    static inline bool _is_right_children(size_t index) {
        return index & 1;
    }
    void _no_recursive_update(size_t level, size_t index) {
        //_father
        size_t father_level = level + 1;
        size_t father_index = _father(index);

        auto data_level_it = data_[level].cbegin();//should be const!

        if (father_level < _num_levels()) {
            if (2 * father_index + 1 < data_[level].size()) { //Have two childrens
                data_[father_level][father_index] = func_(data_level_it[2 * father_index], data_level_it[2 * father_index + 1]);
            }
            else { //Have just one, so copy the data
                data_[father_level][father_index] = data_level_it[index];
            }
        }
    }
    void _update(size_t level, size_t index) {
        //_father
        size_t father_level = level + 1;
        size_t father_index = _father(index);

        auto data_level_it = data_[level].cbegin();//should be const!

        if (father_level < _num_levels()) {
            if (2 * father_index + 1 < data_[level].size()) { //Have two childrens
                data_[father_level][father_index] = func_(data_level_it[2 * father_index], data_level_it[2 * father_index + 1]);
            }
            else { //Have just one, so copy the data
                data_[father_level][father_index] = data_level_it[index];
            }

            _update(father_level, father_index);
        }
    }
    void _update(size_t level, size_t first_index, size_t last_index) {
        if (first_index < last_index) {
            size_t last_i;
            for (size_t i = first_index; i < last_index; i += 2) {
                _update(level, i);
                last_i = i;
            }
            if (last_i != (last_index - 1) && _is_left_children(last_index - 1)) {
                //If the last one is a left children and it was not _update by itselft should be
                _update(level, last_index - 1);
            }
        }
    }
    /**
        Should be used for a level-index pair already allocated and set, but with fathers maybe not allocated maybe yet.
    */
    void _update_and_resize(size_t level, size_t index) {
        if (data_[level].size() <= 1) {
            _no_recursive_update(level, index);
        }
        else {
            size_t father_level = level + 1;
            size_t father_index = _father(index);

            if (_num_levels() <= father_level) {
                _emplace_back_level(father_index + 1);
            }
            else if (father_index >= data_[father_level].size()) {
                data_[father_level].resize(father_index + 1);
            }

            _no_recursive_update(level, index);
            _update_and_resize(father_level, father_index);
        }
    }
    inline size_t _num_levels() {
        return last_level_ + 1;
    }
    inline void _emplace_back_level(size_t size_new_level) {
        assert(last_level_ < data_.size());
        //The current last_level_ should always be allocated!

        last_level_++;//new level

        if (last_level_ == data_.size()) { //New level not allocated yet, should allocated
            data_.emplace_back(size_new_level);
        }
        else { //New level existed, but should have the correct size
            data_[last_level_].resize(size_new_level);
        }
    }
    inline void _pop_back_level() {
        assert(last_level_ != 0); //should have more than one level

        data_[last_level_].clear();
        last_level_--;
    }
    inline void _num_levels(size_t new_num_levels) {
        if (new_num_levels < _num_levels()) {
            //less than corrected used levels, should clear not used anymore levels
            for (auto it = data_.begin() + new_num_levels; it != data_.begin() + last_level_ + 1; it++) {
                it->clear();
            }
        }
        else if (new_num_levels > data_.size()) {
            //more levels than currenct allocated, should reallocate
            data_.resize(new_num_levels);
        }

        last_level_ = new_num_levels - 1;
    }

protected:
    inline void _base_resize(size_t old_size,size_t size) {
        size_t level = 0;
        size_t size_it = size;

        while (size_it > 1) {
            level++;
            size_it = div2ceil(size_it);

            if (_num_levels() <= level) { //this level did not exist yet
                //data_.emplace_back(size_it);
                _emplace_back_level(size_it);
            }
            else {
                data_[level].resize(size_it);
            }
        }

        //data_.resize(level + 1); //If level is greather than need, resize to shrink or keep the same
        _num_levels(level + 1);

                                 //Update new values
        if (old_size < size) {
            //size_t last_i;
            //for (int i = old_size; i < size; i += 2) {
            //  _update(0, i);
            //  last_i = i;
            //}
            //if (last_i != (size-1) && _is_left_children(size-1)) {
            //  //If the last one is a left children and it was not _update by itselft should be
            //  _update(0, size - 1);
            //}
            _update(0, old_size, size);
        }
        else if (_is_left_children(data_[0].size() - 1)) {
            _update(0, data_[0].size() - 1); //_update the last one remaining if they are a left children
        }
    }

public:
    void print_debug() {
        size_t i_index = 0;
        for (const auto& i : data_) {
            for (const auto& j : i) {
                std::cout << j << " ";
            }

            if (i_index == last_level_) {
                std::cout << " (last level)\n";
            }
            else {
                std::cout << " <<\n";
            }

            i_index++;
        }
        std::cout << "_________________________\n";
    }
    void print_debug_ref() {
        size_t i_index = 0;
        for (const auto& i : data_) {
            for (const auto& j : i) {
                std::cout << (*j) << " ";
            }

            if (i_index == last_level_) {
                std::cout << " (last level)\n";
            }
            else {
                std::cout << " <<\n";
            }

            i_index++;
        }
        std::cout << "_________________________\n";
    }
};

#endif