#search.py
#demo various aspects of searching

from random import randint

size = 100
list1 = []
for i in range(size):
    list1.append(randint(1,size*10))
print("Unsorted list of numbers:")
print(list1)

inp = input("count&index and 'in': Enter a number to search for: ")
if inp != "":
    search_item = int(inp)
    #could do:  Easiest/shortest to code but most inefficient
    if list1.count(search_item) > 0:   #count() needs to look at all items in the list.
        print("Found it at",list1.index(search_item)) # #comparisons is all items
    else:
        print("Not found")   # #comparisons is all items
    if search_item in list1:   #presumably is sequential search
        print("Found it with 'in' but don't know where")
    else:
        print("Not found with 'in'")
    
#sequential search an unsorted list
#for a successful search, on average half the items.  is O(n)
#for unsuccessful search, all items
print("\nSequential search unsorted list")
inp = input("  Enter a number to search for: ")
while inp!="":
    search_item = int(inp)
    #list object does not have a (unsuccessful) search method.
    # index(val)   method throws error if val not in list
    i = 0
    comps = 0
    while i<size and list1[i]!=search_item:   #sequential search an unsorted list
        i += 1
        comps += 1
    if i<size:
        comps += 1
        print("Found it at",i," #comparisons:",comps)
    else:
        print("Not found  #comparisons:",comps)

    inp = input("  Enter a number to search for: ")


list_ordered = sorted(list1)
print("\nSorted list of the same numbers:")
print(list_ordered)
#sequential search a sorted list
#for a successful search, on average half the items. 
#for unsuccessful search, on average half the items.  is O(n)
print("Sequential search sorted list")
inp = input("  Enter a number to search for: ")
while inp!="":
    search_item = int(inp)
    i = 0
    comps = 1
    while i<size and list_ordered[i]<search_item:   #sequential search a sorted list
        i += 1
        comps += 1
    if i<size and list_ordered[i]==search_item:      # increment comps?
        print("Found it at",i," #comparisons:",comps)   
    else:
        print("Not found  #comparisons:",comps)

    inp = input("  Enter a number to search for: ")


#binary search a sorted list
#search is O(log2 n)
print("\nBinary search the sorted list")
inp = input("  Enter a number to search for: ")
while inp!="":
    search_item = int(inp)
    left = 0
    right = size-1
    i = (left+right)//2  #middle index
    comps = 1
    while left<=i<=right and list_ordered[i]!=search_item:   #binary search a sorted list
        if search_item < list_ordered[i]:   # increment comps?
            right = i-1
        else:
            left = i+1
        i = (left+right)//2
        comps += 1
        
    if list_ordered[i]==search_item:      # increment comps?
        print("Found it at",i," #comparisons:",comps)
    else:
        print("Not found  #comparisons:",comps)

    inp = input("  Enter a number to search for: ")
    

#digression, maintain a list in sorted order
size = 100
list2 = []
for item_count in range(size):
    new_item = randint(1,size*10)   #must be inserted into correct position
    #search to find position
    i = 0
    while i<len(list2) and new_item>list2[i]:
        i += 1
    list2.insert(i,new_item)
print("\nList built up in order:")
print(list2)


    
#search a SET of numbers
#but have no access to amount of work (i.e. #comparisons) req'd
#but uses hashing, which is O(1)
set1 = set(list1)    #no difference if sorted list.  Dups lost...
print("\nSet of the same original numbers:")
print(set1)
print("Search the set")
inp = input("  Enter a number to search for: ")
while inp!="":
    search_item = int(inp)
    if search_item in set1:
        print("Found it")
    else:
        print("Not found")
    inp = input("  Enter a number to search for: ")



# items now a struct/record, actually objects...
class record:
    def __init__(self,id,name,amount,measure):
        self.id = id
        self.name = name
        self.amount = amount
        self.measure = measure

    def __str__(self):
        return(str(self.id) + " " + self.name + " " + str(self.amount) + " " + str(self.measure))

def make_random_record():
    from random import randint
    from random import choice
    from random import random
    vowels = ['a','e','i','o','u']
    consonants = ['b','c','d','f','g','h','k','l','m','n','p','r','s','t','v','w','z']
    id = randint(1,1000000)
    name = choice(consonants) +\
           choice(vowels) +\
           choice(consonants) +\
           choice(vowels) +\
           choice(consonants) +\
           choice(vowels)
    amount = randint(0,100)
    measure = round(random() * 100, 3)
    return record(id,name,amount,measure)


#unsorted list of records. 
size = 10
list_records = []
for i in range(size):
    list_records.append(make_random_record())
print("\nUnsorted list of records:")
for rec in list_records:
    print(rec, end="     ")
print()

#search unsorted list of records. based on the id field
# can not do the count&index or 'in', as they require entire record
print("Sequential search unsorted list of records")
inp = input("  Enter an ID to search for: ")
while inp!="":
    search_id = int(inp)
    i = 0
    comps = 0
    while i<size and list_records[i].id!=search_id:   #sequential search an unsorted list
        i += 1
        comps += 1
    if i<size:
        comps += 1
        print("Found it at",i," #comparisons:",comps)
    else:
        print("Not found  #comparisons:",comps)

    inp = input("  Enter an ID to search for: ")

#sort the list of records on id field:
list_records_ordered = sorted(list_records,key=lambda rec: rec.id)
print("\nSorted list of records:")
for rec in list_records_ordered:
    print(rec, end="     ")
print()
#now can do better sequential search and binary search


#set of records
set_records = set(list_records)
print("\nSet of records:")    #will not be is same "order" as the list
for rec in set_records:
    print(rec, end="     ")
print()

print("Search set of records")
inp = input("  Enter an ID to search for: ")
while inp!="":
    search_id = int(inp)
    comps = 0
    found = False
    for rec in set_records:   #can not use 'in', so do sequential search
        comps += 1
        if rec.id == search_id:
            print("Found it    #comparisons:",comps)
            found = True
            break
    if not found:
        print("Not found  #comparisons:",comps)

    inp = input("  Enter an ID to search for: ")