From 1b5dfd989d55fe9997c9ed30cb037818a24b6edf Mon Sep 17 00:00:00 2001 From: Thomas Jarosch Date: Tue, 8 Jul 2008 11:30:07 +0000 Subject: [PATCH] [MERGE] libi2ncommon: (reinhard) added interval arithmetics to timefunc. --- src/timefunc.cpp | 369 ++++++++++++++++++++++++++++++++++++++++++++++++++++- src/timefunc.hxx | 150 +++++++++++++++++++++- test/Makefile.am | 2 +- 3 files changed, 506 insertions(+), 15 deletions(-) diff --git a/src/timefunc.cpp b/src/timefunc.cpp index fb5e672..f54a11f 100644 --- a/src/timefunc.cpp +++ b/src/timefunc.cpp @@ -1,10 +1,12 @@ -/*************************************************************************** - timecvt.cpp - description - ------------------- - begin : Fri May 11 2001 - copyright : (C) 2001 by STYLETEC - email : info@styletec.de - ***************************************************************************/ +/** @file + * @brief time related functions. + * + * @copyright Copyright © 2001-2008 by Intra2net AG + * @license commercial + * @contact info@intra2net.com + * + */ + #include #include @@ -12,6 +14,8 @@ #include #include #include +#include +#include #include #include @@ -353,3 +357,354 @@ string get_month_name(unsigned char month) return rtn; } + + +/* +** implementaion of Interval +*/ + +/** + * @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 + + +/** + * @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. + */ +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; + } + // 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; + } + + // now let's extend the end: + current_frame.m_upper_bound = new_frame.m_upper_bound; + + // 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. + */ +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: + current_frame.m_lower_bound= del_frame.m_upper_bound; + // 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; + // 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 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. + */ +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::comtains(const Intervals&) const + + +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&) + + +Intervals& Intervals::operator+=(const Intervals& other) +{ + for(const_iterator it= other.begin(); + it != other.end(); + ++it) + { + add( *it ); + } + return *this; +} // eo operator+=(const Intervals&) + + +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&) diff --git a/src/timefunc.hxx b/src/timefunc.hxx index 2c0e82c..b4657b5 100644 --- a/src/timefunc.hxx +++ b/src/timefunc.hxx @@ -1,15 +1,19 @@ -/*************************************************************************** - timecvt.hxx - description - ------------------- - begin : Fri May 11 2001 - copyright : (C) 2001 by STYLETEC - email : info@styletec.de - ***************************************************************************/ +/** @file + * @brief time related functions. + * + * @copyright Copyright © 2001-2008 by Intra2net AG + * @license commercial + * @contact info@intra2net.com + * + */ #ifndef __TIMEFUNC_HXX #define __TIMEFUNC_HXX +#include #include +#include + double prec_time(void); @@ -69,4 +73,136 @@ class WEEK static std::string get_english_display(WEEKDAY day); }; + +/** + * @brief structure representing a single (half-open) interval. + */ +class Interval +{ + public: + Interval() + : m_lower_bound(0) + , m_upper_bound(0) + { + } // + + Interval( unsigned int start, unsigned int end ) + : m_lower_bound(start) + , m_upper_bound(end) + { + } // + + bool is_valid() const + { + return m_lower_bound <= m_upper_bound; + } // eo is_valid() const + + bool empty() const + { + return m_lower_bound == m_upper_bound; + } // eo empty() const + + + unsigned int lower_bound() const { return m_lower_bound; } + unsigned int upper_bound() const { return m_upper_bound; } + + + bool operator== (const Interval& other) const + { + return m_lower_bound == other.m_lower_bound and m_upper_bound == other.m_upper_bound; + } // eo operator==(const Interval&) + + + /** + * @brief less operator. compares only the start times! + * @param other the other interval to compare with. + * @return @a true if the current start is less than the other start. + */ + bool operator<(const Interval& other) const + { + return m_lower_bound < other.m_lower_bound; + } // eo operator<(const Interval&) + + + bool intersects(const Interval& other) const; + bool contains(const Interval& other) const; + + + protected: + + friend class Intervals; + + unsigned int m_lower_bound; + unsigned int m_upper_bound; + +}; // eo Interval + + + +/** + * @brief structure representing a combination of single disjoint (half open) intervals. + * + * Basic idea is that this structure provides an interface for adding and + * subtracting single intervals and keeps the internal list of intervals as + * a list of disjoint intervals. + * + * @note the list is sorted by the start; lower comes first. + * + * @note the class provides some methods similar to STL container classes; + * i.e. it can be used with (at least some) STL algorithms. + * + * @internal + * we use a std::list for the intervals; this means we don't invalidate all + * iterators when we insert or delete within loops... + * And we use that fact!! + */ +class Intervals +{ + public: + typedef std::list< Interval > IntervalList; + typedef IntervalList::value_type value_type; + typedef IntervalList::const_iterator const_iterator; + typedef IntervalList::const_iterator iterator; // we allow only const... + typedef IntervalList::size_type size_type; + + public: + Intervals(); + + void add(const Interval& new_frame); + void sub(const Interval& new_frame); + + + const_iterator begin() const { return m_intervals.begin(); } + const_iterator end() const { return m_intervals.end(); } + + bool empty() const { return m_intervals.empty(); } + const Interval& front() const { return m_intervals.front(); } + const Interval& back() const { return m_intervals.back(); } + + size_type size() const { return m_intervals.size(); } + + bool intersects(const Interval& other) const; + bool intersects(const Intervals& other) const; + + bool contains(const Interval& other) const; + bool contains(const Intervals& other) const; + + bool operator==(const Intervals& other) const; + bool operator!=(const Intervals& other) const {return not (*this == other) ; } + + Intervals& operator+=(const Interval& other); + Intervals& operator-=(const Interval& other); + + Intervals& operator+=(const Intervals& other); + Intervals& operator-=(const Intervals& other); + + protected: + + std::list< Interval > m_intervals; + +}; // eo Intervals + + + + #endif diff --git a/test/Makefile.am b/test/Makefile.am index 25b8af3..a4793d0 100644 --- a/test/Makefile.am +++ b/test/Makefile.am @@ -2,7 +2,7 @@ INCLUDES = -I$(top_srcdir)/src @CPPUNIT_CFLAGS@ METASOURCES = AUTO check_PROGRAMS = test test_SOURCES = ip_range.cpp stringfunc.cpp test.cpp test_containerfunc.cpp \ - test_filefunc.cpp test_logging.cpp test_pidfile.cpp + test_filefunc.cpp test_logging.cpp test_pidfile.cpp test_timefunc.cpp test_LDADD = $(top_builddir)/src/libi2ncommon.la @CPPUNIT_LIBS@ TESTS = test -- 1.7.1