basicAlgs.py

"""
Python code to do sometihng that we can easily break

Most of it will be classic Algorithms.
"""

import logging

def bubblesort(theList):
    """

    The Classic Bubble sort.

    Iterate through the list, looking at each pair of items.
    If the left hand side of the pair is larger than the right hand side
    swap them.

    This means that after the first iteration, the largest item is at
    the end of the list.
    
    We then repeat the process, shifting the second largest item to the correct place.
    Then continue till all items are sorted.

    See:

    https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm

    
    @param theList:  Initial List (or iterable)
    @return: A sorted version of the list

    """
    #Outer Loop 
    for outer in range(len(theList)):
        # Inner Loop, 
    for inner in range(len(theList)-1):
            #Get the values
            rightItem = theList[inner+1]
            leftItem = theList[inner]

            #Do the Comparison
            if leftItem > rightItem:
                #Swap
                theList[inner] = leftItem
                theList[inner] = rightItem

        logging.debug("Iteration {0} List is {1}".format(outer, theList))
                
    return theList


def binarySearch(theList, value):
    """
    The Classic Binary Search Algorithm

    This will take a *SORTED* list, and search it for a given 
    value.

    We use an iterative approach here, because recursive might be 
    confusing (even though its actually a lot easier to code).

    @param theList: Sorted list to search
    @param value: Value to search for
    @return Index of item in the List
    """

    bottom = 0
    top = len(theList)
    #while True:
    #for x in range(5):
    while (top - bottom) >= 1:
        # Find the Middle of the Array
        middle = bottom + (top - bottom) // 2
        #middle = bottom + top // 2
        logging.debug("Binary Search Bottom %d Top %d  Middle (%d)", bottom, top, middle)

        # Get the item at this index
        item = theList[middle]
        logging.debug("--> Item is %d", item)
        logging.debug("--> Searching Array {0}".format(theList[bottom:top]))
        if item == value:
            #If we have found the Item
            return middle
        elif item > value:
            # The Value at the Midpoint is Greater than our value
            # We need to look in the bottom half
            logging.debug("Use Bottom Half")
            top = middle# + 1
        elif item < value:
            # The Value at the Midpoint is Less than our Value
            # We need to look in the Top half
            logging.debug("Use Top Half")
            bottom = middle + 1
            
    

def searcher(theList, theValue):
    """
    Take a user specified list and search it for
    a value

    @param theList: List of items to check
    @param theValue: Value to look for

    @return: Index of item if it exists
    """
    theList = bubblesort(theList)
    hasItem = binarySearch(theList, theValue)
    return hasItem


def convertValues(rawValues, rawSearch):
    """
    Convert text based user input into integer arrays
    and values

    @param rawValues:  A user supplied comma sepeated string
    @param rawSearch: User supplied text integer

    @return list, value converted to integers
    """

    #And process into numbers
    values = [int(x) for x in rawValues.split(",")]
    logging.debug("Values are {0}".format(values))

    searchValue = int(rawSearch)
    logging.debug("Searching for {0}".format(searchValue))

    return values, searchValue

            
if __name__ == "__main__":
    """
    Main Function
    """
    #You can change this to debug to see the debugging messages
    logging.basicConfig(level=logging.INFO)
    #logging.basicConfig(level=logging.DEBUG)

    print("==== COPY THE BELOW INTO THE REPORT  =====")
    print("---- Sanity Check 1 -----")
    values = [1,2,3,4,5,6,7,8,9,10]
    out = searcher(values, 3)
    print(out)


    print("---- Sanity Check  2-----")
    values = [7,6,5,4,3,2,1]
    out = searcher(values, 3)
    print(out)