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             : /**
      29             :  * A container to store intervals of elements efficently.
      30             :  *
      31             :  * The type can be any class or typename which has the semantics of natural
      32             :  * numbers for addition and comparison operations. Not thread-safe.
      33             :  *
      34             :  * Example: @include tests/IntervalSet.cpp
      35             :  */
      36           1 : template< typename T > 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             : 
      88             : private:
      89             :     typedef std::pair< T, bool > Edge;
      90             : 
      91             :     struct EdgeCompare
      92             :     {
      93          54 :         bool operator()( const Edge & p1, const Edge & p2 ) const
      94             :         {
      95          54 :             if( p1.first < p2.first )
      96          21 :                 return true;
      97          33 :             if( p1.first == p2.first )
      98          13 :                 return p1.second && !p2.second;
      99          20 :             return false;
     100             :         }
     101             :     };
     102             : 
     103             :     // The first element of the pair is the edge value, the second element is
     104             :     // true for the start of an interval and false for the end.
     105             :     typedef std::multiset< Edge,  EdgeCompare > EdgeSet;
     106             :     EdgeSet _intervals;
     107             :     size_t _size;
     108             : };
     109             : }
     110             : 
     111             : #include "intervalSet.ipp" // template implementation
     112             : 
     113             : #endif // LUNCHBOX_INTERVALSET_H