#!/usr/bin/python3
"""Demonstration linked list reversal code in Python.

Shows three approaches, all functional rather than imperative.

Slightly cleaned up.

Probably better to read this code first with comments hidden if you
have the option.

"""

class Nil:
    "A list is either nothing (Nil) or a pair."
    def __str__(self):
        return '[]'

class Pair:
    "A pair is a list that has a first item and the rest; the rest is a list."
    def __init__(self, item, rest):
        self.item, self.rest = item, rest
    def __str__(self):
        return '%s :: %s' % (self.item, self.rest)

def append(a, b):
    "Returns list 'a' appended to list 'b'."

    # If list 'a' is empty, the result is 'b'.
    if isinstance(a, Nil):
        return b

    # But if list 'a' has a first item, the result is a list whose
    # first item is that same first item, and of which the rest is the
    # rest of 'a' appended to b.
    return Pair(a.item, append(a.rest, b))

    # Recursion well-foundedness argument: this function recurses the
    # same number of times as there are items in list 'a', which we
    # hypothesize is not infinite, because it does not recurse when
    # list 'a' is empty, and when it does recurse, it recurses with an
    # 'a' that is one item shorter.
 
def reverse(lst):
    "Returns list 'lst' backwards."

    # The empty list backwards is still empty.
    if isinstance(lst, Nil): return Nil()

    # But if 'lst' has a first item, 'lst' backwards is the rest
    # backwards, followed by that first item.
    return append(reverse(lst.rest), Pair(lst.item, Nil()))

    # The recursion well-foundedness argument is the same as for
    # 'append'.  This takes quadratic time: in calling 'reverse' on a
    # list of 5 items, we will have 5 recursive calls to 'reverse',
    # calling 'append' on lists of respectively 4, 3, 2, 1, and 0
    # items, and this will result in a total of 10 recursive calls to
    # append.  Because there is a much faster way to do this, this
    # algorithm is generally considered bad.
    
def reverse_fast(a, b=Nil()):
    "Returns list 'a' backwards appended to list 'b', in linear time."

    # If list 'a' is empty, then list 'a' appended to list 'b' is just
    # list 'b'.
    if isinstance(a, Nil): return b

    # Otherwise, it's the rest of list 'a' backwards appended to the
    # first item of 'a' followed by 'b'.
    return reverse_fast(a.rest, Pair(a.item, b))

    # You could think of list 'b' as being an output list that's being
    # built up node by node.  The in-place algorithm you wrote works
    # exactly the same way except that it recycles the node at 'a'
    # instead of allocating a new one.

def reverse_nonrecursive(a):
    "Translation of the tail-recursion in reverse_fast to explicit iteration."
    b = Nil()
    while not isinstance(a, Nil):
        b = Pair(a.item, b) # allocating new Pair here
        a = a.rest
    return b
    # Because we allocate new objects in a loop that can run an
    # unlimited number of times, this is not in-place or
    # constant-space, which are the same thing as far as I'm
    # concerned.  This function is not purely functional because,
    # although it doesn't mutate pairs, it does mutate its own local
    # variables.


# In the OO paradigm all of the above is unclean, because we're using
# isinstance checks.  The OO way to do this is to do your type testing
# with method dispatch.  Here's an OO translation of most of the above
# that's still purely functional, because it doesn't use any mutation:

class Noo:
    "Nil, object-oriented."
    def __str__(self):
        return '[]'

    def append(self, other):
        return other

    def reverse(self):
        return self

    def reverse_fast(self, other=None):
        return Noo() if other is None else other

class Poo:
    "Pair, object-oriented."
    def __init__(self, item, rest):
        self.item, self.rest = item, rest

    def __str__(self):
        return '%s :: %s' % (self.item, self.rest)

    def append(self, other):
        return Poo(self.item, self.rest.append(other))

    def reverse(self):
        return self.rest.reverse().append(Poo(self.item, Noo()))

    def reverse_fast(self, other=Noo()):
        return self.rest.reverse_fast(Poo(self.item, other))
    

if __name__ == '__main__':
    x = Pair(1, Pair(2, Pair(3, Nil())))
    print(x)
    print(reverse(x), 'reversed')
    print(reverse_fast(x), 'reversed')
    print(reverse_nonrecursive(x), 'reversed')
          
    y = Poo(1, Poo(2, Poo(3, Noo())))
    print(y)
    print(y.reverse(), 'reversed')
    print(y.reverse_fast(), 'reversed')