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
|
#ifndef _FSO_UTILITY_H
#define _FSO_UTILITY_H
#include <vector>
#include "globalincs/globals.h"
#include "globalincs/toolchain.h"
// Goober5000
// A sort for use with small or almost-sorted lists. Iteration time is O(n) for a fully-sorted list.
// This uses a type-safe version of the function prototype for stdlib's qsort, although the size is an int rather than a size_t (for the reasons that j is an int).
// The fncompare function should return <0, 0, or >0 as the left item is less than, equal to, or greater than the right item.
template <typename array_t, typename T>
void insertion_sort(array_t& array_base, int array_size, int (*fncompare)(const T*, const T*))
{
// NOTE: j *must* be a signed type because j reaches -1 and j+1 must be 0.
int i, j;
T *current, *current_buf;
// allocate space for the element being moved
// (Taylor says that for optimization purposes malloc/free should be used rather than vm_malloc/vm_free here)
current_buf = new T();
if (current_buf == nullptr)
{
UNREACHABLE("Malloc failed!");
return;
}
// loop
for (i = 1; i < array_size; i++)
{
// grab the current element
// this does a lazy move/copy because if the array is mostly sorted,
// there's no sense copying sorted items to their own places
bool lazily_copied = false;
current = &array_base[i];
// bump other elements toward the end of the array
for (j = i - 1; (j >= 0) && (fncompare(&array_base[j], current) > 0); j--)
{
if (!lazily_copied)
{
// this may look strange but it is just copying the data
// into the buffer, then pointing to the buffer
*current_buf = std::move(*current);
current = current_buf;
lazily_copied = true;
}
array_base[j + 1] = std::move(array_base[j]);
}
if (lazily_copied)
{
// insert the current element at the correct place
array_base[j + 1] = std::move(*current);
}
}
// free the allocated space
delete current_buf;
}
//
// See https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C++
//
template<typename T>
typename T::size_type GeneralizedLevenshteinDistance(const T &source,
const T &target,
typename T::size_type insert_cost = 1,
typename T::size_type delete_cost = 1,
typename T::size_type replace_cost = 1) {
if (source.size() > target.size()) {
return GeneralizedLevenshteinDistance(target, source, delete_cost, insert_cost, replace_cost);
}
using TSizeType = typename T::size_type;
const TSizeType min_size = source.size(), max_size = target.size();
std::vector<TSizeType> lev_dist(min_size + 1);
lev_dist[0] = 0;
for (TSizeType i = 1; i <= min_size; ++i) {
lev_dist[i] = lev_dist[i - 1] + delete_cost;
}
for (TSizeType j = 1; j <= max_size; ++j) {
TSizeType previous_diagonal = lev_dist[0], previous_diagonal_save;
lev_dist[0] += insert_cost;
for (TSizeType i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (source[i - 1] == target[j - 1]) {
lev_dist[i] = previous_diagonal;
}
else {
lev_dist[i] = std::min(std::min(lev_dist[i - 1] + delete_cost, lev_dist[i] + insert_cost), previous_diagonal + replace_cost);
}
previous_diagonal = previous_diagonal_save;
}
}
return lev_dist[min_size];
}
// Lafiel
template<typename T>
typename T::size_type stringcost(const T& op, const T& input, typename T::size_type max_expected_length = NAME_LENGTH) {
using TSizeType = typename T::size_type;
if(input.empty())
return T::npos;
struct string_search_it {
TSizeType count;
TSizeType lastpos;
TSizeType cost;
};
std::vector<string_search_it> iterators;
//Go through the input. If we find it split up into parts, prefer things that are least split, and within this prefer things that are closer together
for (TSizeType i = 0; i < op.length(); i++) {
std::vector<string_search_it> insert;
for (auto& it : iterators) {
if (it.count < input.length() && op[i] == input[it.count]) {
//We found something. There may be a better match for this later, so only make a copy.
insert.emplace_back(string_search_it{it.count + 1, i, i - it.lastpos <= 1 ? it.cost : max_expected_length + i - it.lastpos - 1});
}
}
iterators.insert(iterators.end(), insert.begin(), insert.end());
if (op[i] == input[0])
iterators.emplace_back(string_search_it{1, i, i});
}
auto cost = T::npos;
for (const auto& it : iterators) {
//Things that are missing letters are considered worse by default
auto localcost = (input.length() - it.count) * (max_expected_length * max_expected_length) + it.cost;
if (localcost < cost)
cost = localcost;
}
return cost;
}
#endif
|
