'''
CSCI 204.01 Exam 1 review exercise
Divide the students into groups and each group solves one proble, then exchange their ideas
or solution.
1. Write a Python function that can remove all nodes with a specific value in a singly linked list.
2. Write a Python function that can count the number of nodes in a circular linked list with a specific data value.
3. Write an operator overloading function __sub__ that removes a node with specified value in a singly linked list.
4. Write a recursive function to compute the length of a doubly linked list.
5. Write a child class with a constructor and string function that inherits information from a parent class.
'''

'''
This file contains solution for P1 and P3 
'''
class UserList:
    def __init__(self):
        self.head = None
        self.tail = None

    def __str__(self):
        """ String function """
        s = '['
        h = self.head
        while h != None:
            s += str(h.data)
            h = h.next
            if h != None:
                s += ', '
        s += ']'
        return s

    def __len__(self):
        '''Return the length of the list'''
        return self.count_length(self.head)

    def __sub__(self, node):
        '''Overloading the operator '-' '''
        return self.remove_node(node)
    
    def insert_after(self, data):
        """ Insert a node with data at the end of the list
        """
        node = ListNode(data)
        if self.is_empty():   # the node will be the first one in list
            self.head = node
            self.tail = node
        else:                 # insert after the current tail
            self.tail.next = node
            self.tail = node

    def count_length(self, node):
        '''Help function: Computing the length recursively'''        
        
        if node == None:
            return 0
        else:
            return 1 + self.count_length(node.next)

    def is_empty(self):
        """ Return True if the list is empty, False otherwise.
        """
        return self.head == None

    def remove_node(self, target):
        """ Remove the target node
        """
        prev = None
        cur  = self.head
        while cur != None and cur.data != target.data:
            prev = cur
            cur  = cur.next

        if cur != None:    # found it and remove it
            if cur == self.head:
                self.head = cur.next  # head is removed, reset head
            else:
                prev.next = cur.next  # remove a middle node
        else:
            print('Node not found' + str(target))

        return self

    def remove_all(self, value):
        """Remove all nodes with the given value"""
        prev = None
        cur = self.head
        while cur != None:
            if cur.data == value: # remove it
                if cur == self.head:  # remove the head
                    self.head = self.head.next
                elif cur == self.tail:  # remove tail
                    self.tail = prev
                    self.tail.next = None
                else:
                    prev.next = cur.next
                cur = cur.next # move cur, but not prev
            else:              # move both cur and prev
                prev = cur
                cur = cur.next
            
class ListNode:
    """ The node class for list notes"""
    def __init__(self, data):
        self.data = data
        self.next = None