sublist_search.cpp

/**
 * @file
 * @brief Implementation of the [Sublist Search
 * Algorithm](https://www.geeksforgeeks.org/sublist-search-search-a-linked-list-in-another-list)
 * @details
 *
 * ### Algorithm
 *
 *  * Sublist search is used to detect a presence of one list in another list.
 *  * Suppose we have a single-node list (let's say the first list), and we
 *  want to ensure that the list is present in another list (let's say the
 * second list), then we can perform the sublist search to find it.
 *
 *  * For instance, the first list contains these elements: 23 -> 30 -> 41,
 *  and the second list contains these elements: 10 -> 15 -> 23 -> 30 -> 41
 *  -> 49. At a glance, we see that the first list presents in the second list.
 *
 * ### Working
 *
 *  * The sublist search algorithm works by comparing the first element
 *  of the first list with the first element of the second list.
 *  * If the two values don't match, it goes to the next element of the
 *  second list. It does this until the two values match.
 *
 * @author [Nitin Sharma](https://github.com/foo290)
 */

#include <cassert>   /// for assert
#include <cstdint>
#include <iostream>  /// for IO operations
#include <vector>    /// for std::vector

/**
 * @namespace search
 * @brief Searching algorithms
 */
namespace search {
/**
 * @namespace sublist_search
 * @brief Functions for the [Sublist
 * Search](https://www.geeksforgeeks.org/sublist-search-search-a-linked-list-in-another-list)
 * implementation
 */
namespace sublist_search {
/**
 * @brief A Node structure representing a single link Node in a linked list
 */
struct Node {
    uint32_t data = 0;  ///< the key/value of the node
    Node *next{};       ///< pointer to the next node
};

/**
 * @brief A simple function to print the linked list
 * @param start The head of the linked list
 * @returns void
 */
void printLinkedList(Node *start) {
    while (start != nullptr) {
        std::cout << "->" << start->data;
        start = start->next;
    }
    std::cout << std::endl;
}

/**
 * @brief Give a vector of data,
 * it adds each element of vector in the linked list and return the address of
 * head pointer.
 * @param data A vector of "int" containing the data that is supposed to be
 * stored in nodes of linked list.
 * @returns Node* A head pointer to the linked list.
 */
Node *makeLinkedList(const std::vector<uint64_t> &data) {
    /// This is used in test cases for rapidly creating linked list with 100+
    /// elements, instead of hard-coding 100 elements in test cases.
    Node *head = nullptr;
    Node *tail = nullptr;
    for (int i : data) {
        Node *node = new Node;
        node->data = i;
        node->next = nullptr;
        if (head == nullptr) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = tail->next;
        }
    }
    return head;
}

/*
 * @brief This function dealocates memory related to the given list
 * It recursively deletes all of the nodes of the input list.
 * @param room the root/head of the input list
 * @warning Plese note that the memory for each node has to be alocated using
 * new.
 */
void deleteList(Node *const root) {
    if (root != NULL) {
        deleteList(root->next);
        delete root;
    }
}

/**
 * @brief Main searching function
 * @param sublist A linked list which is supposed to be searched in mainList.
 * @param mainList A linked list in which sublist will be searched.
 * @returns true if the sublist is found
 * @returns false if the sublist is NOT found
 */
bool sublistSearch(Node *sublist, Node *mainList) {
    if (sublist == nullptr || mainList == nullptr) {
        return false;
    }

    /// Initialize target pointer to the head node of sublist.
    Node *target_ptr = sublist;

    while (mainList != nullptr) {
        /// Initialize main pointer to the current node of main list.
        Node *main_ptr = mainList;

        while (target_ptr != nullptr) {
            if (main_ptr == nullptr) {
                return false;

            } else if (main_ptr->data == target_ptr->data) {
                /// If the data of target node and main node is equal then move
                /// to the next node of both lists.
                target_ptr = target_ptr->next;
                main_ptr = main_ptr->next;

            } else {
                break;
            }
        }

        if (target_ptr == nullptr) {
            /// Is target pointer becomes null that means the target list is
            /// been traversed without returning false. Which means the sublist
            /// has been found and return ture.
            return true;
        }

        /// set the target pointer again to stating point of target list.
        target_ptr = sublist;

        /// set the main pointer to the next element of the main list and repeat
        /// the algo.
        mainList = mainList->next;
    }

    /// If the main list is exhausted, means sublist does not found, return
    /// false
    return false;
}

}  // namespace sublist_search
}  // namespace search

/**
 * @brief class encapsulating the necessary test cases
 */
class TestCases {
 private:
    /**
     * @brief A function to print given message on console.
     * @tparam T Type of the given message.
     * @returns void
     * */
    template <typename T>
    void log(T msg) {
        // It's just to avoid writing cout and endl
        std::cout << "[TESTS] : ---> " << msg << std::endl;
    }

 public:
    /**
     * @brief Executes test cases
     * @returns void
     * */
    void runTests() {
        log("Running Tests...");

        testCase_1();
        testCase_2();
        testCase_3();

        log("Test Cases over!");
        std::cout << std::endl;
    }

    /**
     * @brief A test case contains edge case, Only contains one element.
     * @returns void
     * */
    void testCase_1() {
        const bool expectedOutput = true;  ///< Expected output of this test

        log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
            "~");
        log("This is test case 1 for sublist search Algorithm : ");
        log("Description:");
        log("   EDGE CASE : Only contains one element");

