PyDS-A: Python Data Structures and Algorithms Library - Your go-to resource for essential data structures and algorithms, implemented in Python. Improve your coding skills and optimize your programs with this comprehensive collection.
# pyds_a/__init__.py

"""
PyDS-A: A Python Library for Data Structures and Algorithms

PyDS-A is a Python library that provides a collection of data structures and algorithms
to help you with various programming tasks.

Usage:
    - Import specific modules or classes from subpackages.
    - Access package-level variables and functions.

Example:
    To use the LinkedList class:
    >>> from pyds_a.data_structures.linked_list import LinkedList
    >>> linked_list = LinkedList()
    >>> linked_list.insert(42)
    >>> print(linked_list.size())

Package Contents:
    - data_structures: Subpackage containing various data structures.
    - algorithms: Subpackage containing algorithms.
    - PACKAGE_VERSION: The version of this PyDS-A package.
    - greet(): A function to provide a welcome message.

For more information and examples, visit the PyDS-A GitHub repository:
https://github.com/AIBauchi/PyDS-A
"""

# Import specific modules or classes from subpackages
from .data_structures.linked_list import LinkedList
from .algorithms.searching import binary_search
from .algorithms import *
from .data_structures import *

# Define package-level variables
PACKAGE_VERSION = "1.0.0"

# Define package-level function
def author():
    """Provide a welcome message for PyDS-A users.

    Returns:
        str: A welcome message.
    """
    return "Welcome to PyDS-A! an AIBauchi Initiative"

pyds_a/__init__.py
AIBauchi/PyDS-A
"""
Author: matt-wisdom

euclidean_algorithm.py - A Python implementation of the Euclidean Algorithm for 
finding the Greatest Common Divisor (GCD) of two numbers.

The Euclidean Algorithm is an efficient method for finding the GCD of two integers. 
It works by repeatedly applying the modulo operation until the remainder becomes zero. 
The GCD is the last non-zero remainder.

Resources used:
- https://en.wikipedia.org/wiki/Euclidean_algorithm

For doctests run the following command:
python3 -m doctest -v euclidean_algorithm.py

For manual testing run:
python3 euclidean_algorithm.py
"""


def gcd(a, b):
    """
    Find the Greatest Common Divisor (GCD) of two integers using the Euclidean Algorithm.

    Parameters:
        a (int): The first integer.
        b (int): The second integer.

    Returns:
        int: The GCD of the two integers.

    Examples:
    >>> gcd(48, 18)
    6

    >>> gcd(60, 48)
    12
    """
    while b:
        a, b = b, a % b
    return a


if __name__ == "__main__":
    import doctest

    doctest.testmod()

pyds_a/algorithms/numerical/euclidean_algorithm.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

binary_search.py - A Python implementation of the binary search algorithm.

This script provides a Python function for performing binary search in a sorted list or array.
The binary_search function takes a sorted list and a target value as input and returns the
index of the target value if found, or -1 if not found.
"""
from functools import lru_cache


@lru_cache
def binary_search(arr, target):
    """
    Perform binary search to find the target value in a sorted list.

    Args:
        arr (list): The sorted list to search within.
        target: The value to search for.

    Returns:
        int: The index of the target value if found, or -1 if not found.
    """
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

pyds_a/algorithms/searching/binary_search.py
AIBauchi/PyDS-A
"""
Author: Racso-3141


breadth_first_search.py - A Python implementation of the Breadth First
Search algorithm.


This script offers a pure Python implementation of the Breadth First
Search(BFS) algorithm. BFS is used for traversing or searching a graph
in level order. Specifically, the BFS algorithm ensures that all nodes
at the current depth are processed before moving to nodes at the next
depth level. A queue is employed as the primary data structure to
achieve this systematic traversal.


For doctests run the following command: python3 -m doctest -v
breadth_first_search.py


For manual testing run: python3 fibonacci_search.py
"""


from collections import deque


def breadth_first_search(graph: dict, start: int) -> list:
    """
    Implements the Breadth First Search (BFS) algorithm to traverse
    or search through a graph.


    Args:
    - graph (dict): The graph, represented as an adjacency list where keys are
    integers and values are lists of integers.
    - start (int): The starting node for the BFS traversal.


    Returns:
    - list: A list of nodes, representing the order of traversal by BFS.


    Examples:
    # Argument checks:
    >>> breadth_first_search(None, 1)
    Traceback (most recent call last):
    ...
    ValueError: The 'graph' argument must not be None.


    >>> breadth_first_search([], 1)
    Traceback (most recent call last):
    ...
    TypeError: Expected 'graph' type 'dict', but got 'list'


    >>> breadth_first_search({}, 1)
    Traceback (most recent call last):
    ...
    ValueError: The 'graph' argument must not be empty.


    >>> graph = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}
    >>> breadth_first_search(graph, '1')
    Traceback (most recent call last):
    ...
    TypeError: Expected 'start' type 'int', but got 'str'


    >>> breadth_first_search(graph, 7)
    Traceback (most recent call last):
    ...
    ValueError: The 'graph' does not contain 'start': 7.


    # BFS functionality:
    >>> breadth_first_search(graph, 1)
    [1, 2, 3, 4, 5]


    >>> graph2 = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
    >>> breadth_first_search(graph2, 1)
    [1, 2, 3]


    # Graph with loops:
    >>> graph3 = {1: [2, 3], 2: [1, 3, 4], 3: [1, 2], 4: [2]}
    >>> breadth_first_search(graph3, 1)
    [1, 2, 3, 4]


    # Graph with isolated nodes:
    >>> graph4 = {1: [2], 2: [1], 3: [], 4: []}
    >>> breadth_first_search(graph4, 1)
    [1, 2]
    """

    if graph is None:
        raise ValueError("The 'graph' argument must not be None.")
    if not isinstance(graph, dict):
        raise TypeError(
            f"Expected 'graph' type 'dict', but got '{type(graph).__name__}'"
        )
    if not graph:
        raise ValueError("The 'graph' argument must not be empty.")
    if not isinstance(start, int):
        raise TypeError(
            f"Expected 'start' type 'int', but got '{type(start).__name__}'"
        )
    if start not in graph:
        raise ValueError(f"The 'graph' does not contain 'start': {start}.")

    visited = set()
    visited.add(start)
    queue: deque[int] = deque()
    queue.append(start)

    bfs_result = []
    while len(queue):
        for _ in range(len(queue)):
            node = queue.popleft()
            bfs_result.append(node)
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    return bfs_result

pyds_a/algorithms/searching/breadth_first_search.py
AIBauchi/PyDS-A
"""
depth_first_search.py: A python implementation of the Depth First Search (DFS) algorithm that is 
used to traverse and search graph data structures which is realised using an adjacency list. 
DFS generates nodes and compares them with the goal along the largest depth of the graph.
It uses a stack to realise the recursion in keeping track of visited nodes and unvisited neighbours. 

