Phonebook.cpp

/*
    =====================================================================
     DIGITAL PHONEBOOK  -  DSA PROJECT (C++)
    =====================================================================
    Data Structures used (and why):

    1. TRIE (Prefix Tree)
       -> Used to give live "as-you-type" name suggestions, exactly like
          the contact search box on a real phone.
       -> insert()   : O(L)      L = length of name
       -> getSuggestions(prefix): O(L + K) K = number of matching names
       -> remove()   : O(L), also cleans up dead branches so the trie
          never grows unbounded after deletions.

    2. HASH MAP (unordered_map)
       -> contactsByName : name(lowercased) -> Contact   => O(1) avg
          add / search / update / delete by exact name.
       -> contactsByPhone: phone number     -> name       => O(1) avg
          reverse lookup so you can also search by number.

    3. FILE HANDLING (fstream)
       -> Every change is written to "phonebook_data.txt" so the data
          survives after the terminal / program is closed.
       -> On startup the file is read back into the Trie + Hash Maps.

    Design choice asked for: a name is the ONLY compulsory field.
    Phone number, email and address can all be left blank and filled
    in later with "Update Contact" -- just like a real paper phonebook
    where you might jot down just a name first.
    =====================================================================
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <map>
#include <vector>
#include <algorithm>
#include <limits>
#include <regex>
#include <cctype>

#if defined(_WIN32)
    #include <conio.h>          // Windows: _getch()
    #include <windows.h>        // Windows: SetConsoleOutputCP / SetConsoleCP
#else
    #include <termios.h>
    #include <unistd.h>
    #include <cstdio>
#endif

using namespace std;

const string DATA_FILE = "phonebook_data.txt";
const char   DELIM     = '|';   // field separator used in the save file

// ---------------------------------------------------------------------
//  Utility helpers
// ---------------------------------------------------------------------
// Lowercases only ASCII letters (bytes 0-127). Bytes >= 128 are the
// continuation/lead bytes of multi-byte UTF-8 sequences (e.g. emoji,
// accented letters) and are passed through unchanged -- calling
// ::tolower() directly on those would be undefined behaviour, and
// there's no "case" for an emoji anyway.
string toLower(const string &s) {
    string r = s;
    for (char &c : r) {
        unsigned char uc = static_cast<unsigned char>(c);
        if (uc < 128) c = static_cast<char>(::tolower(uc));
    }
    return r;
}

string trim(const string &s) {
    size_t start = s.find_first_not_of(" \t\r\n");
    if (start == string::npos) return "";
    size_t end = s.find_last_not_of(" \t\r\n");
    return s.substr(start, end - start + 1);
}

// Removes one whole UTF-8 character from the end of a string. A single
// emoji or accented letter can be 2-4 bytes; a plain backspace() /
// pop_back() would only strip one byte and leave a broken, invisible
// half-character behind. This strips any trailing "continuation"
// bytes (the ones matching bit pattern 10xxxxxx) and then the lead
// byte itself, so one Backspace press always deletes one full
// character, emoji included.
void popUTF8Char(string &s) {
    if (s.empty()) return;
    while (!s.empty() && (static_cast<unsigned char>(s.back()) & 0xC0) == 0x80)
        s.pop_back();          // strip continuation bytes
    if (!s.empty()) s.pop_back();   // strip the lead byte
}

// Reads one full line of input safely (works after cin >> too)
string readLine(const string &prompt) {
    cout << prompt;
    string line;
    getline(cin, line);
    return trim(line);
}

// ---------------------------------------------------------------------
//  Validation
// ---------------------------------------------------------------------

// Phone number rule: must look like a real, existing 10-digit mobile
// number -- not just "10 digits or fewer of anything".
//   - exactly 10 digits (no more, no less)
//   - first digit must be 6, 7, 8, or 9 (valid Indian mobile prefixes;
//     no real mobile number starts with 0-5)
//   - rejects obviously fake numbers like 0000000000 / 9999999999
// (Empty string is treated as "skipped" by the callers below.)
bool isValidPhone(const string &phone) {
    if (phone.empty()) return true;                       // skipped, allowed
    if (phone.size() != 10) return false;                  // must be exactly 10 digits
    for (char c : phone)
        if (!isdigit((unsigned char)c)) return false;      // digits only

    if (phone[0] < '6' || phone[0] > '9') return false;    // valid starting digit

    if (all_of(phone.begin(), phone.end(), [&](char c) { return c == phone[0]; }))
        return false;                                       // e.g. 8888888888 -> reject

    return true;
}

// Simple but solid RFC-5322-ish email check: local@domain.tld
bool isValidEmail(const string &email) {
    if (email.empty()) return true;               // skipped, allowed
    static const regex pattern(
        R"(^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}$)");
    return regex_match(email, pattern);
}

// Keeps re-prompting until the user enters a valid phone number or,
// if allowSkip is true, just presses Enter to leave it blank.
string readValidPhone(const string &prompt, bool allowSkip) {
    while (true) {
        string phone = readLine(prompt);
        if (phone.empty()) {
            if (allowSkip) return phone;
            cout << "Phone number cannot be empty here.\n";
            continue;
        }
        if (!isValidPhone(phone)) {
            cout << "Invalid phone number: must be exactly 10 digits, start with 6-9, and be a real-looking number.\n";
            continue;
        }
        return phone;
    }
}

// Keeps re-prompting until the user enters a valid email or, if
// allowSkip is true, just presses Enter to leave it blank.
string readValidEmail(const string &prompt, bool allowSkip) {
    while (true) {
        string email = readLine(prompt);
        if (email.empty()) {
            if (allowSkip) return email;
            cout << "Email cannot be empty here.\n";
            continue;
        }
        if (!isValidEmail(email)) {
            cout << "Invalid email format. Example: name@example.com\n";
            continue;
        }
        return email;
    }
}

// Portable single-key read (no Enter needed) for the live-suggestion mode
#if !defined(_WIN32)
int _getch() {
    struct termios oldt, newt;
    int ch;
    tcgetattr(STDIN_FILENO, &oldt);
    newt = oldt;
    newt.c_lflag &= ~(ICANON | ECHO);
    tcsetattr(STDIN_FILENO, TCSANOW, &newt);
    ch = getchar();
    tcsetattr(STDIN_FILENO, TCSANOW, &oldt);
    return ch;
}
#endif

// ---------------------------------------------------------------------
//  Contact record
// ---------------------------------------------------------------------
struct Contact {
    string name;                 // compulsory
    string phone   = "-";        // optional (default "-" means "not set")
    string email   = "-";        // optional
    string address = "-";        // optional
};

// ---------------------------------------------------------------------
//  TRIE  -  for prefix based name suggestions
// ---------------------------------------------------------------------
struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
    TrieNode* root;

    // Recursive delete used by remove()
    bool removeHelper(TrieNode* node, const string &word, int depth) {
        if (!node) return false;

        if (depth == (int)word.size()) {
            if (!node->isEnd) return false;   // word wasn't there
            node->isEnd = false;
            return node->children.empty();    // true => safe to delete this node
        }

        char c = word[depth];
        if (node->children.find(c) == node->children.end()) return false;

        bool shouldDeleteChild = removeHelper(node->children[c], word, depth + 1);

        if (shouldDeleteChild) {
            delete node->children[c];
            node->children.erase(c);
        }

        return node->children.empty() && !node->isEnd;
    }

    void dfsCollect(TrieNode* node, string current, vector<string> &results) {
        if (!node) return;
        if (node->isEnd) results.push_back(current);
        for (auto &p : node->children)
            dfsCollect(p.second, current + p.first, results);
    }

public:
    Trie() { root = new TrieNode(); }

    void insert(const string &word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end())
                node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->isEnd = true;
    }

    void remove(const string &word) {
        removeHelper(root, word, 0);
    }

    // Returns every stored (lowercase) word that starts with 'prefix'
    vector<string> getSuggestions(const string &prefix) {
        vector<string> results;
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end())
                return results;              // no match at all
            node = node->children[c];
        }
        dfsCollect(node, prefix, results);
        sort(results.begin(), results.end());
        return results;
    }
};

// ---------------------------------------------------------------------
//  PHONEBOOK  -  ties Trie + Hash Maps + File storage together
// ---------------------------------------------------------------------
class PhoneBook {
    unordered_map<string, Contact> contactsByName;   // key = lowercase name
    unordered_map<string, string>  contactsByPhone;  // key = phone -> lowercase name
    Trie nameTrie;

    void indexContact(const Contact &c) {
        string key = toLower(c.name);
        contactsByName[key] = c;
        nameTrie.insert(key);
        if (c.phone != "-" && !c.phone.empty())
            contactsByPhone[c.phone] = key;
    }

    void deindexContact(const Contact &c) {
        string key = toLower(c.name);
        nameTrie.remove(key);
        if (c.phone != "-" && !c.phone.empty())
            contactsByPhone.erase(c.phone);
        contactsByName.erase(key);
    }

public:
    // ---------- persistence ----------
    void loadFromFile() {
        ifstream in(DATA_FILE);
        if (!in.is_open()) return;   // first run, no file yet

        string line;
        while (getline(in, line)) {
            if (trim(line).empty()) continue;
            stringstream ss(line);
            string field;
            vector<string> fields;
            while (getline(ss, field, DELIM)) fields.push_back(field);
            while (fields.size() < 4) fields.push_back("-");

            Contact c;
            c.name    = fields[0];
            c.phone   = fields[1];
            c.email   = fields[2];
            c.address = fields[3];
            indexContact(c);
        }
        in.close();
    }

    void saveToFile() {
        ofstream out(DATA_FILE, ios::trunc);
        for (auto &p : contactsByName) {
            Contact &c = p.second;
            out << c.name << DELIM << c.phone << DELIM
                << c.email << DELIM << c.address << "\n";
        }
        out.close();
    }

    // ---------- CRUD ----------
    bool addContact(const Contact &c) {
        string key = toLower(c.name);
        if (contactsByName.count(key)) return false;   // already exists
        if (c.phone != "-" && contactsByPhone.count(c.phone)) return false; // number taken
        indexContact(c);
        saveToFile();
        return true;
    }

    bool exists(const string &name) {
        return contactsByName.count(toLower(name)) > 0;
    }

    Contact* getByName(const string &name) {
        auto it = contactsByName.find(toLower(name));
        if (it == contactsByName.end()) return nullptr;
        return &it->second;
    }

    Contact* getByPhone(const string &phone) {
        auto it = contactsByPhone.find(phone);
        if (it == contactsByPhone.end()) return nullptr;
        return getByName(it->second);
    }

    vector<string> suggest(const string &prefix) {
        return nameTrie.getSuggestions(toLower(trim(prefix)));
    }

    // Prefix matches (fast, via the Trie) PLUS a substring fallback so
    // a search still finds a name when the typed text is in the middle
    // or end of the name -- e.g. searching just an emoji finds
    // "Amit ??" even though the emoji isn't the first character.
    // The substring pass is a simple O(N) linear scan; a plain Trie
    // only indexes prefixes, and building a full suffix structure is
    // overkill for a phonebook's contact list size.
    vector<string> smartSearch(const string &query) {
        string q = toLower(trim(query));
        if (q.empty()) return {};

        vector<string> results = nameTrie.getSuggestions(q);   // prefix matches first

        vector<string> extra;
        for (auto &p : contactsByName) {
            if (p.first.find(q) != string::npos &&
                find(results.begin(), results.end(), p.first) == results.end())
                extra.push_back(p.first);
        }
        sort(extra.begin(), extra.end());
        results.insert(results.end(), extra.begin(), extra.end());
        return results;
    }

    bool updateContact(const string &name, const string &newPhone,
                        const string &newEmail, const string &newAddress) {
        Contact* c = getByName(name);
        if (!c) return false;

        // free old phone index if the number is changing
        if (c->phone != "-" && c->phone != newPhone)
            contactsByPhone.erase(c->phone);

        if (!newPhone.empty())   c->phone   = newPhone;
        if (!newEmail.empty())   c->email   = newEmail;
        if (!newAddress.empty()) c->address = newAddress;

        if (c->phone != "-" && !c->phone.empty())
            contactsByPhone[c->phone] = toLower(name);

        saveToFile();
        return true;
    }

    bool deleteContact(const string &name) {
        Contact* c = getByName(name);
        if (!c) return false;
        Contact copy = *c;          // deindex needs the data before erasing
        deindexContact(copy);
        saveToFile();
        return true;
    }

    void displayAll() {
        if (contactsByName.empty()) {
            cout << "\n[Phonebook is empty]\n";
            return;
        }
        vector<Contact> all;
        for (auto &p : contactsByName) all.push_back(p.second);
        sort(all.begin(), all.end(), [](const Contact &a, const Contact &b) {
            return toLower(a.name) < toLower(b.name);
        });

        cout << "\n" << string(70, '-') << "\n";
        cout << "Total contacts: " << all.size() << "\n";
        cout << string(70, '-') << "\n";
        for (auto &c : all) printContact(c);
        cout << string(70, '-') << "\n";
    }

    static void printContact(const Contact &c) {
        cout << "Name: " << c.name
             << " | Phone: " << c.phone
             << " | Email: " << c.email
             << " | Address: " << c.address << "\n";
    }

    int count() { return (int)contactsByName.size(); }
};

// ---------------------------------------------------------------------
//  Live typing preview (WhatsApp-style compose box)
//  Shows exactly what you've typed, updating with every keystroke --
//  including emoji, which normal line input would just echo raw
//  anyway, but this gives the same "watch it appear as you type" feel
//  everywhere, and handles Backspace on a whole emoji correctly.
// ---------------------------------------------------------------------
string liveTypedInput(const string &label) {
    cout << "\n" << label << "  (BACKSPACE to erase, ESC to clear, ENTER to confirm)\n";
    string typed = "";
    while (true) {
        cout << "\r" << string(80, ' ') << "\r";   // clear the line
        cout << "> " << typed << flush;

        int ch = _getch();

        if (ch == '\r' || ch == '\n') break;                  // Enter -> confirm
        if (ch == 27) { typed = ""; continue; }                // Esc -> clear, keep typing
        if (ch == 127 || ch == 8) {                            // Backspace
            popUTF8Char(typed);                                 // removes one whole
                                                                 // character, emoji included
        } else if (isprint(ch) || ch == ' ' || (unsigned char)ch >= 0x80) {
            typed += (char)ch;                                  // covers ASCII AND every
                                                                 // byte of a UTF-8 emoji
        }
    }
    cout << "\n";
    return trim(typed);
}

// ---------------------------------------------------------------------
//  Live "type-a-letter-see-suggestions" search box
// ---------------------------------------------------------------------
void liveSuggestSearch(PhoneBook &book) {
    cout << "\n--- Live Search (type letters, BACKSPACE to erase, ENTER to finish, ESC to cancel) ---\n";
    string typed = "";
    while (true) {
        cout << "\r" << string(80, ' ') << "\r";   // clear line
        cout << "Search: " << typed << flush;

        int ch = _getch();

        if (ch == '\r' || ch == '\n') break;                 // Enter
        if (ch == 27) { typed = ""; cout << "\nCancelled.\n"; return; } // Esc
        if (ch == 127 || ch == 8) {                           // Backspace
            popUTF8Char(typed);                                // removes one whole
                                                                 // character, even if
                                                                 // it's a multi-byte emoji
        } else if (isprint(ch) || ch == ' ' || (unsigned char)ch >= 0x80) {
            // isprint(ch) covers normal ASCII letters/digits/punctuation.
            // (unsigned char)ch >= 0x80 covers every byte of a UTF-8
            // multi-byte sequence (emoji, accented letters, etc.) --
            // those bytes are NOT "printable" in the C locale that
            // isprint() checks against, so without this they'd be
            // silently dropped and emoji could never be typed here.
            typed += (char)ch;
        }

        if (!typed.empty()) {
            vector<string> suggestions = book.smartSearch(typed);
            cout << "\n";
            if (suggestions.empty()) {
                cout << "  (no matches)";
            } else {
                cout << "  Suggestions: ";
                for (size_t i = 0; i < suggestions.size() && i < 8; i++) {
                    cout << suggestions[i];
                    if (i + 1 < suggestions.size() && i + 1 < 8) cout << ", ";
                }
            }
            cout << "\033[F";   // move cursor back up one line (ANSI)
        }
    }
    cout << "\n";

    if (typed.empty()) return;
    vector<string> matches = book.smartSearch(typed);
    if (matches.empty()) { cout << "No contact found starting with \"" << typed << "\".\n"; return; }

    cout << "\nMatches:\n";
    for (size_t i = 0; i < matches.size(); i++)
        cout << "  " << (i + 1) << ". " << matches[i] << "\n";

    string choice = readLine("Enter full name to view details (or press Enter to skip): ");
    if (choice.empty()) return;
    Contact* c = book.getByName(choice);
    if (c) PhoneBook::printContact(*c);
    else cout << "Not found.\n";
}

// ---------------------------------------------------------------------
//  Resolve a (possibly partial) name typed by the user into a single
//  Contact, using the Trie to find every name that STARTS WITH what
//  was typed. This is the shared logic behind Search / Update / Delete
//  so half a name ("ami") is always enough to find "Amit Sharma".
// ---------------------------------------------------------------------
Contact* findContactInteractive(PhoneBook &book, const string &promptLabel) {
    string input = readLine(promptLabel);
    if (input.empty()) return nullptr;

    // 1) exact match first (fastest path, O(1) hash lookup)
    Contact* exact = book.getByName(input);
    if (exact) return exact;

    // 2) otherwise treat it as a prefix and ask the Trie for every
    //    name that starts with these letters
    vector<string> sug = book.smartSearch(input);
    if (sug.empty()) {
        cout << "No contact found starting with \"" << input << "\".\n";
        return nullptr;
    }
    if (sug.size() == 1) {
        cout << "Matched: " << sug[0] << "\n";
        return book.getByName(sug[0]);
    }

    // 3) multiple names share this prefix -> let the user pick one
    cout << "Multiple contacts start with \"" << input << "\":\n";
    for (size_t i = 0; i < sug.size(); i++)
        cout << "  " << (i + 1) << ". " << sug[i] << "\n";

    string choice = readLine("Enter the number, or type the full name (Enter to cancel): ");
    if (choice.empty()) return nullptr;

    bool isNumber = !choice.empty() &&
                    all_of(choice.begin(), choice.end(), [](unsigned char ch) { return isdigit(ch); });
    if (isNumber) {
        int idx = stoi(choice);
        if (idx >= 1 && idx <= (int)sug.size()) return book.getByName(sug[idx - 1]);
        cout << "Invalid selection.\n";
        return nullptr;
    }

    Contact* c = book.getByName(choice);
    if (!c) cout << "Not found.\n";
    return c;
}

// ---------------------------------------------------------------------
//  Menu-driven interface
// ---------------------------------------------------------------------
void showMenu() {
    cout << "\n====================== DIGITAL PHONEBOOK ======================\n";
    cout << " 1. Add Contact\n";
    cout << " 2. Live Search\n";
    cout << " 3. Search by Name \n";
    cout << " 4. Search by Phone Number\n";
    cout << " 5. Update Contact \n";
    cout << " 6. Delete Contact \n";
    cout << " 7. Display All Contacts\n";
    cout << " 8. Exit\n";
    cout << "=================================================================\n";
    cout << "Choice: ";
}

int main() {
    // Make the console interpret and print bytes as UTF-8, so emoji and
    // other multi-byte characters render correctly instead of showing
    // up as "?". On Linux/macOS the terminal is almost always UTF-8 by
    // default already, so this block only matters on Windows.
    // NOTE: this fixes the *encoding* problem. It can't fix a console
    // font that has no emoji glyphs at all -- if you're on classic
    // cmd.exe and still see boxes/"?" after this, switch to Windows
    // Terminal (ships with Windows 11, free in the Microsoft Store on
    // Windows 10), which renders emoji properly.
#if defined(_WIN32)
    SetConsoleOutputCP(CP_UTF8);
    SetConsoleCP(CP_UTF8);
#endif

    PhoneBook book;
    book.loadFromFile();

    cout << "Loaded " << book.count() << " contact(s) from " << DATA_FILE << "\n";

    int choice;
    while (true) {
        showMenu();
        if (!(cin >> choice)) {               // guard against non-numeric input
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cout << "Please enter a valid number.\n";
            continue;
        }
        cin.ignore(numeric_limits<streamsize>::max(), '\n');

        if (choice == 1) {
            // ---- ADD ---- only name is compulsory
            string name = liveTypedInput("Enter name:");
            if (name.empty()) { cout << "Name cannot be empty.\n"; continue; }
            if (book.exists(name)) { cout << "A contact with this name already exists.\n"; continue; }

            string phone = readValidPhone("Enter phone number: ", true);
            string email = readValidEmail("Enter email : ", true);
            string address = readLine("Enter address : ");

            Contact c;
            c.name = name;
            c.phone = phone.empty() ? "-" : phone;
            c.email = email.empty() ? "-" : email;
            c.address = address.empty() ? "-" : address;

            if (book.addContact(c)) cout << "Contact added and saved.\n";
            else cout << "Could not add contact (duplicate name or phone number).\n";
        }
        else if (choice == 2) {
            liveSuggestSearch(book);
        }
        else if (choice == 3) {
            Contact* c = findContactInteractive(book, "Enter name: ");
            if (c) PhoneBook::printContact(*c);
        }
        else if (choice == 4) {
            string phone = readLine("Enter phone number: ");
            Contact* c = book.getByPhone(phone);
            if (c) PhoneBook::printContact(*c);
            else cout << "No contact with this number.\n";
        }
        else if (choice == 5) {
            Contact* c = findContactInteractive(book, "Enter name of contact to update: ");
            if (!c) continue;
            string targetName = c->name;   // save before pointer is invalidated by updateContact()
            cout << "Leave a field blank to keep it unchanged.\n";
            string phone = readValidPhone("New phone: ", true);
            string email = readValidEmail("New email : ", true);
            string address = readLine("New address: ");
            book.updateContact(targetName, phone, email, address);
            cout << "Contact updated and saved.\n";
        }
        else if (choice == 6) {
            Contact* c = findContactInteractive(book, "Enter name of contact to delete: ");
            if (!c) continue;
            string targetName = c->name;
            string confirm = readLine("Delete \"" + targetName + "\"? (y/n): ");
            if (toLower(confirm) == "y" || toLower(confirm) == "yes") {
                if (book.deleteContact(targetName)) cout << "Contact deleted and saved.\n";
                else cout << "Contact not found.\n";
            } else {
                cout << "Deletion cancelled.\n";
            }
        }
        else if (choice == 7) {
            book.displayAll();
        }
        else if (choice == 8) {
            cout << "Goodbye! Your data is safely stored in " << DATA_FILE << "\n";
            break;
        }
        else {
            cout << "Invalid choice, try again.\n";
        }
    }
    return 0;
}