Lunchbox  1.17.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 {
35 template <typename T>
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 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 "intervalSet.ipp" // template implementation
111 
112 #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:29
const_iterator end() const
size_t size() const
void clear()
Remove all stored elements.