-
Notifications
You must be signed in to change notification settings - Fork 0
/
deque_set.h
127 lines (100 loc) · 2.73 KB
/
deque_set.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#ifndef __DEQUE_SET
#define __DEQUE_SET
#include <deque>
#include <algorithm>
// A way to potentially speed up the sorting routines (which can consume a non-trivial
// amount of CPU time) is to use the g++-specific __gnu_parallel::sort funcion instead
// of the std::sort function. Since __gnu_parallel::sort is a drop in replacement for
// std::sort, we could include:
//#include <parallel/algorithm>
// and define
//#define SORT __gnu_parallel::sort
// or
#define SORT std::sort
// to switch between the two versions. This approach still needs benchmarking on the target machine
// (for speed and correctness). This approach will not work on non-g++ compilers (i.e. clang or intel).
template <class T>
void make_set(std::deque<T> &m_set)
{
SORT( m_set.begin(), m_set.end() );
m_set.erase( unique( m_set.begin(), m_set.end() ), m_set.end() );
}
template <class T>
std::deque<T> intersection(const std::deque<T> &m_A, const std::deque<T> &m_B)
{
std::deque<T> ret;
// All inputs must be sorted in ascending order and contain unique elements
typename std::deque<T>::const_iterator a = m_A.begin();
typename std::deque<T>::const_iterator b = m_B.begin();
while( ( a != m_A.end() ) && ( b != m_B.end() ) ){
if(*a == *b){
ret.push_back(*a);
++a;
++b;
}
else{
if(*a < *b){
++a;
}
else{ // *a > *b
++b;
}
}
}
return ret;
}
template<class T>
bool set_contains(const std::deque<T> &m_set, const T &m_query)
{
typename std::deque<T>::const_iterator i = std::lower_bound(m_set.begin(), m_set.end(), m_query);
return ( i != m_set.end() ) && (*i == m_query);
}
template<class T>
size_t get_index(const std::deque<T> &m_set, const T &m_query)
{
typename std::deque<T>::const_iterator iter =
std::lower_bound(m_set.begin(), m_set.end(), m_query);
if( ( iter == m_set.end() ) || (*iter != m_query) ){
throw __FILE__ ":get_index: Unable to find index!";
}
return ( iter - m_set.begin() );
};
template<class T>
bool operator==(const std::deque<T> &m_a, const std::deque<T> &m_b)
{
const size_t len = m_a.size();
if( len != m_b.size() ){
return false;
}
for(size_t i = 0;i < len;++i){
if(m_a[i] != m_b[i]){
return false;
}
}
return true;
}
template<class T>
bool operator!=(const std::deque<T> &m_a, const std::deque<T> &m_b)
{
const size_t len = m_a.size();
if( len != m_b.size() ){
return true;
}
for(size_t i = 0;i < len;++i){
if(m_a[i] != m_b[i]){
return true;
}
}
return false;
}
template <class T>
bool find_in_set(const std::deque<T> &m_set, const T &m_query)
{
typename std::deque<T>::const_iterator iter =
lower_bound(m_set.begin(), m_set.end(), m_query);
if( ( iter == m_set.end() ) || (*iter != m_query) ){
return false;
}
return true;
}
#endif // __DEQUE_SET