Justin Marshall
100 lines
3.0 KiB
C++
100 lines
3.0 KiB
C++
#pragma once
|
|
|
|
template<typename type>
|
|
class idSearch {
|
|
public:
|
|
virtual ~idSearch() = default;
|
|
virtual int Search(const type* base, unsigned int num,
|
|
const type& value) const = 0;
|
|
virtual int Search_FirstGreater(const type* base, int num,
|
|
const type& value) const = 0;
|
|
virtual int Search_FirstGreaterEqual(const type* base, int num,
|
|
const type& value) const = 0;
|
|
virtual int Search_LastLess(const type* base, int num,
|
|
const type& value) const = 0;
|
|
virtual int Search_LastLessEqual(const type* base, int num,
|
|
const type& value) const = 0;
|
|
};
|
|
|
|
template<typename type, typename derived>
|
|
class idSearch_Binary : public idSearch<type> {
|
|
public:
|
|
int Search(const type* base, const unsigned int num,
|
|
const type& value) const override {
|
|
if (base == nullptr || num == 0) {
|
|
return -1;
|
|
}
|
|
const int index = Search_LastLessEqual(base, static_cast<int>(num), value);
|
|
return Compare(base[index], value) == 0 ? index : -1;
|
|
}
|
|
|
|
int Search_FirstGreater(const type* base, const int num,
|
|
const type& value) const override {
|
|
int first = 0;
|
|
int count = num < 0 ? 0 : num;
|
|
while (count > 0) {
|
|
const int step = count / 2;
|
|
const int middle = first + step;
|
|
if (Compare(base[middle], value) <= 0) {
|
|
first = middle + 1;
|
|
count -= step + 1;
|
|
} else {
|
|
count = step;
|
|
}
|
|
}
|
|
return first;
|
|
}
|
|
|
|
int Search_FirstGreaterEqual(const type* base, const int num,
|
|
const type& value) const override {
|
|
int first = 0;
|
|
int count = num < 0 ? 0 : num;
|
|
while (count > 0) {
|
|
const int step = count / 2;
|
|
const int middle = first + step;
|
|
if (Compare(base[middle], value) < 0) {
|
|
first = middle + 1;
|
|
count -= step + 1;
|
|
} else {
|
|
count = step;
|
|
}
|
|
}
|
|
return first;
|
|
}
|
|
|
|
int Search_LastLess(const type* base, const int num,
|
|
const type& value) const override {
|
|
const int result = Search_FirstGreaterEqual(base, num, value) - 1;
|
|
return result < 0 ? 0 : result;
|
|
}
|
|
|
|
int Search_LastLessEqual(const type* base, const int num,
|
|
const type& value) const override {
|
|
const int result = Search_FirstGreater(base, num, value) - 1;
|
|
return result < 0 ? 0 : result;
|
|
}
|
|
|
|
private:
|
|
int Compare(const type& left, const type& right) const {
|
|
return static_cast<const derived*>(this)->Compare(left, right);
|
|
}
|
|
};
|
|
|
|
template<typename type>
|
|
class idSearch_BinaryDefault
|
|
: public idSearch_Binary<type, idSearch_BinaryDefault<type>> {
|
|
public:
|
|
int Compare(const type& left, const type& right) const {
|
|
if (left < right) {
|
|
return -1;
|
|
}
|
|
if (right < left) {
|
|
return 1;
|
|
}
|
|
return 0;
|
|
}
|
|
};
|
|
|
|
template<typename type>
|
|
using idSearch_DefaultCompare = idSearch_BinaryDefault<type>;
|