rectangle-union-area/segment_tree.cpp

62 lines
2.5 KiB
C++
Raw Permalink Normal View History

2022-04-16 11:34:29 +02:00
//
// Created by maximilian on 16.04.22.
//
2022-04-16 11:49:45 +02:00
#include <cassert>
2022-04-16 11:34:29 +02:00
#include <bit>
#include "segment_tree.h"
SegmentTree::SegmentTree(const std::vector<RectCoord> &coords):
_num_leaf_nodes(coords.size() -1),
// reserve nodes for a full binary tree with at least as many leaves as intervals
_num_meta_nodes(std::bit_ceil(_num_leaf_nodes) -1),
_nodes(2 * _num_meta_nodes + 1, {0, coords[_num_leaf_nodes].coord, coords[_num_leaf_nodes].coord, 0}) {
2022-04-16 11:34:29 +02:00
assert(!coords.empty());
// Initialize all nodes with zero coverage and dummy interval
// We initialize the tree from bottom up, keeping track of the index ranges
// and the length of the corresponding segment
for(Index leaf_node_idx = 0 ; leaf_node_idx < _num_leaf_nodes ; ++leaf_node_idx) {
_nodes[leaf_node_idx + _num_meta_nodes].left_coord = coords[leaf_node_idx].coord;
_nodes[leaf_node_idx + _num_meta_nodes].right_coord = coords[leaf_node_idx + 1].coord;
2022-04-16 11:34:29 +02:00
}
// Note that there are remaining leafs that represent dummy ranges
for(Index node_idx = _num_meta_nodes - 1; node_idx != -1 ; --node_idx) {
2022-04-16 11:34:29 +02:00
_nodes[node_idx].left_coord = left_child(node_idx).left_coord;
_nodes[node_idx].right_coord = right_child(node_idx).right_coord;
}
assert(_nodes.front().left_coord == coords.front().coord);
assert(_nodes.front().right_coord == coords.back().coord);
assert(_nodes.front().segment_length() == coords.back().coord - coords.front().coord);
}
void SegmentTree::add_interval(Interval interval, Index node_idx) {
if (interval.left <= _nodes[node_idx].left_coord && _nodes[node_idx].right_coord <= interval.right) {
add_coverage(node_idx);
2022-04-16 11:34:29 +02:00
} else {
if(interval.left < left_child(node_idx).right_coord) {
add_interval(interval, left_child_idx(node_idx));
}
if(right_child(node_idx).left_coord < interval.right) {
add_interval(interval, right_child_idx(node_idx));
}
update_covered_length(node_idx);
2022-04-16 11:34:29 +02:00
}
}
void SegmentTree::remove_interval(Interval interval, Index node_idx) {
if (interval.left <= _nodes[node_idx].left_coord && _nodes[node_idx].right_coord <= interval.right) {
remove_coverage(node_idx);
2022-04-16 11:34:29 +02:00
} else {
if(interval.left < left_child(node_idx).right_coord) {
remove_interval(interval, left_child_idx(node_idx));
}
if(right_child(node_idx).left_coord < interval.right) {
remove_interval(interval, right_child_idx(node_idx));
}
update_covered_length(node_idx);
2022-04-16 11:34:29 +02:00
}
}