rangelist.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 rangelist.h Interface for RangeList class */
00020 
00021 #ifndef __RANGELIST_H__
00022 #define __RANGELIST_H__
00023 
00024 #include <hn/range.h>
00025 #include <hn/lambda_placeholders.h>
00026 
00027 namespace CGComm {
00028         enum {
00029                 OP_RANGELIST = 0x11
00030         };
00031 }
00032 
00033 /**
00034  * RangeList<T> is a generic container for Range<T> type objects. It supports
00035  * all the operations single Range<T> objects support, however is also capable
00036  * of performing those operations over several ranges. RangeList<T> provides
00037  * public typedef CIter for iterating on the underlying implementation.
00038  * Ranges in RangeList are guaranteed to be ordered based on Range begin values,
00039  * as defined by Range<T> object.
00040  *
00041  * RangeList does not perform any lower or upper bound checking, except for
00042  * those inherent from the underlying data type.
00043  *
00044  * Ranges can be either push()'ed or merge()'d into RangeList. In the former
00045  * case, duplicates are allowed, and overlapping/bordering ranges are not merged
00046  * together into larger ranges. In the latter case, overlapping/bordering ranges
00047  * are compacted into bigger Range objects. The same logic applies to remove()
00048  * and erase() methods, former erasing an exact copy of the passed Range, latter
00049  * erasing a region of RangeList, possibly modifying existing ranges. After
00050  * call to erase(X, Y), it is guaranteed that RangeList::contains(X, Y) shall
00051  * return false, however in case of remove(), there is no such guarantee.
00052  *
00053  * All operations on RangeLists have logarithmic complexity, so it is possible
00054  * to store vast amounts of ranges here with little performance penalty.
00055  *
00056  * @param T         Data type the ranges consist of. This is generally integer.
00057  * @param RangeType Derived from @param T, this indicates the actual Range
00058  *                  object type. It is possible to override this parameter with
00059  *                  user-defined class, which implements the requirements posed
00060  *                  by Range class.
00061  */
00062 template<typename RangeType>
00063 class RangeList {
00064 public:
00065         //! Implementation object type
00066         typedef std::multiset<RangeType>      Impl;
00067         //! For iterating on the implementation
00068         typedef typename Impl::iterator       Iter;
00069         //! For iterating on the implementation
00070         typedef typename Impl::const_iterator CIter;
00071         //! The size type
00072         typedef typename RangeType::size_type size_type;
00073 
00074         //! Default constructor
00075         RangeList() {}
00076         //! Destructor
00077         ~RangeList() {}
00078         //! Construct and load from stream
00079         RangeList(std::istream &i) {
00080                 using namespace Utils;
00081                 uint32_t cnt = getVal<uint32_t>(i);
00082                 for (uint32_t j = 0; j < cnt; ++j) {
00083                         CHECK_THROW(getVal<uint8_t>(i) == CGComm::OP_RANGE);
00084                         CHECK_THROW(getVal<uint16_t>(i) == sizeof(size_type)*2);
00085                         m_ranges.insert(RangeType(i));
00086                 }
00087         }
00088 
00089         //! Output operator for streams
00090         friend std::ostream& operator<<(std::ostream &o, const RangeList &rl) {
00091                 Utils::putVal<uint8_t>(o, CGComm::OP_RANGELIST);
00092                 Utils::putVal<uint16_t>(o, rl.size()*(sizeof(size_type)*2+3));
00093                 Utils::putVal<uint32_t>(o, rl.size());
00094                 for_each(rl.begin(), rl.end(), o << __1);
00095                 return o;
00096         }
00097 
00098         /**
00099          * Push a range into the rangelist.
00100          *
00101          * @param r       Range to be inserted
00102          * @return        True if the range was inserted, false if it already
00103          *                existed (e.g. duplicates are not allowed)
00104          */
00105         bool push(const RangeType &r) {
00106                 Iter i = m_ranges.find(r);
00107                 if (i != end() && *i == r) {
00108                         return false;
00109                 }
00110                 m_ranges.insert(r);
00111                 return true;
00112         }
00113 
00114         /**
00115          * Remove an exact range from the rangelist.
00116          *
00117          * @param r       Range to be removed
00118          * @return        True if the exact range was found and removed, false
00119          *                otherwise.
00120          */
00121         bool remove(const RangeType &r) {
00122                 Iter i = m_ranges.find(r);
00123                 if (i != end() && *i == r) {
00124                         m_ranges.erase(i);
00125                         return true;
00126                 }
00127                 return false;
00128         }
00129 
00130         /**
00131          * Merge a range into the existing rangelist. Merging concept means all
00132          * ranges bordering or overlapping with the passed range will be
00133          * "merged" together with the passed range, and erased from the list,
00134          * after which the (now modified) passed range is inserted to the
00135          * list.
00136          *
00137          * @param r       Range to be merged into the rangelist.
00138          */
00139         void merge(RangeType r) {
00140                 Iter i = doGetContains(r);
00141                 while (i != end()) {
00142                         r.merge(*i);
00143                         m_ranges.erase(i);
00144                         i = doGetContains(r);
00145                 }
00146                 i = doGetBorders(r);
00147                 while (i != end()) {
00148                         r.merge(*i);
00149                         m_ranges.erase(i);
00150                         i = doGetBorders(r);
00151                 }
00152                 m_ranges.insert(r);
00153         }
00154 
00155         /**
00156          * Erase a range from the rangelist.
00157          *
00158          * @param r        Range to be erased
00159          */
00160         void erase(const RangeType &r) {
00161                 Iter i = doGetContains(r);
00162                 while (i != m_ranges.end()) {
00163                         RangeType one(*i), two(r);
00164                         boost::logic::tribool ret = one.erase(&two);
00165                         m_ranges.erase(i);
00166                         if (ret == true) {
00167                                 m_ranges.insert(one);
00168                         } else if (boost::indeterminate(ret)) {
00169                                 m_ranges.insert(one);
00170                                 m_ranges.insert(two);
00171                         }
00172                         i = doGetContains(r);
00173                 }
00174         }
00175 
00176         /**
00177          * Locate the first free (unused) range in the rangelist, optionally
00178          * indicating the upper bound until which to search.
00179          *
00180          * @param limit        Optional upper bound for searching
00181          * @return             An unused range
00182          */
00183         RangeType getFirstFree(
00184                 const size_type &limit = std::numeric_limits<size_type>::max()
00185         ) const {
00186                 size_type curPos = std::numeric_limits<size_type>::min();
00187                 size_type endPos = std::numeric_limits<size_type>::max();
00188                 if (size()) {
00189                         if ((*begin()).begin() > curPos) {
00190                                 endPos = (*begin()).begin() - 1;
00191                                 if (endPos - curPos + 1 > limit) {
00192                                         endPos = curPos + limit - 1;
00193                                 }
00194                         } else {
00195                                 curPos = (*begin()).end() + 1;
00196                                 if (++begin() == end()) {
00197                                         endPos = curPos + limit - 1;
00198                                 } else {
00199                                         endPos = (*++begin()).begin() - 1;
00200                                 }
00201                         }
00202                 } else {
00203                         endPos = curPos + limit - 1;
00204                 }
00205                 return RangeType(curPos, endPos);
00206         }
00207 
00208         /**
00209          * Check if a given range is contained within this rangelist.
00210          *
00211          * @param x        Range to be tested
00212          * @return         True if the range is even partially contained within
00213          *                 one of the existing ranges of this rangelist.
00214          *
00215          * \note Keep in mind that this method returns true even during partial
00216          *       matches, e.g. when a subrange of @param x overlaps with one
00217          *       (or more) of the existing ranges. True return value thus does
00218          *       not indicate here that @param x is fully contained within this
00219          *       rangelist. \see RangeList::containsFull()
00220          */
00221         bool contains(const RangeType &r) const {
00222                 return getContains(r) != end();
00223         }
00224 
00225         /**
00226          * Check whether a given range is completely contained within this.
00227          *
00228          * @param x       Range to be tested
00229          * @return        True if the range is fully contained in here.
00230          */
00231         bool containsFull(const RangeType &r) const {
00232                 CIter i = getContains(r);
00233                 if (i != end() && (*i).containsFull(r)) {
00234                         return true;
00235                 } else if (i != begin() && (*--i).containsFull(r)) {
00236                         return true;
00237                 }
00238                 return false;
00239         }
00240 
00241         /**
00242          * Locate the first (?) range which contains the passed range.
00243          *
00244          * @param r       Range to be searched for
00245          * @return        Iterator to the found range, or end() if not found.
00246          *
00247          * \note It is guaranteed that the returned range is the first range
00248          *       (first in the sense of lower-value) range that contains the
00249          *       questioned range. (hence the while-loop in here).
00250          */
00251         CIter getContains(const RangeType &r) const {
00252                 CIter i = m_ranges.lower_bound(r);
00253                 if (i != end() && (*i).contains(r)) {
00254                         while (i != begin() && (*--i).contains(r));
00255                         return (*i).contains(r) ? i : ++i;
00256                 } else if (i != begin() && (*--i).contains(r)) {
00257                         return i;
00258                 }
00259                 return end();
00260         }
00261 
00262         /**
00263          * Locate the first (?) range which borders with the passed range.
00264          *
00265          * @param r      Range to be searched for
00266          * @return       Iterator to the found range, or end() if not found
00267          */
00268         CIter getBorders(const RangeType &r) const {
00269                 Iter i = m_ranges.lower_bound(r);
00270                 if (i != end() && (*i).borders(r)) {
00271                         return i;
00272                 } else if (i != begin()) {
00273                         if ((*--i).borders(r)) {
00274                                 return i;
00275                         }
00276                 } else if (i != end()) {
00277                         if (++i != end() && (*i).borders(r)) {
00278                                  return i;
00279                         }
00280                 }
00281                 return end();
00282         }
00283 
00284         /**
00285          * @name More convenient versions for the above functions
00286          *
00287          * These methods construct the RangeType object internally from the
00288          * passed values. These only work when using built-in Range types, or
00289          * user-defined types which do not pose additional constructor argument
00290          * requirements.
00291          */
00292         //! @{
00293         template<typename X, typename Y>
00294         bool push(const X &x, const Y &y) {
00295                 return push(RangeType(x, y));
00296         }
00297         template<typename X, typename Y>
00298         bool remove(const X &x, const Y &y) {
00299                 return remove(RangeType(x, y));
00300         }
00301         template<typename X, typename Y>
00302         void merge(const X &x, const Y &y) {
00303                 merge(RangeType(x, y));
00304         }
00305         template<typename X, typename Y>
00306         void erase(const X &x, const Y &y) {
00307                 erase(RangeType(x, y));
00308         }
00309         template<typename X>
00310         bool contains(const X &x) const {
00311                 return contains(RangeType(x, x));
00312         }
00313         template<typename X, typename Y>
00314         bool contains(const X &x, const Y &y) const {
00315                 return contains(RangeType(x, y));
00316         }
00317         template<typename X>
00318         bool containsFull(const X &x) const {
00319                 return containsFull(RangeType(x, x));
00320         }
00321         template<typename X, typename Y>
00322         bool containsFull(const X &x, const Y &y) const {
00323                 return containsFull(RangeType(x, y));
00324         }
00325         template<typename X>
00326         CIter getContains(const X &x) const {
00327                 return getContains(RangeType(x, x));
00328         }
00329         template<typename X, typename Y>
00330         CIter getContains(const X &x, const Y &y) const {
00331                 return getContains(RangeType(x, y));
00332         }
00333         //! @}
00334 
00335         //! @name Generic accessors
00336         //! @{
00337         //! Returns number of elements in the rangelist
00338         size_t size() const { return m_ranges.size(); }
00339         //! Erases all elements in the list
00340         void clear() { m_ranges.clear(); }
00341         //! Tests if the rangelist is empty, e.g. size() == 0
00342         bool empty() const { return !size(); }
00343         //! @}
00344 
00345         /**
00346          *  @name Accessors
00347          *
00348          *  \note The list is sorted based on the center-point of the ranges,
00349          *        thus the first element in the list is not guaranteed to start
00350          *        before every other element, however, it is guaranteed to have
00351          *        the lowest begin+end/2 value.
00352          */
00353         //! @{
00354         //! Constant iterator to the first element of the list
00355         CIter begin() const { return m_ranges.begin(); }
00356         //! Constant iterator to one-past-end of the list
00357         CIter end()   const { return m_ranges.end(); }
00358         //! Iterator to the first element of the list
00359         Iter  begin() { return m_ranges.begin(); }
00360         //! Iterator to one-past-end of the list
00361         Iter  end()   { return m_ranges.end();   }
00362         //! @}
00363 
00364         /**
00365          * @name Accessors for first and last members of the list
00366          *
00367          * \return Reference to the element requested.
00368          * \throws std::runtime_error if the list is empty.
00369          */
00370         //! @{
00371         const RangeType& front() const {
00372                 CHECK_THROW(size());
00373                 return *begin();
00374         }
00375         const RangeType& back() const {
00376                 CHECK_THROW(size());
00377                 return *--end();
00378         }
00379         //! @}
00380 private:
00381         Impl m_ranges;
00382 
00383         /**
00384          * Implementation of getContains() method, using non-const types;
00385          * Locates the first (?) range which contains the passed range.
00386          *
00387          * @param r    Range to be searched for
00388          * @return     Iterator to the range, or end() if not found
00389          */
00390         Iter doGetContains(const RangeType &r) {
00391                 Iter i = m_ranges.lower_bound(r);
00392                 if (i != end() && (*i).contains(r)) {
00393                         while (i != begin() && (*--i).contains(r));
00394                         return (*i).contains(r) ? i : ++i;
00395                 } else if (i != begin() && (*--i).contains(r)) {
00396                         return i;
00397                 }
00398                 return end();
00399         }
00400 
00401         /**
00402          * Implementation of getBorders() method, using non-const types;
00403          * Locates the first range which borders with the passed range.
00404          *
00405          * @param r       Range to be searched for
00406          * @return        Iterator to the bordering range, or end() if not found
00407          */
00408         Iter doGetBorders(const RangeType &r) {
00409                 Iter i = m_ranges.lower_bound(r);
00410                 if (i != end() && (*i).borders(r)) {
00411                         return i;
00412                 } else if (i != begin()) {
00413                         if ((*--i).borders(r)) {
00414                                 return i;
00415                         }
00416                 } else if (i != end()) {
00417                         if (++i != end() && (*i).borders(r)) {
00418                                  return i;
00419                         }
00420                 }
00421                 return end();
00422         }
00423 };
00424 
00425 //! \name Commonly used RangeList types
00426 //! @{
00427 typedef RangeList<Range64> RangeList64;
00428 typedef RangeList<Range32> RangeList32;
00429 typedef RangeList<Range16> RangeList16;
00430 typedef RangeList<Range8 > RangeList8;
00431 //! @}
00432 
00433 #endif