Homework 2: Still needs map function

3 files changed, 637 insertions, 0 deletions

diff --git a/cmpsc132_homework_1-1.py b/hw1/cmpsc132_homework_1-1.py
index a451474..a451474 100644
--- a/cmpsc132_homework_1-1.py
+++ b/hw1/cmpsc132_homework_1-1.py
diff --git a/hw2/assignment_lists_f22-1(possible solutions).py b/hw2/assignment_lists_f22-1(possible solutions).py
new file mode 100644
index 0000000..4b9048e
--- /dev/null
+++ b/hw2/assignment_lists_f22-1(possible solutions).py
@@ -0,0 +1,309 @@
+# -*- coding: utf-8 -*-
+"""assignment-lists-f22.ipynb
+
+Automatically generated by Colaboratory.
+
+Original file is located at
+    https://colab.research.google.com/drive/1x6L0YQtnlu96uhVtx4vXaPQIWLSICCZ6
+
+### 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 __repr__(self):
+        return str((self.element, self.next_node))
+
+"""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.next_node
+        for i in range(self.__size): 
+            out += f"({node.element}), "
+            node = node.next_node    
+        return out[:-2]+')'
+
+    def __iter__(self):
+        """Standard python iterator method"""
+        self.__current = None
+        return self
+      
+    def __next__(self):
+        """Standard python iterator method"""
+        if self.is_empty():
+          raise StopIteration()        
+        #beggingin
+        elif self.__current is None:
+          self.__current = self.__header
+        #midds
+        self.__current = self.__current.next_node
+        #endo
+        if self.__current == self.__trailer:
+          raise StopIteration()
+        else:
+          return self.__current
+      
+      
+    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"""
+        pass
+    def get_last(self):
+        """Get the last element of the list"""
+        pass
+    def get_previous(self, node):
+        """Returns the node before the given node"""
+        pass
+    def get_next(self, node):
+        """Returns the node after the given node"""
+        pass
+    def add_before(self, new, existing):
+        """Insert the new before existing"""
+        previous = existing.previous_node 
+        previous.next_node = new
+        new.previous_node = previous
+        new.next_node = existing 
+        existing.previous_node = new
+        self.__size += 1
+      
+    def add_after(self, new, existing):
+        """Insert the new after existing"""
+        pass
+    def add_first(self, new):
+        """Insert the node at the head of the list"""
+        pass
+    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"""
+        pass
+
+"""**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))
+
+for node in dL: 
+  print(f"NODES: {node}")
+  
+print(f"136: {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`.
+"""
+
+# 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)$.
+"""
\ No newline at end of file
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)$.
+"""