Lunchbox  1.8.0
unorderedIntervalSet.h
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 
35 template< typename T > class UnorderedIntervalSet
36 {
37 public:
39  class const_iterator;
40 
43 
45  void insert( const T& element );
46 
48  void insert( const T& startElement, const T& endElement );
49 
51  void insert( const UnorderedIntervalSet& rhs );
52 
54  void erase( const T& element );
55 
57  void erase( const T& startElement, const T& endElement );
58 
60  void clear();
61 
63  void swap( UnorderedIntervalSet& rhs );
64 
66  bool exists( const T& element ) const;
67 
72  const_iterator find( const T& element ) const;
73 
75  const_iterator begin() const;
76 
78  const_iterator end() const;
79 
81  size_t size() const;
82 
84  bool empty() const;
85 
86 
87 private:
88  typedef std::pair< T, bool > Edge;
89 
90  struct EdgeCompare
91  {
92  bool operator()( const Edge & p1, const Edge & p2 ) const
93  {
94  if( p1.first < p2.first )
95  return true;
96  if( p1.first == p2.first )
97  return p1.second && !p2.second;
98  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 "unorderedIntervalSet.ipp" // template implementation
111 
112 #endif // LUNCHBOX_UNORDEREDINTERVALSET_H