USE PYTHON for the following questions. And the end of this page I have posted tjo codes to work with for the questions.

Here are the codes:

binheap.py

import unittest

# this heap takes key value pairs, we will assume that the keys are integers

class BinHeap:

def __init__(self):

self.heapList = [0]

self.currentSize = 0

def buildHeap(self,alist):

i = len(alist) // 2

self.currentSize = len(alist)

self.heapList = [0] + alist[:]

# print(len(self.heapList), i)

while (i > 0):

# print(self.heapList, i)

self.percDownRec(i)

i = i - 1

# print(self.heapList,i)

def percUpRec(self, i):

# ADD CODE HERE

pass

## def percUp(self,i):

## while i // 2 > 0:

## if self.heapList[i]

## tmp = self.heapList[i // 2]

## self.heapList[i // 2] = self.heapList[i]

## self.heapList[i] = tmp

## i = i // 2

##

def insert(self,k):

self.heapList.append(k)

self.currentSize = self.currentSize + 1

self.percUpRec(self.currentSize)

def percDownRec(self,i):

# ADD CODE HERE

pass

## def percDown(self,i):

## while (i * 2)

## mc = self.minChild(i)

## if self.heapList[i] > self.heapList[mc]:

## tmp = self.heapList[i]

## self.heapList[i] = self.heapList[mc]

## self.heapList[mc] = tmp

## i = mc

def minChild(self,i):

if i * 2 + 1 > self.currentSize:

return i * 2

else:

if self.heapList[i * 2]

return i * 2

else:

return i * 2 + 1

def delMin(self):

retval = self.heapList[1]

self.heapList[1] = self.heapList[self.currentSize]

self.currentSize = self.currentSize - 1

self.heapList.pop()

self.percDownRec(1)

return retval

def isEmpty(self):

if currentSize == 0:

return True

else:

return False

def size(self):

return self.currentSize

def __str__(self):

return str(self.heapList[1:])

class FooThing:

def __init__(self,x,y):

self.key = x

self.val = y

def getKey(self):

return self.key

def getValue(self):

return self.val

def setValue(self, newValue):

self.val = newValue

def __eq__(self,other):

if self.key == other.key:

return True

else:

return False

def __ne__(self,other):

if self.key != other.key:

return True

else:

return False

def __lt__(self,other):

if self.key

return True

else:

return False

def __le__(self,other):

if self.key

return True

else:

return False

def __gt__(self,other):

if self.key > other.key:

return True

else:

return False

def __ge__(self,other):

if self.key >= other.key:

return True

else:

return False

def __hash__(self):

return self.key

class TestBinHeap(unittest.TestCase):

def setUp(self):

self.theHeap = BinHeap()

self.theHeap.insert(FooThing(5,'a'))

self.theHeap.insert(FooThing(9,'d'))

self.theHeap.insert(FooThing(1,'x'))

self.theHeap.insert(FooThing(2,'y'))

self.theHeap.insert(FooThing(3,'z'))

def testInsert(self):

assert self.theHeap.currentSize == 5

def testDelmin(self):

assert self.theHeap.delMin().getValue() == 'x'

assert self.theHeap.delMin().getValue() == 'y'

assert self.theHeap.delMin().getValue() == 'z'

assert self.theHeap.delMin().getValue() == 'a'

def testMixed(self):

myHeap = BinHeap()

myHeap.insert(9)

myHeap.insert(1)

myHeap.insert(5)

assert myHeap.delMin() == 1

myHeap.insert(2)

myHeap.insert(7)

assert myHeap.delMin() == 2

assert myHeap.delMin() == 5

def testDupes(self):

myHeap = BinHeap()

myHeap.insert(9)

myHeap.insert(1)

myHeap.insert(8)

myHeap.insert(1)

assert myHeap.currentSize == 4

assert myHeap.delMin() == 1

assert myHeap.delMin() == 1

assert myHeap.delMin() == 8

def testBuildHeap(self):

myHeap = BinHeap()

