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
128
129
|
#ifndef SVECTOR_H_
#define SVECTOR_H_
using namespace std;
#include <vector>
#include <iterator>
#include <assert.h>
#include <algorithm>
#include "base/ErrorHandling.h"
template <class T>
class svec : public vector<T>
{
public:
int isize() const {return (int)vector<T>::size();}
long long lsize() const {return vector<T>::size();}
const T & operator[] (long long i) const {
#ifndef NDEBUG
if (i>= lsize()) {
cout << "ERROR: i=" << i << " lsize=" << lsize() << endl;
ThrowError("i>=lsize()", "svec");
}
if (i<0) {
cout << "ERROR: i=" << i << " lsize=" << lsize() << endl;
ThrowError("i<0", "svec");
}
//assert(i<lsize());
//assert(i>=0);
#endif
return vector<T>::operator[](i);
}
T & operator[] (long long i) {
#ifndef NDEBUG
if (i>= lsize()) {
cout << "ERROR: i=" << i << " lsize=" << lsize() << endl;
ThrowError("i>=lsize()", "svec");
}
if (i<0) {
cout << "ERROR: i=" << i << " lsize=" << lsize() << endl;
ThrowError("i<0", "svec");
}
//assert(i<lsize());
//assert(i>=0);
#endif
return vector<T>::operator[](i);
}
};
template <class T>
class vec : public svec<T>
{
};
template<class T>
void Sort(svec<T>& v)
{
sort(v.begin(), v.end());
}
template<class T>
void UniqueSort(svec<T>& v)
{
sort(v.begin(), v.end());
long long i;
long long k = 0;
for (i=0; i<v.lsize(); i++) {
v[k] = v[i];
while (i+1<v.lsize() && !(v[k] < v[i+1]))
i++;
k++;
}
v.resize(k);
}
template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
// Finds the lower bound in at most log(last - first) + 1 comparisons
Iter i = std::lower_bound(begin, end, val);
if (i != end && !(val < *i))
return i; // found
else
return end; // not found
}
template<class T>
long long BinSearch(svec<T> & v, const T & item)
{
typename svec<T>::iterator iter = binary_find(v.begin(), v.end(), item);
if (iter == v.end())
return -1;
return iter - v.begin();
}
template<class T>
long long BinSearchFuzzy(svec<T> & v, const T & item)
{
typename svec<T>::iterator iter;
typename svec<T>::iterator begin = v.begin();
typename svec<T>::iterator end = v.end();
iter = lower_bound(begin, end, item);
long pos = distance(begin, iter);
if (pos < 0)
return -1;
return pos;
}
#endif //SVECTOR_H_
|
