Phone Directory Implementation in C++

Here we are going to make our own C++ program to make a phone directory. So what is a phone directory and how to create it? A phone directory is a collection of data, which consists of names of people and their phone numbers. To create a phone directory, we will use a data structure trie. Its search complexity is equal to that of the key length. The nodes of trie contain alphabets and these nodes are connected to further tries thus they form a tree. When a word is finished, we mark it as finished in a trie as shown in the diagram. 

C++ Program to create phone directory

#include <bits/stdc++.h>
using namespace std;
// global declaration of contact list
string contactList[] = {"phantom" , "phone","phul"};

struct TrieNode
{
    // every trie Node contains a Map 'child'
    // in which each alphabet points to another trie node
    unordered_map<char,TrieNode*> child;

    // 'lastLetter' is true if the node represents
    // end of a contact
    bool lastLetter   ;

    // Constructor
    TrieNode()
    {
        // Initializing all nodes as null
        for (char i = 'a'; i <= 'z'; i++)
            child[i] = NULL;

        lastLetter = false;
    }
};

// Making root NULL for ease so that it doesn't
// have to be passed to all functions.
TrieNode *root = NULL;

// Add contacts int trie node
void AddContact(string s)
{
    int length = s.length();

    // 'head' is used to iterate the Trie Nodes
    TrieNode *head = root;
    for (int i = 0; i < length; i++)
    {
        // Check if the s[i] is already present in
        // Trie
        TrieNode *nextNode = head->child[s[i]];
        if (nextNode == NULL)
        {
            // If not found then create a new TrieNode
            nextNode = new TrieNode();

            // Insert into the Map
            head->child[s[i]] = nextNode;
        }

        // Move the head, to point to next
        // Trie Node
        head = nextNode;

        // If its the last character of the string 's'
        // then mark 'lastLetter' as true
        if (i == length - 1)
            head->lastLetter = true;
    }
}

// This function simply displays all contacts in
//phone directory.
// teaverse current node. String 'pre'
// stands for string corelating to the path from
// root to currentNode.
void showContactsTil(TrieNode *currentNode, string pre)
{
    // Checking if string 'pre' ends here
    // If yes then display the string till now
    if (currentNode->lastLetter)
        cout << pre << endl;

    // Find the Nodes adjecent to the current
    // Node and then recursively call the function

   for (char i = 'a'; i <= 'z'; i++)
    {
        TrieNode *next = currentNode->child[i];
        if (next != NULL)
            showContactsTil(next, pre + (char)i);
    }
}

   //this function show contacts
    //as user inputs a letter, for example
    //if user inputs "phu" then first it will show
    //all contacts starting from p then from ph
    //and finally from phu if no contact is present
    //then is will tell no result is found.
void showContacts(string str)
{
    TrieNode *previousNode = root;

    string pre = "";
    int length = str.length();

    // Display the contact List for string formed
    // after entering every character
    int i;
    for (i=0; i<length; i++)
    {
        // 'pre' stores the string formed so far
        pre += (char)str[i];

        // Get the last character entered
        char lastChar = pre[i];

        // Find the Node corelating to the last
        // character of 'pre' which is pointed by
        // prevNode of the Trie
        TrieNode *currentNode = previousNode->child[lastChar];

        // If nothing found, then break the loop as
        // no more prefixes are going to be present.
        if (currentNode == NULL)
        {
            cout << "No result found "<<" " << pre
                 << endl;
            i++;
            break;
        }

  
        cout << "Suggesions for" <<" "<< pre<<" "
             << "are "<< endl;
        showContactsTil(currentNode, pre);

        // Change prevNode for next pre
        previousNode = currentNode;
    }

   
    for (; i<length; i++)
    {
        pre += (char)str[i];
        cout << "no contact found for"<<" " << pre
             << endl;
    }
}

// Insert all the Contacts into the Trie
void insertInDirectory(string contacts[],int n)
{
    // Initialize root Node
    root = new TrieNode();

    // Insert each contact into the trie
    for (int i = 0; i < n; i++)
        AddContact(contacts[i]);
}


int main()
{

    // Size of the Contact List
    int n = sizeof(contactList)/sizeof(string);


    insertInDirectory(contactList, n);

    string Search = "phum";


    showContacts(Search);

    return 0;
}

function implementation

1. InsertInDirectory 
   this function names in the phone directory 
2. AddContact 
   this function adds the contact to directory 
3. showContacts 
   this function displays contact letter by letter suppose user gives an input “p” it will show all contacts starting from “p“if the user then gives input as u then it will show all contacts starting from “pu”.
4. showContactsTil 
   this function displays all contacts from the phone directory starting from a pedicular prefix. 

Implementation 

To add contacts, we have made a global string array in which we can add contacts. Then we have called a function “InsertInDirectory” this function runs a loop and adds one string at a time from the array to the phone directory by calling the function “AddContact”. To search a contact, we have created a search string, the program will be going to search then, this string in phone directory letter by letter and going to display all the contacts letter by letter, as explained above. 

 To search we will call the function showContacts this will first check if there is a contact present starting from the 1st letter of the search string if yes then it will call showContactsTil, this function will show all the contacts starting from the letter.  

For example-:
let’s assume the phone directory has two contacts {Ram, Raghav} and the search string is {Rishabh}.
So “showContact” first will check if there are any contacts starting from “R” if yes (as in our case) then it will call “showContactsTil” and this function will show all the contacts staring form “R”. Then “showContact” will check is there any contact which starts from “Ri”, as there is no contact starting from “Ri” thus it will return no contacts are found. 

Output

Noe it’s time to run our code. Below is the result that we will see after running our code:

Suggestions based on p are
phantom
phone
phul
Suggestions based on ph are
phantom
phone
phul
Suggestions based on phu are
phul
No contact Found for phum