path: root/hw2/assignment_lists_sp23.py

# -*- coding: utf-8 -*-
"""
### Doubly Linked List

The purpose of this assignment is to make you familiar with implementing a data structure in Python in an object oriented way.
During lectures we implemented a few simple linear data structres: queue, list, deques, stacks. Now we expect you to implement one of these structures yourself.

You are provided with two classes: **Node** and **DoublyLinkedList**. The first one is already implemented (you don't need to modify it), the second one consist only a structure of empty methods defined. Your task is to come up with an implementation of these methods.

_Note_: If a list is doubly linked, each node contains a reference to the _previous_ node in the chain and a reference to the _next_ node.

You are expected to implement every function in DoublyLinkedList. Including the *next()* function, which is used by an iterator object in python. The *map(func)* function applies a function to every element in the list.
All other functions are available in the PSADS book.

## Constructing a Doubly Linked List

The **Node** class implementation is already given:
"""

class Node(object):
    """Doubly linked node which stores an object"""

    def __init__(self, element, next_node=None, previous_node=None):
        # The underscores are to prevent overwriting the variables if inherited and prevents access from outside of scope
        self.element = element
        self.next_node = next_node
        self.previous_node = previous_node

    def get_next(self):
        return self.next_node

    def get_previous(self):
        return self.previous_node

    def set_next(self, new):
        self.next_node = new

    def set_previous(self, new):
        self.previous_node = new

    def get_element(self):
        return self.element

    def __repr__(self):
        return str((self.element, self.get_next()))

"""The following code snippet is a constructor provided by the **DoublyLinkedList** Python class for the creation of a new doubly linked list. **Extend the snippet below with your implementation of the DoublyLinkedList**. """

class DoublyLinkedList(object):
    """Doubly linked node data structure"""
    def __init__(self):
        self.__size = 0
        self.__header = Node('Header')
        self.__trailer = Node('Trailer')
        self.__header.next_node = self.__trailer
        self.__trailer.previous_node = self.__header
        self.__current = None

    def __repr__(self):
        """This needs to work in order to pass the assertions below"""
        out = '('
        node = self.__header.get_next()
        for i in range(self.__size):
            out += f"({node.get_element()}), "
            node = node.get_next()
        return out[:-2]+')'

    def __iter__(self):
        """Standard python iterator method"""
        self.__current = None
        return self

    def __next__(self):
        """Standard python iterator method"""
        if self.__current is None:
            self.__current = self.__header

        if self.__current.next_node is self.__trailer:
            raise StopIteration

        self.__current = self.__current.next_node
        return self.__current

    def map(self, function):
        """Run function on every element in the list"""
        for n in self:
            n.element = function(n.element)

    def size(self):
        """Returns the number of elements in the list"""
        return self.__size

    def is_empty(self):
        """Returns the number of elements in the list"""
        return self.size() == 0

    def get_first(self):
        """Get the first element of the list"""
        node = self.__header.next_node
        if node != self.__trailer:
            return node

    def get_last(self):
        """Get the last element of the list"""
        node = self.__trailer.previous_node
        if node != self.__header:
            return node

    def get_previous(self, node):
        """Returns the node before the given node"""
        return node.previous_node

    def get_next(self, node):
        """Returns the node after the given node"""
        return node.next_node

    def add_before(self, new, existing):
        """Insert the new before existing"""
        prev = self.get_previous(existing)
        prev.next_node = new
        new.previous_node = prev
        new.next_node = existing
        existing.previous_node = new
        self.__size += 1

    def add_after(self, new, existing):
        """Insert the new after existing"""
        next = existing.next_node
        existing.next_node = new
        new.previous_node = existing
        new.next_node = next
        next.previous_node = new
        self.__size += 1

    def add_first(self, new):
        """Insert the node at the head of the list"""
        self.add_after(new, self.__header)

    def add_last(self, new):
        """Insert the node at the tail of the list"""
        self.add_before(new, self.__trailer)

    def remove(self, node):
        """Remove the given node from the list"""
        prev = node.previous_node
        next = node.next_node
        prev.next_node = next
        next.previous_node = prev
        node.next_node = None
        node.previous_node = None
        self.__size -= 1

"""**Task 1 (5 points)**: Using the constructor from the **DoublyLinkedList**, create a new doubly linked list of integers between 0 and 3."""

dL = DoublyLinkedList()

for i in range(4):
    dL.add_last(Node(i))

print(dL)

assert str(dL) == f"((0), (1), (2), (3))"

"""## Using a Doubly Linked List

The given **DoublyLinkedList** Python class
contains helpful methods for using a doubly linked list.
Answer the following questions while implementing
the methods of the **DoublyLinkedList** class.

**Task 2 (10 points)**: Implement the `size` method that returns the size of a doubly linked list.


"""

#Test your implementation here
print(dL.size())
assert dL.size() == 4

"""**Task 3 (5 points)**: Implement the `is_empty` method that checks
whether a doubly linked list is empty.


"""

