RoutingTable.cpp

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

struct TrieNode
{
    char bit;
    TrieNode *left;  // represents bit 0
    TrieNode *right; // represents bit 1;
    bool isEndOfIP = false;
    int nextHopId;
};
class RoutingTable
{
private:
    string convertToBinary(string destIp)
    {
        // assuming 32-bit ip Address
        string binary;
        string temp;
        int length = destIp.length();
        string ipPart;
        int num = 0;
        int a = 0;
        int count = 0;
        while (count < 4 && a <= destIp.length())
        {
            while (a < destIp.length() && destIp[a] != '.')
            {
                ipPart += destIp[a]; // seperating numbers by '.'
                a++;
            }
            count++;
            for (size_t j = 0; j < ipPart.length(); j++)
            {
                num = num + (ipPart[j] - 48) * pow(10, ipPart.length() - 1 - j); // converting string number into int e.g. "198" to 198
            }
            while (num > 0)
            {
                int rem = num % 2;
                num = num / 2;
                temp += '0' + rem; // reversed binary number
            }
            while (temp.length() < 8)
            {
                temp += '0';
            }
            for (int i = 0; i < temp.length(); i++)
            {
                binary += temp[temp.length() - 1 - i]; // forward binary number
            }
            a++; // to skip the "."
            num = 0;
            temp = "";
            ipPart = "";
        }
        return binary;
    }

public:
    TrieNode *root;
    int routerId;
    RoutingTable()
    {
        root = new TrieNode();
        root->bit = '#'; // dummy root node
        root->left = NULL;
        root->right = NULL;
        root->isEndOfIP = false;
        root->nextHopId = -1;
    }
    void insert(string ip, int next_id)
    {
        TrieNode *curr = root;
        string ipAddr = convertToBinary(ip);
        int len = ipAddr.length();
        char ch;
        for (size_t i = 0; i < len; i++)
        {
            // every node in trie contains 2 possible pointers, '1' or '0'
            // the next bit of the ipAddr again could be '1' or '0' and so on.
            ch = ipAddr[i];
            if (ch == '0')
            {
                if (curr->left == NULL)
                {
                    TrieNode *node = new TrieNode();
                    node->bit = ch;
                    curr->left = node;
                }
                curr = curr->left;
            }
            else
            {
                if (curr->right == NULL)
                {
                    TrieNode *node = new TrieNode();
                    node->bit = ch;
                    curr->right = node;
                }
                curr = curr->right;
            }
        }
        curr->nextHopId = next_id;
        // this implies that there is a string ending at current Node
        curr->isEndOfIP = true;
    }
    int searchTrie(string destIp)
    {
        TrieNode *curr = root;
        string ipAddr = convertToBinary(destIp);
        int len = ipAddr.length();
        int nextHop = -1; // shows the corresponding next hop routerId of the longest prefix match
        char ch;
        for (size_t i = 0; i < len; i++)
        {
            ch = ipAddr[i];
            if (curr->isEndOfIP == true) // if end is reached, means we get the longest prefix match
            {
                nextHop = curr->nextHopId;
            }
            // Check if the node exist for the current character in the Trie
            if (ch == '0')
            {
                if (curr->left == NULL)
                {
                    break; // if
                }
                curr = curr->left;
            }
            else
            {
                if (curr->right == NULL)
                {
                    break; // if not found in trie
                }
                curr = curr->right;
            }
        }
        return nextHop; // next Hop router Id is returned
    }
    void displayTrie(TrieNode *curr, string prefix)
    {
        if (curr == NULL)
            return;

        // Only add current bit if it's 0 or 1 (not root node)
        if (curr->bit == '0' || curr->bit == '1')
        {
            prefix += curr->bit;
        }

        if (curr->isEndOfIP)
        {
            cout << "Binary Prefix: " << prefix << ", Next Hop: " << curr->nextHopId << endl;
        }

        displayTrie(curr->left, prefix);
        displayTrie(curr->right, prefix);
    }
};
int main(int argc, char const *argv[])
{
    string ip;
    int nextHop;
    RoutingTable *table = new RoutingTable();
    for (int i = 0; i < 2; i++)
    {
        cout << "Enter ip address: ";
        cin >> ip;
        cout << "Enter next Hop: ";
        cin >> nextHop;
        table->insert(ip, nextHop);
    }
    table->displayTrie(table->root, "");
    return 0;
}