#!/usr/bin/env python3

"""

Code file for M269 20J TMA01 Question 4.

Student version 4: 22/04/2020

"""

class WaitingList:

"""

An implementation of waiting lists, using Python lists.

Each item in the list is an (integer, string) tuple

representing a group of people.

The tuples need not be unique.

Groups join the end of the waiting list.

Groups can be taken from anywhere on the waiting list and will be

selected by searching from the start of the list until the first

group matching the required criteria is found.

"""

def __init__(self):

"""

Initialise the waiting list to be empty.

"""

self.items = []

def hasGroup(self,max, destination):

"""

Return True if the waiting list has at least one group

of no more than max people wanting to go to destination,

otherwise return False.

"""

for index in range(0,self.size()):

thisGroup = self.items[index]

if thisGroup[0] <= max and thisGroup[1] == destination:

return True

return False

def put(self, groupSize, destination):

"""

Add group to the end of the waiting list.

"""

self.items.append((groupSize, destination))

def size(self):

"""

Return the number of groups in the waiting list.

"""

return len(self.items)

def take(self, max, destination):

"""

Remove the first group of no more than max people

wanting to go to destination.

If there is no such group do nothing.

"""

index = 0

notFound = True

while index < self.size() and notFound:

thisGroup = self.items[index]

if thisGroup[0] <= max and thisGroup[1] == destination:

self.items.pop(index)

notFound = False

else:

index = index + 1

def stillWaiting(self, destination):

"""

Return the total number of people on the waiting list

wanting to go to destination.

"""

pass# replace this by your code

==========================================

"""

Test file for M269 20J TMA01 Question 4.

Student version 4: 22/04/20

"""

from M269_TMA01_20J_Q4 import WaitingList

# tests for part (e)

print("tests for part (e)")

def testStillWaiting(waitingList,destination):

numberWaiting = w.stillWaiting(destination)

print(numberWaiting, " waiting to fly to ", destination)

w=WaitingList()

print("Waiting list empty")

testStillWaiting(w,"Milan")

w.put(2,"Rome")

print("only one group in waiting list")

testStillWaiting(w,"Rome")

w.put(3,"Rome")

w.put(2,"Naples")

w.put(1,"Pisa")

w.put(1,"Florence")

w.put(25,"Rome")

print("longer waiting list")

testStillWaiting(w,"Rome")

testStillWaiting(w,"Naples")

testStillWaiting(w,"Pisa")

testStillWaiting(w,"Florence")

testStillWaiting(w,"Milan")

w.take(4,"Rome")

print("removed a group")

testStillWaiting(w,"Rome")

==============================================================

We have created an ADT to represent waiting lists of groups of airline passengers wanting to fly on the next available plane to their destination.

Each group has a number of people and a destination. There must be at least one person in a group. The destination may not be blank. Groups are not uniquely identified. For instance, there can be several groups of 4 people wanting to fly to Sydney. They are distinguished by their position on the waiting list.

Groups are added to the end of the waiting list. Groups are taken off the waiting list as follows: if a number of seats to a given destination becomes available, the first group on the waiting list meeting the criteria of waiting for that destination and requiring no more than the available number of seats will be removed from the waiting list. If there is no such group, no group can be taken off the waiting list.

• a.Explain why the waiting list cannot be implemented using the Stack ADT.
• (2 marks)
• b.Study our WaitingList ADT implementation in the provided code file.
• Classify each of the following operations as creator, modifier or inspector with a brief justification.
• WaitingList()
• hasGroup(max,destination)
• put(groupSize, destination)
• size()
• take(max, destination)
• (5 marks)
• c.Write a specification for the take operation as implemented in the WaitingList ADT.

def take(self, max, destination):

"""

Remove the first group of no more than max people

wanting to go to destination.

If there is no such group do nothing.

"""

index = 0

notFound = True

while index < self.size() and notFound:

thisGroup = self.items[index]

if thisGroup[0] <= max and thisGroup[1] == destination:

self.items.pop(index)

notFound = False

else:

index = index + 1

Example:

def findHighest(intList):

assert len(intList) > 0

result = intList[0]

for eachNum in intList:

if eachNum > result:

result = eachNum

return result

Specification

Name: FindHighest

Inputs: A sequence of integersI= (i₁,i₂,i₃, ...,i_n)

Outputs: An integerh

Precondition: Length ofI> 0

Postcondition: his inIandhi_kfor alli_kinI

Following are the specifications

name: Take

Inputs: an integer max and a string destination

output: a list G of 2 elements [ integer, string] or null

preconditions: items is a list of list where every list element is a 2 value list of type [integer,string]

postcondition: G[0] <=max and G[1]==destination

please note that though the function take has 3 arguments but self is parameter that allows use of WaitingList ADT members in the function

• (6 marks)

• d.How many comparisons will the take operation require, where the length of the waiting list is n and the first group that meets the criteria is at the end of the waiting list? Explain your answer. You may assume that the built-in list operations pop() and indexing make no comparisons. Taking comparison as the basic unit of computation, what is the Big(O) complexity in this case? Is this a best case or worst case? Give an example of a waiting list that is the other case, briefly justifying your choice.
• (5 marks)
• e.Implement the stillWaiting operation in the provided code file to compute the total number of people in all groups on the waiting list wanting to go to the given destination. Check your code using the tests for part (e) in the provided test file.
• (5 marks)
• f.If hasGroup returns an index rather than a Boolean, as follows:
• def hasGroup(self, max, destination):
• for index in range(0, self.size()):
• thisGroup = self.items[index]
• if thisGroup[0] <= max and thisGroup[1] == destination:
• return index
• return -1
• we can rewrite take as follows:
• def take(self, max, destination):
• index = self.hasGroup(max, destination)
• if index != -1:
• self.items.pop(index)
• Does this rewritten take operation still meet the specification you wrote in part (c)?
• Briefly explain your answer.
• (2 marks)