View difference between Paste ID: jWtW6Vxn and PPp6sXrq
SHOW: | | - or go back to the newest paste.
1
// Код поисковой системы из финального задания спринта №2
2
#include <algorithm>
3
#include <cmath>
4
#include <iostream>
5
#include <map>
6
#include <set>
7
#include <string>
8
#include <utility>
9
#include <vector>
10
#include <numeric>
11
12
using namespace std;
13
14
const int MAX_RESULT_DOCUMENT_COUNT = 5;
15
constexpr double EPSILON = 1e-6;
16
17
string ReadLine() {
18
    string s;
19
    getline(cin, s);
20
    return s;
21
}
22
23
int ReadLineWithNumber() {
24
    int result;
25
    cin >> result;
26
    ReadLine();
27
    return result;
28
}
29
30
vector<string> SplitIntoWords(const string& text) {
31
    vector<string> words;
32
    string word;
33
    for (const char c : text) {
34
        if (c == ' ') {
35
            if (!word.empty()) {
36
                words.push_back(word);
37
                word.clear();
38
            }
39
        } else {
40
            word += c;
41
        }
42
    }
43
    if (!word.empty()) {
44
        words.push_back(word);
45
    }
46
47
    return words;
48
}
49
50
template <typename StringCollection>
51
set<string> NotEmptyStringCollection(const StringCollection& collection) {
52
    set<string> not_empty_strings_collection;
53
    for (const auto& stringg : collection) {
54
        if (!(stringg.empty())) {
55
            not_empty_strings_collection.insert(stringg);
56
        }
57
    }
58
    return not_empty_strings_collection;
59
}
60
61
struct Document {
62
    
63
    Document() = default;
64
    
65
    Document(int id_doc, double relevance_doc, int rating_doc) : id(id_doc), relevance(relevance_doc), rating(rating_doc){}
66
    
67
    int id = 0;
68
    double relevance = 0.0;
69
    int rating = 0;
70
};
71
72
enum class DocumentStatus {
73
    ACTUAL,
74
    IRRELEVANT,
75
    BANNED,
76
    REMOVED,
77
};
78
79
class SearchServer {
80
public:
81
    
82
    explicit SearchServer(const string& stop_words_string) : SearchServer(SplitIntoWords(stop_words_string)){}
83
    
84
    template <typename StringCollection>
85
    explicit SearchServer(const StringCollection& stop_words) : stop_words_(NotEmptyStringCollection(stop_words)){}
86
87
    void AddDocument(int document_id, const string& document, DocumentStatus status,
88
                     const vector<int>& ratings) {
89
        const vector<string> words = SplitIntoWordsNoStop(document);
90
        const double inv_word_count = 1.0 / words.size();
91
        for (const string& word : words) {
92
            word_to_document_freqs_[word][document_id] += inv_word_count;
93
        }
94
        documents_.emplace(document_id, DocumentData{ComputeAverageRating(ratings), status});
95
    }
96
97
    template <typename Helper>
98
    vector<Document> FindTopDocuments(const string& raw_query, const Helper& helper) const {
99
        const Query query = ParseQuery(raw_query);
100
        auto matched_documents = FindAllDocuments(query, helper);
101
102
        sort(matched_documents.begin(), matched_documents.end(),
103
             [](const Document& lhs, const Document& rhs) {
104
                 if (abs(lhs.relevance - rhs.relevance) < EPSILON) {
105
                     return lhs.rating > rhs.rating;
106
                 } else {
107
                     return lhs.relevance > rhs.relevance;
108
                 }
109
             });
110
        if (matched_documents.size() > MAX_RESULT_DOCUMENT_COUNT) {
111
            matched_documents.resize(MAX_RESULT_DOCUMENT_COUNT);
112
        }
113
        return matched_documents;
114
    }
115
    
116
    vector<Document> FindTopDocuments(const string& raw_query, DocumentStatus status) const {
117
        auto result = FindTopDocuments(raw_query, [status](int id, const DocumentStatus& doc_status, int raring) {return status == doc_status;});
118
        return result;
119
    }
120
 
121
    vector<Document> FindTopDocuments(const string& raw_query) const {
122
       auto result = FindTopDocuments(raw_query, DocumentStatus::ACTUAL);
123
       return result;
124
    }
125
126
    int GetDocumentCount() const {
127
        return documents_.size();
128
    }
129
130
    tuple<vector<string>, DocumentStatus> MatchDocument(const string& raw_query,
131
                                                        int document_id) const {
132
        const Query query = ParseQuery(raw_query);
133
        vector<string> matched_words;
134
        for (const string& word : query.plus_words) {
135
            if (word_to_document_freqs_.count(word) == 0) {
136
                continue;
137
            }
138
            if (word_to_document_freqs_.at(word).count(document_id)) {
139
                matched_words.push_back(word);
140
            }
141
        }
142
        for (const string& word : query.minus_words) {
143
            if (word_to_document_freqs_.count(word) == 0) {
144
                continue;
145
            }
146
            if (word_to_document_freqs_.at(word).count(document_id)) {
147
                matched_words.clear();
148
                break;
149
            }
150
        }
151
        return {matched_words, documents_.at(document_id).status};
152
    }
153
   
154
155
private:
156
    struct DocumentData {
157
        int rating;
158
        DocumentStatus status;
159
    };
160
161
    set<string> stop_words_;
162
    map<string, map<int, double>> word_to_document_freqs_;
163
    map<int, DocumentData> documents_;
164
165
    bool IsStopWord(const string& word) const {
166
        return stop_words_.count(word) > 0;
167
    }
168
169
    vector<string> SplitIntoWordsNoStop(const string& text) const {
170
        vector<string> words;
171
        for (const string& word : SplitIntoWords(text)) {
172
            if (!IsStopWord(word)) {
173
                words.push_back(word);
174
            }
175
        }
176
        return words;
177
    }
178
179
    static int ComputeAverageRating(const vector<int>& ratings) {
180
        if (ratings.empty()) {
181
            return 0;
182
        }
183
        /*int rating_sum = 0;
184
        for (const int rating : ratings) {
185
            rating_sum += rating;
186
        }*/
187
        return accumulate(ratings.begin(), ratings.end(), 0) / static_cast<int>(ratings.size());
188
    }
189
190
    struct QueryWord {
191
        string data;
192
        bool is_minus;
193
        bool is_stop;
194
    };
195
196
    QueryWord ParseQueryWord(string text) const {
197
        bool is_minus = false;
198
        // Word shouldn't be empty
199
        if (text[0] == '-') {
200
            is_minus = true;
201
            text = text.substr(1);
202
        }
203
        return {text, is_minus, IsStopWord(text)};
204
    }
205
206
    struct Query {
207
        set<string> plus_words;
208
        set<string> minus_words;
209
    };
210
211
    Query ParseQuery(const string& text) const {
212
        Query query;
213
        for (const string& word : SplitIntoWords(text)) {
214
            const QueryWord query_word = ParseQueryWord(word);
215
            if (!query_word.is_stop) {
216
                if (query_word.is_minus) {
217
                    query.minus_words.insert(query_word.data);
218
                } else {
219
                    query.plus_words.insert(query_word.data);
220
                }
221
            }
222
        }
223
        return query;
224
    }
225
226
    // Existence required
227
    double ComputeWordInverseDocumentFreq(const string& word) const {
228
        return log(GetDocumentCount() * 1.0 / word_to_document_freqs_.at(word).size());
229
    }
230
231
    template <typename Helper>
232
    vector<Document> FindAllDocuments(const Query& query, Helper& helper) const {
233
        map<int, double> document_to_relevance;
234
        for (const string& word : query.plus_words) {
235
            if (word_to_document_freqs_.count(word) == 0) {
236
                continue;
237
            }
238
            const double inverse_document_freq = ComputeWordInverseDocumentFreq(word);
239
            for (const auto [document_id, term_freq] : word_to_document_freqs_.at(word)) {
240
                const auto& document_data = documents_.at(document_id);
241
                if (helper(document_id, document_data.status, document_data.rating)) {
242
                    document_to_relevance[document_id] += term_freq * inverse_document_freq;
243
                }
244
            }
245
        }
246
247
        for (const string& word : query.minus_words) {
248
            if (word_to_document_freqs_.count(word) == 0) {
249
                continue;
250
            }
251
            for (const auto [document_id, _] : word_to_document_freqs_.at(word)) {
252
                document_to_relevance.erase(document_id);
253
            }
254
        }
255
256
        vector<Document> matched_documents;
257
        for (const auto [document_id, relevance] : document_to_relevance) {
258
            matched_documents.push_back(
259
                {document_id, relevance, documents_.at(document_id).rating});
260
        }
261
        return matched_documents;
262
    }
263
};
264
265
// ==================== для примера =========================
266
267
 
268