"""
 linked_list.py

 An implementation of a doubled linked list class LinkedList , including :

   * printing a list by walking down the chain of nodes and printing each value
   * pop (start and end, nodes and values)
   * push (start and end, nodes and values)
   * get length recursively (even though python is not good at recursion ...)
     ... and iteratively
     ... and by keeping track as we go along, which doesn't pay the O(n) cost
   * searching for a node with a given value (backwards from end)
   * inserting a node after another node

 as well as a bunch of consistency tests.

    $ python linked_list.py 

    Failed 1 of 15 tests : 
    NOT OK  1 == 2
    ok      begin value of (1 2 3 4) is 1
    ok      end value of (1 2 3 4) is 4
    ok      linked list __str__ method
    ok      find node with given value
    ok      insert after
    ok      size recursive
    ok      size iterative
    ok      pop begin leaves rest
    ok      pop begin gives correct bare node
    ok      pop end leaves rest
    ok      pop begin gives correct bare node
    ok      find still works after pop_end
    ok      pop_end to empty list
    ok      pop_begin to empty list

    Linked list with length 3 : 
      <Node value=1 prev=None           id=0x7fdff0082340 next=0x7fdff00824c0 >
      <Node value=2 prev=0x7fdff0082340 id=0x7fdff00824c0 next=0x7fdff00823d0 >
      <Node value=3 prev=0x7fdff00824c0 id=0x7fdff00823d0 next=None           >

 This uses f-strings, and so requires python version 3.6 or higher.
 It was tested with version 3.9.1.

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

# ---- Node --------

class Node:
    """ one node in a linked list """
    # Here a 'node' is just a container to hold three properties :
    #   .next  : the next node in the chain (or None if there isn't one)
    #            a "forward" link in the chain :  this_node => next_node
    #   .prev  : the previous node in the chain (or None if there isn't one)
    #            a "backward" liink :   prev_node <= this_node
    #   .value : some sort of data attached to this node
    
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None
        
    def __str__(self):
        id_self = hex(id(self))
        id_prev = hex(id(self.prev)) if self.prev else 'None'
        id_next = hex(id(self.next)) if self.next else 'None'
        return f"<Node value={self.value}" + \
               f" prev={id_prev:14} id={id_self} next={id_next:14} >"

# ---- size functions - recursive and iterative ------------
    
def size_recursive(node):
    """ return size of linked list from this node forward, recursively """    
    # i.e. implemented by calling this same function again.
    if node == None:
        return 0
    else:
        return 1 + size_recursive(node.next)

def size_iterative(node):
    """ return size of linked list from this node forward, iteratively """
    # i.e. with an iterative explicit loop
    count = 0
    while node:
        count += 1
        node = node.next
    return count

def size(node, how='iterative'):
    """ return size of linked list from this node forward """
    return size_iterative(node) if how=='iterative' else size_recursive(node)

# ---- LinkedList ------------------------

class LinkedList:
    """ a doubly linked list """
    # This class holds the begin and end elements of the list,
    # and methods to manipulate both node objects and the values within them.
    #
    # The convention I'm using is that the nodes are arranged left-to-right,
    # with the leftmost also called "begin" and the rightmost also called "end".
    # As a doubly linked list, the nodes can be found either by moving
    # forward through the .next pointers from begin to end, left-to-right,
    # or backward through the .prev pointers from end to begin, right-to-left.
    
    def __init__(self):
        self.begin = None
        self.end = None
        self.length = 0

    def __len__(self):
        return self.length
        
    def is_empty(self):
        return self.begin == None
    
    def push_end(self, node):
        """ add a node to the end the list """
        # Since this only modifies at most 2 nodes, this is O(1).
        if self.is_empty():
            self.begin = self.end = node
        else:
            self.end.next = node    #  ... => self.end => node  # forward links
            node.prev = self.end    #  ... <= self.end <= node  # reverse links
            self.end = node         #  reset end
        self.length += 1
            
    def push_begin(self, node):
        """ add a node to the start of the list """
        # Since this only modifies at most 2 nodes, this too is O(1).
        if self.is_empty():
            self.begin = self.end = node
        else:
            self.begin.prev = node  #  node <= self.begin <= ... # back links
            node.next = self.begin  #  node => self.begin <= ... # forward links
            self.begin = node       #  reset start
        self.length += 1

    def push_end_value(self, value):
        """ create a node with given value; add to end of the list """
        self.push_end(Node(value))
        
    def push_begin_value(self, value):
        """ create a node with given value; add to start of the list """
        self.push_begin(Node(value))

    def pop_end(self):
        """ remove and return the (rightmost) end node """
        if not self.end:
            return None
        else:
            self.length -= 1
            # Lots of link bookkeeping ...
            popped = self.end
            self.end = popped.prev
            if self.end:
                self.end.next = None
            else:
                self.begin = None     # handle case where list is now empty
            popped.prev = None
            return popped

    def pop_begin(self):
        """ remove and return the (leftmost) begin node """
        if not self.begin:
            return None
        else:
            self.length -= 1
            # Lots of link bookkeeping (again) ...
            popped = self.begin
            self.begin = popped.next
            if self.begin:
                self.begin.prev = None
            else:
                self.end = None        # empty list; must set end correctly
            popped.next = None
            return popped

    def pop_begin_value(self):
        return self.pop_begin().value

    def pop_end_value(self):
        return self.pop_end().value
    
    def insert_after(self, new_node, node):
        """ insert a new node into the list after a given node """
        # An O(1) operation.
        # Assumes that node is already in this linked list,
        # so we can't use this on an empty list.
        # The links that need to be rearranged are :
        #   2 previous links :   (node => old_next) , (node <= old_next)
        #   4 new links :        (node => new), (node <= new)
        #                        (new => old_next), (new <= old_next)
        # Even more bookkeeping.
        self.length += 1
        old_next = node.next
        node.next = new_node                      #  node => new
        new_node.prev = node                      #  node <= new
        new_node.next = old_next                  #  new  => old
        if old_next: old_next.prev = new_node     #  new  <= old
        if self.end == node: self.end = new_node
        
    def find(self, value):
        """ return the node with the given value, or None if not found """
        # implemented by walking backwards through list from end
        # ... rather than walking foward, just to be different. ;)
        # An O(n) operation since it must walk chain of nodes.
        if not self.is_empty():
            node = self.end
            while (node):
                if node.value == value: return node
                node = node.prev
        return None
    
    def __str__(self):
        """ return as a string e.g. '(1 2 3)'"""
        # implemented by walking foward through the list with .next in a loop
        # An O(n) operation since it walks the chain of nodes.
        if self.is_empty():
            return '()'
        else:
            result = '('
            node = self.begin
            while node:
                result += str(node.value) + ' '
                node = node.next
            return result[:-1] + ')'

    def details(self):
        """ return string giving details of the list and its nodes """
        result = f"Linked list with length {self.length} : \n"
        node = self.begin
        while node:
            result += f"  {node}\n"
            node = node.next
        return result

def new_counting_list(size):
    """ returned a LinkedList with integer values 1, 2, ..., size """
    the_list = LinkedList()
    for i in range(1, size+1):
        the_list.push_end_value(i)
    return the_list

# ---- testing framework (adhoc; similar to what Perl does) --------------

test_printing = [True]      # global state variables!
test_results = []           # (which I usually avoid)
def init_tests(verbose=True):
    test_printing[0] = verbose
    test_results = []
    
def ok(boolean, message):
    """ print 'ok' or 'NOT OK' for one True/False test """
    # The idea here is that "ok" means one passed test;
    # see for example https://perldoc.perl.org/Test::Simple .
    # What can I say? I used to code in perl a lot ...
    ok_or_not = {True: 'ok ', False: 'NOT OK '}
    if test_printing[0]: print(f"{ok_or_not[boolean]:8}{message}")
    test_results.append(boolean)

def tests():
    """ Check to see if all the tests pass; print stuff if something fails. """
    run_tests(verbose=False)
    if not all(test_results):
        print()
        print(f"Failed {test_results.count(False)} " +\
              f"of {len(test_results)} tests : ")
        run_tests(verbose=True)
        print()

def run_tests(verbose=True):
    """ Run the tests, with or within printing """
    init_tests(verbose)

    ok(1==2, '1 == 2')    # This test fails on purpose, just so we see 'em all.
    
    numbers = new_counting_list(4)    
    ok(numbers.begin.value == 1,           'begin value of (1 2 3 4) is 1')
    ok(numbers.end.value == 4,             'end value of (1 2 3 4) is 4')    
    ok(str(numbers) == '(1 2 3 4)',        'linked list __str__ method')

    two = numbers.find(2)
    numbers.insert_after(Node(2.5), two)
    ok(two.value == 2,                     'find node with given value')
    ok(str(numbers) == '(1 2 2.5 3 4)',    'insert after')

    root  = numbers.begin
    ok(size_recursive(root) == 5,          'size recursive')
    ok(size_iterative(root) == 5,          'size iterative')

    start = numbers.pop_begin()
    ok(str(numbers) == '(2 2.5 3 4)',      'pop begin leaves rest')
    ok(start.value == 1 and
       start.prev == None and
       start.next == None,                 'pop begin gives correct bare node')
    
    end = numbers.pop_end()
    ok(str(numbers) == '(2 2.5 3)',        'pop end leaves rest')
    ok(end.value == 4 and
       end.prev==None and
       end.next==None,                     'pop begin gives correct bare node')

    ok(numbers.find(2.5).value == 2.5,     'find still works after pop_end')
    
    singlet = new_counting_list(1)
    singlet.pop_end()
    ok(len(singlet)==0 and
       singlet.begin == None and
       singlet.end == None,                'pop_end to empty list')

    singlet = new_counting_list(1)
    singlet.pop_begin()
    ok(len(singlet)==0 and
       singlet.begin == None and
       singlet.end == None,                'pop_begin to empty list')

# -- main -----------------------------------
    
def main():
    tests()
    numbers = new_counting_list(3)
    print(numbers.details())

# Run main() for "python linked_list.py" but not "import linked_list".
if __name__ == '__main__':           
    main()