Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
Classes | |
class | Function |
class | ConvexFunction |
class | FunctionBinsearch |
Functions | |
template<typename T > | |
T | range_middle (T left, T right) |
template<typename ValueType , typename SizeType > | |
SizeType | lower_bound (ValueType pole[], SizeType left, SizeType right, ValueType value) |
template<typename ValueType , typename SizeType > | |
SizeType | upper_bound (ValueType pole[], SizeType left, SizeType right, ValueType value) |
SizeType math::binsearch::lower_bound | ( | ValueType | pole[], |
SizeType | left, | ||
SizeType | right, | ||
ValueType | value | ||
) |
Find first index in array range [left, right) where the value may be inserted without violating the ordering
Note that the definition is same as ``index of first element which is >= value'' except that the result is right if no such value exists
Example:
a = 1 1 2 2 2 3 5 lb(1) = ^ lb(2) = ^ lb(4) = ^ lb(6) = ^ (==right)
left | start of the interval |
right | index after the end of the interval |
T math::binsearch::range_middle | ( | T | left, |
T | right | ||
) |
Finds the middle of the range [left, right)
Middle is defined as floor((left + right) / 2)
left | start of the interval |
right | first index after the end of the interval |
SizeType math::binsearch::upper_bound | ( | ValueType | pole[], |
SizeType | left, | ||
SizeType | right, | ||
ValueType | value | ||
) |
Finds last position from range [left, right) where the value may be inserted without violating ordering
Note that the definitions is the same as ``index of first element that is greater than value'' except that the result is right if no such value exists
Example:
1 1 2 2 3 5 ub(6) ^ (== right) ub(2) ^ ub(1) ^ ub(0) ^
left | start of the interval |
right | index after the end of the interval |