IntervalTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <memory>
#include <vector>
#include <cstdint>
#include <cassert>
#include <algorithm>
 
template <class T>
class FlatIntervalTree {
private:
    struct Interval {
        uint64_t low, high;
        T payload;
        
        bool contains(uint64_t point) const { return low <= point && point <= high; }
        bool contains(const Interval& other) const { return low <= other.low && high >= other.high; }
    };
    
    std::vector<Interval> intervals;
    bool sorted = false;
    
    void ensure_sorted() {
        if (!sorted) {
            // Sort by low, then by high (descending) so wider intervals come first
            std::sort(intervals.begin(), intervals.end(),
                [](const Interval& a, const Interval& b) {
                    return a.low < b.low || (a.low == b.low && a.high > b.high);
                });
            sorted = true;
        }
    }
    
public:
    void insert(uint64_t low, uint64_t high, T payload) {
        // TODO(@rail5): Assertions to ensure that our invariants are maintained
        intervals.push_back({low, high, payload});
        sorted = false;
    }
    
    T find_innermost_overlap(uint64_t point) {
        ensure_sorted();
        
        // Binary search for first interval with low <= point
        auto it = std::upper_bound(intervals.begin(), intervals.end(), point,
            [](uint64_t point, const Interval& interval) {
                return point < interval.low;
            });
        
        if (it == intervals.begin()) return T();
        
        // Scan backwards to find innermost (since sorted by low then wide-first)
        --it;
        const Interval* best = nullptr;
        for (; it >= intervals.begin() && it->low <= point; --it) {
            if (it->contains(point)) {
                if (!best || it->low > best->low) {
                    best = &*it;
                }
            }
 
            if (it == intervals.begin()) break; // Prevent underflow/UB
        }
        return best ? best->payload : T();
    }
};