        std::vector<uint64_t> sublistData = {
            6};  ///< Data to make linked list which will be the sublist
        std::vector<uint64_t> mainlistData = {
            2, 5, 6, 7,
            8};  ///< Data to make linked list which will be the main list

        search::sublist_search::Node *sublistLL =
            search::sublist_search::makeLinkedList(
                sublistData);  ///< Sublist to be searched
        search::sublist_search::Node *mainlistLL =
            search::sublist_search::makeLinkedList(
                mainlistData);  ///< Main list in which sublist is to be
                                ///< searched

        bool exists = search::sublist_search::sublistSearch(
            sublistLL, mainlistLL);  ///< boolean, if sublist exist or not

        log("Checking assert expression...");
        assert(exists == expectedOutput);
        log("Assertion check passed!");

        log("[PASS] : TEST CASE 1 PASS!");
        log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
            "~");

        deleteList(mainlistLL);
        deleteList(sublistLL);
    }

    /**
     * @brief A test case which contains main list of 100 elements and sublist
     * of 20.
     * @returns void
     * */
    void testCase_2() {
        const bool expectedOutput = true;  /// Expected output of this test

        log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
            "~");
        log("This is test case 2 for sublist search Algorithm : ");
        log("Description:");
        log("   contains main list of 100 elements and sublist of 20");

        std::vector<uint64_t> sublistData(
            20);  ///< Data to make linked list which will be the sublist
        std::vector<uint64_t> mainlistData(
            100);  ///< Main list in which sublist is to be searched

        for (int i = 0; i < 100; i++) {
            /// Inserts 100 elements in main list
            mainlistData[i] = i + 1;
        }

        int temp = 0;
        for (int i = 45; i < 65; i++) {
            /// Inserts 20 elements in sublist
            sublistData[temp] = i + 1;
            temp++;
        }

        search::sublist_search::Node *sublistLL =
            search::sublist_search::makeLinkedList(
                sublistData);  ///< Sublist to be searched
        search::sublist_search::Node *mainlistLL =
            search::sublist_search::makeLinkedList(
                mainlistData);  ///< Main list in which sublist is to be
                                ///< searched

        bool exists = search::sublist_search::sublistSearch(
            sublistLL, mainlistLL);  ///< boolean, if sublist exist or not

        log("Checking assert expression...");
        assert(exists == expectedOutput);
        log("Assertion check passed!");

        log("[PASS] : TEST CASE 2 PASS!");
        log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
            "~");

        deleteList(mainlistLL);
        deleteList(sublistLL);
    }

    /**
     * @brief A test case which contains main list of 50 elements and sublist
     * of 20.
     * @returns void
     * */
    void testCase_3() {
        const bool expectedOutput = false;  ///< Expected output of this test

        log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
            "~");
        log("This is test case 3 for sublist search Algorithm : ");
        log("Description:");
        log("   contains main list of 50 elements and sublist of 20");

        std::vector<uint64_t> sublistData(20);  ///< Sublist to be searched
        std::vector<uint64_t> mainlistData(
            50);  ///< Main list in which sublist is to be searched

        for (int i = 0; i < 50; i++) {
            /// Inserts 100 elements in main list
            mainlistData.push_back(i + 1);
        }

        for (int i = 45; i < 65; i++) {
            /// Inserts 20 elements in sublist
            sublistData.push_back(i + 1);
        }

        search::sublist_search::Node *sublistLL =
            search::sublist_search::makeLinkedList(
                sublistData);  ///< Sublist to be searched
        search::sublist_search::Node *mainlistLL =
            search::sublist_search::makeLinkedList(
                mainlistData);  ///< Main list in which sublist is to be
                                ///< searched

        bool exists = search::sublist_search::sublistSearch(
            sublistLL, mainlistLL);  ///< boolean, if sublist exist or not

        log("Checking assert expression...");
        assert(exists == expectedOutput);
        log("Assertion check passed!");

        log("[PASS] : TEST CASE 3 PASS!");
        log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
            "~");

        deleteList(mainlistLL);
        deleteList(sublistLL);
    }
};

/**
 * @brief Self-test implementations
 * @returns void
 */
static void test() {
    TestCases tc;
    tc.runTests();
}

/**
 * @brief Main function
 * @param argc commandline argument count (ignored)
 * @param argv commandline array of arguments (ignored)
 * @returns 0 on exit
 */
int main(int argc, char *argv[]) {
    test();  // run self-test implementations

    std::vector<uint64_t> mainlistData = {
        2, 5, 6, 7, 8};  ///< Main list in which sublist is to be searched
    std::vector<uint64_t> sublistData = {6, 8};  ///< Sublist to be searched

    search::sublist_search::Node *mainlistLL =
        search::sublist_search::makeLinkedList(mainlistData);
    search::sublist_search::Node *sublistLL =
        search::sublist_search::makeLinkedList(
            sublistData);  ///< Main list in which sublist is to be
                           ///< searched

    bool exists = search::sublist_search::sublistSearch(
        sublistLL,
        mainlistLL);  ///< boolean to check if the sublist exists or not

    std::cout << "Sublist: " << std::endl;
    search::sublist_search::printLinkedList(sublistLL);

    std::cout << "Main list: " << std::endl;
    search::sublist_search::printLinkedList(mainlistLL);
    std::cout << std::endl;

    if (exists) {
        std::cout << "[TRUE] - sublist found in main list\n";
    } else {
        std::cout << "[FALSE] - sublist NOT found in main list\n";
    }

    deleteList(mainlistLL);
    deleteList(sublistLL);
    return 0;
}