'''
   20211128
   
   Robin Dawes

   Linked List class
'''
      
class LinkedList():
   '''Basic implementation of a Linked List'''
   
   class ListNode():
      '''Basic implementation of a Linked List Node
      
         This class is defined inside the LinkedList class because it is only used by
         LinkedList objects.  This is another example of encapsulation.
      '''
   
      def __init__(self, val = None):
         self.value = val
         self.next = None
         
      def __str__(self):
         return "ListNode with value = " + str(self.value)
         
      def set_value(self, val):
         self.value = val
         
      def get_value(self):
         return self.value
         
      def set_next(self, n):
         self.next = n
         
      def get_next(self):
         return self.next
      
   # end of class ListNode
   
   
   def __init__(self):
      self.head = None
      self.tail = None
      self.counter = 0
      
   def __str__(self):
      return "LinkedList containing "+str(LinkedList.counter)+" values"


   # __iter__(self)   and __next__(self) are used to make it possible to iterate through the linked list
      
   def __iter__(self):
      ''' initializes the iterator '''
      self.current = self.head
      return self        # must return self
      
   def __next__(self):
      ''' advances the iterator to the next element of the list '''
      if self.current == None:
         raise StopIteration       # must be used to end the iteration
      else:
         return_val = self.current.value
         self.current = self.current.next
         return return_val
         
         
         
   # other functions      
      
   def append_value(self, val):
      ''' append a value to the list '''
      new_node = self.ListNode(val)     # create a new ListNode and put the new value in it
      if self.tail == None:
         self.head = new_node
         self.tail = new_node
      else:
         self.tail.set_next(new_node)
         self.tail = new_node
      
      self.counter += 1
      
   def insert_value_in_position(self, val, pos):
      ''' Inserts a value in a specified position
         If the position is >= the number of nodes in the list, the value is appended
         If the position is 0, the value becomes the head of the list
      '''
      if pos >= self.counter:
         self.append_value(val)        # self.append_value() increments self.counter
      elif pos == 0:
         new_node = self.ListNode(val)
         new_node.set_next(self.head)
         self.head = new_node
         self.counter += 1
      else:                   
         # walk through the list to the desired position
         cur_pos = 0
         current = self.head
         while cur_pos < pos:
            previous = current
            current = current.get_next()
            cur_pos += 1
         # create a ListNode to hold the new value and link it in
         new_node = self.ListNode(val)
         new_node.set_next(current)
         previous.set_next(new_node)
         self.counter += 1
  
   def delete_value(self, x):
      ''' deletes the first instance of x in the list '''
      if self.head == None:
         return
      else:
         if self.head.value == x:
            self.head = self.head.next
            self.counter -= 1
         else:
            previous = self.head
            current = self.head.next
            while current != None  and current.value != x:
               previous = current
               current = current.next
            if current == None:     # the value is not in the list
               return
            else:
               # unlink the ListNode containing the value from the list
               previous.next = current.next
               self.counter -= 1
               return
      
         
   def get_length(self):
      ''' returns the current length of the list '''
      return self.counter         
      
   def find_max(self):
      ''' returns the largest value in the list 
      
         values stored in the list must be comparable
      '''
      
      if self.head == None:
         return None
      else:
         max_val = self.head.value
         current = self.head.next
         while current != None:
            if current.value > max_val:
               max_val = current.value
            current = current.next
         return max_val   


   def sort(self):
      ''' Replace the list with a sorted version of itself.
      
         This is NOT an efficient sort.  It would be faster to copy the list values into an
         array and use Quicksort on the array, then copy the values back into this linked list.
         
         I've written the sort this way as a useful illustration of how a class instance can create
         another class instance, manipulate it, extract the contents, then delete the instance it
         created.
         
      '''
      if self.head == None:
         return
      else:
         new_list = LinkedList()
         for i in range(self.counter):
            m = self.find_max()                    # find the largest value
            self.delete_value(m)                   # remove it from this list
            new_list.insert_value_in_position(m, 0)      # insert it at the beginning of the new list
         
         self.head = new_list.head              # link to the first ListNode inside the new LinkedList
         self.tail = new_list.tail
         del new_list                                    # delete the new LinkedList ... this does NOT delete
                                                                # the ListNodes that were created because this LinkedList
                                                                # now links to them.
         return
         
# end of class LinkedList            
     
# main

import random

my_list = LinkedList()

some_nums = random.sample(range(100),6)

for x in some_nums:
   my_list.append_value(x)

print()
print("my_list")

for x in iter(my_list):
   print(x)


my_list.insert_value_in_position(9999,3)
print("\nAfter inserting a new value in position 3")

for x in iter(my_list):
   print(x)

print("\nThe max value in my_list is", my_list.find_max())

my_list.delete_value(my_list.find_max())

print("\nAfter deleting the largest value, the max value in my_list is", my_list.find_max())

my_list.sort()

print("\nAfter sorting")

for x in iter(my_list):
   print(x)