SHARE
TWEET

Untitled

a guest Feb 20th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "test_runner.h"
  2.  
  3. #include <iostream>
  4. #include <map>
  5. #include <string>
  6. #include <unordered_map>
  7. #include <unordered_set>
  8.  
  9.  
  10. using namespace std;
  11.  
  12. struct Record {
  13.     string id;
  14.     string title;
  15.     string user;
  16.     int timestamp;
  17.     int karma;
  18. };
  19.  
  20. struct RecordHasher {
  21.     size_t operator()(const Record &record) const {
  22.         const size_t c = 514'229;
  23.  
  24.        const hash<int> int_hasher;
  25.        const hash<string> string_hasher;
  26.  
  27. //        return int_hasher(record.karma) + c * int_hasher(record.timestamp) + c * c * string_hasher(record.user) +
  28. //               c * c * c * string_hasher(record.title) + c * c * c * c * string_hasher(record.id);
  29.        return  c * c * c * c * string_hasher(record.id);
  30.  
  31.    }
  32. };
  33.  
  34. bool operator==(const Record &lhs, const Record &rhs) {
  35.    return lhs.id == rhs.id;
  36. }
  37.  
  38. // Реализуйте этот класс
  39. class Database {
  40.    using BulkWarehouse = unordered_set<Record, RecordHasher>;
  41.    using RecordPointer = BulkWarehouse::iterator;
  42.    using IdWarehouse = unordered_map<string, RecordPointer>;
  43.    using UserIndex = multimap<string, RecordPointer>;
  44.    using IntegerIndex = multimap<int, RecordPointer>;
  45.  
  46.  
  47. public:
  48.    bool Put(const Record &record) {
  49.        auto result = bulkWarehouse.insert(record);
  50.        bool success = result.second;
  51.        if (success) {
  52.            idWarehouse[record.id] = result.first;
  53.            auto user_result = userIndex.insert({record.user, result.first});
  54.            auto karma_result = karmaIndex.insert({record.karma, result.first});
  55.            auto timestamp_result = timestampIndex.insert({record.timestamp, result.first});
  56.  
  57.            invertedIndex.insert({record.id, make_tuple(user_result, karma_result, timestamp_result)});
  58.        }
  59.        return success;
  60.    };
  61.  
  62.    const Record *GetById(const string &id) const {
  63.        if (idWarehouse.count(id) == 0) {
  64.            return nullptr;
  65.        }
  66.        return &(*idWarehouse.at(id));
  67.    };
  68.  
  69.    bool Erase(const string &id) {
  70.        if (idWarehouse.count(id) == 0) {
  71.            return false;
  72.        }
  73.        auto p = idWarehouse[id];
  74.        bulkWarehouse.erase(p);
  75.        idWarehouse.erase(id);
  76.  
  77.        auto ip = invertedIndex[id];
  78.        userIndex.erase(get<0>(ip));
  79.        karmaIndex.erase(get<1>(ip));
  80.        timestampIndex.erase(get<2>(ip));
  81.  
  82.        invertedIndex.erase(id);
  83.        return true;
  84.    };
  85.  
  86.    template<typename Callback>
  87.    void RangeByTimestamp(int low, int high, Callback callback) const {
  88.        auto lower = timestampIndex.lower_bound(low);
  89.        auto upper = timestampIndex.upper_bound(high);
  90.  
  91.        for (auto it = lower; it != upper; it++) {
  92.            if (!callback(*it->second)) {
  93.                break;
  94.            }
  95.        }
  96.    };
  97.  
  98.    template<typename Callback>
  99.    void RangeByKarma(int low, int high, Callback callback) const {
  100.        auto lower = karmaIndex.lower_bound(low);
  101.        auto upper = karmaIndex.upper_bound(high);
  102.  
  103.        for (auto it = lower; it != upper; it++) {
  104.            if (!callback(*it->second)) {
  105.                break;
  106.            }
  107.        }
  108.    };
  109.  
  110.    template<typename Callback>
  111.    void AllByUser(const string &user, Callback callback) const {
  112.        auto range = userIndex.equal_range(user);
  113.        for (auto it = range.first; it != range.second; it++) {
  114.            if (!callback(*it->second)) {
  115.                break;
  116.            }
  117.        }
  118.    };
  119. private:
  120.    BulkWarehouse bulkWarehouse;
  121.    IdWarehouse idWarehouse;
  122.  
  123.    UserIndex userIndex;
  124.    IntegerIndex karmaIndex;
  125.    IntegerIndex timestampIndex;
  126.  
  127.    unordered_map<string, tuple<UserIndex::iterator, IntegerIndex::iterator, IntegerIndex::iterator>> invertedIndex;
  128. };
  129.  
  130. void TestBoundariesSinglePoint() {
  131.  
  132.    Database db;
  133.    db.Put({"id1", "Hello there", "master", 1536107260, 1});
  134.    db.Put({"id23", "Hello there", "master", 1536107260, 1});
  135.    db.Put({"id2", "O>>-<", "general2", 1536107260, 2});
  136.    db.Put({"id3", "O>>-<", "general2", 1536107260, 3});
  137.    db.Put({"id4", "O>>-<", "general2", 1536107260, 4});
  138.    int counter_whole = 0;
  139.    db.RangeByKarma(0, 1, [&counter_whole](const Record &) {
  140.        ++counter_whole;
  141.        return true;
  142.    });
  143.    ASSERT_EQUAL(2, counter_whole);
  144. }
  145.  
  146. void TestRangeBoundaries() {
  147.  
  148.    Database db;
  149.    db.Put({"id1", "Hello there", "master", 1536107260, 1});
  150.    db.Put({"id2", "O>>-<", "general2", 1536107260, 2});
  151.    db.Put({"id3", "O>>-<", "general2", 1536107260, 3});
  152.    db.Put({"id4", "O>>-<", "general2", 1536107260, 4});
  153.  
  154.    // testing whole range
  155.    int counter_whole = 0;
  156.    db.RangeByKarma(1, 4, [&counter_whole](const Record &) {
  157.        ++counter_whole;
  158.        return true;
  159.    });
  160.    ASSERT_EQUAL(4, counter_whole);
  161.  
  162.  
  163.    int counter_nolast = 0;
  164.    db.RangeByKarma(1, 3, [&counter_nolast](const Record &) {
  165.        ++counter_nolast;
  166.        return true;
  167.    });
  168.    ASSERT_EQUAL(3, counter_nolast);
  169.  
  170.  
  171.    int counter_nofirst = 0;
  172.    db.RangeByKarma(2, 4, [&counter_nofirst](const Record &) {
  173.        ++counter_nofirst;
  174.        return true;
  175.    });
  176.    ASSERT_EQUAL(3, counter_nofirst);
  177.  
  178.    int ct_no = 0;
  179.    db.RangeByKarma(100, 101, [&ct_no](const Record &) {
  180.        ++ct_no;
  181.        return true;
  182.    });
  183.    ASSERT_EQUAL(0, ct_no);
  184. }
  185.  
  186. void TestRangeBoundariesInclusive() {
  187.    const int good_karma = 1000;
  188.    const int bad_karma = -10;
  189.  
  190.    Database db;
  191.    db.Put({"id1", "Hello there", "master", 1536107260, good_karma});
  192.    db.Put({"id2", "O>>-<", "general2", 1536107260, bad_karma});
  193.  
  194.    int count = 0;
  195.    db.RangeByKarma(bad_karma, good_karma, [&count](const Record &) {
  196.        ++count;
  197.        return true;
  198.    });
  199.  
  200.    ASSERT_EQUAL(2, count);
  201. }
  202.  
  203. void TestRangeBoundariesErase() {
  204.    const int good_karma = 1000;
  205.    const int bad_karma = -10;
  206.  
  207.    Database db;
  208.    db.Put({"id1", "Hello there", "master", 1536107260, good_karma});
  209.    db.Put({"id2", "O>>-<", "general2", 1536107260, bad_karma});
  210.    db.Erase("id2");
  211.  
  212.    int count = 0;
  213.    db.RangeByKarma(bad_karma, good_karma, [&count](const Record &) {
  214.        ++count;
  215.        return true;
  216.    });
  217.  
  218.    ASSERT_EQUAL(1, count);
  219. }
  220.  
  221. ostream &operator<<(ostream &os, const Record &r) {
  222.    os << r.id << " " << r.title << " " << r.user << " " << r.timestamp << " " << r.karma;
  223.    return os;
  224. }
  225.  
  226. void TestPutUser() {
  227.    Database db;
  228.    bool done = db.Put({"id1", "Hello there", "master", 1536107260, 1});
  229.    ASSERT_EQUAL(done, true)
  230.  
  231.    bool notdone = db.Put({"id1", "Hello111 there", "master", 1536107260, 1});
  232.    ASSERT_EQUAL(notdone, false)
  233. }
  234.  
  235. void TestPutRetrieveUser() {
  236.    Database db;
  237.    Record testRecord{"id1", "Hello there", "master", 1536107260, 1};
  238.    bool done = db.Put(testRecord);
  239.  
  240.    const Record *r = db.GetById(testRecord.id);
  241.    ASSERT_EQUAL(*r, testRecord)
  242. }
  243.  
  244. void TestPutRetrieveUserNonExist() {
  245.    Database db;
  246.    Record testRecord{"id1", "Hello there", "master", 1536107260, 1};
  247.    bool done = db.Put(testRecord);
  248.  
  249.    const Record *r = db.GetById("id2");
  250.    ASSERT(!r)
  251. }
  252.  
  253. void TestEraseExist() {
  254.    Database db;
  255.    Record testRecord{"id1", "Hello there", "master", 1536107260, 1};
  256.    db.Put(testRecord);
  257.    bool done = db.Erase(testRecord.id);
  258.    ASSERT_EQUAL(done, true)
  259.    ASSERT(!db.GetById(testRecord.id))
  260. }
  261.  
  262. void TestEraseNonExist() {
  263.    Database db;
  264.    Record testRecord{"id1", "Hello there", "master", 1536107260, 1};
  265.    bool done = db.Erase("NO SUCH ID");
  266.    ASSERT_EQUAL(done, false)
  267. }
  268.  
  269. void TestSameUser() {
  270.    Database db;
  271.    db.Put({"id1", "Don't sell", "master", 1536107260, 1000});
  272.    db.Put({"id2", "Rethink life", "master", 1536107260, 2000});
  273.  
  274.    int count = 0;
  275.    db.AllByUser("master", [&count](const Record &) {
  276.        ++count;
  277.        return true;
  278.    });
  279.  
  280.    ASSERT_EQUAL(2, count)
  281. }
  282.  
  283. void TestSameUserWithDelete() {
  284.    Database db;
  285.    db.Put({"id1", "Don't sell", "master", 1536107260, 1000});
  286.    db.Put({"id2", "Rethink life", "master", 1536107260, 2000});
  287.    db.Erase("id2");
  288.    int count = 0;
  289.    db.AllByUser("master1", [&count](const Record &) {
  290.        ++count;
  291.        return true;
  292.    });
  293.  
  294.    ASSERT_EQUAL(0, count)
  295. }
  296.  
  297. //
  298. void TestReplacement() {
  299.    const string final_body = "Feeling sad";
  300.  
  301.    Database db;
  302.    db.Put({"id", "Have a hand", "not-master", 1536107260, 10});
  303.    db.Erase("id");
  304.    db.Put({"id", final_body, "not-master", 1536107260, -10});
  305.  
  306.    auto record = db.GetById("id");
  307.    ASSERT(record != nullptr);
  308.    ASSERT_EQUAL(final_body, record->title);
  309. }
  310.  
  311. int main() {
  312.    TestRunner tr;
  313.    RUN_TEST(tr, TestPutUser);
  314.    RUN_TEST(tr, TestPutRetrieveUser);
  315.    RUN_TEST(tr, TestPutRetrieveUserNonExist);
  316.    RUN_TEST(tr, TestEraseExist);
  317.    RUN_TEST(tr, TestEraseNonExist);
  318.    RUN_TEST(tr, TestRangeBoundariesInclusive);
  319.    RUN_TEST(tr, TestRangeBoundariesErase);
  320.    RUN_TEST(tr, TestSameUser);
  321.    RUN_TEST(tr, TestSameUserWithDelete);
  322.    RUN_TEST(tr, TestReplacement);
  323.    RUN_TEST(tr, TestRangeBoundaries);
  324.    RUN_TEST(tr, TestBoundariesSinglePoint);
  325.    return 0;
  326. }
RAW Paste Data
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
 
Top