Author: davutgl

"""
from typing import List

def is_stack_empty(stack: List) -> bool:
    """
    Checks if the stack is empty.
    
    Args:
        stack (List): Stack to be checked.
        
    Returns:
        bool: True if the stack is empty, False otherwise.
    """
    return len(stack) == 0

def get_node_neighbours(node: str) -> List[str]:
    """
    Retrieves the neighbors of a given node in the graph.
    
    Args:
        node (str): Node for which neighbors are to be retrieved.
        
    Returns:
        List[str]: List of neighbouring nodes.
    """
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    # Checks if the node exists in the graph, if not, returns an empty list
    return graph.get(node, [])

def depth_first_search(starting_node: str, goal_node: str) -> bool:
    """
    Perform Depth-First Search on a graph to find the goal node.
    
    Args:
        starting_node (str): Node to start the search from.
        goal_node (str): Node to be searched.
        
    Returns:
        bool: True if the goal node is found, False otherwise.
    """
    stack = [starting_node]
    while not is_stack_empty(stack):
        stack_top_element = stack.pop()
        if stack_top_element == goal_node:
            return True  # Goal node is found
        else:
            # Add the neighbours of the current node to the stack
            neighbours = get_node_neighbours(stack_top_element)
            stack.extend(neighbours)
    return False  # Goal node is not found

pyds_a/algorithms/searching/depth_first_search.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

fibonacci_search.py - A Python implementation of the Fibonacci search algorithm.

This script provides a pure Python implementation of the Fibonacci search algorithm
for searching an element in a sorted list or array. The Fibonacci search algorithm
uses Fibonacci numbers to divide the search space efficiently.

Resources used:
- https://en.wikipedia.org/wiki/Fibonacci_search_technique

For doctests run the following command:
python3 -m doctest -v fibonacci_search.py

For manual testing run:
python3 fibonacci_search.py
"""

from functools import lru_cache


@lru_cache
def fibonacci(k: int) -> int:
    """
    Finds the Fibonacci number at index k.

    Parameters:
        k (int): Index of the Fibonacci number to find.

    Returns:
        int: Fibonacci number at position k.

    Raises:
        TypeError: If k is not an integer.
        ValueError: If k is negative.

    Examples:
        >>> fibonacci(0)
        0
        >>> fibonacci(2)
        1
        >>> fibonacci(5)
        5
        >>> fibonacci(15)
        610
        >>> fibonacci('a')
        Traceback (most recent call last):
        TypeError: k must be an integer.
        >>> fibonacci(-5)
        Traceback (most recent call last):
        ValueError: k integer must be greater or equal to zero.
    """
    if not isinstance(k, int):
        raise TypeError("k must be an integer.")
    if k < 0:
        raise ValueError("k integer must be greater or equal to zero.")
    if k == 0:
        return 0
    elif k == 1:
        return 1
    else:
        return fibonacci(k - 1) + fibonacci(k - 2)


def fibonacci_search(arr: list, val: int) -> int:
    """
    A pure Python implementation of the Fibonacci search algorithm.

    Parameters:
        arr (list): List of sorted elements.
        val: Element to search in the list.

    Returns:
        int: The index of the element in the array, or -1 if not found.

    Examples:
        >>> fibonacci_search([4, 5, 6, 7], 4)
        0
        >>> fibonacci_search([4, 5, 6, 7], -10)
        -1
        >>> fibonacci_search([-18, 2], -18)
        0
        >>> fibonacci_search([5], 5)
        0
        >>> fibonacci_search(['a', 'c', 'd'], 'c')
        1
        >>> fibonacci_search(['a', 'c', 'd'], 'f')
        -1
        >>> fibonacci_search([], 1)
        -1
        >>> fibonacci_search([.1, .4 , 7], .4)
        1
        >>> fibonacci_search([], 9)
        -1
        >>> fibonacci_search(list(range(100)), 63)
        63
        >>> fibonacci_search(list(range(100)), 99)
        99
        >>> fibonacci_search(list(range(-100, 100, 3)), -97)
        1
        >>> fibonacci_search(list(range(-100, 100, 3)), 0)
        -1
        >>> fibonacci_search(list(range(-100, 100, 5)), 0)
        20
        >>> fibonacci_search(list(range(-100, 100, 5)), 95)
        39
    """
    len_list = len(arr)
    # Find m such that F_m >= n where F_i is the i-th Fibonacci number.
    i = 0
    while True:
        if fibonacci(i) >= len_list:
            fibb_k = i
            break
        i += 1
    offset = 0
    while fibb_k > 0:
        index_k = min(
            offset + fibonacci(fibb_k - 1), len_list - 1
        )  # Prevent out of range
        item_k_1 = arr[index_k]
        if item_k_1 == val:
            return index_k
        elif val < item_k_1:
            fibb_k -= 1
        elif val > item_k_1:
            offset += fibonacci(fibb_k - 1)
            fibb_k -= 2
        else:
            return -1


if __name__ == "__main__":
    import doctest

    doctest.testmod()

pyds_a/algorithms/searching/fibonacci_search.py
AIBauchi/PyDS-A
"""
Author: matt-wisdom

jump_search.py - A Python implementation of the Jump Search algorithm.

This script provides a pure Python implementation of the Jump Search algorithm, 
which is used to search for an element in a sorted list or array efficiently. 
The algorithm jumps through blocks of the list to reduce the number of elements 
that need to be checked compared to linear search.

Resources used:
- https://en.wikipedia.org/wiki/Jump_search

Usage:
1. Import the `jump_search` function.
2. Create a sorted list or array.
3. Call `jump_search(arr, target)` with the list or array and the target element
 to search for.

"""

import math


