START WITH THIS CODE: https://paste.ee/p/0Q7xz only add code to the ADT methods

Question

START WITH THIS CODE: https://paste.ee/p/0Q7xz

only add code to the ADT methods where indicated in the code. The file contains extra methods and code at the end to both test your implementation and help you debug your code by using the dump() method. Read the comments in the file. You should keep the names of things the same for everything already defined. (also you can add a instance variable to keep track of the number of nodes in deque, but do not name it size or it will conflict with the instance method named size().)

Your code is test with a series of assert statements. If an assert statement fails, the rest of the testing will not be reached. So fix the problems that cause the first error, before worrying about the next test.

When a test fails, you can either set debug to true at the top of file to dump a graphic picture of the list. or add dq.dump() just before the failing assertion statement.

The test code also calls dq.integrity_check() that verifies that the links look consistent for a double linked List. I follows the links from front and from rear to see if they are not messed up.

Implement the ADT for Deque methods shown in the book using a double linked list to hold the data for the deque.

For Extra Credit:

Also implement a pop method that takes an integer argument i such that it returns the ith nodes data counting from 0 from the beginning of the list if i is positive and returns the ith node counting backward from the end of the list if i is negative. (So pop(-1) would remove and return the last item in the list)

It should also remove the node from the list.

Explanation / Answer

import time
from collections import deque

def append(c):
    for i in range(num):
        c.append(i)

def appendleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.appendleft(i)
    else:
        for i in range(num):
            c.insert(0, i)
def pop(c):
    for i in range(num):
        c.pop()

def popleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.popleft()
    else:
        for i in range(num):
            c.pop(0)

for container in [deque, list]:
    for operation in [append, appendleft, pop, popleft]:
        c = container(range(num))
        start = time.time()
        operation(c)
        elapsed = time.time() - start
        print "Completed %s/%s in %.2f seconds: %.1f ops/sec" % (container.__name__, operation.__name__, elapsed, num / elapsed)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.