Lunchbox  1.10.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
37 template< typename T > class UnorderedIntervalSet
38 {
39 public:
41  class const_iterator;
42 
45 
47  void insert( const T& element );
48 
50  void insert( const T& startElement, const T& endElement );
51 
53  void insert( const UnorderedIntervalSet& rhs );
54 
56  void erase( const T& element );
57 
59  void erase( const T& startElement, const T& endElement );
60 
62  void clear();
63 
65  void swap( UnorderedIntervalSet& rhs );
66 
68  bool exists( const T& element ) const;
69 
74  const_iterator find( const T& element ) const;
75 
77  const_iterator begin() const;
78 
80  const_iterator end() const;
81 
83  size_t size() const;
84 
86  bool empty() const;
87 
88 
89 private:
90  typedef std::pair< T, bool > Edge;
91 
92  struct EdgeCompare
93  {
94  bool operator()( const Edge & p1, const Edge & p2 ) const
95  {
96  if( p1.first < p2.first )
97  return true;
98  if( p1.first == p2.first )
99  return p1.second && !p2.second;
100  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
void erase(const T &element)
Remove the given element.
const_iterator find(const T &element) const
Basic type definitions not provided by the operating system.
const_iterator begin() const
void clear()
Remove all stored elements.
void insert(const T &element)
Insert a new element.
A container to store intervals of elements efficently.
bool exists(const T &element) const
UnorderedIntervalSet()
Construct a new interval set.
const_iterator end() const
void swap(UnorderedIntervalSet &rhs)
Swap this container with another one.