"""
 linked_list_basic.py

 a linked list in python - the basics

    $ python linked_list_basic.py
    LinkedList :
      <Node value=30 id=0x7f90601ba460 next=0x7f90601ba4c0>
      <Node value=20 id=0x7f90601ba4c0 next=0x7f90601ba5e0>
      <Node value=10 id=0x7f90601ba5e0 next=None>

    Finding its length :
      recursive gives 3
      iterative gives 3

    Popping until empty : 30  20  10

 Jim Mahoney | cs.bennington.college | MIT License | March 2021
"""

class Node:
    """ a Node is a container that holds two things : 
           (1) value : either a number or a string
           (2) next  : a reference to the next node in a chain.
        It also has an __str__ method which shows all its details.
    """
    
    def __init__(self, value):
        self.value = value
        self.next = None

    def __str__(self):
        self_id = hex(id(self))
        next_id = hex(id(self.next)) if self.next != None else "None"
        return f"<Node value={self.value} id={self_id} next={next_id}>"

class LinkedList:
    """ a LinkedList is an object with methods that manipulate
        a linked list chain of nodes. You can visualize the chain like this :
              node1  ==>  node2  ==> node2

        Here the beginning of the chain is called "begin"; 
        other common names include "root", "head", and "first".

        The methods implemented here are
            push(node)     put a node on the beginning of the chain
            pop()          remove and return node at beginning
            is_empty()     test to see if its empty or not
            __str__        return it as a string
    """
    
    def __init__(self):
        self.begin = None
        
    def push(self, node):
        """ add a new node to the beginning of the chain """
        node.next = self.begin   # Put the old stuff after this new node.
        self.begin = node        # Set the new beginning.

    def pop(self):
        """ remove the begining node and return it """
        popped = self.begin      # First remember what to return.
        if popped:               # If that isn't None, rearrange links :
            self.begin = popped.next    # (a) make LinkedList shorter
            popped.next = None          # (b) clean up the return value
        return popped
    
    def is_empty(self):
        """ return True if the list is empty """
        return self.begin == None

    def __str__(self):
        result = "LinkedList : \n"
        node = self.begin
        while node:
            result += f"  {node} \n"
            node = node.next
        return result

def length_iterative(node):
    """ Return length of chain of nodes, iterative implementation """
    # This is an O(n) operation; walking through all the nodes.
    count = 0
    while node:
        count += 1
        node = node.next
    return count

def length_recursive(node):
    """ Return length of chain of nodes, recursive implementation """
    # This is an O(n) operation, with many calls to this same function.
    if not node:
        return 0
    else:
        return 1 + length_recursive(node.next)
    
def main():
    
    linky = LinkedList()          # Create a linked list,
    for i in (10, 20, 30):        # put some stuff into it,
        linky.push(Node(i))
    print(linky)                  # and take a look at it.

    print("Finding its length : ")
    print(f"  recursive gives {length_recursive(linky.begin)}")
    print(f"  iterative gives {length_iterative(linky.begin)}")
    print()
    
    print("Popping until empty : ", end="")
    while not linky.is_empty():
        print(linky.pop().value, " ", end="")
    print()

    
if __name__ == '__main__':
    # if this is being imported from another file, don't run main().
    main()