//////////////////// // // Name: Simple Search Engine // Author: Shadow // Version: 1.5.0 // Date: 08.10.2018 // Description: A simple search engine, the task's // reference is in the comments. // The implementation makes use of the // 'Flyweight' pattern in order to reduce // the required memory space as the // number of entries grows by time. // For Sololearn, there is only a dummy // code in main() that doesn't need any // input. // However, I wrote a full menu // ( also in main() ) that you can use if // you try the code in an IDE (just // outcomment it). // If you want to, have a look at it. // If the code reports a compilation // error, blame the regex that sometimes // seems to throw the SL compiler off // (atleast for me, lol). // I used that for checking the input, // so just recompile in case of // compilation errors. // Any ideas for improvement are highly // welcome, I am not really sure if this // is a good approach/implementation // for what I am trying to accomplish... // Planned: - // //////////////////// // //////////PREPROCESSOR////////// // #include #include #include #include #include #include #include #include // //////////CLASSES////////// // /* Simple struct holding two values; * It is later required to act as a simple map. */ template struct Pair { A key; B value; Pair(const A& key, const B& value) :key{key}, value{value} {} }; /* These values will act as the key values for the map * ageKey keys the different ages and * can hold 2^8 different values, * professionsKey keys the different professions, * enabling 2^16 professions, * and nameKey keys all names (first and last names), * possibly a total of 2^32. * If the maps need to take more entries than * these, the maximum number of different * entries can be upgraded here (max: uint64_t). */ typedef uint8_t ageKey; typedef uint16_t professionKey; typedef uint32_t nameKey; /* Forward declaration of the databank */ class PersonDatabase; /* class Person * holds * -> the attributes in form of key values (see above) * -> internal databanks in form of static vectors * of Pair * -> seeds for the key values */ class Person { private: /* friend methods/classes */ friend class PersonDatabase; friend bool operator==(const Person&, const Person&); /* The idea is simply not to give every single * person its own string attributes, because there * will most likely be many duplicate attributes * between persons, especially in larger datasets. * Instead, each person holds key values as * members, which take up less memory space * and act as indices for internal lists of those * attributes that all persons share. */ nameKey firstName; nameKey lastName; professionKey profession; ageKey age; /* Each name gets a key packed with it. * If a user has a yet unique value, it will be * added to the list, and the user gets to hold * the key that indices that particular name. * To later get the name, one must simply refer * to it using the key. */ static std::vector< Pair > names; static std::vector< Pair > professions; static std::vector< Pair > ages; /* Now, why not simply make a vector of strings * instead of maps with complex key-value systems, * so that each person can hold a pointer * to the string that is their name? * The answer is memory space. * On most modern machines, pointers have a * fixed size; 32 bits (4 bytes) on 32 bit * machines, and 64 bits (8 bytes) on * 64 bit machines. * So a stored pointer makes atleast 4 byte, * whereas uint16_t for example only takes up * 16 bits (2 bytes). On 64 bit machines, * even uint32_t would save space. * So overall you can save quite some memory * space, as it will add up with growing entries. */ std::vector< Pair >::const_iterator findElement(const nameKey&) const; std::vector< Pair >::const_iterator findElement(const professionKey&) const; std::vector< Pair >::const_iterator findElement(const ageKey&) const; /* The seeds keep track of how many entries * the different maps have. Also, they are used * as seeds for new key values. */ static nameKey nameSeed; static professionKey professionSeed; static ageKey ageSeed; /* The following functions 'transform' the strings * in the constructor to key values. */ static nameKey addName(const std::string&); static professionKey addProfession(const std::string&); static ageKey addAge(const std::string&); /* substringMatches() acts as the base for search * operations. It goes through all different * properties and looks if it can find the * given substring in one of them, if it does, * true is returned, false otherwise. * This enables the search by age. */ bool substringMatches(const std::string&) const; public: Person(const std::string&, const std::string&, const std::string&, const std::string&); Person(const Person&); /* Inline getters to obtain the actual strings * from the keys. */ inline const std::string& getFirstName() const { return findElement(firstName)->value; } inline const std::string& getLastName() const { return findElement(lastName)->value; } inline const std::string& getProfession() const { return findElement(profession)->value; } inline const std::string& getAge() const { return findElement(age)->value; } }; /* Initialization of the static members */ std::vector< Pair > Person::names = {}; std::vector< Pair > Person::professions = {}; std::vector< Pair > Person::ages = {}; nameKey Person::nameSeed = 0; professionKey Person::professionSeed = 0; ageKey Person::ageSeed = 0; Person::Person(const std::string& firstName, const std::string& lastName, const std::string& profession, const std::string& age) :firstName{ addName( firstName ) }, lastName{ addName( lastName ) }, profession{ addProfession( profession ) }, age{ addAge( age ) } {} Person::Person(const Person& person) :firstName{ person.firstName }, lastName{ person.lastName }, profession{ person.profession }, age{ person.age } {} /* The findElement() method is overloaded for the * different maps (not very handy, I know) and * performs a linear search to find the value mapped * by the key which is given as the argument. */ std::vector< Pair >::const_iterator Person::findElement(const nameKey& key) const { for (auto it = names.cbegin(); it != names.cend(); ++it) { if (it->key == key) { return it; } } return names.cend(); } std::vector< Pair >::const_iterator Person::findElement(const professionKey& key) const { for (auto it = professions.cbegin(); it != professions.cend(); ++it) { if (it->key == key) { return it; } } return professions.cend(); } std::vector< Pair >::const_iterator Person::findElement(const ageKey& key) const { for (auto it = ages.cbegin(); it != ages.cend(); ++it) { if (it->key == key) { return it; } } return ages.cend(); } /* The addXYZ() method takes in the string and * performs a linear search on the appropriate map. * If the string is already in the list, its key is * returned, otherwise a new entry is made using the * seed as the index, which is then returned. */ nameKey Person::addName(const std::string& name) { for (auto it = names.begin(); it != names.end(); ++it) { if (it->value == name) { return it->key; } } names.push_back( {++nameSeed, name} ); return nameSeed; } professionKey Person::addProfession(const std::string& profession) { for (auto it = professions.begin(); it != professions.end(); ++it) { if (it->value == profession) { return it->key; } } professions.push_back( {++professionSeed, profession} ); return professionSeed; } ageKey Person::addAge(const std::string& age) { for (auto it = ages.begin(); it != ages.end(); ++it) { if (it->value == age) { return it->key; } } ages.push_back( {++ageSeed, age} ); return ageSeed; } bool Person::substringMatches(const std::string& s) const { return getFirstName().find(s) != std::string::npos || getLastName().find(s) != std::string::npos || getProfession().find(s) != std::string::npos || getAge().find(s) != std::string::npos; } /* The comparison operator is overloaded for * operations where the comparison of objects of type * Person is required, for example when traversing * the database for duplicates. */ bool operator==(const Person& p1, const Person& p2) { return ( p1.firstName == p2.firstName && p1.lastName == p2.lastName && p1.profession == p2.profession && p1.age == p2.age ); } /* Overloading of << for pretty-printing of Person */ std::ostream& operator<<(std::ostream& os, const Person& person) { os << person.getFirstName() << " " << person.getLastName() << ", " << person.getProfession() << ", " << person.getAge(); return os; } class PersonDatabase { private: /* For a databank, the random access granted by * vectors is not required, plus lists generally * perform better on insert and erase operations * anywhere in the list. * Therefore, a forward_list seems to be the best * solution as a storage container. */ std::forward_list persons; /* Methods to construct a person based on user * input. */ std::string requestFirstName() const; std::string requestLastName() const; std::string requestProfession() const; std::string requestAge() const; Person requestPerson() const; public: PersonDatabase() = default; PersonDatabase(const std::initializer_list&); PersonDatabase(const std::vector&); /* available public methods for the list */ void addEntry(const Person&); bool addEntry(); void deleteEntry(const Person&); bool deleteEntry(); void deleteEntriesBySubstring(const std::string&); void deleteEntriesBySubstring(); bool deleteAllEntries(); void printAllEntries() const; void printEntries(const std::string&) const; void printEntries() const; /* A list of methods to enable iterating * the databank from the outside. * The methods directly refer to the methods * found in std::forward_list. */ inline std::forward_list::const_iterator cbefore_begin() const { return persons.cbefore_begin(); } inline std::forward_list::const_iterator cbegin() const { return persons.cbegin(); } inline std::forward_list::const_iterator cend() const { return persons.cend(); } }; /* Implementation of the input methods. * Each method repeatedly asks the user for one * specific property of Person such as the age * until the input matches a predefined formular * given by an object of std::regex. */ std::string PersonDatabase::requestFirstName() const { std::string firstName; std::regex is_Name( "[A-Z][a-z]*" ); std::cout << "\nPlease enter the first name: "; do { std::cin >> firstName; if ( !std::regex_match(firstName, is_Name) ) { std::cout << "\nInvalid name. Please try gain: "; } } while ( !std::regex_match(firstName, is_Name) ); return firstName; } std::string PersonDatabase::requestLastName() const { std::string lastName; std::regex is_Name( "[A-Z][a-z]*" ); std::cout << "\nPlease enter the last name: "; do { std::cin >> lastName; if ( !std::regex_match(lastName, is_Name) ) { std::cout << "\nInvalid name. Please try gain: "; } } while ( !std::regex_match(lastName, is_Name) ); return lastName; } std::string PersonDatabase::requestProfession() const { std::string profession; std::regex is_Profession( "([A-Z][a-z]*.?)+" ); std::cout << "\nPlease enter the profession: "; do { std::cin.ignore(); std::getline(std::cin, profession); if ( !std::regex_match(profession, is_Profession) ) { std::cout << "\nInvalid profession. Please try again: "; } } while ( !std::regex_match(profession, is_Profession) ); return profession; } std::string PersonDatabase::requestAge() const { std::string age; std::regex is_Age( "[0-9]{1,3}" ); std::cout << "\nPlease enter the age: "; do { std::cin >> age; if ( !std::regex_match(age, is_Age) ) { std::cout << "\nInvalid age. Please try again: "; } } while ( !std::regex_match(age, is_Age) ); return age; } /* requestPerson() simply puts the preceding methods * together and returns a Person object constructed * from the input values. */ Person PersonDatabase::requestPerson() const { return { requestFirstName(), requestLastName(), requestProfession(), requestAge() }; } PersonDatabase::PersonDatabase(const std::initializer_list& list) :persons{ list.begin(), list.end() } {} PersonDatabase::PersonDatabase(const std::vector& list) :persons{ list.begin(), list.end() } {} /* Implementations of the public methods available for * users of the database. */ void PersonDatabase::addEntry(const Person& person) { persons.push_front( person ); } bool PersonDatabase::addEntry() { Person person{ requestPerson() }; for (auto it = persons.begin(); it != persons.end(); ++it) { if (*it == person) { return false; } } addEntry(person); return true; } void PersonDatabase::deleteEntry(const Person& person) { persons.remove(person); } bool PersonDatabase::deleteEntry() { Person person{ requestPerson() }; for (auto it = persons.begin(); it != persons.end(); ++it) { if (*it == person) { deleteEntry( person ); return true; } } return false; } void PersonDatabase::deleteEntriesBySubstring(const std::string& s) { persons.remove_if ( [&](const Person& person) { return person.substringMatches(s); } ); } void PersonDatabase::deleteEntriesBySubstring() { std::string token; std::cout << "\nPlease enter a term used as indicator for the delete operation: "; std::cin >> token; deleteEntriesBySubstring(token); } bool PersonDatabase::deleteAllEntries() { if ( persons.empty() ) { return false; } else { persons.clear(); return true; } } void PersonDatabase::printAllEntries() const { std::cout << "\n"; for (auto it = persons.begin(); it != persons.end(); ++it) { std::cout << *it << std::endl; } } void PersonDatabase::printEntries(const std::string& s) const { std::cout << "\n"; for (auto it = persons.begin(); it != persons.end(); ++it) { if ( it->substringMatches(s) ) { std::cout << *it << std::endl; } } } void PersonDatabase::printEntries() const { std::string token; std::cout << "\nPlease enter a term to search the database for: "; std::cin >> token; printEntries(token); } /* Function for the menu which simply asks the user * for his next step. */ void executeSubmenu(char& option) { std::cout << "\n\n(R)eturn to menu (C)ontinue" << "\nPlease choose an option: "; do { std::cin >> option; if (option != 'R' && option != 'C') { std::cout << "\nInvalid option. Please try again: "; } } while (option != 'R' && option != 'C'); } int main() { /* Start of the original menu */ /* This is the original menu. * You can use this when trying * the code in an IDE where it works * at it is supposed to do. enum class OPTION { ADD_ENTRY = 1, DELETE_ENTRY, DELETE_ENTRIES, DELETE_ALL_ENTRIES, PRINT_ENTRIES, PRINT_ALL_ENTRIES, EXIT }; short menu_option; char submenu_option; PersonDatabase database; std::cout << "Welcome, User."; do { std::cout << "\n\n~~~Database Menu~~~\n" << "(1) Add Entry\n" << "(2) Delete Entry\n" << "(3) Delete multiple Entries\n" << "(4) Delete all Entries\n" << "(5) Print Entries\n" << "(6) Print all Entries\n" << "(7) Exit\n"; std::cout << "Please choose an option: "; do { std::cin >> menu_option; if (menu_option < 1 || menu_option > 7) { std::cout << "\nInvalid option. Please try again: "; } } while (menu_option < 1 || menu_option > 7); switch (menu_option) { case static_cast( OPTION::ADD_ENTRY ): { do { if ( database.addEntry() ) { std::cout << "\nThe person was added to the database."; } else { std::cout << "\nThe person could not be added to the database because a similar entry already exists."; } executeSubmenu(submenu_option); } while (submenu_option == 'C'); } break; case static_cast( OPTION::DELETE_ENTRY ): { do { if ( database.deleteEntry() ) { std::cout << "\nThe entry was deleted from the database."; } else { std::cout << "\nThere is no such entry in the database."; } executeSubmenu(submenu_option); } while (submenu_option == 'C'); } break; case static_cast( OPTION::DELETE_ENTRIES ): { do { database.deleteEntriesBySubstring(); std::cout << "\nAll entries matching the term were deleted from the database."; executeSubmenu(submenu_option); } while (submenu_option == 'C'); } break; case static_cast( OPTION::DELETE_ALL_ENTRIES ): { if ( database.deleteAllEntries() ) { std::cout << "\nAll entries were erased from the database."; } else { std::cout << "\nThe database currently has no entries."; } } break; case static_cast( OPTION::PRINT_ENTRIES ): { database.printEntries(); } break; case static_cast( OPTION::PRINT_ALL_ENTRIES ): { database.printAllEntries(); } break; case static_cast( OPTION::EXIT ): { std::cout << "\nShutting down the application..." << "\nGoodbye, User."; } break; default: { std::cout << "\nSomething went wrong. Redirecting to menu...\n\n"; } }; } while ( menu_option != static_cast( OPTION::EXIT ) ); /* End of the original menu */ /* Start of the demo code */ // Set up a databank // /* I was loop-listening to * 'A Cruel Angel's Thesis' while doing this, * sorry for the EVA data thing XD */ PersonDatabase eva_Data { { "Shinji", "Ikari", "EVA Pilot", "14" }, { "Asuka", "Langley", "EVA Pilot", "13" }, { "Rei", "Ayanami", "EVA Pilot", "14" }, { "Misato", "Katsuragi", "Captain", "29" }, { "Ritsuko", "Akagi", "Scientist", "30" }, { "Gendo", "Ikari", "Commander of NERV", "48" }, { "Yui", "Ikari", "Bioengineer", "27" }, { "Kozo", "Fuyutsuki", "Vice commander of NERV", "58" }, { "Ryoji", "Kaji", "Chief Inspector", "30" }, { "Maya", "Ibuki", "Computer Technician", "24" }, { "Kaworu", "Nagisa", "Fifth Child/Angel", "15" }, { "Keel", "Lorenz", "Leader of Seele", "Unknown" } }; // print all entries // std::cout << "List of EVA characters:\n"; eva_Data.printAllEntries(); // print all entries containing the substring "Pilot" // std::cout << "\n\nList of Pilots:\n"; eva_Data.printEntries("Pilot"); // delete all entries containing the substring "Ikari" // eva_Data.deleteEntriesBySubstring("Ikari"); std::cout << "\n\nList after erasing 'Ikari':\n"; eva_Data.printAllEntries(); /* End of the demo code */ return 0; }