def jump_search(arr, target):
    """
    Finds the index of target in a sorted list using jump search algorithm.

    Parameters:
        arr (list): Sorted list of numbers to search.
        target (int): item to find

    Returns:
        int: Index of target in arr

    Examples:
        >>> arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
        >>> target = 11
        >>> result = jump_search(arr, target)
        >>> result
        5
        >>> target = 8
        >>> result = jump_search(arr, target)
        >>> result
        -1
    """
    n = len(arr)
    # Finding the jump size
    step = int(math.sqrt(n))
    prev = 0
    # Jump through the blocks
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        # If reached or gone beyond the end of the array, the target is not present
        if prev >= n:
            return -1
    while arr[prev] < target:
        prev += 1

        # If we've reached the next block or the end of the array,
        # the target is not present
        if prev == min(step, n):
            return -1
    # If the element is found, return its index
    if arr[prev] == target:
        return prev
    return -1


if __name__ == "__main__":
    import doctest

    doctest.testmod()

pyds_a/algorithms/searching/jump_search.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

linear_search.py - A Python implementation of the linear search algorithm.

This script provides a pure Python implementation of the linear search algorithm,
which is used to search for a target element in a given list or sequence.

For doctests, run the following command:
python3 -m doctest -v linear_search.py

For manual testing, run:
python3 linear_search.py
"""


def linear_search(sequence: list, target: int) -> int:
    """
    A pure Python implementation of a linear search algorithm.

    Args:
        sequence (list): A collection with comparable items (no sorting required).
        target (int): The item value to search for.

    Returns:
        int: The index of the found item or -1 if the item is not found.

    Examples:
        >>> linear_search([0, 5, 7, 10, 15], 0)
        0
        >>> linear_search([0, 5, 7, 10, 15], 15)
        4
        >>> linear_search([0, 5, 7, 10, 15], 5)
        1
        >>> linear_search([0, 5, 7, 10, 15], 6)
        -1
    """
    for index, item in enumerate(sequence):
        if item == target:
            return index
    return -1


def rec_linear_search(sequence: list, low: int, high: int, target: int) -> int:
    """
    A pure Python implementation of a recursive linear search algorithm.

    Args:
        sequence (list): A collection with comparable items (no sorting required).
        low (int): Lower bound of the search range.
        high (int): Upper bound of the search range.
        target (int): The element to be found.

    Returns:
        int: The index of the found key or -1 if the key is not found.

    Examples:
        >>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 0)
        0
        >>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 700)
        4
        >>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 30)
        1
        >>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, -6)
        -1
    """
    if not (0 <= high < len(sequence) and 0 <= low < len(sequence)):
        raise Exception("Invalid upper or lower bound!")
    if high < low:
        return -1
    if sequence[low] == target:
        return low
    if sequence[high] == target:
        return high
    return rec_linear_search(sequence, low + 1, high - 1, target)


if __name__ == "__main__":
    user_input = input("Enter numbers separated by comma:\n").strip()
    sequence = [int(item.strip()) for item in user_input.split(",")]

    target = int(input("Enter a single number to be found in the list:\n").strip())
    result = linear_search(sequence, target)
    if result != -1:
        print(f"linear_search({sequence}, {target}) = {result}")
    else:
        print(f"{target} was not found in {sequence}")

pyds_a/algorithms/searching/linear_search.py
AIBauchi/PyDS-A
#!/usr/bin/env python3
"""
    Author: Tinny-Robot
    module to operations with prime numbers
"""

import math


def is_prime(number: int) -> bool:
    """Checks to see if a number is a prime in O(sqrt(n)).

    A number is prime if it has exactly two factors: 1 and itself.

    >>> is_prime(0)
    False
    >>> is_prime(1)
    False
    >>> is_prime(2)
    True
    >>> is_prime(3)
    True
    >>> is_prime(27)
    False
    >>> is_prime(87)
    False
    >>> is_prime(563)
    True
    >>> is_prime(2999)
    True
    >>> is_prime(67483)
    False
    """

    # precondition
    assert isinstance(number, int) and (
        number >= 0
    ), "'number' must been an int and positive"

    if 1 < number < 4:
        # 2 and 3 are primes
        return True
    elif number < 2 or not number % 2:
        # Negatives, 0, 1 and all even numbers are not primes
        return False

    odd_numbers = range(3, int(math.sqrt(number) + 1), 2)
    return not any(not number % i for i in odd_numbers)


def next_prime(value, factor=1, **kwargs):
    value = factor * value
    first_value_val = value

    while not is_prime(value):
        value += 1 if not ("desc" in kwargs and kwargs["desc"] is True) else -1

    if value == first_value_val:
        return next_prime(value + 1, **kwargs)
    return value
pyds_a/algorithms/searching/prime_numbers.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

A Python implementation of the quick select algorithm, which is efficient for
calculating the value that would appear in the index of a list if it would be
sorted, even if it is not already sorted
https://en.wikipedia.org/wiki/Quickselect
"""
import random


def _partition(data: list, pivot) -> tuple:
    """
    Three way partition the data into smaller, equal and greater lists,
    in relationship to the pivot
    :param data: The data to be sorted (a list)
    :param pivot: The value to partition the data on
    :return: Three list: smaller, equal and greater
    """
    less, equal, greater = [], [], []
    for element in data:
        if element < pivot:
            less.append(element)
        elif element > pivot:
            greater.append(element)
        else:
            equal.append(element)
    return less, equal, greater


def quick_select(items: list, index: int):
    """
    >>> quick_select([2, 4, 5, 7, 899, 54, 32], 5)
    54
    >>> quick_select([2, 4, 5, 7, 899, 54, 32], 1)
    4
    >>> quick_select([5, 4, 3, 2], 2)
    4
    >>> quick_select([3, 5, 7, 10, 2, 12], 3)
    7
    """
    # index = len(items) // 2 when trying to find the median
    #   (value of index when items is sorted)

    # invalid input
    if index >= len(items) or index < 0:
        return None

    pivot = items[random.randint(0, len(items) - 1)]
    count = 0
    smaller, equal, larger = _partition(items, pivot)
    count = len(equal)
    lenght_of_smaller = len(smaller)

    # index is the pivot
    if lenght_of_smaller <= index < lenght_of_smaller + count:
        return pivot
    # must be in smaller
    elif lenght_of_smaller > index:
        return quick_select(smaller, index)
    # must be in larger
    else:
        return quick_select(larger, index - (lenght_of_smaller + count))

pyds_a/algorithms/searching/quick_select.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