myHeap.buildHeap([9,5,6,2,3])

f = myHeap.delMin()

# print("f = ", f)

assert f == 2

assert myHeap.delMin() == 3

assert myHeap.delMin() == 5

assert myHeap.delMin() == 6

assert myHeap.delMin() == 9

if __name__ == '__main__':

suite = unittest.makeSuite(TestBinHeap)

unittest.TextTestRunner().run(suite)

node.py

class Node:

def __init__(self,initdata):

self.data = initdata

self.next = None

def getData(self):

return self.data

def getNext(self):

return self.next

def setData(self,newdata):

self.data = newdata

def setNext(self,newnext):

self.next = newnext

ordered linked list.py

from node import Node

class OrderedList(object):

def __init__(self): """ Constructs an empty unsorted list. Precondition: none Postcondition: Reference to empty unsorted list returned. """ self._head = None self._tail = None self._size = 0 self._current = None self._previous = None self._currentIndex = 0

def search(self, targetItem): """ Searches for the targetItem in the list. Precondition: none. Postcondition: Returns True and makes it the current item if targetItem is in the list; otherwise False is returned. """ def searchHelper(): """ Recursive helper function that moves down the linked list. It has no parameters, but uses self._current, self._previous, and self._currentIndex.""" # ADD CODE HERE pass

# START OF SEARCH - DO NOT MODIFY BELOW CODE if self._current != None and self._current.getData() == targetItem: return True self._previous = None self._current = self._head self._currentIndex = 0 return searchHelper() # Returns the result of searchHelper

## NON-RECURSIVE CODE WE ARE REPLACING ## def search(self, targetItem): ## """ Searches for the targetItem in the list. ## Precondition: none. ## Postcondition: Returns True and makes it the current item if targetItem is in the list; ## otherwise False is returned. ## """ ## if self._current != None and self._current.getData() == targetItem: ## return True ## ## self._previous = None ## self._current = self._head ## self._currentIndex = 0 ## while self._current != None: ## if self._current.getData() == targetItem: ## return True ## elif self._current.getData() > targetItem: ## return False ## else: #inch-worm down list ## self._previous = self._current ## self._current = self._current.getNext() ## self._currentIndex += 1 ## return False

def add(self, newItem): """ Adds the newItem to is sorted spot in the list. Precondition: newItem is not in the list. Postcondition: newItem is added to the list. """ if self.search(newItem): raise ValueError("Cannot not add since item is already in the list!") temp = Node(newItem) temp.setNext(self._current) if self._previous == None: self._head = temp else: self._previous.setNext(temp) if self._current == None: self._tail = temp self._size += 1

def remove(self, item): """ Removes item from the list. Precondition: item is in the list. Postcondition: Item is removed from the list. """ if not self.search(item): raise ValueError("Cannot remove item since it is not in the list!")

if self._current == self._tail: self._tail = self._previous if self._current == self._head: self._head = self._head.getNext() else: self._previous.setNext(self._current.getNext()) self._current = None self._size -= 1

def isEmpty(self): """ Checks to see if the list is empty. Precondition: none. Postcondition: Returns True if the list is empty; otherwise returns False. """ return self._size == 0

def length(self): """ Returns the number of items in the list. Precondition: none. Postcondition: Returns the number of items in the list. """ return self._size

def index(self, item): """ Returns the position of item in the list. Precondition: item is in the list. Postcondition: Returns the position of item from the head of list. """ if not self.search(item): raise ValueError("Cannot determine index since item is not in the list!")

return self._currentIndex

def pop(self, *pos): """ Removes and returns the item at position pos of the list. Precondition: position pos exists in the list. Postcondition: Removes and returns the item at position pos of the list. """ if len(pos) == 0: pos = self._size - 1 elif len(pos) != 1: raise TypeError("Too many parameters to pop") else: pos = pos[0] if not isinstance(pos, int): raise TypeError("Position must be an integer!") if pos >= self._size or pos

