interval.hpp

Go to the documentation of this file.

#ifndef GENESIS_UTILS_CONTAINERS_INTERVAL_TREE_INTERVAL_H_
#define GENESIS_UTILS_CONTAINERS_INTERVAL_TREE_INTERVAL_H_
 
/*
    Genesis - A toolkit for working with phylogenetic data.
    Copyright (C) 2014-2022 Lucas Czech
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
    Contact:
    Lucas Czech <lczech@carnegiescience.edu>
    Department of Plant Biology, Carnegie Institution For Science
    260 Panama Street, Stanford, CA 94305, USA
*/
 
/*
    The code below is adapted from https://github.com/5cript/interval-tree
    which was published under the CC0-1.0 License (Creative Commons Zero v1.0 Universal).
    We modified the code to fit our needs and formatting, but the functionality is the same.
 */
 
#include <cassert>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <string>
#include <type_traits>
 
#include "genesis/utils/containers/interval_tree/fwd.hpp"
 
namespace genesis {
namespace utils {
 
// =================================================================================================
//     Helper Types
// =================================================================================================
 
using DefaultIntervalNumericalType = int;
 
struct EmptyIntervalData
{};
 
// =================================================================================================
//     Interval Types
// =================================================================================================
 
// -------------------------------------------------------------------------
//     left open `(]` interval
// -------------------------------------------------------------------------
 
struct IntervalLeftOpen
{
    template <typename NumericalType>
    static inline bool within(NumericalType b, NumericalType e, NumericalType p)
    {
        assert( b <= e );
        return (b < p) && (p <= e);
    }
 
    template <typename NumericalType>
    static inline std::string to_string(NumericalType b, NumericalType e, bool narrow = false)
    {
        if( narrow ) {
            return "("  + std::to_string(b) + ","  + std::to_string(e) + "]";
        } else {
            return "( " + std::to_string(b) + ", " + std::to_string(e) + " ]";
        }
    }
 
    template<typename NumericalType>
    static inline size_t length(NumericalType b, NumericalType e)
    {
        assert( b <= e );
        return e - b;
    }
};
 
// -------------------------------------------------------------------------
//     right open `[)` interval
// -------------------------------------------------------------------------
 
struct IntervalRightOpen
{
    template <typename NumericalType>
    static inline bool within(NumericalType b, NumericalType e, NumericalType p)
    {
        assert( b <= e );
        return (b <= p) && (p < e);
    }
 
    template <typename NumericalType>
    static inline std::string to_string(NumericalType b, NumericalType e, bool narrow = false)
    {
        if( narrow ) {
            return "["  + std::to_string(b) + ","  + std::to_string(e) + ")";
        } else {
            return "[ " + std::to_string(b) + ", " + std::to_string(e) + " )";
        }
    }
 
    template<typename NumericalType>
    static inline size_t length(NumericalType b, NumericalType e)
    {
        assert( b <= e );
        return e - b;
    }
};
 
// -------------------------------------------------------------------------
//     open `()` interval
// -------------------------------------------------------------------------
 
struct IntervalOpen
{
    template <typename NumericalType>
    static inline bool within(NumericalType b, NumericalType e, NumericalType p)
    {
        assert( b <= e );
        return (b < p) && (p < e);
    }
 
    template <typename NumericalType>
    static inline std::string to_string(NumericalType b, NumericalType e, bool narrow = false)
    {
        if( narrow ) {
            return "("  + std::to_string(b) + ","  + std::to_string(e) + ")";
        } else {
            return "( " + std::to_string(b) + ", " + std::to_string(e) + " )";
        }
    }
 
    template<
        typename NumericalType,
        typename std::enable_if< std::is_integral<NumericalType>::value >::type = 0
    >
    static inline size_t length(NumericalType b, NumericalType e)
    {
        // implementation for integer types.
 
        if( b == e ) {
            throw std::invalid_argument(
                "Invalid open interval with the same integer for the low and high values."
            );
        }
        assert( b <= e );
        return e - b - 1;
    }
 
    template<
        typename NumericalType,
        typename std::enable_if< ! std::is_integral<NumericalType>::value >::type = 0
    >
    static inline size_t length(NumericalType b, NumericalType e)
    {
        // implementation for floating point types.
 
        assert( b <= e );
        return e - b;
    }
};
 
// -------------------------------------------------------------------------
//     closed `[]` interval
// -------------------------------------------------------------------------
 
struct IntervalClosed
{
    template <typename NumericalType>
    static inline bool within(NumericalType b, NumericalType e, NumericalType p)
    {
        assert( b <= e );
        return (b <= p) && (p <= e);
    }
 
    template <typename NumericalType>
    static inline std::string to_string(NumericalType b, NumericalType e, bool narrow = false)
    {
        if( narrow ) {
            return "["  + std::to_string(b) + ","  + std::to_string(e) + "]";
        } else {
            return "[ " + std::to_string(b) + ", " + std::to_string(e) + " ]";
        }
    }
 
    template<
        typename NumericalType,
        typename std::enable_if< std::is_integral<NumericalType>::value >::type = 0
    >
    static inline size_t length(NumericalType b, NumericalType e)
    {
        // implementation for integer types.
 
        assert( b <= e );
        return e - b + 1;
    }
 
