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.
uint64_t	LinearSearch (const std::array< uint64_t, N > &dataArr, const uint64_t &val) const
	Search an element using linear search.
uint64_t	search (const uint64_t &val)
void	sort ()
	Sort the list.
void	insert (const uint64_t &val)
	Insert the new element in the list.
void	remove (const uint64_t &val)
	To remove the element from the list.
void	show ()
	Utility function to print array.

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.

Definition at line 37 of file list_array.cpp.

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

Definition at line 49 of file list_array.cpp.

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

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

Definition at line 143 of file list_array.cpp.

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

Definition at line 80 of file list_array.cpp.

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

Definition at line 183 of file list_array.cpp.

                                     {
        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

Definition at line 97 of file list_array.cpp.

                                         {
        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

Definition at line 203 of file list_array.cpp.

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

Definition at line 121 of file list_array.cpp.

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

Member Data Documentation

data

template<uint64_t N>

std::array<uint64_t, N> data_structures::list_array::list< N >::data {}

Definition at line 38 of file list_array.cpp.

{};  // Array that implement list

isSorted

template<uint64_t N>

bool data_structures::list_array::list< N >::isSorted = false

Definition at line 40 of file list_array.cpp.

top

template<uint64_t N>

uint64_t data_structures::list_array::list< N >::top = 0

Definition at line 39 of file list_array.cpp.

---

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

• data_structures/list_array.cpp