wildcardtree.cpp

main 130 lines · 3 KB Raw
Alex Alex Commit Server upload 18/10/2026 23:38
1/**
2 * The Forgotten Server - a free and open-source MMORPG server emulator
3 * Copyright (C) 2019 Mark Samman <mark.samman@gmail.com>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 */
19
20#include "otpch.h"
21
22#include <stack>
23
24#include "wildcardtree.h"
25
26WildcardTreeNode* WildcardTreeNode::getChild(char ch)
27{
28 auto it = children.find(ch);
29 if (it == children.end()) {
30 return nullptr;
31 }
32 return &it->second;
33}
34
35const WildcardTreeNode* WildcardTreeNode::getChild(char ch) const
36{
37 auto it = children.find(ch);
38 if (it == children.end()) {
39 return nullptr;
40 }
41 return &it->second;
42}
43
44WildcardTreeNode* WildcardTreeNode::addChild(char ch, bool breakpoint)
45{
46 WildcardTreeNode* child = getChild(ch);
47 if (child) {
48 if (breakpoint && !child->breakpoint) {
49 child->breakpoint = true;
50 }
51 } else {
52 auto pair = children.emplace(std::piecewise_construct,
53 std::forward_as_tuple(ch), std::forward_as_tuple(breakpoint));
54 child = &pair.first->second;
55 }
56 return child;
57}
58
59void WildcardTreeNode::insert(const std::string& str)
60{
61 WildcardTreeNode* cur = this;
62
63 size_t length = str.length() - 1;
64 for (size_t pos = 0; pos < length; ++pos) {
65 cur = cur->addChild(str[pos], false);
66 }
67
68 cur->addChild(str[length], true);
69}
70
71void WildcardTreeNode::remove(const std::string& str)
72{
73 WildcardTreeNode* cur = this;
74
75 std::stack<WildcardTreeNode*> path;
76 path.push(cur);
77 size_t len = str.length();
78 for (size_t pos = 0; pos < len; ++pos) {
79 cur = cur->getChild(str[pos]);
80 if (!cur) {
81 return;
82 }
83 path.push(cur);
84 }
85
86 cur->breakpoint = false;
87
88 do {
89 cur = path.top();
90 path.pop();
91
92 if (!cur->children.empty() || cur->breakpoint || path.empty()) {
93 break;
94 }
95
96 cur = path.top();
97
98 auto it = cur->children.find(str[--len]);
99 if (it != cur->children.end()) {
100 cur->children.erase(it);
101 }
102 } while (true);
103}
104
105ReturnValue WildcardTreeNode::findOne(const std::string& query, std::string& result) const
106{
107 const WildcardTreeNode* cur = this;
108 for (char pos : query) {
109 cur = cur->getChild(pos);
110 if (!cur) {
111 return RETURNVALUE_PLAYERWITHTHISNAMEISNOTONLINE;
112 }
113 }
114
115 result = query;
116
117 do {
118 size_t size = cur->children.size();
119 if (size == 0) {
120 return RETURNVALUE_NOERROR;
121 } else if (size > 1 || cur->breakpoint) {
122 return RETURNVALUE_NAMEISTOOAMBIGUOUS;
123 }
124
125 auto it = cur->children.begin();
126 result += it->first;
127 cur = &it->second;
128 } while (true);
129}
130
Top