bubble_sort.py - A Python implementation of the Bubble Sort algorithm for sorting lists.

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, 
compares adjacent elements, and swaps them if they are in the wrong order. 
The pass through the list is repeated until the list is sorted.

Resources used:
- https://en.wikipedia.org/wiki/Bubble_sort

For doctests run the following command:
python3 -m doctest -v bubble_sort.py

For manual testing run:
python3 bubble_sort.py
"""
from functools import lru_cache

@lru_cache
def bubble_sort(arr):
    """
    Sorts a list in ascending order using the Bubble Sort algorithm.

    Parameters:
        arr (list): The list to be sorted.

    Returns:
        list: The sorted list.

    Examples:
    >>> bubble_sort([64, 34, 25, 12, 22, 11, 90])
    [11, 12, 22, 25, 34, 64, 90]

    >>> bubble_sort([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    """
    number_of_elements = len(arr)
    for i in range(number_of_elements):
        # Flag to optimize the algorithm
        swapped = False

        # Last i elements are already sorted, so no need to compare them again
        for j in range(0, number_of_elements - i - 1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # If no two elements were swapped in the inner loop, the array is already sorted
        if not swapped:
            break

    return arr

if __name__ == "__main__":
    import doctest

    doctest.testmod()

pyds_a/algorithms/sorting/bubble_sort.py
AIBauchi/PyDS-A
"""
Author: Raghav Sharma (rghvsh)

bucket_sort.py - A Python implementation of the Bucket Sort algorithm for sorting lists.

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements
of an array into a number of buckets. Each bucket is then sorted individually, either using
a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

Resources used:
- https://en.wikipedia.org/wiki/Bucket_sort

For doctests run the following command:
- python -m doctest -v bucket_sort.py

For manual testing run:
- python bucket_sort.py -v
"""


def bucket_sort(array):
    """
           Sorts a list in ascending order using the Bucket Sort algorithm.

           Parameters:
               arr (list): The list to be sorted.
           Returns:
               list: The sorted list.

           Examples:
           >>> bucket_sort([64, 34, 25, 12, 22, 11, 90])
           [11, 12, 22, 25, 34, 64, 90]
           >>> bucket_sort([5, 4, 3, 2, 1])
           [1, 2, 3, 4, 5]
           >>> bucket_sort([2, 45, 21, 34, 67, 88, 64, 78])
           [2, 21, 34, 45, 64, 67, 78, 88]
           >>> bucket_sort([4, 7, 2, 5, 4, 6, 1, 78, 44, 56, 90, 87, 65])
           [1, 2, 4, 4, 5, 6, 7, 44, 56, 65, 78, 87, 90]

      """
    largest = max(array)
    length = len(array)
    size = largest / length

    buckets = [[] for i in range(length)]

    for i in range(length):
        index = int(array[i] / size)
        if index != length:
            buckets[index].append(array[i])
        else:
            buckets[length - 1].append(array[i])

    for i in range(len(array)):
        buckets[i] = sorted(buckets[i])

    result = []
    for i in range(length):
        result = result + buckets[i]

    return result


if __name__ == "__main__":
    import doctest

    doctest.testmod()

pyds_a/algorithms/sorting/bucket_sort.py
AIBauchi/PyDS-A
"""
Author: Avijit-Dey

insertion_sort.py - A Python implementation of the Insertion Sort algorithm for 
sorting lists.

Insertion sort is a simple sorting algorithm that builds the final 
sorted array (or list) one item at a time by comparisons.
Insertion sort iterates, consuming one input element each repetition, 
and grows a sorted output list. At each iteration, insertion sort removes
one element from the input data, finds the location it belongs within the 
sorted list, and inserts it there. It repeats until no input elements remain. 

Resources used:
--https://en.wikipedia.org/wiki/Insertion_sort

For doctests run the following command:
python3 -m doctest -v insertion_sort.py

For manual testing run:
python3 insertion_sort.py
"""


def insertion_sort(arr):
    """
    Sorts a list in ascending order using the Insertion Sort algorithm.

    Parameters:
        arr (list): The list to be sorted.

    Returns:
        list: The sorted list.

    This algorithm has quadratic time complexity & constant auxiliary space complexity.

    Examples:
    >>> insertion_sort([64, 34, 25, 12, 22, 11, 90])
    [11, 12, 22, 25, 34, 64, 90]

    >>> insertion_sort([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]

    >>> insertion_sort([6,5,3,1,8,7,2,4])
    [1, 2, 3, 4, 5, 6, 7, 8]

    """
    # Case when we have only one element in the array
    if (n := len(arr)) <= 1:
        return

    # Iterating the unsorted part (considering the first element to be sorted)
    for j in range(1, n):
        key = arr[j]
        i = j - 1

        # Performing checks with the first element of the unsorted part
        while i >= 0 and arr[i] > key:
            arr[i + 1] = arr[i]
            i -= 1
        # When above condition fails, the key is finally put in its rightful place
        arr[i + 1] = key

    return arr


if __name__ == "__main__":
    import doctest

    doctest.testmod()

pyds_a/algorithms/sorting/insertion_sort.py
AIBauchi/PyDS-A
"""
Author: Raghav Sharma (rghvsh)
merge_sort.py - A Python implementation of the Merge Sort algorithm for sorting lists.
Merge sort is a general purpose and comparison based algorithm
Conceptually, a merge sort works as follows:
Divide the unsorted list into n sublists, each containing one element
(a list of one element is considered sorted).Repeatedly merge sublists
to produce new sorted sublists until there is only one sublist remaining.
This will be the sorted list.
Resources used:
- https://en.wikipedia.org/wiki/Merge_sort
For doctests run the following command:
python -m doctest -v merge_sort.py
For manual testing run:
python merge_sort.py -v
"""

def merge_two_sorted_arrarys(a, b):
    """
         Merges the elements of two sorted arrays in such a way that the output array is in ascending order.
         Parameters:
             a (list): First sorted list to be merged.
             b (list): Second sorted list to be merged.
         Returns:
             list: The merged and sorted list.
         Examples:
         >>> merge_two_sorted_arrarys([1, 3, 7, 9],[2, 4, 6, 8])
         [1, 2, 3, 4, 6, 7, 8, 9]
         >>> merge_two_sorted_arrarys([11, 13, 14, 34],[7, 9, 12, 24])
         [7, 9, 11, 12, 13, 14, 24, 34]
    """
    array = []
    i = j = 0

    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            array.append(a[i])
            i = i + 1

        else:
            array.append(b[j])
            j = j+1

    while i < len(a):
        array.append(a[i])
        i = i+1

    while j < len(b):
        array.append(b[j])
        j = j + 1

    return array


def merge_sort(arr):
    """
         Sorts a list in ascending order using the Merge Sort algorithm.
         Parameters:
             arr (list): The list to be sorted.
         Returns:
             list: The sorted list.
         Examples:
         >>> merge_sort([64, 34, 25, 12, 22, 11, 90])
         [11, 12, 22, 25, 34, 64, 90]
         >>> merge_sort([5, 4, 3, 2, 1])
         [1, 2, 3, 4, 5]
    """

    if len(arr) <= 1:
        return arr

    mid = len(arr)//2
    left = arr[mid:]
    right = arr[:mid]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge_two_sorted_arrarys(left, right)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

pyds_a/algorithms/sorting/merge_sort.py
AIBauchi/PyDS-A
"""
Author: Rajat Gupta

quick_sort.py - A Python implementation of the Quick Sort algorithm for sorting lists.

Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array 
and partitioning the other elements into two sub-arrays, according to whether they are less than or 
greater than the pivot. For this reason, it is sometimes called partition-exchange sort. 
The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional 
amounts of memory to perform the sorting.

Resources used:
- https://en.wikipedia.org/wiki/Quicksort

For doctests run the following command:
python3 -m doctest -v quick_sort.py

For manual testing run:
python3 quick_sort.py
"""

def quick_sort(arr):
    """
    Sorts a list in ascending order using the Quick Sort algorithm.

    Parameters:
        arr (list): The list to be sorted.

    Returns:
        list: The sorted list.

    Examples:
    >>> quick_sort([64, 34, 25, 12, 22, 11, 90])
    [11, 12, 22, 25, 34, 64, 90]

    >>> quick_sort([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    """
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [var_x for var_x in arr if var_x < pivot]
    middle = [var_x for var_x in arr if var_x == pivot]
    right = [var_x for var_x in arr if var_x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

if __name__ == "__main__":
    import doctest

    doctest.testmod()
    

pyds_a/algorithms/sorting/quick_sort.py
AIBauchi/PyDS-A
# data_structures/__init__.py

# Import modules from the package
from .stack import Stack
from .queue import Queue
from .linked_list import LinkedList

pyds_a/data_structures/__init__.py
AIBauchi/PyDS-A
""" 
    Author: Tinny-Robot
    
    Implementation of Circular Queue (using Python lists)
"""

class CircularQueue:
    """Circular FIFO queue with a fixed capacity"""

    def __init__(self, n: int):
        self.n = n
        self.array = [None] * self.n
        self.front = 0  # index of the first element
        self.rear = 0
        self.size = 0

    def __len__(self) -> int:
        """
        >>> cq = CircularQueue(5)
        >>> len(cq)
        0
        >>> cq.enqueue("A")  # doctest: +ELLIPSIS
        <data_structures.queue.circular_queue.CircularQueue object at ...
        >>> len(cq)
        1
        """
        return self.size

    def is_empty(self) -> bool:
        """
        >>> cq = CircularQueue(5)
        >>> cq.is_empty()
        True
        >>> cq.enqueue("A").is_empty()
        False
        """
        return self.size == 0

    def first(self):
        """
        >>> cq = CircularQueue(5)
        >>> cq.first()
        False
        >>> cq.enqueue("A").first()
        'A'
        """
        return False if self.is_empty() else self.array[self.front]

    def enqueue(self, data):
        """
        This function insert an element in the queue using self.rear value as an index
        >>> cq = CircularQueue(5)
        >>> cq.enqueue("A")  # doctest: +ELLIPSIS
        <data_structures.queue.circular_queue.CircularQueue object at ...
        >>> (cq.size, cq.first())
        (1, 'A')
        >>> cq.enqueue("B")  # doctest: +ELLIPSIS
        <data_structures.queue.circular_queue.CircularQueue object at ...
        >>> (cq.size, cq.first())
        (2, 'A')
        """
        if self.size >= self.n:
            raise Exception("QUEUE IS FULL")

        self.array[self.rear] = data
        self.rear = (self.rear + 1) % self.n
        self.size += 1
        return self

    def dequeue(self):
        """
        This function removes an element from the queue using on self.front value as an
        index
        >>> cq = CircularQueue(5)
        >>> cq.dequeue()
        Traceback (most recent call last):
           ...
        Exception: UNDERFLOW
        >>> cq.enqueue("A").enqueue("B").dequeue()
        'A'
        >>> (cq.size, cq.first())
        (1, 'B')
        >>> cq.dequeue()
        'B'
        >>> cq.dequeue()
        Traceback (most recent call last):
           ...
        Exception: UNDERFLOW
        """
        if self.size == 0:
            raise Exception("UNDERFLOW")

        temp = self.array[self.front]
        self.array[self.front] = None
        self.front = (self.front + 1) % self.n
        self.size -= 1
        return temp
pyds_a/data_structures/circular_queue.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

This module defines a simple singly linked list data structure with basic operations like
adding nodes, removing nodes, searching for a specific value, and displaying the list's contents.
"""


class Node:
    """
    Represents a node in a singly linked list.

    Attributes:
        data: The data stored in the node.
        next: Reference to the next node in the linked list.
    """

    def __init__(self, data):
        """
        Initialize a new Node with the given data.

        Args:
            data: The data to be stored in the node.
        """
        self.data = data
        self.next = None

    def get_data(self):
        """
        Get the data stored in the node.

        Returns:
            The data stored in the node.
        """
        return self.data

    def set_data(self, data):
        """
        Set the data in the node to a new value.

        Args:
            data: The new data value to be stored in the node.
        """
        self.data = data


class LinkedList:
    """
    Represents a singly linked list data structure.

    The LinkedList class provides basic operations for working with a linked list,
    including appending and prepending nodes, deleting nodes by value, searching for values,
    and displaying the list's contents.

    Attributes:
        head (Node): A reference to the head (first node) of the linked list.

    Methods:
        is_empty(): Check if the linked list is empty.
        append(data): Append a new node with the given data to the end of the linked list.
        prepend(data): Prepend a new node with the given data to the beginning of the linked list.
        delete(data): Delete the first occurrence of a node with the given data from the linked list.
        search(data): Search for a node with the given data in the linked list.
        display(): Display the contents of the linked list.
    """

    def __init__(self):
        """
        Initialize an empty linked list.
        """
        self.head = None

    def is_empty(self):
        """
        Check if the linked list is empty.

        Returns:
            bool: True if the linked list is empty, False otherwise.
        """
        return self.head is None

    def append(self, data):
        """
        Append a new node with the given data to the end of the linked list.

        Args:
            data: The data to be added to the linked list.
        """
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def prepend(self, data):
        """
        Prepend a new node with the given data to the beginning of the linked list.

        Args:
            data: The data to be added to the linked list.
        """
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def size(self):
        """Get the number of elements in the linked list.

        Returns:
            int: The number of elements in the linked list.
        """
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

    def insert(self, data):
        """Insert a new element with the given data at the end of the list.

        Args:
            data: The data to be inserted.
        """
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def search(self, data):
        """Search for an element with the specified data in the list.

        Args:
            data: The data to search for.

        Returns:
            bool: True if the data is found, False otherwise.
        """
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False

    def delete(self, data):
        """Delete the first occurrence of an element with the specified data.

        Args:
            data: The data to delete.
        """
        if self.head is None:
            return

        if self.head.data == data:
            self.head = self.head.next
            return

        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    def get_list(self):
        """Get a list containing all elements in the linked list.

        Returns:
            list: A list of elements in the linked list.
        """
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return result

    def clear(self):
        """Clear the linked list by setting the head to None."""
        self.head = None

    def display(self):
        """
        Display the contents of the linked list.
        """
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

pyds_a/data_structures/linked_list.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

queue.py - A Python implementation of a queue data structure.

This file contains the implementation of a queue data structure using a list.
A queue follows the First-In-First-Out (FIFO) principle, where the first element added
to the queue is the first one to be removed.

The Queue class provides methods for adding items to the end of the queue, removing items
from the front of the queue, checking if the queue is empty, and getting the current size
of the queue.

Usage:
    from queue import Queue

    my_queue = Queue()
    my_queue.enqueue(1)
    my_queue.enqueue(2)
    item = my_queue.dequeue()
    size = my_queue.size()

"""


class Queue:
    """
    Represents a queue data structure implemented using a list.

    A queue follows the First-In-First-Out (FIFO) principle, where the first element added
    to the queue is the first one to be removed.

    Methods:
        enqueue(item): Add an item to the end of the queue.
        dequeue(): Remove and return the item from the front of the queue.
        is_empty(): Check if the queue is empty.
        size(): Get the current size of the queue.
    """

    def __init__(self):
        """
        Initialize an empty queue.
        """
        self.items = []

    def enqueue(self, item):
        """
        Add an item to the end of the queue.

        Args:
            item: The item to be added to the queue.
        """
        self.items.append(item)

    def dequeue(self):
        """
        Remove and return the item from the front of the queue.

        Returns:
            The item removed from the front of the queue.
        """
        if not self.is_empty():
            return self.items.pop(0)
        else:
            raise IndexError("Queue is empty")

    def is_empty(self):
        """
        Check if the queue is empty.

        Returns:
            bool: True if the queue is empty, False otherwise.
        """
        return len(self.items) == 0

    def size(self):
        """
        Get the current size of the queue.

        Returns:
            int: The number of items in the queue.
        """
        return len(self.items)

pyds_a/data_structures/queue.py
AIBauchi/PyDS-A
"""
Author: Racso-3141

This module defines a singly linked list data structure with basic operations 
like adding nodes, removing nodes, searching for a specific value, and displaying the 
list's contents.
"""


class Node:
    """
    Represents a node in a singly linked list.

    Attributes:
        data: The data stored in the node.
        next: Reference to the next node in the singly linked list.
    """

    def __init__(self, data):
        """
        Initialize a new Node with the given data.

        Args:
            data: The data to be stored in the node.
        """
        self.data = data
        self.next = None


class SinglyLinkedList:
    """
    Represents a singly linked list data structure.

    The SinglyLinkedList class provides basic operations for working with a linked list,
    including appending and prepending nodes, deleting nodes by value, searching for
    values, and displaying the list's contents.

    Attributes:
        head (Node): A reference to the head (first node) of the singly linked list.
        tail (Node): A reference to the tail (last node) of the singly linked list.
        size (int) : Number of nodes in the singly linked list.

    Methods:
        is_empty(): Check whether the singly linked list is empty.
        append(data): Add a new node with the given data to the end.
        prepend(data): Add a new node with the given data to the start.
        find_first(data): Find the first node with the given data.
        find_all(data): Find all nodes containing the given data.
        delete_first(data): Delete the first node with the given data.
        delete_all(data): Delete all nodes with the given data.
        get_list(): Get a list of all nodes in order.
        clear(): Clear the singly linked list by setting the head to None, tail to None,
        size to 0.
        display(): Print all nodes in a string.

    """

    def __init__(self):
        """
        Initialize an empty linked list.
        """
        self.head = None
        self.tail = None
        self.size = 0

    def is_empty(self):
        """
        Check whether the singly linked list is empty.

        Returns:
            bool: True if the singly linked list is empty, False otherwise.

        >>> l = SinglyLinkedList()
        >>> l.is_empty()
        True
        >>> l.append(1)
        >>> l.is_empty()
        False
        """
        return self.size == 0

    def append(self, data):
        """
        Add a new node with the given data to the end.

        Args:
            data: The data of the new node.

        >>> l = SinglyLinkedList()
        >>> l.append(1)
        >>> l.head.data
        1
        >>> l.tail.data
        1
        >>> l.size
        1
        >>> l.get_list()
        [1]
        >>> l.append(2)
        >>> l.head.data
        1
        >>> l.tail.data
        2
        >>> l.size
        2
        >>> l.get_list()
        [1, 2]
        >>> l.append(3)
        >>> l.head.data
        1
        >>> l.tail.data
        3
        >>> l.size
        3
        >>> l.get_list()
        [1, 2, 3]
        """
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def prepend(self, data):
        """
        Add a new node with the given data to the start.

        Args:
            data: The data of the new node.

        >>> l = SinglyLinkedList()
        >>> l.prepend(1)
        >>> l.head.data
        1
        >>> l.tail.data
        1
        >>> l.size
        1
        >>> l.get_list()
        [1]
        >>> l.prepend(2)
        >>> l.head.data
        2
        >>> l.tail.data
        1
        >>> l.size
        2
        >>> l.get_list()
        [2, 1]
        >>> l.prepend(3)
        >>> l.head.data
        3
        >>> l.tail.data
        1
        >>> l.size
        3
        >>> l.get_list()
        [3, 2, 1]
        """
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self.size += 1

    def find_first(self, data):
        """
        Find the first node with the given data.

        Args:
            data: Data of the node to be found.

        Returns:
            The first node that contains the provided data else None.

        >>> l = SinglyLinkedList()
        >>> l.append(1)
        >>> l.append(2)
        >>> l.append(3)
        >>> node = l.find_first(2)
        >>> node.data
        2
        >>> print(l.find_first(4))
        None
        """
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return None

    def find_all(self, data):
        """
        Find all nodes containing the given data.

        Args:
            data: Data of nodes to be found.

        Returns:
            list: A list of nodes containing the provided data if found else
            an empty list.

        >>> l = SinglyLinkedList()
        >>> l.append(1)
        >>> l.append(2)
        >>> l.append(2)
        >>> l.append(3)
        >>> nodes = l.find_all(2)
        >>> [node.data for node in nodes]
        [2, 2]
        >>> l.find_all(4)
        []
        """
        nodes_data = []
        current = self.head
        while current:
            if current.data == data:
                nodes_data.append(current)
            current = current.next
        return nodes_data

    def delete_first(self, data):
        """
        Delete the first node with the given data.

        Args:
            data: Data of the node to be deleted.

        >>> l = SinglyLinkedList()
        >>> l.append(1)
        >>> l.append(2)
        >>> l.append(1)
        >>> l.delete_first(1)
        >>> l.head.data
        2
        >>> l.tail.data
        1
        >>> l.size
        2
        >>> l.get_list()
        [2, 1]
        >>> l.delete_first(1)
        >>> l.head.data
        2
        >>> l.tail.data
        2
        >>> l.size
        1
        >>> l.get_list()
        [2]
        >>> l.delete_first(3)
        >>> l.head.data
        2
        >>> l.tail.data
        2
        >>> l.size
        1
        >>> l.get_list()
        [2]
        >>> l.delete_first(2)
        >>> l.head is None
        True
        >>> l.tail is None
        True
        >>> l.size
        0
        >>> l.get_list()
        []
        """
        if self.is_empty():
            return

        dm = Node(None)
        dm.next = self.head
        prev = dm

        while prev.next:
            if prev.next.data == data:
                prev.next = prev.next.next
                self.size -= 1
                break
            prev = prev.next

        self.head = dm.next
        if self.size == 0:
            self.head = None
            self.tail = None
        elif not prev.next:
            self.tail = prev

    def delete_all(self, data):
        """
        Delete all nodes with the given data.

        Args:
            data: Data of nodes to be deleted.

        >>> l = SinglyLinkedList()
        >>> l.append(2)
        >>> l.append(2)
        >>> l.append(3)
        >>> l.append(2)
        >>> l.delete_all(2)
        >>> l.head.data
        3
        >>> l.tail.data
        3
        >>> l.size
        1
        >>> l.get_list()
        [3]
        >>> l.delete_all(3)
        >>> l.head is None
        True
        >>> l.tail is None
        True
        >>> l.size
        0
        >>> l.get_list()
        []
        """
        if self.is_empty():
            return

        dm = Node(None)
        dm.next = self.head
        prev = dm

        while prev.next:
            if prev.next.data == data:
                prev.next = prev.next.next
                self.size -= 1
                continue
            prev = prev.next

        self.head = dm.next
        if self.size == 0:
            self.head = None
            self.tail = None
        else:
            self.tail = prev

    def get_list(self):
        """
        Get a list of all nodes in order.

         Returns:
             A list of all nodes in the singly linked list.

         >>> l = SinglyLinkedList()
         >>> l.append(1)
         >>> l.append(2)
         >>> l.get_list()
         [1, 2]
        """
        list = []
        current = self.head
        while current:
            list.append(current.data)
            current = current.next
        return list

    def clear(self):
        """
        Clear the singly linked list by setting the head to None, tail to None,
        size to 0.

        >>> l = SinglyLinkedList()
        >>> l.append(1)
        >>> l.clear()
        >>> l.head is None
        True
        >>> l.tail is None
        True
        >>> l.size == 0
        True
        """
        self.head = None
        self.tail = None
        self.size = 0

    def display(self):
        """
        Print all nodes of the singly linked list in a string.

        >>> l = SinglyLinkedList()
        >>> l.display()
        None
        >>> l.append(1)
        >>> l.display()
        1 -> None
        >>> l.append(2)
        >>> l.display()
        1 -> 2 -> None
        """
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

pyds_a/data_structures/singly_linked_list.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

Based on "Skip Lists: A Probabilistic Alternative to Balanced Trees" by William Pugh
https://epaperpress.com/sortsearch/download/skiplist.pdf
"""
import random


class SkipListNode:
    """
    SkipListNode represents a node in the SkipList.

    Attributes:
        value: The value stored in the node.
        forward: A list of references to the forward nodes at different levels.
    """
    def __init__(self, value, level=0):
        """
        Initialize a SkipListNode.

        Args:
            value: The value to store in the node.
            level: The level of the node in the SkipList.
        """
        self.value = value
        self.forward = [None] * (level + 1)

class SkipList:
    """
    SkipList is a data structure for efficient search, insertion, and deletion in a sorted sequence.

    Attributes:
        head: The head node of the SkipList.
        level: The maximum level of the SkipList.
    """
    def __init__(self):
        """
        Initialize an empty SkipList.
        """
        self.head = SkipListNode(None, 0)
        self.level = 0

    def random_level(self):
        """
        Generate a random level for a new SkipListNode.

        Returns:
            int: The random level.
        """
        level = 0
        while random.random() < 0.5 and level < self.level + 1:
            level += 1
        return level

    def insert(self, value):
        """
        Insert a value into the SkipList.

        Args:
            value: The value to insert.
        """
        update = [None] * (self.level + 1)
        node = self.head

        for i in range(self.level, -1, -1):
            while node.forward[i] is not None and node.forward[i].value < value:
                node = node.forward[i]
            update[i] = node

        level = self.random_level()
        if level > self.level:
            for i in range(self.level + 1, level + 1):
                update.append(self.head)
            self.level = level

        new_node = SkipListNode(value, level)
        for i in range(level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, value):
        """
        Search for a value in the SkipList.

        Args:
            value: The value to search for.

        Returns:
            bool: True if the value is found, False otherwise.
        """
        node = self.head

        for i in range(self.level, -1, -1):
            while node.forward[i] is not None and node.forward[i].value < value:
                node = node.forward[i]

        if node.forward[0] is not None and node.forward[0].value == value:
            return True
        return False

    def delete(self, value):
        """
        Delete a value from the SkipList.

        Args:
            value: The value to delete.

        Returns:
            bool: True if the value is deleted, False if not found.
        """
        update = [None] * (self.level + 1)
        node = self.head

        for i in range(self.level, -1, -1):
            while node.forward[i] is not None and node.forward[i].value < value:
                node = node.forward[i]
            update[i] = node

        if node.forward[0] is not None and node.forward[0].value == value:
            for i in range(self.level + 1):
                if update[i].forward[i] != node.forward[i]:
                    break
                update[i].forward[i] = node.forward[i]

            while self.level > 0 and self.head.forward[self.level] is None:
                self.level -= 1

            return True
        return False

    def display(self):
        """
        Display the SkipList.
        """
        for level in range(self.level, -1, -1):
            node = self.head.forward[level]
            values = []
            while node is not None:
                values.append(node.value)
                node = node.forward[level]
            print(f"Level {level}: {values}")

# Example usage:
if __name__ == "__main__":
    skip_list = SkipList()
    elements = [3, 6, 9, 2, 7, 5, 8, 1, 4]

    for element in elements:
        skip_list.insert(element)

    skip_list.display()

    search_value = 7
    if skip_list.search(search_value):
        print(f"{search_value} found in the skip list.")
    else:
        print(f"{search_value} not found in the skip list.")

    delete_value = 5
    if skip_list.delete(delete_value):
        print(f"{delete_value} deleted from the skip list.")
    else:
        print(f"{delete_value} not found in the skip list.")

    skip_list.display()

pyds_a/data_structures/skip_list.py
AIBauchi/PyDS-A
"""
Author: Tinny-Robot

stack.py - A Python implementation of a stack data structure.

This file contains the implementation of a stack data structure using a list.
A stack follows the Last-In-First-Out (LIFO) principle, where the last element added
to the stack is the first one to be removed.

The Stack class provides methods for adding items to the top of the stack, removing items
from the top of the stack, checking if the stack is empty, getting the current size
of the stack, and peeking at the item on the top of the stack without removing it.

"""


class Stack:
    """
    Represents a stack data structure implemented using a list.

    A stack follows the Last-In-First-Out (LIFO) principle, where the last element added
    to the stack is the first one to be removed.

    Methods:
        push(item): Add an item to the top of the stack.
        pop(): Remove and return the item from the top of the stack.
        is_empty(): Check if the stack is empty.
        size(): Get the current size of the stack.
        peek(): Return the item at the top of the stack without removing it.
    """

    def __init__(self):
        """
        Initialize an empty stack.
        """
        self.items = []

    def push(self, item):
        """
        Add an item to the top of the stack.

        Args:
            item: The item to be added to the stack.
        """
        self.items.append(item)

    def pop(self):
        """
        Remove and return the item from the top of the stack.

        Returns:
            The item removed from the top of the stack.
        """
        try:
            return self.items.pop()
        except IndexError as exc:
            raise IndexError("Stack is empty") from exc

    def is_empty(self):
        """
        Check if the stack is empty.

        Returns:
            bool: True if the stack is empty, False otherwise.
        """
        return len(self.items) == 0

    def size(self):
        """
        Get the current size of the stack.

        Returns:
            int: The number of items in the stack.
        """
        return len(self.items)

    def peek(self):
        """
        Return the item at the top of the stack without removing it.

        Returns:
            The item at the top of the stack.
        """

        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("Stack is empty")

pyds_a/data_structures/stack.py
AIBauchi/PyDS-A
from setuptools import setup, find_packages

# Package metadata
NAME = "PyDS-A"
VERSION = "1.0.0"
DESCRIPTION = "A collection of data structures and algorithms in Python."
AUTHOR = "Tinny-Robot"
EMAIL = "handanfoun@gmail.com"
URL = "https://github.com/AIBauchi/PyDS-A"
LICENSE = "MIT"
CLASSIFIERS = [
    "License :: OSI Approved :: MIT License",
    "Programming Language :: Python :: 3",
    "Programming Language :: Python :: 3.10",
    "Programming Language :: Python :: 3.11",
    "Topic :: Software Development :: Libraries",
]

# Package dependencies
INSTALL_REQUIRES = []

# Package setup
setup(
    name=NAME,
    version=VERSION,
    description=DESCRIPTION,
    author=AUTHOR,
    author_email=EMAIL,
    url=URL,
    license=LICENSE,
    classifiers=CLASSIFIERS,
    packages=find_packages(),
    install_requires=INSTALL_REQUIRES,
)

setup.py
AIBauchi/PyDS-A
# pylint: disable=missing-function-docstring

import pytest
from pyds_a.data_structures.linked_list import (
    LinkedList,
)  # Import your LinkedList implementation


def test_empty_linked_list():
    test_list = LinkedList()
    assert test_list.is_empty() is True
    assert test_list.size() == 0


def test_linked_list_insert():
    test_list = LinkedList()
    test_list.insert(1)
    assert test_list.size() == 1
    assert test_list.search(1) is True


def test_linked_list_delete():
    test_list = LinkedList()
    test_list.insert(1)
    test_list.insert(2)
    test_list.delete(1)
    assert test_list.size() == 1
    assert test_list.search(1) is False
    assert test_list.search(2) is True


def test_linked_list_get_list():
    test_list = LinkedList()
    test_list.insert(1)
    test_list.insert(2)
    test_list.insert(3)
    assert test_list.get_list() == [1, 2, 3]


def test_linked_list_clear():
    test_list = LinkedList()
    test_list.insert(1)
    test_list.insert(2)
    test_list.clear()
    assert test_list.size() == 0
    assert test_list.is_empty() is True
    assert test_list.search(1) is False
    assert test_list.search(2) is False


if __name__ == "__main__":
    pytest.main()

test/test_data_structures/test_linked_list.py
AIBauchi/PyDS-A