Line data    Source code

       1             : 
       2             : /* Copyright (c) 2008, Juan Hernando <jhernando@fi.upm.es>
       3             :  *               2013, 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_UNORDEREDINTERVALSET_H
      20             : #define LUNCHBOX_UNORDEREDINTERVALSET_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. The intervals are stored in
      33             :  * an unordered fashion. Not thread-safe.
      34             :  *
      35             :  * Example: @include tests/unorderedIntervalSet.cpp
      36             :  */
      37           1 : template< typename T > class UnorderedIntervalSet
      38             : {
      39             : public:
      40             :     /** Element iterator which points to a current element of type T. */
      41             :     class const_iterator;
      42             : 
      43             :     /** Construct a new interval set. @version 1.7.1 */
      44             :     UnorderedIntervalSet();
      45             : 
      46             :     /** Insert a new element. @version 1.7.1 */
      47             :     void insert( const T& element );
      48             : 
      49             :     /** Insert a new closed interval of elements. @version 1.7.1 */
      50             :     void insert( const T& startElement, const T& endElement );
      51             : 
      52             :     /** Insert another interval set into this. @version 1.7.1 */
      53             :     void insert( const UnorderedIntervalSet& rhs );
      54             : 
      55             :     /** Remove the given element. @version 1.7.1 */
      56             :     void erase( const T& element );
      57             : 
      58             :     /** Remove all element inside the given closed interval. @version 1.7.1 */
      59             :     void erase( const T& startElement, const T& endElement );
      60             : 
      61             :     /** Remove all stored elements. @version 1.7.1 */
      62             :     void clear();
      63             : 
      64             :     /** Swap this container with another one. @version 1.7.1 */
      65             :     void swap( UnorderedIntervalSet& rhs );
      66             : 
      67             :     /** @return true if element exists. @version 1.7.1 */
      68             :     bool exists( const T& element ) const;
      69             : 
      70             :     /**
      71             :      * @return an iterator to element if stored, end() otherwise.
      72             :      * @version 1.7.1
      73             :      */
      74             :     const_iterator find( const T& element ) const;
      75             : 
      76             :     /** @return an iterator to the first element. @version 1.7.1 */
      77             :     const_iterator begin() const;
      78             : 
      79             :     /** @return an iterator to the end of the interval set. @version 1.7.1 */
      80             :     const_iterator end() const;
      81             : 
      82             :     /** @return the number of elements in the stored intervals. @version 1.7.1*/
      83             :     size_t size() const;
      84             : 
      85             :     /** @return true if container is empty. @version 1.7.1 */
      86             :     bool empty() const;
      87             : 
      88             : 
      89             : private:
      90             :     typedef std::pair< T, bool > Edge;
      91             : 
      92             :     struct EdgeCompare
      93             :     {
      94          54 :         bool operator()( const Edge & p1, const Edge & p2 ) const
      95             :         {
      96          54 :             if( p1.first < p2.first )
      97          21 :                 return true;
      98          33 :             if( p1.first == p2.first )
      99          13 :                 return p1.second && !p2.second;
     100          20 :             return false;
     101             :         }
     102             :     };
     103             : 
     104             :     // The first element of the pair is the edge value, the second element is
     105             :     // true for the start of an interval and false for the end.
     106             :     typedef std::multiset< Edge,  EdgeCompare > EdgeSet;
     107             :     EdgeSet _intervals;
     108             :     size_t _size;
     109             : };
     110             : }
     111             : 
     112             : #include "unorderedIntervalSet.ipp" // template implementation
     113             : 
     114             : #endif // LUNCHBOX_UNORDEREDINTERVALSET_H