[MERGE] libi2ncommon: (reinhard) added contains_exact method to interval classes.

[libi2ncommon] / src / timefunc.cpp

/** @file
 * @brief time related functions.
 *
 * @copyright Copyright © 2001-2008 by Intra2net AG
 * @license commercial
 * @contact info@intra2net.com
 *
 */


#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <stdexcept>
#include <iterator>
#include <algorithm>

#include <time.h>
#include <sys/timeb.h>

#include <timefunc.hxx>
#include <i18n.h>

using namespace std;

double prec_time(void)
{
    struct timeb tb;
    double ret;

    ftime(&tb);

    ret=tb.time+(static_cast<float>(tb.millitm)/1000);

    return ret;
}

// converts ISO-DATE: 2003-06-13
int date_to_seconds(const std::string &date)
{
    int rtn = -1, year = -1, month = -1, day = -1;
    
    string::size_type pos = date.find("-");
    if (pos == string::npos)
        return rtn;
    
    istringstream in(string(date,0,pos));
    in >> year;
    year -= 1900;
        
    string dstr(date, pos+1);
    if ((pos = dstr.find("-")) == string::npos)
        return rtn;
    
    in.clear();
    in.str(string(dstr, 0, pos));
    in >> month;
    month -= 1;
        
    in.clear();
    in.str(string(dstr, pos+1));
    in >> day;
    
    if (year < 0 || month == -1 || day == -1)
        return rtn;
    
    struct tm tm_struct;
    bzero (&tm_struct, sizeof(struct tm));
    tm_struct.tm_year = year;
    tm_struct.tm_mon = month;
    tm_struct.tm_mday = day;
    tm_struct.tm_isdst = -1;
    
    rtn = mktime (&tm_struct);
    return rtn;
}

string make_nice_time(int seconds)
{
    ostringstream out;

    int days=seconds/86400;
    seconds%=86400;

    int hours=seconds/3600;
    seconds%=3600;

    int minutes=seconds/60;
    seconds%=60;

    if (days==1)
        out << i18n("1 day") << ", ";
    else if (days>1)
        out << days << ' ' << i18n("days") << ", ";

    out << setfill('0');
    out << setw(2) << hours << ':' << setw(2) << minutes << ':' << setw(2) << seconds;

    return out.str();
}

string format_full_time(int seconds)
{
    char buf[50];
    memset (buf, 0, 50);
    struct tm *ta = localtime ((time_t *)&seconds);

    strftime (buf, 49, "%d.%m.%Y %H:%M", ta);
    return string(buf);
}

void seconds_to_hour_minute(int seconds, int *hour, int *minute)
{
    if (hour != NULL) {
        *hour = 0;
        while (seconds >= 3600) {
            seconds-=3600;
            (*hour)++;
        }
    }

    if (minute != NULL) {
        *minute = 0;
        while (seconds >= 60) {
            seconds-=60;
            (*minute)++;
        }
    }
}

std::string output_hour_minute(int hour, int minute, bool h_for_00)
{
    ostringstream out;
    
    if (hour >= 0 && hour < 10)
        out << '0';
    out << hour;
    
    if (!h_for_00 || minute != 0)
    {
        out << ':';
        if (minute >= 0 && minute < 10)
            out << '0';
        out << minute;
    }
    else
        out << 'h';

    return out.str();
}

WEEK::WEEK(const std::string& daystring)
{
    int len=daystring.length();
    for (int p=0; p < len; p++)
    {
        char nr[2];
        nr[0]=daystring[p];
        nr[1]=0;
        istringstream c(nr);
        int wnr=-1;
        if (!(c >> wnr) || wnr<0 || wnr >6)
            throw range_error("illegal weekday >"+string(nr)+"< in "+daystring);
            
        days.set(wnr);
    }
}

std::string WEEK::get_daystring() const
{
    ostringstream out;
    for (int i = 0; i < 7; i++)
        if (days[i])
            out << i;

    return out.str();
}

std::string WEEK::get_displaystring() const
{
    string weekdays_str;

    // From Monday to Saturday
    int j;
    for (int i = 1; i < 7; i++)
    {
        if (days[i])
        {
            if (!weekdays_str.empty())
                weekdays_str += ", ";

            weekdays_str += get_day_display(static_cast<WEEKDAY>(i));

            // check if we can group two or more days
            j = i;
            while (days[j] && j < 7)
                j++;
            j--;

            // Sunday end of week? j -> 7
            if (j-i > 0 && j == 6 && days[0])
                j++;

            if (j-i > 1) 
            {
                if (j == 7)
                    weekdays_str += "-" + get_day_display(SU);
                else
                    weekdays_str += "-" + get_day_display(static_cast<WEEKDAY>(j));

                i = j;
            }
        }
    }

    // special: sunday
    if (days[0] && j != 7) 
    {
        if (!weekdays_str.empty())
            weekdays_str += ", ";

        weekdays_str += get_day_display(SU);
    }

    return weekdays_str;
}