self._current = self._head self._previous = None for count in range(pos): self._previous = self._current self._current = self._current.getNext() if self._current == self._tail: self._tail = self._previous if self._current == self._head: self._head = self._head.getNext() else: self._previous.setNext(self._current.getNext()) returnValue = self._current.getData() self._current = None self._size -= 1 return returnValue

def __str__(self): """ Returns a string representation of the list with a space between each item. Precondition: none Postcondition: Returns a string representation of the list with a space between each item. """ def strHelper(current): if current == None: return "" else: return str(current.getData()) + " " + strHelper(current.getNext()) resultStr = "(head) " + strHelper(self._head) + "(tail)" return resultStr ## def __str__(self): ## """ Removes and returns the item at position pos of the list. ## Precondition: position pos exists in the list. ## Postcondition: Removes and returns the item at position pos of the list. ## """ ## resultStr = "(head)" ## current = self._head ## while current != None: ## resultStr += " " + str(current.getData()) ## current = current.getNext() ## return resultStr + " (tail)" if __name__ == '__main__': myList = OrderedList() assert myList.search('a') == False myList.add('3') myList.add('5') myList.add('7') assert myList.search('1') == False assert myList.search('3') == True assert myList.search('4') == False assert myList.search('5') == True assert myList.search('6') == False assert myList.search('7') == True assert myList.search('8') == False print("ALL SEARCH TESTS PASSED!!!")

list tester.py

from ordered_linked_list import OrderedList

def main():

myList = OrderedList()

while True:

print(" Ordered List Tester Menu")

print("a - add")

print("r - remove(item)")

print("i - index(item)")

print("p - pop()")

print("pp - pop(position)")

print("s - search(item)")

print("l - length")

print("x - eXit")

print(" The current list is:", str(myList))

command = input(" Enter your choice: ").lower()

if command == 'a':

item = input("Enter item to add: ")

myList.add(item)

elif command == 'r':

item = input("Enter item to remove from list")

myList.remove(item)

elif command == 'i':

item = input("Enter item to determine index")

index = myList.index(item)

print("The item is at index:",index)

elif command == 'p':

item = myList.pop()

print("The item popped from the tail was:",item)

elif command == 'pp':

index = eval(input("Enter index to pop from:"))

item = myList.pop(index)

print("The item popped from the index was:",item)

elif command == 's':

item = input("Enter item to search for ")

found = myList.search(item)

print("The item search result:",found)

elif command == 'l':

print("The length of the list is:",myList.length())

elif command == 'x':

break

else:

print(" Invalid command only 'a', 'r', 'i', 'p', 'pp', 's', 'l', 'x' are valid ")

main()

Part A: Recall: We modified the textbook's ordered list ADT that uses a singly-linked list implementation by adding the_size, _tail, _current, _previous, and_currentIndex attributes OrderedList Object data next data next data next data next data next head 'm size4 previous currentIndex 3 current tail NON-RECURSIVE CODE WE ARE REPLACING def search(self, targetitem) def search (self, targetItem) if self- current != None and \ def searchHelper elf._current.getData)targetItem: """ Recursive helper function th t moves down the linked list It has no paraneters, but uses self._current, self._previous self. currentIndex.""" return True ADD CODE EERE self previous = None self. current= self- head self, current!ndex = 0 while self- current !-None ; if self. current.getData)targetItem: elif self._current.getData) > targetItem: else: #inch-worm down list return True return False # START OF SEARCH - DO NOT MODIFY BELO' CODE if self, current != None and \ self.-previous = self-current self._currentself._current.getNext) self- curr ntIndex +.. 1 self._current.getDatal) - targetitem: return True return False self. previousNone self._currentself._head self. currentIndex0 return searchHelper() # Returns the result of searchHelper a) What are the base case(s) for the searchRelper that halt the while-loop of the non-recursive search codc? b) What are the recursive case(s) for the searchHelper that replaces the while-loop of the non-recursive search codc? c) Complete the recursive searchHelper function in the search method of our OrderedList class in ordered_linked list.py. Test it with the 1istTester.py program