API tools faq
paste
Advertisement
kutuzzzov

Урок 6

kutuzzzov
Sep 19th, 2022 (edited)
904
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 20.43 KB | None | 0 0
raw download clone embed print report
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <set>
  4. #include <string>
  5. #include <utility>
  6. #include <vector>
  7. #include <map>
  8. #include <cmath>
  9. #include <cassert>
  10.  
  11. using namespace std;
  12.  
  13. const int MAX_RESULT_DOCUMENT_COUNT = 5;
  14.  
  15. string ReadLine() {
  16.     string s;
  17.     getline(cin, s);
  18.     return s;
  19. }
  20.  
  21. int ReadLineWithNumber() {
  22.     int result = 0;
  23.     cin >> result;
  24.     ReadLine();
  25.     return result;
  26. }
  27.  
  28. vector<string> SplitIntoWords(const string& text) {
  29.     vector<string> words;
  30.     string word;
  31.     for (const char c : text) {
  32.         if (c == ' ') {
  33.             if (!word.empty()) {
  34.                 words.push_back(word);
  35.                 word.clear();
  36.             }
  37.         }
  38.         else {
  39.             word += c;
  40.         }
  41.     }
  42.     if (!word.empty()) {
  43.         words.push_back(word);
  44.     }
  45.     return words;
  46. }
  47.  
  48. struct Document {
  49.     Document() = default;
  50.  
  51.     Document(int id_, double relevance_, int rating_)
  52.         : id(id_), relevance(relevance_), rating(rating_)
  53.     {}
  54.  
  55.     int id = 0;
  56.     double relevance = 0.0;
  57.     int rating = 0;
  58. };
  59.  
  60. enum class DocumentStatus {
  61.     ACTUAL,
  62.     IRRELEVANT,
  63.     BANNED,
  64.     REMOVED
  65. };
  66.  
  67. class SearchServer {
  68. public:
  69.     SearchServer() = default;
  70.  
  71.     explicit SearchServer(const string& stop_words) {
  72.         for (const string& word : SplitIntoWords(stop_words)) {
  73.             stop_words_.insert(word);
  74.         }
  75.     }
  76.  
  77.     template <typename StringCollection>
  78.     explicit SearchServer(const StringCollection& stop_words) {
  79.         string stop_words_text;
  80.         for (const auto& text : stop_words) {
  81.             stop_words_text += " "s;
  82.             stop_words_text += text;
  83.         }
  84.         for (const auto& word : SplitIntoWords(stop_words_text)) {
  85.             stop_words_.insert(word);
  86.         }
  87.     }
  88.  
  89.     void AddDocument(int document_id, const string& document, DocumentStatus status, const vector<int>& ratings) {
  90.         const vector<string> words = SplitIntoWordsNoStop(document);
  91.         for (auto& word : words) {
  92.             word_to_document_freqs_[word][document_id] += 1.0 / words.size();
  93.         }
  94.         documents_.emplace(document_id, DocumentData { ComputeAverageRating(ratings), status });
  95.     }
  96.  
  97.     int GetDocumentCount() const {
  98.         return static_cast<int>(documents_.size());
  99.     }
  100.  
  101.     template<typename DocumentPredicate>
  102.     vector<Document> FindTopDocuments(const string& raw_query, DocumentPredicate predicate) const {
  103.         const Query query = ParseQuery(raw_query);
  104.         auto matched_documents = FindAllDocuments(query, predicate);
  105.  
  106.         sort(matched_documents.begin(), matched_documents.end(),
  107.             [](const Document& lhs, const Document& rhs) {
  108.                 const double EPSILON = 1e-6;
  109.                 if (abs(lhs.relevance - rhs.relevance) < EPSILON) {
  110.                     return lhs.rating > rhs.rating;
  111.                 }
  112.                 else {
  113.                     return lhs.relevance > rhs.relevance;
  114.                 }
  115.             });
  116.         if (matched_documents.size() > MAX_RESULT_DOCUMENT_COUNT) {
  117.             matched_documents.resize(MAX_RESULT_DOCUMENT_COUNT);
  118.         }
  119.         return matched_documents;
  120.     }
  121.  
  122.     vector<Document> FindTopDocuments(const string& raw_query) const {
  123.         return FindTopDocuments(raw_query, DocumentStatus::ACTUAL);
  124.     }
  125.  
  126.     vector<Document> FindTopDocuments(const string& raw_query, DocumentStatus status) const {
  127.         return FindTopDocuments(raw_query,
  128.             [&status](int document_id, DocumentStatus new_status, int rating) {
  129.                 return new_status == status;
  130.             });
  131.     }
  132.  
  133.     tuple<vector<string>, DocumentStatus> MatchDocument(const string& raw_query, int document_id) const {
  134.         const Query query = ParseQuery(raw_query);
  135.         vector<string> matched_words;
  136.         for (const string& word : query.plus_words) {
  137.             if (word_to_document_freqs_.count(word) == 0) {
  138.                 continue;
  139.             }
  140.             if (word_to_document_freqs_.at(word).count(document_id)) {
  141.                 matched_words.push_back(word);
  142.             }
  143.         }
  144.         for (const string& word : query.minus_words) {
  145.             if (word_to_document_freqs_.count(word) == 0) {
  146.                 continue;
  147.             }
  148.             if (word_to_document_freqs_.at(word).count(document_id)) {
  149.                 matched_words.clear();
  150.                 break;
  151.             }
  152.         }
  153.         return { matched_words, documents_.at(document_id).status };
  154.     }
  155.  
  156. private:
  157.     struct Query {
  158.         set<string> plus_words;
  159.         set<string> minus_words;
  160.     };
  161.  
  162.     struct DocumentData {
  163.         int rating;
  164.         DocumentStatus status;
  165.     };
  166.  
  167.     map<string, map<int, double>> word_to_document_freqs_;
  168.     map<int, DocumentData> documents_;
  169.     set<string> stop_words_;
  170.  
  171.     bool IsStopWord(const string& word) const {
  172.         return stop_words_.count(word) > 0;
  173.     }
  174.  
  175.     vector<string> SplitIntoWordsNoStop(const string& text) const {
  176.         vector<string> words;
  177.         for (const string& word : SplitIntoWords(text)) {
  178.             if (!IsStopWord(word)) {
  179.                 words.push_back(word);
  180.             }
  181.         }
  182.         return words;
  183.     }
  184.  
  185.     static int ComputeAverageRating(const vector<int>& ratings) {
  186.         if (ratings.empty()) {
  187.             return 0;
  188.         }
  189.         int rating_sum = 0;
  190.         for (const auto rating : ratings) {
  191.             rating_sum += rating;
  192.         }
  193.         return rating_sum / static_cast<int>(ratings.size());
  194.     }
  195.  
  196.     Query ParseQuery(const string& text) const {
  197.         Query query;
  198.         for (string& word : SplitIntoWordsNoStop(text)) {
  199.             if (word[0] == '-') {
  200.                 word = word.substr(1);
  201.                 if (!IsStopWord(word)) {
  202.                     query.minus_words.insert(word);
  203.                 }
  204.             }
  205.             query.plus_words.insert(word);
  206.         }
  207.         return query;
  208.     }
  209.  
  210.     template<typename DocumentPredicate>
  211.     vector<Document> FindAllDocuments(const Query& query, DocumentPredicate predicate) const {
  212.         map<int, double> document_to_relevance;
  213.         for (const string& word : query.plus_words) {
  214.             if (word_to_document_freqs_.count(word) == 0) {
  215.                 continue;
  216.             }
  217.             for (const auto& [document_id, term_freq] : word_to_document_freqs_.at(word)) {
  218.                 const DocumentData documents_data = documents_.at(document_id);
  219.                 if (predicate(document_id, documents_data.status, documents_data.rating)) {
  220.                     const double IDF = log(GetDocumentCount() * 1.0 / word_to_document_freqs_.at(word).size());
  221.                     document_to_relevance[document_id] += IDF * term_freq;
  222.                 }
  223.             }
  224.         }
  225.         for (const string& word : query.minus_words) {
  226.             if (word_to_document_freqs_.count(word) == 0) {
  227.                 continue;
  228.             }
  229.             for (const auto& [document_id, term_freq] : word_to_document_freqs_.at(word)) {
  230.                 document_to_relevance.erase(document_id);
  231.             }
  232.         }
  233.  
  234.         vector<Document> matched_documents;
  235.         for (const auto [document_id, relevance] : document_to_relevance) {
  236.             matched_documents.push_back({ document_id, relevance, documents_.at(document_id).rating });
  237.         }
  238.         return matched_documents;
  239.     }
  240. };
  241.  
  242. /*
  243.  
  244. //   Подставьте сюда вашу реализацию макросов
  245. //   ASSERT, ASSERT_EQUAL, ASSERT_EQUAL_HINT, ASSERT_HINT и RUN_TEST
  246.  
  247.  
  248. template <typename T, typename U>
  249. ostream& operator<<(ostream& out, const pair<T, U>& container) {
  250.     return out << container.first << ": " << container.second;
  251. }
  252.  
  253. template <typename T>
  254. void Print(ostream& out, const T& container) {
  255.     bool is_first = true;
  256.     for (const auto& element : container) {
  257.         if (is_first) {
  258.             out << element;
  259.             is_first = false;
  260.         }
  261.         else {
  262.             out << ", "s << element;
  263.         }
  264.     }
  265. }
  266.  
  267. template <typename T>
  268. ostream& operator<<(ostream& out, const vector<T>& container) {
  269.     out << "["s;
  270.     Print(out, container);
  271.     out << "]"s;
  272.     return out;
  273. }
  274.  
  275. template <typename T>
  276. ostream& operator<<(ostream& out, const set<T>& container) {
  277.     out << "{"s;
  278.     Print(out, container);
  279.     out << "}"s;
  280.     return out;
  281. }
  282.  
  283. template <typename T, typename U>
  284. ostream& operator<<(ostream& out, const map<T, U>& container) {
  285.     out << "{"s;
  286.     Print(out, container);
  287.     out << "}"s;
  288.     return out;
  289. }
  290.  
  291. template <typename T, typename U>
  292. void AssertEqualImpl(const T& t, const U& u, const string& t_str, const string& u_str, const string& file,
  293.     const string& func, unsigned line, const string& hint) {
  294.     if (t != u) {
  295.         cerr << boolalpha;
  296.         cerr << file << "("s << line << "): "s << func << ": "s;
  297.         cerr << "ASSERT_EQUAL("s << t_str << ", "s << u_str << ") failed: "s;
  298.         cerr << t << " != "s << u << "."s;
  299.         if (!hint.empty()) {
  300.             cerr << " Hint: "s << hint;
  301.         }
  302.         cerr << endl;
  303.         abort();
  304.     }
  305. }
  306.  
  307. void AssertImpl(bool value, const string& expr_str, const string& file, const string& func, unsigned line,
  308.     const string& hint) {
  309.     if (!value) {
  310.         cerr << file << "("s << line << "): "s << func << ": "s;
  311.         cerr << "ASSERT("s << expr_str << ") failed."s;
  312.         if (!hint.empty()) {
  313.             cerr << " Hint: "s << hint;
  314.         }
  315.         cerr << endl;
  316.         abort();
  317.     }
  318. }
  319.  
  320. template <typename T>
  321. void RunTestImpl(T func, const string& func_str) {
  322.     func();
  323.     cerr << func_str << " OK" << endl;
  324. }
  325.  
  326. #define ASSERT(expr) AssertImpl(!!(expr), #expr, __FILE__, __FUNCTION__, __LINE__, ""s)
  327.  
  328. #define ASSERT_EQUAL(a, b) AssertEqualImpl((a), (b), #a, #b, __FILE__, __FUNCTION__, __LINE__, ""s)
  329.  
  330. #define ASSERT_EQUAL_HINT(a, b, hint) AssertEqualImpl((a), (b), #a, #b, __FILE__, __FUNCTION__, __LINE__, (hint))
  331.  
  332. #define ASSERT_HINT(expr, hint) AssertImpl(!!(expr), #expr, __FILE__, __FUNCTION__, __LINE__, (hint))
  333.  
  334. #define RUN_TEST(func) RunTestImpl((func), #func)
  335.  
  336. // -------- Начало модульных тестов поисковой системы ----------
  337.  
  338. // Тест проверяет, что поисковая система исключает стоп-слова при добавлении документов
  339.  
  340. void TestExcludeStopWordsFromAddedDocumentContent() {
  341.     const int doc_id = 42;
  342.     const string content = "cat in the city"s;
  343.     const vector<int> ratings = { 1, 2, 3 };
  344.  
  345.     {
  346.         SearchServer server;
  347.         server.AddDocument(doc_id, content, DocumentStatus::ACTUAL, ratings);
  348.         const auto found_docs = server.FindTopDocuments("in"s);
  349.         ASSERT_EQUAL(found_docs.size(), 1u);
  350.         const Document& doc0 = found_docs[0];
  351.         ASSERT_EQUAL(doc0.id, doc_id);
  352.     }
  353.  
  354.  
  355.  
  356.     {
  357.         SearchServer server;
  358.         server.SetStopWords("in the"s);
  359.         server.AddDocument(doc_id, content, DocumentStatus::ACTUAL, ratings);
  360.         ASSERT_HINT(server.FindTopDocuments("in"s).empty(), "Stop words must be excluded from documents"s);
  361.     }
  362. }
  363.  
  364. // Добавление документов. Добавленный документ должен находиться по поисковому запросу, который содержит слова из документа.
  365. void TestFindAddedDocumentByDocumentWord() {
  366.     const int doc_id = 42;
  367.     const string content = "cat in the city"s;
  368.     const vector<int> ratings = { 1, 2, 3 };
  369.  
  370.     {
  371.         SearchServer server;
  372.         ASSERT_EQUAL(server.GetDocumentCount(), 0);
  373.         server.AddDocument(doc_id, content, DocumentStatus::ACTUAL, ratings);
  374.         ASSERT_EQUAL(server.GetDocumentCount(), 1);
  375.         server.AddDocument(doc_id + 1, "black dog fluffy tail", DocumentStatus::ACTUAL, ratings);
  376.         ASSERT_EQUAL(server.GetDocumentCount(), 2);
  377.         const auto found_docs = server.FindTopDocuments("cat"s);
  378.         ASSERT_EQUAL(found_docs.size(), 1u);
  379.         const Document& doc0 = found_docs[0];
  380.         ASSERT_EQUAL(doc0.id, doc_id);
  381.     }
  382. }
  383.  
  384. // Поддержка минус-слов. Документы, содержащие минус-слова из поискового запроса, не должны включаться в результаты поиска.
  385. void TestExcludeDocumentsWithMinusWordsFromResults() {
  386.     SearchServer server;
  387.     server.AddDocument(101, "fluffy cat fluffy tail"s, DocumentStatus::ACTUAL, { 1,2,3 });
  388.     server.AddDocument(102, "fluffy red dog "s, DocumentStatus::ACTUAL, { 1,2,3 });
  389.  
  390.     {
  391.         const auto found_docs = server.FindTopDocuments("fluffy -dog"s);
  392.         ASSERT_EQUAL(found_docs.size(), 1u);
  393.         ASSERT_EQUAL(found_docs[0].id, 101);
  394.     }
  395.  
  396.     {
  397.         const auto found_docs = server.FindTopDocuments("fluffy -cat"s);
  398.         ASSERT_EQUAL(found_docs.size(), 1u);
  399.         ASSERT_EQUAL(found_docs[0].id, 102);
  400.     }
  401.  
  402. }
  403.  
  404. // Соответствие документов поисковому запросу.
  405. void TestMatchedDocuments() {
  406.     SearchServer server;
  407.     server.SetStopWords("and in on"s);
  408.     server.AddDocument(100, "fluffy cat and black dog in a collar"s, DocumentStatus::ACTUAL, { 1, 2, 3 });
  409.  
  410.     {
  411.         const auto [matched_words, status] = server.MatchDocument("dog and cat"s, 100);
  412.         const vector<string> expected_result = { "cat"s, "dog"s };
  413.         ASSERT_EQUAL(expected_result, matched_words);
  414.     }
  415.  
  416.     {
  417.         const auto [matched_words, status] = server.MatchDocument("dog and -cat"s, 100);
  418.         const vector<string> expected_result = {}; // пустой результат поскольку есть минус-слово
  419.         ASSERT_EQUAL(expected_result, matched_words);
  420.         ASSERT(matched_words.empty());
  421.     }
  422. }
  423.  
  424. // Сортировка найденных документов по релевантности.
  425. void TestSortResultsByRelevance() {
  426.     SearchServer server;
  427.     server.AddDocument(100, "fluffy cat fluffy tail"s, DocumentStatus::ACTUAL, { 1, 2, 3 });
  428.     server.AddDocument(101, "fluffy dog"s, DocumentStatus::ACTUAL, { 1, 2, 3 });
  429.     server.AddDocument(102, "dog leather collar"s, DocumentStatus::ACTUAL, { 1, 2, 3 });
  430.  
  431.     {
  432.         const auto found_docs = server.FindTopDocuments("fluffy cat"s);
  433.         ASSERT_EQUAL(found_docs.size(), 2u);
  434.         for (size_t i = 1; i < found_docs.size(); i++) {
  435.             ASSERT(found_docs[i - 1].relevance >= found_docs[i].relevance);
  436.         }
  437.     }
  438. }
  439.  
  440. // Вычисление рейтинга документов.
  441. void TestCalculateDocumentRating() {
  442.     SearchServer server;
  443.     const vector<int> ratings = { 10, 11, 3 };
  444.     const int average = (10 + 11 + 3) / 3;
  445.     server.AddDocument(0, "fluffy cat fluffy tail"s, DocumentStatus::ACTUAL, ratings);
  446.  
  447.     {
  448.         const auto found_docs = server.FindTopDocuments("fluffy cat"s);
  449.         ASSERT_EQUAL(found_docs.size(), 1u);
  450.         ASSERT_EQUAL(found_docs[0].rating, average);
  451.     }
  452. }
  453.  
  454. // Фильтрация результатов поиска с использованием предиката.
  455. void TestDocumentSearchByPredicate() {
  456.     SearchServer server;
  457.     server.AddDocument(100, "cat in the city"s, DocumentStatus::ACTUAL, { 1, 2, 3 });
  458.     server.AddDocument(101, "dog in the town"s, DocumentStatus::IRRELEVANT, { -1, -2, -3 });
  459.     server.AddDocument(102, "dog and rabbit in the town"s, DocumentStatus::ACTUAL, { -4, -5, -6 });
  460.     const auto found_docs = server.FindTopDocuments("in the cat"s, [](int document_id, DocumentStatus status, int rating) { return rating > 0; });
  461.  
  462.     {
  463.         ASSERT_HINT(found_docs[0].id == 100, "Wrong predicate");
  464.     }
  465. }
  466.  
  467. // Поиск документов, имеющих заданный статус.
  468. void TestDocumentSearchByStatus() {
  469.     const int doc_id1 = 42;
  470.     const int doc_id2 = 43;
  471.     const int doc_id3 = 44;
  472.     const string content1 = "cat in the city"s;
  473.     const string content2 = "cat in the town"s;
  474.     const string content3 = "cat in the town or city"s;
  475.     const vector<int> ratings = { 1, 2, 3 };
  476.     SearchServer server;
  477.     server.AddDocument(doc_id1, content1, DocumentStatus::ACTUAL, ratings);
  478.     server.AddDocument(doc_id2, content2, DocumentStatus::IRRELEVANT, ratings);
  479.     server.AddDocument(doc_id3, content3, DocumentStatus::IRRELEVANT, ratings);
  480.     const auto found_docs = server.FindTopDocuments("in the cat"s, DocumentStatus::IRRELEVANT);
  481.  
  482.     {
  483.         ASSERT_HINT(found_docs[0].id == doc_id2, "Wrong status");
  484.         ASSERT_HINT(found_docs[1].id == doc_id3, "Wrong status");
  485.         ASSERT_HINT(found_docs.size() == 2, "Wrong status request");
  486.     }
  487. }
  488.  
  489. // Корректное вычисление релевантности найденных документов.
  490. void TestCalculateRelevance() {
  491.     SearchServer server;
  492.     server.AddDocument(100, "white cat with new ring"s, DocumentStatus::ACTUAL, { 1, 2, 3 });
  493.     server.AddDocument(101, "fluffy cat fluffy tail"s, DocumentStatus::ACTUAL, { 1, 2, 3 });
  494.     server.AddDocument(102, "good dog big eyes"s, DocumentStatus::ACTUAL, { 1, 2, 3 });
  495.     const auto found_docs = server.FindTopDocuments("fluffy good cat"s);
  496.     double relevance_query = log((3 * 1.0) / 1) * (2.0 / 4.0) + log((3 * 1.0) / 2) * (1.0 / 4.0);
  497.  
  498.     {
  499.         ASSERT_HINT(fabs(found_docs[0].relevance - relevance_query) < 1e-6, "Wrong calculation relevance");
  500.     }
  501. }
  502.  
  503. // Функция TestSearchServer является точкой входа для запуска тестов
  504. void TestSearchServer() {
  505.     RUN_TEST(TestExcludeStopWordsFromAddedDocumentContent);
  506.     RUN_TEST(TestFindAddedDocumentByDocumentWord);
  507.     RUN_TEST(TestExcludeDocumentsWithMinusWordsFromResults);
  508.     RUN_TEST(TestMatchedDocuments);
  509.     RUN_TEST(TestSortResultsByRelevance);
  510.     RUN_TEST(TestCalculateDocumentRating);
  511.     RUN_TEST(TestDocumentSearchByPredicate);
  512.     RUN_TEST(TestDocumentSearchByStatus);
  513.     RUN_TEST(TestCalculateRelevance);
  514. }
  515. // --------- Окончание модульных тестов поисковой системы -----------
  516.  
  517. int main() {
  518.     TestSearchServer();
  519.     // Если вы видите эту строку, значит все тесты прошли успешно
  520.     cout << "Search server testing finished"s << endl;
  521. }
  522. */
  523.  
  524.  
  525. void PrintDocument(const Document& document) {
  526.     cout << "{ "s
  527.         << "document_id = "s << document.id << ", "s
  528.         << "relevance = "s << document.relevance << ", "s
  529.         << "rating = "s << document.rating
  530.         << " }"s << endl;
  531. }
  532.  
  533. int main() {
  534.     SearchServer search_server;
  535.     // Инициализируем поисковую систему, передавая стоп-слова в контейнере vector
  536.     const vector<string> stop_words_vector = { "и"s, "в"s, "на"s, ""s, "в"s };
  537.     SearchServer search_server1(stop_words_vector);
  538.  
  539.     // Инициализируем поисковую систему передавая стоп-слова в контейнере set
  540.     const set<string> stop_words_set = { "и"s, "в"s, "на"s };
  541.     SearchServer search_server2(stop_words_set);
  542.  
  543.     // Инициализируем поисковую систему строкой со стоп-словами, разделёнными пробелами
  544.     SearchServer search_server3("  и  в на   "s);
  545.  
  546.     search_server.AddDocument(0, "белый кот и модный ошейник"s, DocumentStatus::ACTUAL, { 8, -3 });
  547.     search_server.AddDocument(1, "пушистый кот пушистый хвост"s, DocumentStatus::ACTUAL, { 7, 2, 7 });
  548.     search_server.AddDocument(2, "ухоженный пёс выразительные глаза"s, DocumentStatus::ACTUAL, { 5, -12, 2, 1 });
  549.     search_server.AddDocument(3, "ухоженный скворец евгений"s, DocumentStatus::BANNED, { 9 });
  550.     cout << "ACTUAL by default:"s << endl;
  551.     for (const Document& document : search_server.FindTopDocuments("пушистый ухоженный кот"s)) {
  552.         PrintDocument(document);
  553.     }
  554.     cout << "BANNED:"s << endl;
  555.     for (const Document& document : search_server.FindTopDocuments("пушистый ухоженный кот"s, DocumentStatus::BANNED)) {
  556.         PrintDocument(document);
  557.     }
  558.     cout << "Even ids:"s << endl;
  559.     for (const Document& document : search_server.FindTopDocuments("пушистый ухоженный кот"s, [](int document_id, DocumentStatus status, int rating) { return document_id % 2 == 0; })) {
  560.         PrintDocument(document);
  561.     }
  562. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!