interval.hpp

Go to the documentation of this file.

/*****************************************************************************
    
    interval.hpp -- Approches to represent intervals.

    This file is a part of the Arageli library.

    Copyright (C) Nikolai Yu. Zolotykh, 1999--2006
    Copyright (C) Sergey S. Lyalin, 2006
    University of Nizhni Novgorod, Russia, 2005--2006

*****************************************************************************/

#ifndef _ARAGELI_interval_hpp_
#define _ARAGELI_interval_hpp_

#include "config.hpp"

#include <iostream>
#include <sstream>
#include <utility>

#include "frwrddecl.hpp"
#include "function_traits.hpp"
#include "factory.hpp"
#include "cmp.hpp"
//#include "vector.hpp"

#include "std_import.hpp"


namespace Arageli
{

enum interval_kind
{
    interval_empty = 0, 
    interval_point = 1, 
    interval_length = 2 
};


template <typename T> class interval
{
    std::pair<T, T> lims;

    template <typename T1>
    friend class interval;

public:
    
    typedef T value_type;

    typedef typename binary_function_traits<function_tag::minus, T, T>::result_type difference_type;
    
    interval () : lims(null<T>(), null<T>()) {}

    template <typename T1>
    interval (const T1& x) : lims(x, x) {}

    template <typename T1, typename T2>
    interval (const T1& first_a, const T2& second_a)
    : lims(first_a, second_a) {}

    template <typename T1>
    interval (const interval<T1>& x)
    : lims(x.lims.first, x.lims.second) {}


    interval (const char* s)
    {
        std::istringstream buf(s);
        buf >> *this;
    }

    template <typename T1>
    interval& operator= (const T1& x)
    {
        lims.first = x;
        lims.second = x;
        return *this;
    }

    template <typename T1>
    interval& operator= (const interval<T1>& x)
    {
        lims.first = x.lims.first;
        lims.second = x.lims.second;
        return *this;
    }

    interval& operator= (const char* s)
    {
        std::istringstream buf(s);
        buf >> *this;
        return *this;
    }

    const T& first () const { return lims.first; }
    const T& left () const { return lims.first; }
    const T& second () const { return lims.second; }
    const T& right () const { return lims.second; }

    T& first () { return lims.first; }
    T& left () { return lims.first; }
    T& second () { return lims.second; }
    T& right () { return lims.second; }
    
    bool is_point () const { return lims.first == lims.second; }

    bool is_empty () const { return lims.first > lims.second; }

    bool is_negligible () const { return lims.first >= lims.second; }

    interval_kind kind () const
    { return interval_kind(cmp(lims.second, lims.first) + 1); }
    
    typename binary_function_traits<function_tag::minus, T, T>::result_type
    length () const { return lims.second - lims.first; }

    void turn () { swap(lims.first, lims.second); }

    template <typename T1>
    bool on_limits (const T1& x) const
    { return lims.first == x || lims.second == x; }

    template <typename T1>
    bool inside (const T1& x) const
    { return lims.first < x && x < lims.second; }

    template <typename T1>
    bool outside (const T1& x) const
    { return x < lims.first || lims.second < x; }

    template <typename T1>
    interval& operator+= (const interval<T1>& x)
    { return *this = *this + x; }

    template <typename T1>
    interval& operator-= (const interval<T1>& x)
    { return *this = *this - x; }

    template <typename T1>
    interval& operator*= (const interval<T1>& x)
    { return *this = *this * x; }

    template <typename T1>
    interval& operator/= (const interval<T1>& x)
    { return *this = *this / x; }

    interval& operator++ () { return *this += interval(unit<T>()); }
    interval& operator-- () { return *this -= interval(unit<T>()); }

    interval operator++ (int) { interval t = *this; operator++(); return t; }
    interval operator-- (int) { interval t = *this; operator--(); return t; }

    const interval& operator+ () const { return *this; }
    interval operator- () const { return interval(null<T>()) - *this; }

};


template <typename T>
interval<T> operator+ (const interval<T>& a, const interval<T>& b)
{
    // WARNING! There is simpler way for reals.
    
    T   p1 = a.first() + b.first(),
        p2 = a.first() + b.second(),
        p3 = a.second() + b.first(),
        p4 = a.second() + b.second();
    
    return interval<T>
    (
        std::min(std::min(p1, p2), std::min(p3, p4)),
        std::max(std::max(p1, p2), std::max(p3, p4))
    );
}

template <typename T>
interval<T> operator- (const interval<T>& a, const interval<T>& b)
{
    // WARNING! There is simpler way for reals.
    
    T   p1 = a.first() - b.first(),
        p2 = a.first() - b.second(),
        p3 = a.second() - b.first(),
        p4 = a.second() - b.second();
    
    return interval<T>
    (
        std::min(std::min(p1, p2), std::min(p3, p4)),
        std::max(std::max(p1, p2), std::max(p3, p4))
    );
}

template <typename T>
interval<T> operator* (const interval<T>& a, const interval<T>& b)
{
    // WARNING! There is simpler way for reals.
    
    T   p1 = a.first() * b.first(),
        p2 = a.first() * b.second(),
        p3 = a.second() * b.first(),
        p4 = a.second() * b.second();
    
    return interval<T>
    (
        std::min(std::min(p1, p2), std::min(p3, p4)),
        std::max(std::max(p1, p2), std::max(p3, p4))
    );
}

template <typename T>
interval<T> operator/ (const interval<T>& a, const interval<T>& b)
{
    // WARNING! There is simpler way for reals.
    ARAGELI_ASSERT_0(sign(b.first())*sign(b.second()) > 0);
    
    T   p1 = a.first() / b.first(),
        p2 = a.first() / b.second(),
        p3 = a.second() / b.first(),
        p4 = a.second() / b.second();
    
    return interval<T>
    (
        std::min(std::min(p1, p2), std::min(p3, p4)),
        std::max(std::max(p1, p2), std::max(p3, p4))
    );
}


template <typename T1, typename T2>
inline bool are_overlap_intervals_oooo (const T1& a, const T2& b)
{
    if(a.is_negligible() || b.is_negligible())return false;
    return
        (a.first() < b.first()) ? (b.first < a.second) : (a.first < b.second);
}


//template <typename T1, typename T2>
//inline bool is_overlap_interval_cooo (const T1& a, const T2& b)
//{
//  if(a.is_negligible() || b.is_negligible())return false;
//  return
//      (a.first() < b.first()) ? (b.first < a.second) : (a.first < b.second);
//}
//

template <typename Seg1, typename Seg2>
inline bool is_overlap_segs (const Seg1& a, const Seg2& b)
{
    return (a.first() <= b.first()) ? (b.first() <= a.second()) : (a.first() <= b.second());
}


template <typename Out, typename T>
Out& operator<< (Out& out, const interval<T>& x)
{
    out << "(" << x.first() << ", " << x.second() << ")";
    return out;
}

template <typename In, typename T>
In& operator>> (In& in, interval<T>& x)
{
    vector<T, false> buf;   // WARNING! TEMPORARY!
    in >> buf;
    if(!in && !in.eof() || buf.size() != 2)
        in.clear(std::ios::badbit);
    else
    {
        x.first() = buf[0];
        x.second() = buf[1];
    }

    return in;
}

//template <typename T1, typename T2, typename Outiter>
//void generate_range_helper (interval<T1>& t1, const interval<T2>& t2, Outiter outiter)
//{ ARAGELI_ASSERT_ALWAYS(!"generate_range_helper is not implemented for interval"); }
//
//
//template <typename T1, typename T2, typename T3, typename Outiter>
//void generate_range_helper (interval<T1>& t1, const interval<T2>& t2, const interval<T3>& t3, Outiter outiter)
//{ ARAGELI_ASSERT_ALWAYS(!"generate_range_helper is not implemented for interval"); }


template <typename T1, typename T2>
bool are_comparable_oooo (const interval<T1>& a, const interval<T2>& b)
{ return !are_overlap_intervals_oooo(a, b); }



template <typename T1, typename T2>
int cmp (const interval<T1>& a, const interval<T2>& b)
{
    if(a.is_empty())
        if(b.is_empty())return 0;
        else return -1;
    else if(b.is_empty())return +1;

    ARAGELI_ASSERT_1(!a.is_empty() && !b.is_empty());

    if(a.left() < b.left())return -1;
    else if(a.left() > b.left())return +1;
    else if(a.right() < b.right())return -1;
    else if(a.right() > b.right())return +1;
    else return 0;
}


template <typename T1, typename T2>
bool operator< (const interval<T1>& a, const interval<T2>& b)
{
    if(a.is_empty() || b.is_empty())return true;
    return a.right() < b.left();
}


template <typename T1, typename T2>
bool operator> (const interval<T1>& a, const interval<T2>& b)
{
    if(a.is_empty() || b.is_empty())return true;
    return b.right() < a.left();
}


template <typename T1, typename T2>
bool operator<= (const interval<T1>& a, const interval<T2>& b)
{
    if(a.is_empty() || b.is_empty())return true;
    return a.right() <= b.left();
}


template <typename T1, typename T2>
bool operator>= (const interval<T1>& a, const interval<T2>& b)
{
    if(a.is_empty() || b.is_empty())return true;
    return b.right() <= a.left();
}


template <typename T1, typename T2>
bool operator== (const interval<T1>& a, const interval<T2>& b)
{
    if(a.is_empty() && b.is_empty())return true;
    return a.left() == b.left() && a.right() == b.right();
}


template <typename T1, typename T2>
inline bool operator!= (const interval<T1>& a, const interval<T2>& b)
{ return !(a == b); }


template <typename T>
interval<T> abs (const interval<T>& x)
{
    if(x.is_empty())return x;

    if(!x.outside(null<T>()))
        return interval<T>(null<T>(), std::max(abs(x.left()), abs(x.right())));
    else
    {
        T absleft = abs(x.left()), absright = abs(x.right());
        return interval<T>(std::min(absleft, absright), std::max(absleft, absright));
    }
}




} // namesapce Arageli

namespace std
{

template <typename T>
inline Arageli::interval<T> abs (const Arageli::interval<T>& x)
{ return Arageli::abs(x); }

}


//#ifdef ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE
//  #define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_INTERVAL
//  #include "interval.cpp"
//  #undef  ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_INTERVAL
//#endif

#endif

---