range.h

Go to the documentation of this file.
00001 /**
00002  *  Copyright (C) 2004-2005 Alo Sarv <madcat_@users.sourceforge.net>
00003  *
00004  *  This program is free software; you can redistribute it and/or modify
00005  *  it under the terms of the GNU General Public License as published by
00006  *  the Free Software Foundation; either version 2 of the License, or
00007  *  (at your option) any later version.
00008  *
00009  *  This program is distributed in the hope that it will be useful,
00010  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  *  GNU General Public License for more details.
00013  *
00014  *  You should have received a copy of the GNU General Public License
00015  *  along with this program; if not, write to the Free Software
00016  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00017  */
00018 
00019 /** @file range.h Interface for Range class */
00020 
00021 #ifndef __RANGE_H__
00022 #define __RANGE_H__
00023 
00024 #include <hn/osdep.h>
00025 #include <hn/utils.h>
00026 #include <boost/logic/tribool.hpp>
00027 #include <set>
00028 #include <limits>
00029 
00030 namespace CGComm {
00031         enum {
00032                 OP_RANGE = 0x10
00033         };
00034 }
00035 
00036 /**
00037  * Range object represents a range of values. Range object always has a begin
00038  * and an end (inclusive). Ranges can be compared, merged, and split. The
00039  * underlying object type used for representing the begin/end values of the
00040  * range are generally required to be of integer type, but any suitable
00041  * user-defined type can also be used that satisfies the comparison operations
00042  * used by this class.
00043  */
00044 template<typename T>
00045 class Range {
00046 public:
00047         typedef T size_type;
00048 
00049         //! @name Construction
00050         //! @{
00051         template<typename X, typename Y>
00052         Range(const X &begin, const Y &end) : m_begin(begin), m_end(end) {
00053                 CHECK_THROW(m_begin <= m_end);
00054         }
00055         template<typename X>
00056         Range(const Range<X> &x) {
00057                 m_begin = x.m_begin;
00058                 m_end = x.m_end;
00059         }
00060         template<typename X, typename Y>
00061         Range(const std::pair<X, Y> r) : m_begin(r.first), m_end(r.second) {
00062                 CHECK_THROW(m_begin <= m_end);
00063         }
00064         Range(std::istream &i) {
00065                 m_begin = Utils::getVal<T>(i);
00066                 m_end   = Utils::getVal<T>(i);
00067                 CHECK_THROW(m_end >= m_begin);
00068         }
00069         template<typename X>
00070         Range& operator=(const Range<X> &x) {
00071                 m_begin = x.m_begin;
00072                 m_end = x.m_end;
00073         }
00074         //! Constructs lenght=1 range
00075         explicit Range(const T &t) : m_begin(t), m_end(t) {}
00076         //!@}
00077 
00078         //! @name Comparing ranges
00079         //! @{
00080         template<typename X>
00081         bool operator<(const Range<X> &x) const {
00082                 return (m_begin + m_end) / 2 < (x.m_begin + x.m_end) / 2;
00083         }
00084         template<typename X>
00085         bool operator>(const Range<X> &x) const {
00086                 return !(*this < x);
00087         }
00088         template<typename X>
00089         bool operator==(const Range<X> &x) const {
00090                 return m_begin == x.m_begin && m_end == x.m_end;
00091         }
00092         template<typename X>
00093         bool operator!=(const Range<X> &x) const {
00094                 return !(m_begin == x.m_begin && m_end == x.m_end);
00095         }
00096         friend std::ostream& operator<<(std::ostream &o, const Range &r) {
00097                 Utils::putVal<uint8_t>(o, CGComm::OP_RANGE);
00098                 Utils::putVal<uint16_t>(o, sizeof(T)*2);
00099                 Utils::putVal<T>(o, r.m_begin);
00100                 Utils::putVal<T>(o, r.m_end);
00101                 return o;
00102         }
00103         //!@}
00104 
00105         //! @name Accessors
00106         //! @{
00107         T begin()  const { return m_begin;             }
00108         T end()    const { return m_end;               }
00109         T length() const { return m_end - m_begin + 1; }
00110         void begin(const T &b) {
00111                 CHECK_THROW(b <= m_end);
00112                 m_begin = b;
00113         }
00114         void end(const T &e) {
00115                 CHECK_THROW(e >= m_begin);
00116                 m_end = e;
00117         }
00118         //! @}
00119 
00120         //! @name Operations
00121         //! @{
00122 
00123         /**
00124          * Merge another range with current one.
00125          *
00126          * @param x    Range to merge into current one.
00127          *
00128          * \note Implies that *this contains() @param x. Does nothing if that
00129          *       is not true.
00130          */
00131         template<typename X>
00132         void merge(const Range<X> &x) {
00133                 if (m_begin > x.m_begin) {
00134                         m_begin = x.m_begin;
00135                 }
00136                 if (m_end < x.m_end) {
00137                         m_end = x.m_end;
00138                 }
00139                 if (m_end + 1 == x.m_begin) {
00140                         m_end = x.m_end;
00141                 }
00142                 if (m_begin - 1 == x.m_end) {
00143                         m_begin = x.m_begin;
00144                 }
00145         }
00146 
00147         /**
00148          * Erase target range from current one.
00149          *
00150          * @param x    Pointer to range to be erased. If range splitting
00151          *             happened, it will be modified to contain the second half
00152          *             of the resulting two ranges.
00153          * @return     True if *this was truncated. False if this range was
00154          *             completely cleared out by @param x. boost::indeterminate
00155          *             if *this was split into two, and @param x contains the
00156          *             second half.
00157          */
00158         template<typename X>
00159         boost::logic::tribool erase(Range<X> *x) {
00160                 if (x->m_begin <= m_begin && x->m_end >= m_end) {
00161                         return false;
00162                 }
00163                 if (m_begin >= x->m_begin) {
00164                         m_begin = x->m_end + 1;
00165                         return true;
00166                 } else if (m_end <= x->m_end) {
00167                         m_end = x->m_begin - 1;
00168                         return true;
00169                 }
00170                 if (contains(x->m_begin) && contains(x->m_end)) {
00171                         X tmp = m_end;
00172                         m_end = x->m_begin - 1;
00173                         x->m_begin = x->m_end + 1;
00174                         x->m_end = tmp;
00175                         return boost::indeterminate;
00176                 }
00177                 return true;
00178         }
00179 
00180         /**
00181          * Check if *this contains @param x. A range is considered to contain
00182          * another range if it even partially overlaps with another range. To
00183          * check if another range is completely contained within current range,
00184          * use containsFull() method.
00185          *
00186          * @param x      Range to be checked against current range.
00187          * @return       True if containment is true, false otherwise.
00188          */
00189         template<typename X>
00190         bool contains(const Range<X> &x) const {
00191                 if (contains(x.m_begin)) {
00192                         return true;
00193                 } else if (contains(x.m_end)) {
00194                         return true;
00195                 } else if (x.containsFull(*this)) {
00196                         return true;
00197                 }
00198                 return false;
00199         }
00200 
00201         /**
00202          * Simplified version of the above, this method checks if a given value
00203          * exists in this range.
00204          *
00205          * @param x         Value to check
00206          * @return          True if the value is within this range
00207          */
00208         template<typename X>
00209         bool contains(const X &x) const {
00210                 return x >= m_begin && x <= m_end;
00211         }
00212 
00213         /**
00214          * Check if *this completely contains @param x
00215          *
00216          * @param x    Range to be checked against current range
00217          * @return     True if @param x is completely within *this.
00218          */
00219         template<typename X>
00220         bool containsFull(const Range<X> &x) const {
00221                 if (m_begin <= x.m_begin && m_end >= x.m_end) {
00222                         return true;
00223                 } else {
00224                         return false;
00225                 }
00226         }
00227 
00228         /**
00229          * Check if @param x borders with *this. Bordering is defined if @param
00230          * x begins right after *this's end, or *this's begin starts right after
00231          * @param x's end.
00232          *
00233          * @param x      Range to be checked against bordering
00234          * @return       True if @param x borders with *this.
00235          */
00236         template<typename X>
00237         bool borders(const Range<X> &x) const {
00238                 if (m_begin - 1 == x.m_end) {
00239                         return true;
00240                 }
00241                 if (m_end + 1 == x.m_begin) {
00242                         return true;
00243                 }
00244                 return false;
00245         }
00246 
00247         //! @}    !operations
00248 
00249         //! @name Convenience methods for easier usage
00250         //! @{
00251         template<typename X>
00252         bool contains(const X &x, const X &y) {
00253                 return contains(Range(x, y));
00254         }
00255         template<typename X>
00256         bool containsFull(const X &x, const X &y) {
00257                 return containsFull(Range(x, y));
00258         }
00259         template<typename X>
00260         boost::logic::tribool erase(const X &x, const X &y) {
00261                 return erase(Range(x, y));
00262         }
00263         //!@}
00264 private:
00265         //! Default constructor behaviour cannot be defined and is forbidden
00266         Range();
00267 
00268         T m_begin;   //! begin offset
00269         T m_end;     //! end offset
00270 
00271         //! Be-friend with all our instances
00272         template<typename X> friend class Range;
00273 };
00274 
00275 //! \name Commonly used Range types
00276 //! @{
00277 typedef Range<uint64_t> Range64;
00278 typedef Range<uint32_t> Range32;
00279 typedef Range<uint16_t> Range16;
00280 typedef Range<uint8_t>  Range8;
00281 //! @}
00282 
00283 #endif