std::string WEEK::get_netfilterstring() const
{
    string out;
    for (int i = 0; i < 7; i++)
        if (days[i])
        {
            if (!out.empty())
                out+=","; 
            out+=get_english_display(static_cast<WEEKDAY>(i));;
        }
            
    return out;
}

std::string WEEK::get_day_display(WEEKDAY day)
{
    string weekday_str;

    switch (day) {
        case MO:
            weekday_str = i18n("Mon");
            break;
        case TU:
            weekday_str = i18n("Tue");
            break;
        case WE:
            weekday_str = i18n("Wed");
            break;
        case TH:
            weekday_str = i18n("Thu");
            break;
        case FR:
            weekday_str = i18n("Fri");
            break;
        case SA:
            weekday_str = i18n("Sat");
            break;
        case SU:
            weekday_str = i18n("Sun");
            break;
        default:
            break;
    }

    return weekday_str;
}

std::string WEEK::get_english_display(WEEKDAY day)
{
    string weekday_str;

    switch (day) {
        case MO:
            weekday_str = "Mon";
            break;
        case TU:
            weekday_str = "Tue";
            break;
        case WE:
            weekday_str = "Wed";
            break;
        case TH:
            weekday_str = "Thu";
            break;
        case FR:
            weekday_str = "Fri";
            break;
        case SA:
            weekday_str = "Sat";
            break;
        case SU:
            weekday_str = "Sun";
            break;
        default:
            break;
    }

    return weekday_str;
}

string get_month_name(unsigned char month)
{
    string rtn;
    switch(month) {
        case 1:
            rtn = i18n("January");
            break;
        case 2:
            rtn = i18n("February");
            break;
        case 3:
            rtn = i18n("March");
            break;
        case 4:
            rtn = i18n("April");
            break;
        case 5:
            rtn = i18n("May");
            break;
        case 6:
            rtn = i18n("June");
            break;
        case 7:
            rtn = i18n("July");
            break;
        case 8:
            rtn = i18n("August");
            break;
        case 9:
            rtn = i18n("September");
            break;
        case 10:
            rtn = i18n("October");
            break;
        case 11:
            rtn = i18n("November");
            break;
        case 12:
            rtn = i18n("December");
            break;
        default:
            {
                ostringstream out;
                out << i18n("Illegal month:") << " " << month;
                rtn = out.str();
            }
    }

    return rtn;
}


/*
** implementaion of Interval
*/


/**
 * @brief clears the interval (make it empty).
 */
void Interval::clear()
{
    m_lower_bound = m_upper_bound = 0;
} // eo Interval::clear()


/**
 * @brief tests if there is some overlapping with another interval
 * @param other the other interval
 * @return @a true if the two intervals have a non empty intersection.
 */
bool Interval::intersects(const Interval& other) const
{
    return
        //  // other start within this:
        (other.m_lower_bound >= m_lower_bound and other.m_lower_bound < m_upper_bound )
        // // other end within this:
        or (other.m_upper_bound > m_lower_bound and other.m_upper_bound <= m_upper_bound )
        //  // other contains this
        or (other.m_lower_bound <= m_lower_bound and other.m_upper_bound >= m_upper_bound )
    ;
} // eo Interval::intersects(const Interval&)


/**
 * @brief tests if the current interval (fully) contains another one.
 * @param other the other interval.
 * @return @a true if the current interval fully contains the other interval.
 */
bool Interval::contains(const Interval& other) const
{
    return  (other.m_lower_bound >= m_lower_bound)
        and (other.m_upper_bound <= m_upper_bound)
    ;
} // eo Interval::contains(const Interval& other) const


/*
** implementation of Intervals:
*/


Intervals::Intervals()
{
} // eo Intervals::Intervals


void Intervals::clear()
{
    m_intervals.clear();
} // eo Intervals::clear()

/**
 * @brief tests if one of the intervals of the list intersects with the given interval.
 * @param other the interval to check for intersection.
 * @return @a true if there is an intersection.
 */
bool Intervals::intersects(const Interval& other) const
{
    for(const_iterator it= begin();
        it != end();
        ++it)
    {
        if ( it->intersects(other) )
        {
            return true;
        }
    }
    return false;
} // eo Intervals::intersects(const Interval&) const


/**
 * @brief tests if we have at least one intersection with another Intervals instance.
 * @param other the other instance.
 * @return @a true if there is an intersection.
 */
