this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3/*
4 * Main authors:
5 * Guido Tack <guido.tack@monash.edu>
6 */
7
8/* This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
11
12#include <minizinc/aststring.hh>
13
14#include <iostream>
15#include <vector>
16
17#ifndef HAS_MEMCPY_S
18namespace {
19void memcpy_s(char* dest, size_t /*size*/, const char* src, size_t count) {
20 memcpy(dest, src, count);
21}
22} // namespace
23#endif
24
25namespace MiniZinc {
26
27int ASTString::levenshteinDistance(const ASTString& other) const {
28 int m = size();
29 int n = other.size();
30 const char* s = c_str();
31 const char* t = other.c_str();
32 assert(m > 0);
33 assert(n > 0);
34
35 // dynamic programming matrix
36 std::vector<int> dp0(n + 1);
37 std::vector<int> dp1(n + 1, 0);
38 // initialise matrix
39 for (int i = 0; i <= n; i++) {
40 dp0[i] = i;
41 }
42
43 for (int i = 1; i <= m; i++) {
44 dp1[0] = i;
45 for (int j = 1; j <= n; j++) {
46 int del = dp0[j] + 1;
47 int ins = dp1[j - 1] + 1;
48 int sub = dp0[j - 1] + static_cast<int>(s[i - 1] != t[j - 1]);
49 dp1[j] = std::min(del, std::min(ins, sub));
50 }
51 std::swap(dp0, dp1);
52 }
53 return dp0[n];
54}
55
56ASTStringData::Interner& ASTStringData::interner() {
57 static Interner _interner;
58 return _interner;
59}
60
61ASTStringData::ASTStringData(const std::string& s)
62 : ASTChunk(s.size() + sizeof(size_t) + 1, ASTNode::NID_STR) {
63 memcpy_s(_data + sizeof(size_t), s.size() + 1, s.c_str(), s.size());
64 *(_data + sizeof(size_t) + s.size()) = 0;
65 std::hash<std::string> h;
66 reinterpret_cast<size_t*>(_data)[0] = h(s);
67}
68
69ASTStringData* ASTStringData::a(const std::string& s) {
70 if (s.empty()) {
71 return nullptr;
72 }
73 auto it = interner().find({s.c_str(), s.size()});
74 if (it != interner().end()) {
75 return it->second;
76 }
77 auto* as = static_cast<ASTStringData*>(alloc(1 + sizeof(size_t) + s.size()));
78 new (as) ASTStringData(s);
79 interner().emplace(std::make_pair(as->c_str(), as->size()), as);
80 return as;
81}
82} // namespace MiniZinc