libdballe  7.7
stlutils.h
1 /*
2  * core/stlutils - Useful functions to work with the STL
3  *
4  * Copyright (C) 2013 ARPA-SIM <urpsim@smr.arpa.emr.it>
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18  *
19  * Author: Enrico Zini <enrico@enricozini.com>
20  */
21 
22 #ifndef DBA_CORE_STLUTILS_H
23 #define DBA_CORE_STLUTILS_H
24 
25 #include <vector>
26 #include <set>
27 #include <memory>
28 
29 namespace dballe {
30 namespace stl {
31 
32 namespace stlutils {
33 
34 template<typename T>
35 struct Sequence
36 {
37  virtual ~Sequence() {}
38  virtual bool valid() const = 0;
39  virtual const T& get() const = 0;
40  virtual void next() = 0;
41 };
42 
43 } // back to dballe::stl
44 
46 template<typename T>
47 struct Sequences : public std::vector<stlutils::Sequence<T>*>
48 {
49  typedef typename std::vector<stlutils::Sequence<T>*>::iterator iterator;
50  typedef typename std::vector<stlutils::Sequence<T>*>::const_iterator const_iterator;
51 
52  Sequences() {}
53  ~Sequences()
54  {
55  for (iterator i = this->begin(); i != this->end(); ++i)
56  delete *i;
57  }
58 
60  void add_singleton(const T& val);
61 
62  // Add a begin-end range
63  template<typename ITER>
64  void add(const ITER& begin, const ITER& end);
65 
66  // Add a container's begin()-end() range
67  template<typename C>
68  void add(const C& container);
69 
70  void add(std::unique_ptr< stlutils::Sequence<T> >& sequence);
71 
72  // Add the union of the given sequences
73  void add_union(std::unique_ptr< Sequences<T> >& sequences);
74 
75  // Add the union of the given sequences
76  void add_intersection(std::unique_ptr< Sequences<T> >& sequences);
77 
78 private:
79  Sequences(const Sequences&);
80  Sequences& operator=(const Sequences&);
81 };
82 
83 namespace stlutils {
84 
85 template<typename T>
87 {
88  Sequences<T>* sequences;
89 
90  SequenceGenerator() : sequences(0) {}
91  SequenceGenerator(const SequenceGenerator<T>& sg) : sequences(sg.sequences)
92  {
93  // unique_ptr semantics
94  const_cast<SequenceGenerator<T>*>(&sg)->sequences = 0;
95  }
96  SequenceGenerator(std::unique_ptr< Sequences<T> >& sequences) : sequences(sequences.release()) {}
97  ~SequenceGenerator() { if (sequences) delete sequences; }
98 
99  SequenceGenerator<T>& operator=(const SequenceGenerator<T>& sg)
100  {
101  // unique_ptr semantics
102  if (&sg == this) return this;
103  if (sequences) delete sequences;
104  sequences = sg.sequences;
105  const_cast<SequenceGenerator<T>*>(&sg)->sequences = 0;
106  return *this;
107  }
108 
109  void clear()
110  {
111  if (sequences) delete sequences;
112  sequences = 0;
113  }
114 
115  bool has_items() const { return sequences != 0; }
116 
117  bool operator==(const SequenceGenerator<T>& i) const
118  {
119  if (sequences == i.sequences) return true;
120  if (!sequences || !i.sequences) return false;
121  return *sequences == *i.sequences;
122  }
123  bool operator!=(const SequenceGenerator<T>& i) const
124  {
125  if (sequences == i.sequences) return false;
126  if (!sequences || !i.sequences) return true;
127  return *sequences != *i.sequences;
128  }
129 };
130 
131 template<typename T>
132 struct Itersection : public SequenceGenerator<T>, public std::iterator<std::forward_iterator_tag, T>
133 {
134  Itersection() {}
136  Itersection(std::unique_ptr< Sequences<T> >& sequences)
137  : SequenceGenerator<T>(sequences)
138  {
139  sync_iters();
140  }
141 
142  const T& get() const { return (*this->sequences)[0]->get(); }
143 
144  void advance()
145  {
146  (*this->sequences)[0]->next();
147  sync_iters();
148  }
149 
150  // Advance iterators so that they all point to items of the same value,
151  // or so that we become the end iterator
152  void sync_iters();
153 
154  const T& operator*() const { return this->get(); }
155  Itersection<T>& operator++()
156  {
157  this->advance();
158  return *this;
159  }
160 };
161 
162 template<typename T>
163 struct Iterunion : public SequenceGenerator<T>, public std::iterator<std::forward_iterator_tag, T>
164 {
165  const T* minval;
166 
167  Iterunion() {}
168  Iterunion(const Iterunion<T>& sg)
169  : SequenceGenerator<T>(sg), minval(sg.minval)
170  {
171  // unique_ptr semantics
172  const_cast<Iterunion<T>*>(&sg)->minval = 0;
173  }
174  Iterunion(std::unique_ptr< Sequences<T> >& sequences)
175  : SequenceGenerator<T>(sequences), minval(0)
176  {
177  find_min();
178  }
179  Iterunion<T>& operator=(const Iterunion<T>& sg)
180  {
181  // unique_ptr semantics
183  minval = sg.minval;
184  const_cast<Iterunion<T>*>(&sg)->minval = 0;
185  return *this;
186  }
187 
188  const T& get() const { return *minval; }
189 
200  void find_min();
201 
202  const T& operator*() const { return this->get(); }
203  Iterunion<T>& operator++()
204  {
205  this->find_min();
206  return *this;
207  }
208 };
209 
210 }
211 
216 template<class T>
218 {
219 public:
221 
222  const_iterator begin(std::unique_ptr< Sequences<T> >& sequences) const
223  {
224  return const_iterator(sequences);
225  }
226 
227  const_iterator end() const
228  {
229  return const_iterator();
230  }
231 };
232 
233 template<typename T>
235 {
236 protected:
237  std::vector<const std::set<T>*> sets;
238  Intersection<T> intersection;
239 
240 public:
241  void add(const std::set<T>& set)
242  {
243  sets.push_back(&set);
244  }
245 
247 
248  const_iterator begin()
249  {
250  std::unique_ptr< Sequences<T> > sequences(new Sequences<T>);
251 
252  // Look for the highest first element in all sets
253  bool first = true;
254  T max_of_first;
255  for (typename std::vector<const std::set<T>*>::const_iterator i = sets.begin();
256  i != sets.end(); ++i)
257  {
258  const std::set<T>& s = **i;
259  // If one of the sets is empty, then the intersection is empty
260  if (s.begin() == s.end()) return end();
261  if (first)
262  {
263  max_of_first = *s.begin();
264  first = false;
265  } else {
266  if (max_of_first < *s.begin())
267  max_of_first = *s.begin();
268  }
269  }
270 
271  // Populate intersection with all the ranges we intersect
272  for (typename std::vector<const std::set<T>*>::const_iterator i = sets.begin();
273  i != sets.end(); ++i)
274  {
275  const std::set<T>& s = **i;
276  sequences->add(s.lower_bound(max_of_first), s.end());
277  }
278 
279  return intersection.begin(sequences);
280  }
281 
282  const_iterator end()
283  {
284  return intersection.end();
285  }
286 };
287 
292 template<class T>
293 class Union
294 {
295 public:
297 
298  const_iterator begin(std::unique_ptr< Sequences<T> >& sequences) const
299  {
300  return const_iterator(sequences);
301  }
302 
303  const_iterator end() const
304  {
305  return const_iterator();
306  }
307 };
308 
313 template<typename T>
314 class TrivialInserter : public std::iterator<std::output_iterator_tag, void, void, void, void>
315 {
316 protected:
317  T* target;
318 
319 public:
320  TrivialInserter(T& target) : target(&target) {}
321 
322  template<typename V>
323  V operator=(V val) { target->insert(val); return val; }
324 
325  TrivialInserter& operator*() { return *this; }
326  TrivialInserter& operator++() { return *this; }
327  TrivialInserter& operator++(int) { return *this; }
328 };
329 
330 template<typename T>
331 TrivialInserter<T> trivial_inserter(T& target)
332 {
333  return TrivialInserter<T>(target);
334 }
335 
340 template<typename T>
341 class Pusher : public std::iterator<std::output_iterator_tag, void, void, void, void>
342 {
343 protected:
344  T* target;
345 
346 public:
347  Pusher(T& target) : target(&target) {}
348 
349  template<typename V>
350  V operator=(V val) { target->push(val); return val; }
351 
352  Pusher& operator*() { return *this; }
353  Pusher& operator++() { return *this; }
354  Pusher& operator++(int) { return *this; }
355 };
356 
357 template<typename T>
358 Pusher<T> pusher(T& target)
359 {
360  return Pusher<T>(target);
361 }
362 
367 template<typename T>
368 class Eraser : public std::iterator<std::output_iterator_tag, void, void, void, void>
369 {
370 protected:
371  T* target;
372 
373 public:
374  Eraser(T& target) : target(&target) {}
375 
376  template<typename V>
377  V operator=(V val) { target->erase(val); return val; }
378 
379  Eraser& operator*() { return *this; }
380  Eraser& operator++() { return *this; }
381  Eraser& operator++(int) { return *this; }
382 };
383 
384 template<typename T>
385 Eraser<T> eraser(T& target)
386 {
387  return Eraser<T>(target);
388 }
389 
390 }
391 }
392 
393 #endif
Definition: stlutils.h:35
Copyright (C) 2008–2010 ARPA-SIM urpsim@smr.arpa.emr.it
Definition: cmdline.h:17
void find_min()
Find the next minimum value.
void add_singleton(const T &val)
Add a singleton set.
Definition: stlutils.h:132
Similar to std::inserter, but just calls target.insert() without requiring it to have iterators at al...
Definition: stlutils.h:368
Virtual container containing the intersection of an arbitrary number of sorted (begin, end) sequences.
Definition: stlutils.h:217
List of ranges.
Definition: stlutils.h:47
Similar to std::inserter, but just calls target.insert() without requiring it to have iterators at al...
Definition: stlutils.h:314
Definition: stlutils.h:234
Virtual container containing the union of an arbitrary number of sorted (begin, end) sequences...
Definition: stlutils.h:293
Definition: stlutils.h:163
Similar to std::inserter, but just calls target.insert() without requiring it to have iterators at al...
Definition: stlutils.h:341