bool Intervals::intersects(const Intervals& other) const
{
    for(const_iterator it= begin();
        it != end();
        ++it)
    {
        if ( other.intersects( *it ) )
        {
            return true;
        }
    }
    return false;
} // eo Intervals::intersects(const Intervals&) const


/**
 * @brief adds a new interval to the list.
 * @param new_frame the new interval.
 *
 * Adds the interval to the list and joins overlapping intervals.
 *
 * @internal complexity O(n).
 */
void Intervals::add(const Interval& new_frame)
{
    if (not new_frame.is_valid() or new_frame.empty())
    {
        // well... we will not insert invalid or empty frames!
        return;
    }
    for (IntervalList::iterator it= m_intervals.begin();
         it != m_intervals.end();
         ++it)
    {
        Interval& current_frame = *it;
        if ( new_frame.m_lower_bound > current_frame.m_upper_bound )
        {
            // new_frame begins later than current end; go on:
            continue;
        }
        // at this point: the begin of the new frame is less then the current end.
        // now let's determine how we can insert the new frame:

        if ( new_frame.m_upper_bound < current_frame.m_lower_bound )
        {
            // new disjoint frame; insert it before the current frame:
            m_intervals.insert( it, new_frame );
            // and we are done.
            return;
        }
        // at this point: the end of the new frame is >= current begin. 
        if ( new_frame.m_upper_bound <= current_frame.m_upper_bound )
        {
            // the end of the new frame is within our current frame; we need to combine
            if (new_frame.m_lower_bound < current_frame.m_lower_bound)
            {
                // the new interval starts earlier; we need to adjust our current frame:
                current_frame.m_lower_bound = new_frame.m_lower_bound;
                current_frame.m_changed = true;
            }
            // NOTE no "else" part needed since in that case our current frame already
            // contains the new one!

            // we are done:
            return;
        }
        // at this point: end of new frame > end of current frame
        // so we need to extend the current frame; at least the end.
        // But we need to deal with intersects of following frames... *sigh*

        // first the simple part: let's see if we need to move the start:
        if ( new_frame.m_lower_bound < current_frame.m_lower_bound)
        {
            // yes, we need to move the start:
            current_frame.m_lower_bound = new_frame.m_lower_bound;
            current_frame.m_changed= true;
        }

        // now let's extend the end:
        current_frame.m_upper_bound = new_frame.m_upper_bound;
        current_frame.m_changed = true;

        // well... let's walk through the following frames; looking for more joins...:
        IntervalList::iterator it2 = it;
        while(      ++(it2=it) != m_intervals.end()
                and current_frame.m_upper_bound >= it2->m_lower_bound
           )
        {
            Interval next_frame= *it2;
            if ( current_frame.m_upper_bound < next_frame.m_upper_bound )
            {
                // in this case our end is within the next frame.
                // adjust our end.
                current_frame.m_upper_bound = next_frame.m_upper_bound;
            }
            // and remove the next frame since the current frame contains it (now):
            m_intervals.erase(it2);
        }
        // we are done!
        return;
    }
    // at this point: new frame starts later than the last frame ends
    // append the new frame:
    m_intervals.push_back( new_frame );
} // eo Intervals::add(const Interval&)


/**
 * @brief subtracts a time interval from the list.
 * @param del_frame the time interval to subtract.
 *
 * removes the time interval from the list; cut off parts from or remove existing
 * intervals if they overlap.
 *
 * @internal complexity O(n).
 */
void Intervals::sub(const Interval& del_frame)
{
    if (not del_frame.is_valid() or del_frame.empty() )
    {
        return;
    }
    for (IntervalList::iterator it= m_intervals.begin();
         it != m_intervals.end();
         )
    {
        Interval& current_frame = *it;
        if ( del_frame.m_lower_bound >= current_frame.m_upper_bound )
        {
            // del_frame begins later than current end; go on:
            ++it;
            continue;
        }
        // at this point: the begin of the del frame is less then the current end.
        if ( del_frame.m_upper_bound < current_frame.m_lower_bound )
        {
            // end is before our start; nothing to do.
            return;
        }
        // at this point: the end of the del frame is >= current begin.
        if ( del_frame.m_upper_bound < current_frame.m_upper_bound )
        {
            // del frame end point is within our interval.
            if ( del_frame.m_lower_bound > current_frame.m_lower_bound)
            {
                // the del frame is within our interval... we need to split:
                m_intervals.insert(it, Interval( current_frame.m_lower_bound, del_frame.m_lower_bound ) );
            }
            // adjust start of current frame:
            if (current_frame.m_lower_bound < del_frame.m_upper_bound)
            {
                current_frame.m_lower_bound= del_frame.m_upper_bound;
                current_frame.m_changed= true;
            }
            // and we are done!
            return;
        }
        // at this point the end of the del frame is >= current end
        if ( del_frame.m_lower_bound > current_frame.m_lower_bound )
        {
            // a part of the current interval needs to be preserved..
            // move the end.
            current_frame.m_upper_bound= del_frame.m_lower_bound;
            current_frame.m_changed= true;
            // and continue with the next interval:
            ++it;
            continue;
        }
        // at this point; the whole frame needs to be deleted..
        if ( it == m_intervals.begin())
        {
            m_intervals.erase(it);
            it= m_intervals.begin();
        }
        else
        {
            IntervalList::iterator it2= it++;
            m_intervals.erase(it2);
        }
    }
} // eo Intervals::sub(const Interval&)


