please implement "add_integer" and "rotate" (bottom of file)

add_integer:

Assume the content of the linked list represents an integer such that each digit is stored in a separate node (you do not need to write checks for this). This method will receive an integer num , add it to the number already stored in the linked list and store the result of the addition back in the list nodes, one digit per node. Please see examples below for more details. This addition must be done in place, by changing the values of the existing nodes to the extent possible. However, since the result of the addition may have more digits than nodes in the original linked list, you may need to add some new nodes. However, you should only add the minimum number of nodes necessary and not recreate the entire linked list. For example, if the original list stored the number 123 as [1 <-> 2 <-> 3], and the second integer had the value of 5, no new nodes must be created since the result of the addition can be stored in the same three nodes as [1 <-> 2 <-> 8]. If the original list was [1 <-> 2 <-> 3], and the second integer had the value of 999, you are allowed to create one new node so that the entire result can fit [1 <-> 1 <-> 2 <-> 2].

rotate:

This method rotates the linked list by shifting positions of its elements right or left steps number of times. If steps is a positive integer, elements should be rotated right. Otherwise, rotation is to the left. All work must be done in place without creating any copies of existing nodes or an entire existing list. You are not allowed to swap values of the nodes; the solution must change node pointers. Please note that the value of steps parameter can be very large (from -10 9 to 10 9 ). The solutions runtime complexity must be O(N), where N is the length of the list.

class CDLLException(Exception): """ Custom exception class to be used by Circular Doubly Linked List DO NOT CHANGE THIS CLASS IN ANY WAY """ pass class DLNode: """ Doubly Linked List Node class DO NOT CHANGE THIS CLASS IN ANY WAY """ def __init__(self, value: object) -> None: self.next = None self.prev = None self.value = value class CircularList: def __init__(self, start_list=None): """ Initializes a new linked list with sentinel DO NOT CHANGE THIS METHOD IN ANY WAY """ self.sentinel = DLNode(None) self.sentinel.next = self.sentinel self.sentinel.prev = self.sentinel # populate CDLL with initial values (if provided) # before using this feature, implement add_back() method if start_list is not None: for value in start_list: self.add_back(value) def __str__(self) -> str: """ Return content of singly linked list in human-readable form DO NOT CHANGE THIS METHOD IN ANY WAY """ out = 'CDLL [' if self.sentinel.next != self.sentinel: cur = self.sentinel.next.next out = out + str(self.sentinel.next.value) while cur != self.sentinel: out = out + ' <-> ' + str(cur.value) cur = cur.next out = out + ']' return out def length(self) -> int: """ Return the length of the linked list This can also be used as troubleshooting method. This method works by independently measuring length during forward and backward traverse of the list and return the length if results agree or error code of -1 or -2 if thr measurements are different. Return values: >= 0 - length of the list -1 - list likely has an infinite loop (forward or backward) -2 - list has some other kind of problem DO NOT CHANGE THIS METHOD IN ANY WAY """ # length of the list measured traversing forward count_forward = 0 cur = self.sentinel.next while cur != self.sentinel and count_forward < 101_000: count_forward += 1 cur = cur.next # length of the list measured traversing backwards count_backward = 0 cur = self.sentinel.prev while cur != self.sentinel and count_backward < 101_000: count_backward += 1 cur = cur.prev # if any of the result is > 100,000 -> list has a loop if count_forward > 100_000 or count_backward > 100_000: return -1 # if counters have different values -> there is some other problem return count_forward if count_forward == count_backward else -2 def is_empty(self) -> bool: """ Return True is list is empty, False otherwise DO NOT CHANGE THIS METHOD IN ANY WAY """ return self.sentinel.next == self.sentinel # ------------------------------------------------------------------ # def add_front(self, value: object) -> None: """ Adds value to the front of the list. """ node = DLNode(value) temp = self.sentinel.next self.sentinel.next = node node.next = temp temp.prev = node node.prev = self.sentinel return def add_back(self, value: object) -> None: """ Adds value to back of list. """ new_node = DLNode(value) temp = self.sentinel.prev self.sentinel.prev = new_node new_node.prev = temp temp.next = new_node new_node.next = self.sentinel return def insert_at_index(self, index: int, value: object) -> None: """ Adds a new value at the specified index position in the linked list. Index 0 refers to the beginning of the list (right after the front sentinel). """ if index < 0 or index > self.length(): raise CDLLException node = DLNode(value) tempA = self.sentinel for i in range(index): tempA = tempA.next tempB = tempA.next tempA.next = node node.next = tempB tempB.prev = node node.prev = tempA return def remove_front(self) -> None: """ Removes the first node from the list. """ pass def remove_back(self) -> None: """ Removes the last node from the list. """ pass def remove_at_index(self, index: int) -> None: """ Removes a node from the list given its index. """ if index < 0 or index >= self.length(): raise CDLLException curr = self.sentinel for i in range(index): curr = curr.next curr.next = curr.next.next curr.next.prev = curr return def get_front(self) -> object: """ Returns the value from the first node in the list without removing it. """ if self.length() == 0: raise CDLLException return self.sentinel.next def get_back(self) -> object: """ Returns the value from the last node in the list without removing it. """ pass def remove(self, value: object) -> bool: """ Remove the first node in the list that matches the provided value object. The method returns True if some node was actually removed from the list. Otherwise, it returns False. """ pass

 def add_integer(self, num: int) -> None: """ TODO: Write this implementation """ 

def rotate(self, steps: int) -> None: """ TODO: Write this implementation """ pass 

testing code:

Example #1 (add_integer):

test_cases = ( ([1, 2, 3], 10456), ([], 25), ([2, 0, 9, 0, 7], 108), ([9, 9, 9], 9_999_999), )

for list_content, integer in test_cases:

lst = CircularList(list_content)

print('INPUT :', lst, 'INTEGER', integer)

lst.add_integer(integer) print('OUTPUT:', lst)

Output: INPUT : CDLL [1 <-> 2 <-> 3]

INTEGER 10456

OUTPUT: CDLL [1 <-> 0 <-> 5 <-> 7 <-> 9]

INPUT : CDLL []

INTEGER 25

OUTPUT: CDLL [2 <-> 5]

INPUT : CDLL [2 <-> 0 <-> 9 <-> 0 <-> 7] I

NTEGER 108

OUTPUT: CDLL [2 <-> 1 <-> 0 <-> 1 <-> 5]

INPUT : CDLL [9 <-> 9 <-> 9]

INTEGER 9999999

OUTPUT: CDLL [1 <-> 0 <-> 0 <-> 0 <-> 0 <-> 9 <-> 9 <-> 8]

Example #2: (rotate):

source = [_ for _ in range(-20, 20, 7)]

for steps in [1, 2, 0, -1, -2, 28, -100]:

lst = CircularList(source) lst.rotate(steps)

print(lst, steps) Output: CDLL [15 <-> -20 <-> -13 <-> -6 <-> 1 <-> 8]

1 CDLL [8 <-> 15 <-> -20 <-> -13 <-> -6 <-> 1]

2 CDLL [-20 <-> -13 <-> -6 <-> 1 <-> 8 <-> 15]

0 CDLL [-13 <-> -6 <-> 1 <-> 8 <-> 15 <-> -20]

-1 CDLL [-6 <-> 1 <-> 8 <-> 15 <-> -20 <-> -13]

-2 CDLL [-6 <-> 1 <-> 8 <-> 15 <-> -20 <-> -13]

28 CDLL [8 <-> 15 <-> -20 <-> -13 <-> -6 <-> 1] -100