sublist_search.cpp File Reference

Implementation of the Sublist Search Algorithm More...

#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for sublist_search.cpp:

Classes
struct	search::sublist_search::Node
	A Node structure representing a single link Node in a linked list. More...
class	TestCases
	class encapsulating the necessary test cases More...

Namespaces
namespace	search
	for std::vector
namespace	sublist_search
	Functions for the Sublist Search implementation.

Functions
void	search::sublist_search::printLinkedList (Node *start)
	A simple function to print the linked list.
Node *	search::sublist_search::makeLinkedList (const std::vector< uint64_t > &data)
	Give a vector of data, it adds each element of vector in the linked list and return the address of head pointer.
void	search::sublist_search::deleteList (Node *const root)
bool	search::sublist_search::sublistSearch (Node *sublist, Node *mainList)
	Main searching function.
static void	test ()
	Self-test implementations.
int	main (int argc, char *argv[])
	Main function.

Detailed Description

Implementation of the Sublist Search Algorithm

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

Function Documentation

deleteList()

void search::sublist_search::deleteList

(

Node *const

root

)

                                  {
    if (root != NULL) {
        deleteList(root->next);
        delete root;
    }
}

main()

int main	(	int	argc,
		char *	argv[] )

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

< Main list in which sublist is to be searched

< Sublist to be searched

< Main list in which sublist is to be searched

< boolean to check if the sublist exists or not

                                 {
    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;
}

Here is the call graph for this function:

makeLinkedList()

Node * search::sublist_search::makeLinkedList

(

const std::vector< uint64_t > &

data

)

Give a vector of data, it adds each element of vector in the linked list and return the address of head pointer.

Parameters

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.

This is used in test cases for rapidly creating linked list with 100+ elements, instead of hard-coding 100 elements in test cases.

                                                      {
    /// 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;
}

Here is the call graph for this function:

printLinkedList()

void search::sublist_search::printLinkedList

(

Node *

start

)

A simple function to print the linked list.

Parameters

start

The head of the linked list

Returns

void

                                  {
    while (start != nullptr) {
        std::cout << "->" << start->data;
        start = start->next;
    }
    std::cout << std::endl;
}

Here is the call graph for this function:

sublistSearch()

bool search::sublist_search::sublistSearch	(	Node *	sublist,
		Node *	mainList )

Main searching function.

Parameters

sublist	A linked list which is supposed to be searched in mainList.
mainList	A linked list in which sublist will be searched.

Returns

true if the sublist is found

false if the sublist is NOT found

Initialize target pointer to the head node of sublist.

Initialize main pointer to the current node of main list.

If the data of target node and main node is equal then move to the next node of both lists.

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.

set the target pointer again to stating point of target list.

set the main pointer to the next element of the main list and repeat the algo.

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

                                                  {
    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;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    TestCases tc;
    tc.runTests();
}

Here is the call graph for this function: