-
Notifications
You must be signed in to change notification settings - Fork 7
/
Copy pathalgorithm.hpp
175 lines (143 loc) · 4.27 KB
/
algorithm.hpp
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// solid/utility/algorithm.hpp
//
// Copyright (c) 20015 Valentin Palade (vipalade @ gmail . com)
//
// This file is part of SolidFrame framework.
//
// Distributed under the Boost Software License, Version 1.0.
// See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt.
//
#pragma once
#include "solid/utility/common.hpp"
#include <utility>
namespace solid {
inline size_t max_bit_count(uint8_t _v)
{
return 8 - leading_zero_count(_v);
}
inline size_t max_padded_bit_cout(uint8_t _v)
{
return fast_padded_size(max_bit_count(_v), 3);
}
inline size_t max_padded_byte_cout(uint8_t _v)
{
return max_padded_bit_cout(_v) >> 3;
}
//---
inline size_t max_bit_count(uint16_t _v)
{
return 16 - leading_zero_count(_v);
}
inline size_t max_padded_bit_cout(uint16_t _v)
{
return fast_padded_size(max_bit_count(_v), 3);
}
inline size_t max_padded_byte_cout(uint16_t _v)
{
return max_padded_bit_cout(_v) >> 3;
}
//---
inline size_t max_bit_count(uint32_t _v)
{
return 32 - leading_zero_count(_v);
}
inline size_t max_padded_bit_cout(uint32_t _v)
{
return fast_padded_size(max_bit_count(_v), 3);
}
inline size_t max_padded_byte_cout(uint32_t _v)
{
return max_padded_bit_cout(_v) >> 3;
}
//---
inline size_t max_bit_count(uint64_t _v)
{
return 64 - leading_zero_count(_v);
}
inline size_t max_padded_bit_cout(uint64_t _v)
{
return fast_padded_size(max_bit_count(_v), 3);
}
inline size_t max_padded_byte_cout(uint64_t _v)
{
return max_padded_bit_cout(_v) >> 3;
}
//---
//=============================================================================
template <class It, class Cmp>
size_t find_cmp(It /*_it*/, Cmp const&, std::integral_constant<size_t, 1> /*_s*/)
{
return 0;
}
template <class It, class Cmp>
size_t find_cmp(It _it, Cmp const& _rcmp, std::integral_constant<size_t, 2> /*_s*/)
{
if (_rcmp(*_it, *(_it + 1))) {
return 0;
}
return 1;
}
template <class It, class Cmp, size_t S>
size_t find_cmp(It _it, Cmp const& _rcmp, std::integral_constant<size_t, S> /*_s*/)
{
const size_t off1 = find_cmp(_it, _rcmp, std::integral_constant<size_t, S / 2>());
const size_t off2 = find_cmp(_it + S / 2, _rcmp, std::integral_constant<size_t, S - S / 2>()) + S / 2;
if (_rcmp(*(_it + off1), *(_it + off2))) {
return off1;
}
return off2;
}
//=============================================================================
struct binary_search_basic_comparator {
template <typename K1, typename K2>
int operator()(const K1& _k1, const K2& _k2) const
{
if (_k1 < _k2)
return -1;
if (_k2 < _k1)
return 1;
return 0;
}
};
using binary_search_result_t = std::pair<bool, size_t>;
template <class It, class Key, class Compare = binary_search_basic_comparator>
binary_search_result_t binary_search(It _from, It _to, const Key& _rk, const Compare& _rcmp = Compare())
{
const It beg(_from);
size_t midpos;
while (_to > _from) {
midpos = (_to - _from) >> 1;
int r = _rcmp(*(_from + midpos), _rk);
if (!r)
return binary_search_result_t(true, _from - beg + midpos);
if (r < 0) {
_from += (midpos + 1);
} else {
_to = _from + midpos;
}
}
return binary_search_result_t(false, _from - beg);
}
template <class It, class Key, class Compare = binary_search_basic_comparator>
binary_search_result_t binary_search_first(It _from, It _to, const Key& _rk, const Compare& _rcmp = Compare())
{
binary_search_result_t p = solid::binary_search(_from, _to, _rk, _rcmp);
if (!p.first)
return p; // not found
while (p.second && !_rcmp(*(_from + p.second - 1), _rk)) {
p = solid::binary_search(_from, _from + p.second, _rk, _rcmp);
}
return p;
}
template <class It, class Key, class Compare = binary_search_basic_comparator>
binary_search_result_t binary_search_last(It _from, It _to, const Key& _rk, const Compare& _rcmp = Compare())
{
binary_search_result_t p = solid::binary_search(_from, _to, _rk, _rcmp);
if (!p.first)
return p; // not found
while (p.second != (_to - _from - 1) && !_rcmp(*(_from + p.second + 1), _rk)) {
p = solid::binary_search(_from + p.second + 1, _to, _rk, _rcmp);
}
return p;
}
} // namespace solid