list_array.cpp

/**
 * @file
 * @brief [Dynamic Array](https://en.wikipedia.org/wiki/Dynamic_array)
 *
 * @details
 * The list_array is the implementation of list represented using array.
 * We can perform basic CRUD operations as well as other operations like sorting
 * etc.
 *
 * ### Algorithm
 * It implements various method like insert, sort, search etc. efficiently.
 * You can select the operation and methods will do the rest work for you.
 * You can insert element, sort them in order, search efficiently, delete values
 * and print the list.
 */

#include <array>     /// for std::array
#include <cassert>   /// for assert
#include <cstdint>
#include <iostream>  /// for io operations

/**
 * @namespace data_structures
 * @brief Algorithms with data structures
 */
namespace data_structures {
/**
 * @namespace list_array
 * @brief Functions for [Dynamic
 * Array](https://en.wikipedia.org/wiki/Dynamic_array) algorithm
 */
namespace list_array {
/**
 * @brief Structure of List with supporting methods.
 */
template <uint64_t N>
struct list {
    std::array<uint64_t, N> data{};  // Array that implement list
    uint64_t top = 0;                // Pointer to the last element
    bool isSorted = false;           // indicator whether list is sorted or not
    /**
     * @brief Search an element in the list using binarySearch.
     * @param dataArr list
     * @param first pointer to the first element in the remaining list
     * @param last pointer to the last element in the remaining list
     * @param val element that will be searched
     * @return index of element in the list if present else -1
     */
    uint64_t BinarySearch(const std::array<uint64_t, N> &dataArr,
                          const uint64_t &first, const uint64_t &last,
                          const uint64_t &val) {
        // 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;
    }

    /**
     * @brief Search an element using linear search
     * @param dataArr list
     * @param val element that will be searched
     * @return index of element in the list if present else -1
     */
    uint64_t LinearSearch(const std::array<uint64_t, N> &dataArr,
                          const uint64_t &val) const {
        // 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;
    }

    /*
     * @brief Parent function of binarySearch and linearSearch methods
     * @param val element that will be searched
     * @return index of element in the list if present else -1
     */
    uint64_t search(const uint64_t &val) {
        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;
    }

    /**
     * @brief Sort the list
     * @returns void
     */
    void sort() {
        // 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;
    }

    /**
     * @brief Insert the new element in the list
     * @param val element that will be inserted
     * @returns void
     */
    void insert(const uint64_t &val) {
        // 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
        }
    }

    /**
     * @brief To remove the element from the list
     * @param val element that will be removed
     * @returns void
     */
    void remove(const uint64_t &val) {
        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
    }

    /**
     * @brief Utility function to print array
     * @returns void
     */
    void show() {
        // 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
        }
    }
};  // structure list
}  // namespace list_array
}  // namespace data_structures

/**
 * @brief Test implementations
 * @returns void
 */
static void test() {
    data_structures::list_array::list<50> L;

    // Insert testing
    L.insert(11);
    L.insert(12);
    assert(L.top == 2);
    L.insert(15);
    L.insert(10);
    L.insert(12);
    L.insert(20);
    L.insert(18);
    assert(L.top == 7);
    L.show();  // To print the array

    // Remove testing
    L.remove(12);  // Remove Duplicate value in the list
    L.remove(15);  // Remove the existing value in the list
    assert(L.top == 5);
    L.remove(50);  // Try to remove the non-existing value in the list
    assert(L.top == 5);

    // LinearSearch testing
    assert(L.search(11) == 0);  // search for the existing element
    assert(L.search(12) == 2);
    assert(L.search(50) == -1);  // search for the non-existing element

    // Sort testing
    L.sort();
    assert(L.isSorted == true);
    L.show();

    // BinarySearch testing
    assert(L.search(11) == 1);  // search for the existing element
    assert(L.search(12) == 2);
    assert(L.search(50) == -1);  // search for the non-existing element
}

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    test();  // Execute the tests
    return 0;
}