Homework 2: Still needs map function

1 files changed, 328 insertions, 0 deletions

diff --git a/hw2/assignment_lists_sp23.py b/hw2/assignment_lists_sp23.py
new file mode 100644
index 0000000..57147d9
--- /dev/null
+++ b/hw2/assignment_lists_sp23.py
@@ -0,0 +1,328 @@
+# -*- 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"""
+        return self
+
+    def __next__(self):
+        """Standard python iterator method"""
+        if self.current is None:
+            raise StopIteration()
+
+        result = self.current.data
+        self.current = self.current.next
+        return result
+
+    def map(self, function):
+        """Run function on every element in the list"""
+        pass
+    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
+
+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
+print(twenties)
+assert str(twenties) == "((20), (21), (22), (23), (24), (25), (26), (27), (28), (29))"
+
+##Write more code here to change the DLL
+
+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`."""
+
+# your code here
+print(twentyBy5)
+assert str(twentyBy5) == "((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
+
+assert str(twentyBy5) == '((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`."""
+
+# Your code here
+assert str(twentyBy5) == '((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)$.
+"""