#Test your implementation here
print(dL.is_empty())

dL2 = DoublyLinkedList()
print(dL2.is_empty())


assert dL.is_empty() == False
assert dL2.is_empty() == True
del dL2

"""**T4 (10 points)**: Implement the methods `get_first` and `get_last`
to get the first and the last element of the list, respectively.

_Hint_: Return an exception in case the list is empty.

"""

#Test your implementation here
print(dL.get_first())
print(dL.get_last())

assert str(dL.get_first()) == f"(0, (1, (2, (3, ('Trailer', None)))))"
assert str(dL.get_last()) == f"(3, ('Trailer', None))"

"""**Task 5 (10 points)**: Implement the methods `get_previous` and `get_next`
to get the previous and the next node of the list, respectively.

_Hint_: Return an exception in case the list is empty.

"""

#Test your implementation here
print(dL.get_last().get_previous())
print(dL.get_first().get_next())

assert str(dL.get_last().get_previous()) == "(2, (3, ('Trailer', None)))"
assert str(dL.get_first().get_next()) == "(1, (2, (3, ('Trailer', None))))"

"""**Task 6(10 points)**: Implement the methods `add_before` and `add_after`
to respectively insert new elements before and after a node of the list.

"""

#Test your implementation here
dL.add_after(Node(42),dL.get_first())
dL.add_before(Node(34),dL.get_last())

print(dL)
assert str(dL) == f"((0), (42), (1), (2), (34), (3))"

"""**Task 7 (10 points)**: Implement the methods `add_first` and `add_last`
to respectively insert new nodes in the beginning and in the end of a list.

"""

#Test your implementation here
dL.add_first(Node(7))
dL.add_last(Node(-1))
print(dL)
assert str(dL) == "((7), (0), (42), (1), (2), (34), (3), (-1))"

"""**Task 8 (10 points)**: Implement the method `remove` to remove
a node from a list.

"""

#Test your implementation here
dL.remove(dL.get_first())
print(dL.get_first())

assert dL.get_first().get_element() == 0

"""**Task 9 (10 points)**: Implement the method `map` to apply a function on
each element of a list.
"""

#Test your implementation here
### USE THE MAP FUNCTION HERE

g = lambda a: a ** 2
dL.map(g)

print(dL)

assert str(dL) == "((0), (1764), (1), (4), (1156), (9), (1))"

"""**Task 10 (10 points)**: Implement the method `next` to iterate the elements
of a list.


"""

#Test your implementation here
for node in dL:
    print(node.get_element())

dL

"""## Applying methods of the DoublyLinkedList and Node classes

Answer the following questions by using
the implemented methods from the Node and DoublyLinkedList classes.
Apply your operations on the list you created in T1.

**Task 11 (5 points)**: Add 10 to each element of the list of integers in the twenties.

_Hint_: Use the methods `map`. Make a function that return the list of values in the twenties,
it might be used a few times.
"""

# WRITE YOUR CODE HERE
twenties = DoublyLinkedList()
for i in range(20,30):
    n = Node(i)
    twenties.add_last(n)

print(twenties)
assert str(twenties) == "((20), (21), (22), (23), (24), (25), (26), (27), (28), (29))"

##Write more code here to change the DLL
twenties.map(lambda x: x + 10)

print(twenties)
assert str(twenties) =="((30), (31), (32), (33), (34), (35), (36), (37), (38), (39))"

"""
**Task 12 (5 points)**: Multiply each element of the list of integers in the twenties by 5.

_Hint_: Use the methods `map`, `get_previous`, and `set_element`."""
# Subtracting 10 to undo the last question
twenties.map(lambda x: (x - 10) * 5)

# your code here
print(twenties)
assert str(twenties) == "((100), (105), (110), (115), (120), (125), (130), (135), (140), (145))"

"""
**Task 13 (5 points)**: Remove elements that are multiples of 4.

_Hint_: Use the methods `next` and `remove`."""

# Your code here
cur = twenties.get_first()
end = twenties.get_last().next_node # idk why but python is saying there is no attribute __trailer fora dll
while cur != end:
    next = cur.next_node
    if cur.element % 4 == 0:
        twenties.remove(cur)
    cur = next


assert str(twenties) == '((105), (110), (115), (125), (130), (135), (145))'

"""
**Task 14 (5 points)**: Remove elements from the list that are odd numbers.

_Hint_: Use the methods `get_previous` and `remove`."""
cur = twenties.get_first()
end = twenties.get_last().next_node # idk why but python is saying there is no attribute __trailer fora dll
while cur != end:
    next = cur.next_node
    if not (cur.element % 2 == 0):
        twenties.remove(cur)
    cur = next

# Your code here
assert str(twenties) == '((110), (130))'

"""## Proving performance properties

**T15 (5 points)**: Prove when the complexity to delete a node in a doubly linked list is $O(1)$
and $O(n)$.
"""