/**
 * @brief returns if we contain an interval.
 * @param other the interval to check.
 * @return @a true if we cover the given interval, too.
 */
bool Intervals::contains(const Interval& other) const
{
    for(const_iterator it= begin();
        it != end();
        ++it)
    {
        if ( it->contains( other ))
        {
            return true;
        }
    }
    return false;
} // eo Intervals::contains(const Interval&) const


/**
 * @brief returns if we contain an exact interval.
 * @param other the interval to check.
 * @return @a true if we axactly contains the given interval.
 *
 * @note thsi differs from contain in the way, that we return only @a true
 * iff we have the given interval in our list; not only cover it.
 */
bool Intervals::contains_exact(const Interval& other) const
{
    for(const_iterator it= begin();
        it != end();
        ++it)
    {
        if ( *it == other)
        {
            return true;
        }
    }
    return false;
} // eo Intervals::contains_exact(const Interval&)const


/**
 * @brief returns if we contain another interval combination.
 * @param other the intervals to check.
 * @return @a true if we cover the given intervals, too.
 *
 * @internal we rely on the fact that the lists are sorted and contain
 * disjoint intervals.
 *
 * So this method has a complexity of O(n).
 */
bool Intervals::contains(const Intervals& other) const
{
    const_iterator my_it= begin();
    const_iterator other_it= other.begin();
    while( my_it != end() and other_it!= other.end() )
    {
        // seek the first interval which contains the lower bound of the current other interval
        while (my_it != end()
               and my_it->m_lower_bound > other_it->m_lower_bound
               and other_it->m_lower_bound >= my_it->m_upper_bound
              )
        {
            ++my_it;
        }
        if (my_it == end())
        {
            break;
        }
        if (not my_it->contains( *other_it ))
        {
            // if we don't contain the current other; we're done:
            return false;
        }
        //else check the next other interval:
        ++other_it;
    }
    return (other_it == other.end());
} // eo Intervals::contains(const Intervals&) const


/**
 * @brief combines to interval combinates for equality
 * @param other the other instance.
 * @return @a true if the other is equal to the current.
 *
 * @internal since the lists are sorted, we compare the interval lists.
 * Thus we have a complexity of O(n).
 */
bool Intervals::operator==(const Intervals& other) const
{
    // since we keep sorted lists: just compare the lists :-)
    return m_intervals == other.m_intervals;
} // eo Intervals::operator==(const Intervals&)


Intervals& Intervals::operator+=(const Interval& other)
{
    add(other);
    return *this;
} // eo operator+=(const Interval&)


Intervals& Intervals::operator-=(const Interval& other)
{
    sub(other);
    return *this;
} // eo operator-=(const Interval&)


/**
 * @brief adds the intervals of a second instance to us.
 * @param other the other instance.
 * @return self reference (allow chaining).
 *
 * @internal since we do simple loops over the other and our intervals
 * we have a complexity of O(n^2).
 *
 * @todo optimize if complexity becomes a problem.
 */
Intervals& Intervals::operator+=(const Intervals& other)
{
    for(const_iterator it= other.begin();
        it != other.end();
        ++it)
    {
        add( *it );
    }
    return *this;
} // eo operator+=(const Intervals&)


/**
 * @brief subtracts the intervals of a second instance from us.
 * @param other the other instance.
 * @return self reference (allow chaining).
 *
 * @internal since we do simple loops over the other and our intervals
 * we have a complexity of O(n^2).
 *
 * @todo optimize if complexity becomes a problem.
 */
Intervals& Intervals::operator-=(const Intervals& other)
{
    if (&other == this)
    {
        m_intervals.clear();
    }
    else
    {
        for(const_iterator it= other.begin();
            it != other.end();
            ++it)
        {
            sub( *it );
        }
    }
    return *this;
} // eo operator-=(const Intervals&)