All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SetIntersector.h
Go to the documentation of this file.
1 /*
2  * SetIntersector.h
3  *
4  * Created on: 14.05.2014
5  * Author: Henning
6  */
7 
8 #ifndef SETINTERSECTOR_H_
9 #define SETINTERSECTOR_H_
10 
11 #include <vector>
12 #include <set>
13 
14 namespace Aux {
15 
22 template<class T>
24 public:
28  SetIntersector(T upperBound);
29 
33  std::set<T> intersect(const std::vector<T>& A, const std::vector<T>& B);
34 
35 private:
36  std::vector<bool> bv;
37  uint64_t n;
38 };
39 
40 } // namespace Aux
41 
42 
43 template<class T>
44 inline Aux::SetIntersector<T>::SetIntersector(T upperBound): n(upperBound) {
45  bv.resize(n, false);
46 
47 }
48 
49 template<class T>
50 inline std::set<T> Aux::SetIntersector<T>::intersect(const std::vector<T>& A,
51  const std::vector<T>& B)
52 {
53  const std::vector<T>& smaller = (A.size() <= B.size()) ? A : B;
54  const std::vector<T>& larger = (A.size() <= B.size()) ? B : A;
55 
56  for (auto entry: smaller) {
57  bv[entry] = true;
58  }
59 
60  std::set<T> result;
61  for (auto entry: larger) {
62  if (bv[entry]) {
63  result.insert(entry);
64  }
65  }
66 
67  for (auto entry: smaller) {
68  bv[entry] = false;
69  }
70 
71  return result;
72 }
73 
74 #endif /* SETINTERSECTOR_H_ */
SetIntersector(T upperBound)
Definition: SetIntersector.h:44
std::set< T > intersect(const std::vector< T > &A, const std::vector< T > &B)
Definition: SetIntersector.h:50
Provides set intersection for sets with entries from 0 to an upper bound (exclusive).
Definition: SetIntersector.h:23