Line data    Source code

       1             : 
       2             : /* Copyright (c) 2008-2016, Juan Hernando <jhernando@fi.upm.es>
       3             :  *                          Daniel Nachbaur <danielnachbaur@epfl.ch>
       4             :  *
       5             :  * This library is free software; you can redistribute it and/or modify it under
       6             :  * the terms of the GNU Lesser General Public License version 2.1 as published
       7             :  * by the Free Software Foundation.
       8             :  *
       9             :  * This library is distributed in the hope that it will be useful, but WITHOUT
      10             :  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
      11             :  * FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
      12             :  * details.
      13             :  *
      14             :  * You should have received a copy of the GNU Lesser General Public License
      15             :  * along with this library; if not, write to the Free Software Foundation, Inc.,
      16             :  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
      17             :  */
      18             : 
      19             : #ifndef LUNCHBOX_INTERVALSET_H
      20             : #define LUNCHBOX_INTERVALSET_H
      21             : 
      22             : #include <lunchbox/types.h>
      23             : #include <set>
      24             : 
      25             : namespace lunchbox
      26             : {
      27             : /**
      28             :  * A container to store intervals of elements efficently.
      29             :  *
      30             :  * The type can be any class or typename which has the semantics of natural
      31             :  * numbers for addition and comparison operations. Not thread-safe.
      32             :  *
      33             :  * Example: @include tests/IntervalSet.cpp
      34             :  */
      35             : template <typename T>
      36           1 : class IntervalSet
      37             : {
      38             : public:
      39             :     /** Element iterator which points to a current element of type T. */
      40             :     class const_iterator;
      41             : 
      42             :     /** Construct a new interval set. @version 1.7.1 */
      43             :     IntervalSet();
      44             : 
      45             :     /** Insert a new element. @version 1.7.1 */
      46             :     void insert(const T& element);
      47             : 
      48             :     /** Insert a new closed interval of elements. @version 1.7.1 */
      49             :     void insert(const T& startElement, const T& endElement);
      50             : 
      51             :     /** Insert another interval set into this. @version 1.7.1 */
      52             :     void insert(const IntervalSet& rhs);
      53             : 
      54             :     /** Remove the given element. @version 1.7.1 */
      55             :     void erase(const T& element);
      56             : 
      57             :     /** Remove all element inside the given closed interval. @version 1.7.1 */
      58             :     void erase(const T& startElement, const T& endElement);
      59             : 
      60             :     /** Remove all stored elements. @version 1.7.1 */
      61             :     void clear();
      62             : 
      63             :     /** Swap this container with another one. @version 1.7.1 */
      64             :     void swap(IntervalSet& rhs);
      65             : 
      66             :     /** @return true if element exists. @version 1.7.1 */
      67             :     bool exists(const T& element) const;
      68             : 
      69             :     /**
      70             :      * @return an iterator to element if stored, end() otherwise.
      71             :      * @version 1.7.1
      72             :      */
      73             :     const_iterator find(const T& element) const;
      74             : 
      75             :     /** @return an iterator to the first element. @version 1.7.1 */
      76             :     const_iterator begin() const;
      77             : 
      78             :     /** @return an iterator to the end of the interval set. @version 1.7.1 */
      79             :     const_iterator end() const;
      80             : 
      81             :     /** @return the number of elements in the stored intervals. @version 1.7.1*/
      82             :     size_t size() const;
      83             : 
      84             :     /** @return true if container is empty. @version 1.7.1 */
      85             :     bool empty() const;
      86             : 
      87             : private:
      88             :     typedef std::pair<T, bool> Edge;
      89             : 
      90             :     struct EdgeCompare
      91             :     {
      92          54 :         bool operator()(const Edge& p1, const Edge& p2) const
      93             :         {
      94          54 :             if (p1.first < p2.first)
      95          21 :                 return true;
      96          33 :             if (p1.first == p2.first)
      97          13 :                 return p1.second && !p2.second;
      98          20 :             return false;
      99             :         }
     100             :     };
     101             : 
     102             :     // The first element of the pair is the edge value, the second element is
     103             :     // true for the start of an interval and false for the end.
     104             :     typedef std::multiset<Edge, EdgeCompare> EdgeSet;
     105             :     EdgeSet _intervals;
     106             :     size_t _size;
     107             : };
     108             : }
     109             : 
     110             : #include "intervalSet.ipp" // template implementation
     111             : 
     112             : #endif // LUNCHBOX_INTERVALSET_H