// MonotoneIncreasingExtentsOnIntervalSet.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2021

#pragma once

namespace ceda
{
template <typename Range, typename T>
class MeasureMonotoneIncreasingExtentsOnIntervalSet
{
public:
    explicit MeasureMonotoneIncreasingExtentsOnIntervalSet(Range r, T extent = 0) : 
        r(r), extent(extent) {}

    // Measure the extent of the interval set intersected with [0,t).
    // Calls to Extent() must monotone increase on the given t coord
    T Extent(T t)
    {
        /*
            |<--------------------->|     
            |    region in which    |
            |    extent measured    |
            |         so far        |
            |                       |    *r
            |   [--)   [--------)   [-----------)  [--------)   [-------)  [--------------)
            |                       |           |                  |
            0                   r->begin()   r->end()              t
        */
        while(1)
        {
            if (!r) return extent;
            
            if (t < r->end())
            {
                if (r->begin() < t)
                {
                    return extent + (t - r->begin());
                }
                else
                {
                    return extent;    
                }    
            }
            
            extent += r->size();
            ++r;
        }
    }

private:
    // At any given time, 'extent' represents the extent to the left r->begin()
    Range r;
    T extent;
};
} // namespace ceda