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
|
#include "entities_index.h"
#include <util/stream/str.h>
#include <set>
namespace NTvmAuth::NRoles {
TEntitiesIndex::TStage::TStage(const std::set<TString>& k)
: Keys_(k.begin(), k.end())
{
}
// TODO TStringBuf
bool TEntitiesIndex::TStage::GetNextKeySet(std::vector<TString>& out) {
out.clear();
out.reserve(Keys_.size());
++Id_;
for (size_t idx = 0; idx < Keys_.size(); ++idx) {
bool need = (Id_ >> idx) & 0x01;
if (need) {
out.push_back(Keys_[idx]);
}
}
return !out.empty();
}
TEntitiesIndex::TEntitiesIndex(const std::vector<TEntityPtr>& entities) {
const std::set<TString> uniqueKeys = GetUniqueSortedKeys(entities);
Idx_.Entities = entities;
Idx_.SubTree.reserve(uniqueKeys.size() * entities.size());
TStage stage(uniqueKeys);
std::vector<TString> keyset;
while (stage.GetNextKeySet(keyset)) {
for (const TEntityPtr& e : entities) {
TSubTree* currentBranch = &Idx_;
for (const TString& key : keyset) {
auto it = e->find(key);
if (it == e->end()) {
continue;
}
auto [i, ok] = currentBranch->SubTree.emplace(
TKeyValue{it->first, it->second},
TSubTree());
currentBranch = &i->second;
currentBranch->Entities.push_back(e);
}
}
}
MakeUnique(Idx_);
}
std::set<TString> TEntitiesIndex::GetUniqueSortedKeys(const std::vector<TEntityPtr>& entities) {
std::set<TString> res;
for (const TEntityPtr& e : entities) {
for (const auto& [key, value] : *e) {
res.insert(key);
}
}
return res;
}
void TEntitiesIndex::MakeUnique(TSubTree& branch) {
auto& vec = branch.Entities;
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
for (auto& [_, restPart] : branch.SubTree) {
MakeUnique(restPart);
}
}
static void Print(const TEntitiesIndex::TSubTree& part, IOutputStream& out, size_t offset = 0) {
std::vector<std::pair<TKeyValue, const TEntitiesIndex::TSubTree*>> vec;
vec.reserve(part.SubTree.size());
for (const auto& [key, value] : part.SubTree) {
vec.push_back({key, &value});
}
std::sort(vec.begin(), vec.end(), [](const auto& l, const auto& r) {
if (l.first.Key < r.first.Key) {
return true;
}
if (l.first.Value < r.first.Value) {
return true;
}
return false;
});
for (const auto& [key, value] : vec) {
out << TString(offset, ' ') << "\"" << key.Key << "/" << key.Value << "\"" << Endl;
Print(*value, out, offset + 4);
}
}
TString TEntitiesIndex::PrintDebugString() const {
TStringStream res;
res << Endl;
Print(Idx_, res);
return res.Str();
}
}
|
