115 lines
2.8 KiB
C++
115 lines
2.8 KiB
C++
//
|
|
// 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();
|
|
};
|
|
|
|
|
|
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();
|
|
inline void add_interval(Interval interval);
|
|
inline void remove_interval(Interval interval);
|
|
|
|
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);
|
|
void add_interval(Interval interval, Index node_idx);
|
|
void remove_interval(Interval interval, 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_interval(Interval interval) {
|
|
add_interval(interval, 0);
|
|
}
|
|
|
|
void SegmentTree::remove_interval(Interval interval) {
|
|
remove_interval(interval, 0);
|
|
}
|
|
|
|
void SegmentTree::add_coverage(Index node_idx) {
|
|
++(_nodes[node_idx].coverage);
|
|
update_covered_length(node_idx);
|
|
}
|
|
|
|
void SegmentTree::remove_coverage(Index node_idx) {
|
|
--(_nodes[node_idx].coverage);
|
|
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) {
|
|
if (_nodes[node_idx].coverage > 0) {
|
|
_nodes[node_idx].covered_length = _nodes[node_idx].segment_length();
|
|
} else 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 SegmentTree::is_leaf(Index node_idx) {
|
|
return node_idx > _num_meta_nodes;
|
|
}
|
|
|
|
|
|
#endif //PROG_SEGMENT_TREE_H
|