rectangle-union-area/segment_tree.h

//
// Created by maximilian on 16.04.22.
//

#include<vector>
#include "geometry.h"

#ifndef PROG_SEGMENT_TREE_H
#define PROG_SEGMENT_TREE_H


struct TreeNode {
    unsigned coverage;
    Coordinate left_coord;
    Coordinate right_coord;
    Unit covered_length;
    inline Unit segment_length();
    inline bool covered();
};


class SegmentTree {
    size_t _num_leaf_nodes;
    size_t _num_meta_nodes;
    std::vector<TreeNode> _nodes;
public:
    /**
     *
     * @param coords Sorted vector of coordinates
     */
    SegmentTree(const std::vector<RectCoord>& coords);

    inline Unit length_covered_intervals();
    void add_interval(Interval interval);
    void remove_interval(Interval interval);
    void check_integrity();

private:
    inline static Index left_child_idx(Index node_idx);
    inline static Index right_child_idx(Index node_idx);
    inline TreeNode& left_child(Index node_idx);
    inline TreeNode& right_child(Index node_idx);
    inline void add_coverage(Index node_idx);
    inline void remove_coverage(Index node_idx);
    inline void update_covered_length(Index node_idx);
    inline bool is_leaf(Index node_idx);

};

/*****************************************************
 * INLINE section
 ****************************************************/



TreeNode& SegmentTree::left_child(Index node_idx) {
    return _nodes[left_child_idx(node_idx)];
}

TreeNode& SegmentTree::right_child(Index node_idx) {
    return _nodes[right_child_idx(node_idx)];
}

Unit SegmentTree::length_covered_intervals() {
    return _nodes.front().covered_length;
}

void SegmentTree::add_coverage(Index node_idx) {
    ++(_nodes[node_idx].coverage);
    _nodes[node_idx].covered_length = _nodes[node_idx].segment_length();
}

void SegmentTree::remove_coverage(Index node_idx) {
    --(_nodes[node_idx].coverage);
    if(!_nodes[node_idx].covered()) {
        update_covered_length(node_idx);
    }
}

Index SegmentTree::left_child_idx(Index node_idx) {
    return 2*node_idx + 1;
}

Index SegmentTree::right_child_idx(Index node_idx) {
    return 2*node_idx + 2;
}

void SegmentTree::update_covered_length(Index node_idx) {
    assert(!_nodes[node_idx].covered());
    if (is_leaf(node_idx)) {
        _nodes[node_idx].covered_length = 0;
    } else {
        _nodes[node_idx].covered_length = \
        left_child(node_idx).covered_length + right_child(node_idx).covered_length;
    }
}

Unit TreeNode::segment_length() {
    return right_coord - left_coord;
}

bool TreeNode::covered() {
    return coverage > 0;
}

bool SegmentTree::is_leaf(Index node_idx) {
    return node_idx >= _num_meta_nodes;
}



#endif //PROG_SEGMENT_TREE_H