data_structures::list_array::list< N > Struct Template Reference

Structure of List with supporting methods. More...

Collaboration diagram for data_structures::list_array::list< N >:

Public Member Functions
uint64_t	BinarySearch (const std::array< uint64_t, N > &dataArr, const uint64_t &first, const uint64_t &last, const uint64_t &val)
	Search an element in the list using binarySearch. More...
uint64_t	LinearSearch (const std::array< uint64_t, N > &dataArr, const uint64_t &val) const
	Search an element using linear search. More...
uint64_t	search (const uint64_t &val)
void	sort ()
	Sort the list. More...
void	insert (const uint64_t &val)
	Insert the new element in the list. More...
void	remove (const uint64_t &val)
	To remove the element from the list. More...
void	show ()
	Utility function to print array. More...

Public Attributes
std::array< uint64_t, N >	data {}
uint64_t	top = 0
bool	isSorted = false

Detailed Description

template<uint64_t N>
struct data_structures::list_array::list< N >

Structure of List with supporting methods.

Member Function Documentation

BinarySearch()

template<uint64_t N>

uint64_t data_structures::list_array::list< N >::BinarySearch ( const std::array< uint64_t, N > &  dataArr, const uint64_t &  first, const uint64_t &  last, const uint64_t &  val  )

inline

Search an element in the list using binarySearch.

Parameters

dataArr	list
first	pointer to the first element in the remaining list
last	pointer to the last element in the remaining list
val	element that will be searched

Returns

index of element in the list if present else -1

                                                   {
            // If both pointer cross each other means no element present in the list which is equal to the val
            if (last < first) {
                return -1;
            }
            uint64_t mid = (first + last) / 2;
            // check whether current mid pointer value is equal to element or not
            if (dataArr[mid] == val)
                return mid;
                // if current mid value is greater than  element we have to search in first half
            else if (val < dataArr[mid])
                return (BinarySearch(dataArr, first, mid - 1, val));
                // if current mid value is greater than  element we have to search in second half
            else if (val > dataArr[mid])
                return (BinarySearch(dataArr, mid + 1, last, val));
 
            std::cerr << __func__ << ":" << __LINE__ << ": Undefined condition\n";
            return -1;
        }

Here is the call graph for this function:

insert()

template<uint64_t N>

void data_structures::list_array::list< N >::insert ( const uint64_t &  val )

inline

Insert the new element in the list.

Parameters

val	element that will be inserted

Returns

void

                                         {
            // overflow check
            if (top == N) {
                std::cout << "\nOverflow";
                return;
            }
            // if list is not sorted, insert at the last
            // otherwise place it to correct position
            if (!isSorted) {
                data[top] = val;
                top++;
            } else {
                uint64_t pos = 0; // Initialize the index variable
                // Going through each element and find correct position for element
                for (uint64_t i = 0; i < top - 1; i++) {
                    // check for the correct position
                    if (data[i] <= val && val <= data[i + 1]) {
                        pos = i + 1; // assign correct pos to the index var
                        break; // to get out from the loop
                    }
                }
                // if all elements are smaller than the element
                if (pos == 0) {
                    pos = top - 1;
                }
                // shift all element to make a room for new element
                for (uint64_t i = top; i > pos; i--) {
                    data[i] = data[i - 1];
                }
                top++; // Increment the value of top.
                data[pos] = val; // Assign the value to the correct index in the array
            }
        }

LinearSearch()

template<uint64_t N>

uint64_t data_structures::list_array::list< N >::LinearSearch ( const std::array< uint64_t, N > &  dataArr, const uint64_t &  val  ) const

inline

Search an element using linear search.

Parameters

dataArr	list
val	element that will be searched

Returns

index of element in the list if present else -1

                                                                                               {
            // Going through each element in the list
            for (uint64_t i = 0; i < top; i++) {
                if (dataArr[i] == val) {
                    return i; // element found at ith index
                }
            }
            // element is not present in the list
            return -1;
        }

remove()

template<uint64_t N>

void data_structures::list_array::list< N >::remove ( const uint64_t &  val )

inline

To remove the element from the list.

Parameters

val	element that will be removed

Returns

void

                                         {
            uint64_t pos = search(val); // search the index of the value
            // if search returns -1, element does not present in the list
            if (pos == -1) {
                std::cout << "\n Element does not present in the list ";
                return;
            }
            std::cout << "\n" << data[pos] << " deleted"; // print the appropriate message
            // shift all the element 1 left to fill vacant space
            for (uint64_t i = pos; i < top; i++) {
                data[i] = data[i + 1];
            }
            top--; // decrement the top variable to maintain last index
        }

search()

template<uint64_t N>

uint64_t data_structures::list_array::list< N >::search ( const uint64_t &  val )

inline

                                             {
            uint64_t pos; // pos variable to store index value of element.
            // if list is sorted, binary search works efficiently else linear search is the only option
            if (isSorted) {
                pos = BinarySearch(data, 0, top - 1, val);
            } else {
                pos = LinearSearch(data, val);
            }
            // if index is equal to -1 means element does not present
            // else print the index of that element
            if (pos != -1) {
                std::cout << "\nElement found at position : " << pos;
            } else {
                std::cout << "\nElement not found";
            }
            // return the index of element or -1.
            return pos;
        }

show()

template<uint64_t N>

void data_structures::list_array::list< N >::show ( )

inline

Utility function to print array.

Returns

void

                    {
            // Going through each element in the list
            std::cout << '\n';
            for (uint64_t i = 0; i < top; i++) {
                std::cout << data[i] << " "; // print the element
            }
        }

sort()

template<uint64_t N>

void data_structures::list_array::list< N >::sort ( )

inline

Sort the list.

Returns

void

                    {
            //Going through each element in the list
            for (uint64_t i = 0; i < top; i++) {
                uint64_t min_idx = i; // Initialize the min variable
                for (uint64_t j = i + 1; j < top; j++) {
                    // check whether any element less than current min value
                    if (data[j] < data[min_idx]) {
                        min_idx = j; // update index accordingly
                    }
                }
                // swap min value and element at the ith index
                std::swap(data[min_idx], data[i]);
            }
            // mark isSorted variable as true
            isSorted = true;
        }

Here is the call graph for this function:

---

The documentation for this struct was generated from the following file:

• data_structures/list_array.cpp