    template<
        typename NumericalType,
        typename std::enable_if< ! std::is_integral<NumericalType>::value >::type = 0
    >
    static inline size_t length(NumericalType b, NumericalType e)
    {
        // implementation for floating point types.
 
        assert( b <= e );
        return e - b;
    }
};
 
// =================================================================================================
//     Interval
// =================================================================================================
 
template <
    typename DataType = EmptyIntervalData,
    typename NumericalType = DefaultIntervalNumericalType,
    typename IntervalKind = IntervalClosed
>
struct Interval
{
public:
 
    // -------------------------------------------------------------------------
    //     Member Types
    // -------------------------------------------------------------------------
 
    using data_type      = DataType;
    using numerical_type = NumericalType;
    using value_type     = NumericalType;
    using interval_kind  = IntervalKind;
 
    static_assert(
        std::is_arithmetic<numerical_type>::value,
        "Interval can only be constructued with an arithmetic numerical type."
    );
 
    // -------------------------------------------------------------------------
    //     Constructors and Rule of Five
    // -------------------------------------------------------------------------
 
    #if __cplusplus >= 201703L
        constexpr
    #endif
    Interval( numerical_type low, numerical_type high )
        : Interval{ low, high, data_type{} }
    {}
 
    // Save version. See make_safe_interval() for a function to achieve this.
    // Interval(numerical_type low, numerical_type high)
    //     : low_{std::min(low, high)}
    //     , high_{std::max(low, high)}
    // {}
 
    Interval( numerical_type low, numerical_type high, data_type const& data )
        : Interval{ low, high, data_type{ data }}
    {}
 
    Interval( numerical_type low, numerical_type high, data_type&& data )
        : low_{low}
        , high_{high}
        , data_{std::move(data)}
    {
        if( low > high ){
            throw std::invalid_argument( "Cannot construct Interval with low > high." );
        }
    }
 
    ~Interval() = default;
 
    Interval( Interval const& ) = default;
    Interval( Interval&& )      = default;
 
    Interval& operator= ( Interval const& ) = default;
    Interval& operator= ( Interval&& )      = default;
 
    // -------------------------------------------------------------------------
    //     Data Accessors
    // -------------------------------------------------------------------------
 
    data_type const& data() const
    {
        return data;
    }
 
    data_type& data()
    {
        return data;
    }
 
    // -------------------------------------------------------------------------
    //     Comparators
    // -------------------------------------------------------------------------
 
    friend bool operator==( Interval const& lhs, Interval const& rhs )
    {
        assert( lhs.low_ <= lhs.high_ );
        assert( rhs.low_ <= rhs.high_ );
        return lhs.low_ == rhs.low_ && lhs.high_ == rhs.high_;
    }
 
    friend bool operator!=( Interval const& lhs, Interval const& rhs )
    {
        assert( lhs.low_ <= rhs.high_ );
        assert( rhs.low_ <= rhs.high_ );
        return lhs.low_ != rhs.low_ || lhs.high_ != rhs.high_;
    }
 
    bool overlaps(numerical_type l, numerical_type h) const
    {
        assert( low_ <= high_ );
        return low_ <= h && l <= high_;
    }
 
    bool overlaps_exclusive(numerical_type l, numerical_type h) const
    {
        assert( low_ <= high_ );
        return low_ < h && l < high_;
    }
 
    bool overlaps(Interval const& other) const
    {
        return overlaps(other.low_, other.high_);
    }
 
    bool overlaps_exclusive(Interval const& other) const
    {
        return overlaps_exclusive(other.low_, other.high_);
    }
 
    bool within(numerical_type value) const
    {
        assert( low_ <= high_ );
        return interval_kind::within(low_, high_, value);
    }
 
    bool within(Interval const& other) const
    {
        assert( low_ <= high_ );
        assert( other.low_ <= other.high_ );
        return low_ <= other.low_ && high_ >= other.high_;
    }
 
    // -------------------------------------------------------------------------
    //     Operators
    // -------------------------------------------------------------------------
 
    numerical_type operator-( Interval const& other ) const
    {
        if( overlaps(other) ) {
            return 0;
        }
 
        assert( low_ <= high_ );
        assert( other.low_ <= other.high_ );
        if( high_ < other.low_ ) {
            return other.low_ - high_;
        } else {
            return low_ - other.high_;
        }
    }
 
    numerical_type low() const
    {
        return low_;
    }
 
    numerical_type high() const
    {
        return high_;
    }
 
    numerical_type size() const
    {
        assert( low_ <= high_ );
        return high_ - low_;
    }
 
    numerical_type length() const
    {
        assert( low_ <= high_ );
        return interval_kind::length( low_, high_ );
    }
 
    std::string to_string( bool narrow = false ) const
    {
        return interval_kind::to_string( low_, high_, narrow );
    }
 
    operator std::string() const
    {
        return to_string();
    }
 
    // -------------------------------------------------------------------------
    //     Member Variables
    // -------------------------------------------------------------------------
 
private:
 
    numerical_type low_;
    numerical_type high_;
    data_type  data_;
};
 
} // namespace utils
} // namespace genesis
 
#endif // include guard