Lunchbox  1.15.0
Multi-threaded C++ toolbox library for all application developers creating high-performance multi-threaded programs.
intervalSet.h
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 
36 template< typename T > class IntervalSet
37 {
38 public:
40  class const_iterator;
41 
43  IntervalSet();
44 
46  void insert( const T& element );
47 
49  void insert( const T& startElement, const T& endElement );
50 
52  void insert( const IntervalSet& rhs );
53 
55  void erase( const T& element );
56 
58  void erase( const T& startElement, const T& endElement );
59 
61  void clear();
62 
64  void swap( IntervalSet& rhs );
65 
67  bool exists( const T& element ) const;
68 
73  const_iterator find( const T& element ) const;
74 
76  const_iterator begin() const;
77 
79  const_iterator end() const;
80 
82  size_t size() const;
83 
85  bool empty() const;
86 
87 
88 private:
89  typedef std::pair< T, bool > Edge;
90 
91  struct EdgeCompare
92  {
93  bool operator()( const Edge & p1, const Edge & p2 ) const
94  {
95  if( p1.first < p2.first )
96  return true;
97  if( p1.first == p2.first )
98  return p1.second && !p2.second;
99  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
Basic type definitions not provided by the operating system.
const_iterator find(const T &element) const
bool exists(const T &element) const
A container to store intervals of elements efficently.
Definition: intervalSet.h:36
IntervalSet()
Construct a new interval set.
void erase(const T &element)
Remove the given element.
void swap(IntervalSet &rhs)
Swap this container with another one.
bool empty() const
void insert(const T &element)
Insert a new element.
const_iterator begin() const
Abstraction layer and common utilities for multi-threaded programming.
Definition: algorithm.h:32
const_iterator end() const
size_t size() const
void clear()
Remove all stored elements.