I am very confused by the Assignment2 handout, what should we do in Part1?? Any suggestion??
Btw, I am also worried about how our slogs will be marked? Since the handout says we are also going to be marked on our interactions with other classmates, we need to comment and reply to comments. I am actually looking my friends' slogs but I never left a comment. I suppose now I should start to comment :P
Anyway...
I will say the way to build LinkedList with the help of LListNode is not very difficult since we've implemented tree and LinkedList class already, and the logic to write methods is pretty much the same. But I didn't finish lab on time, and this is because of only one method for LinkedList that I didn't pay attention to in last week's lecture -- "__getitem__"
So I am going to focus on Wrapper & Helper, and the "__getitem__" method followed by three very logic-similar methods from lab: "__setitem__"," __delitem__", and "insert".
LinkedList with LListNode:
I was wondering why we learn LinkedList immediately after the tree but it seems more like a list or Stack. This week we construct LinkedList in a new way -- as nodes with a value and a reference to other nodes. I think this LListNode & LinkedList structure is more like a tree.LinkedList(3, LinkedList(2, LinkedList(1, LinkedList(0, LinkedList()))))
LListNode(3, LListNode(2, LListNode(1, LListNode(0))))
'3 -> 2 -> 1 -> 0 -> None'
Wrapper & Helper:
We've seen helper functions in CSC108 last semester, at that time, we only write function A in global scope and call A in a global scope function B. The function A can be the helper function for any function in global scope. If two or more functions used the same computation, then the helper function can be computation function, and those functions can just call function A for their own use.In this week's lecture, we learned to write the function A within function B, then the function A is in a nonlocal scope of function B. Therefore, the function A can only be the helper function for function B. Both kind helpers can be used in our programming, but I suppose the second kind will be more common in our class construction. Since we will try to avoid build an extra method for our class in order to let our type make sense.
Wrapper seems like a very new stuff, but we already learned in CSC108 as well. For example, there are three functions A, B, C. We will can only reach C by B, B by A.
A -> B -> C: then B is the wrapper function for C, helper function for A.
Now we give the formal definition for wrapper: a method that acts as a middleman between a caller and a helper method, often making the method easier or less error-prone to invoke.
I think wrapper here is not well-defined. I would see wrapper as "a function that acts as a middleman....", since we can consider method as a special function that only applies to a certain type. Since wrapper can be used in functions as well.
__getitem__:
There is one more method for LinkedList that first come up in a ADT: __getitem__(self: 'LinkedList', ind: int) -> object. This method takes an index parameter and returns the corresponding item in the LinkedList. I am only going to talk about the logic here, please see the specific code in the following examples. When I first see a function, I always consider it's special case, it's normal case and in what condition it fails.First, let's consider the simplest case. It is when index is 0, we return the head of the LinkedList. This is very easy to achieve by returning self.head.
Second, we are going to handle a complicated case. Now, we use recursion. Since every LinkedList has only one rest and self.head is very easy to find, we think of returning the (n-1)-th self.rest.head for the n-th self.rest. For example, for the ind = 3 we will return self.rest.rest.head.
"return self.rest.__getitem__(ind - 1)"
Then, when the function fails?? Since we cannot search for item in an empty LinkedList and LinkedList cannot be indexed backwards. If the LinkedList is empty and when the index is negative, the functions fails and we raise IndexError.
__setitem__:
def __setitem__(self: 'LinkedList', ind: int, val: object) -> None:
"""Replace element at position ind by val.
Raise exception if ind is out-of-range.
"""
if self.empty or ind < 0:
raise IndexError
elif ind > 0:
self.rest.__setitem__(ind - 1, val)
else:
self.item = val
__delitem__:
def __delitem__(self: 'LinkedList', ind: int) -> None:
"""Remove item at position ind, shifting every item
after that down by 1. Raise an exception if
ind is out-of-range.
"""
if ind < 0 or self.empty:
raise IndexError
elif ind > 0:
self.rest.__delitem__(ind - 1)
else:
self.decapitate()
insert:
def insert(self: 'LinkedList', ind: int, val: object) -> None:
"""Insert val at position ind, shifting the current occupant
and all subsequent indices up by 1. Raise an exception
if ind is out-of-range.
"""
if ind < 0 or (ind > 0 and self.empty):
raise IndexError
elif ind > 0:
self.rest.insert(ind - 1, val)
else:
self.prepend(val)
* We see these three functions use the exactly same logic as __getitem__, the only difference between them is the last line - Base Case. So we see Base Case is the one that determines what the function actually does and recursive steps are only apply the same operation nested and over and over again.
These are what I benefited most from this week's lecture and lab. Every function is important, I think I will be careful next week try not to skip anything in lecture's materials.
Hope everyone is doing well in Assignment 2, and please help me if you have any good suggestion~~
See you next week~
No comments:
Post a Comment