## Class Recordings

 Week 12 Monday Wednesday No Friday - Thanksgiving Week 13 Monday Wednesday Friday

## Announcements

• Lab 10 is due TONIGHT.

• Lab 11, the final lab, is out now!

• Quiz 5 this Friday, study guide available now.

• Hackathon coming up on campus this weekend.

## Week 12 Topics

• Wrap-up Recursion

• Object-Oriented Programming

• Defining Classes

• The implicit self parameter

• Class methods

• The constructor, `init`

• String conversion, `str`

• Access methods (getters)

• Mutator methods (setters)

## Monday

### Merge Sort

So far, most of the recursion problems we’ve seen could have been solved just as easily (or even more easily) with iteration. Next, we’ll consider a famous sorting algorithm, merge sort, that naturally uses recursion.

### Recursive graphics

Finally, let’s look at a (yet another) attempt to draw trees using the graphics library. This time, we’ll draw the branches of a tree recursively!

### Objects Overview

So far, we have used lots of objects and their methods. Remember an object consists of both data and methods — an object knows stuff and can do stuff. Here are some examples of objects we have used:

• str objects: data = characters in the string. Methods: `split()`, `lower()`, etc.

• list objets: data = items in the list. Methods: `append()`, `pop()`, etc.

• Zelle Circle objects: data = radius, center point, fill color, etc. Methods: `draw()`, `move()`, `setFill()`, `getCenter()`, etc.

• Donation objects

Today, consider the task of managing some pizza orders. Each pizza you make has a number of slices and a topping (unless it is plain). The pizza can be cooked or not. Things we might want to do with a pizza include adding a topping, making the pizza, and serving a slice (as long as the pizza has already been made).

Using what we know so far, writing a pizza program would first need to establish the data, e.g.:

``````pizza1 = ["plain", 8, True]  # True represents that it has been cooked
pizza2 = ["pepperoni", 6, True]
pizza3 = ["mushroom", 8, False]
pizzas = [pizza1, pizza2, pizza3]``````

Now, let’s say we want to order a slice:

``````pizza = input("Which pizza do you want? ")
for i in range(len(pizzas)):
if pizzas[i][0] == pizza:
if (pizzas[i][2] and (pizzas[i][1] > 0)):
pizzas[i][1] -= 1
print("Here is your slice of %s pizza.  There are %d slices left."
% (pizza, pizzas[i][1]))``````

We could extend this to add data and other functionality. However, this isn’t a very satisfying solution. The code will quickly get unwieldy, becoming susceptible to bugs. It also isn’t easy to read, or reuse for a different application. We will return to the concept of object-oriented programming to come up with a better solution.

### Classes and Object-Oriented Programming

In object-oriented programming, we saw that objects described complex types that contained data and methods that could act upon the data. For example, we saw that lists and strings were objects, as were elements of the Graphics library. Each of the objects we created stored data (e.g., a center, radius and color for `Circle` objects) and methods (e.g., `move()`, `getCenter()`, `setFill()`).

Classes are the types of an object; they define the specific methods and data an object stores. We will spend the next two weeks defining classes and creating objects from them. To start, we’ll consider a class definition to solve the problem above.

Open up `pizza.py`. Read through the mostly completed class definition for a pizza. Using this class, we will be able to define `Pizza` objects.

### Defining a Class

Open up `pizza.py`. What do you think each line is doing? What can you explain with your neighbor?

The first key element is the class definition, which follows the format:

``class ClassName(object):``

`ClassName` is a placeholder for the actual name you want to give; `class` is a keyword to indicate that you are defining a new class. The additional item, `(object)`, is an indication that the class will follow certain protocols. You should assume that this will always be there (you can put something else in there if you want to build upon an existing class, but that is beyond our discussion).

#### Methods

Within the class, you will see several class methods. Methods follow the same format as functions, but have the distinction of belonging to a specific class.

``````class ClassName(object):
def __init__(self, param1, ...):
#Constructor - initializes object and data

def getter1(self):
#Return some piece of information

def setter1(self, valToSet):
#Change something about the data``````

Two broad categories of methods are accessors (or getters) and mutators (or setters). Some methods do both. Methods are the primary method for interfacing with the data maintained within the class - we do not directly touch the data, but rather use methods to get/set information. This aspect of classes is critically important: Defining a class allows you to hide the details of how the class works and how it stores its underlying data. The class provides an interface (methods) for users of the class.

For example, consider lists. When we want to add a value to the end of the list, we do not directly access the data within the list. Rather, we use the `append(x)` method which handles that work for us.

Python also has special built-in methods that are flanked by underlines e.g., `init()`. `init` gets called whenever we call the constructor to create a new object. For example, when creating a `Point` object:

``pt = Point(x,y)``

#### Constructor

Python will run the `init(self,x,y)` method of the `Point` class. Every class must have a constructor — it specifies the initial data we need to keep track of and gives it a starting value. There are many other special methods that we will not cover right now. These include `len` (to obtain the length of a sequence e.g., `len(ls)` calls the `list.len()` method) and `str` (to convert an object to a string representation, `str(x)`).

#### self parameter

`self` is perhaps the single most confusing feature of python classes. You will see `self` everywhere when you are writing and designing a class. However, you will not see `self` at all when using a class, which is why we haven’t talked about it until this week.

Notice that all methods in a class have a `self` parameter as the first parameter. This is required, but users of the class do not provide this argument; instead Python automatically assigns the object that called the method as the `self` parameter. For example, if we create a `Pizza` object, `pizza` and call `pizza.serveSlice()`, the `self` parameter points to `pizza`. This is common source of confusion when writing your first class. If you look at the definition of `serveSlice(self)`, it looks like you need to pass in one argument for the self parameter. But since python does this automatically, users actually call this method with zero arguments, e.g., `pizza.serveSlice()`. Calling `serveSlice` with an extra argument will result in a seemingly bizarre error message:

```yum.serveSlice(1)
TypeError: serveSlice() takes exactly 1 argument (2 given)```

Note that providing one user argument to `serveSlice()` reports an error that two arguments were provided. The automatic `self` was the other (and technically first) argument.

In summary, always put `self` as the first parameter of a class method when writing a method, but ignore this parameter when calling the method.

## Wednesday

#### The meaning of self

You may be wondering: if `self` is part of every method, but it’s ignored by the user, why do we need it in the class definition? Recall that objects both know stuff and do stuff. The method definitions inside the class are how classes/objects do stuff, and the `self` variable is how a particular object knows stuff. In any method, we can declare a variable with a `self.` prefix, e.g., `self.cooked=False`. If we set the value of one of these special `self.` attributes in one method, we can access the value in another method without passing an additional parameter. In effect, all methods share all the `self.` attributes.

Typically we use the `init` method to define and initialize values for all attributes we will be using at some point in the class.

### Pizza class

Test out how the `Pizza` class works. What is the output of each of these commands, and can you draw the stack diagram that accompanies it?

```>>> from pizza import *
>>> pizza = Pizza("mushroom")
>>> print(pizza)
>>> pizza.makePizza()
>>> pizza.serveSlice()
>>>```

### Testing a Class

Just as with top-down design, you should practice incremental development when defining a class. Usually, this involves writing a function, thoroughly testing it, moving onto the next function, etc. There are several options for how to test, including using a separate main program. However, a common strategy is to include some test code at the bottom of your class definition file. This way, the test code can always be run in the future when updates are made. To do so, remember to include the following lines at the bottom of your file:

``````if __name__ == "__main__":
# Write testing code here``````

The first line ensures that the testing code does not run when you import the file, but rather only when someone calls the file from the command line:

`\$ python3 pizza.py`

#### Objects, scope, and internal method calls

Inside a class definition, the object is referred to as `self`. If we want to access its data, we use dot notation e.g., `self.cooked` is that records whether or not a pizza is cooked. The `cooked` variable’s scope is the object itself rather than the function it was originally defined in.

Similarly, from within a method of a object, you can call another method by referring to the `self` variable. For example, if a class has two methods, `method1(self, …​)` and `method2(self, …​)`, you can call `method1` from within `method2`:

``````class Thing(object):
def method1(self, x, y, z):
...

def method2(self, ...):
...
self.method1(a, b, c)  # Call method1() on self from within method2
...``````

## Week 13

### Selection Sort

Lab 11 asks you to perform a "selection sort". Here’s the pseudocode for selection sort:

``````def selection_sort(lst):
for each position i in the list:
# keep track of the index with the smallest value
min_index = i

for each position j to the right of i in the list:
if the element at position j is smaller than the element at position min_index:
min_index = j

swap the elements at positions i and j``````

How can we analyze the running time of this algorithm?

### Exercises: Implement Pizza class and test

1. Take some time to implement and test the `addTopping()` method. For now, only allow one topping per pizza. Also, make sure the pizza hasn’t yet been cooked.

2. Analyze and test the `serveSlice()` function. What needs to happen before a slice can be served?

3. Implement and test a `removeTopping()` function, which removes the topping if the pizza hasn’t yet been made.

4. If you have time, modify the Pizza class to allow for multiple toppings. How does this change the data in the Pizza class? How would this change the methods?

### Exercise: Team class

Implement a class called `Team` that stores and manipulates information about a competitive team (e.g., soccer, debate, baseball). Each team keeps track of its name, year, city, wins, and losses. In addition:

• The constructor should take parameters for the name, year, and city. It should initializes the number of wins and losses to 0.

• Write a method to create a string summarizing the team’s data (e.g., "2018 Wolverines: 12 wins, 0 losses")

• Include a getter for each data member

• Have a method `wonGame` that increments the team’s number of wins by 1.

• Similarly, have a `lostGame` that updates the number of losses.

• Write a method, `getWinPercent` that returns the percentage of games won out of the total number of games played. If a team has played 0 games, return a winning percentage of 0.0. If a team has won 3 out of 4 games, return a winning percentage of 0.75

### Exercise: League class

Implement a `League` class that stores information about many teams. It should contain methods to:

• Add a team to the league.

• Find a team by name (you can assume names are unique) and return the matching team object, if there is one.

• Print a leaderboard of teams, sorted from most wins to least. Use selection sort to rank the teams.

• Bonus: remove a team from the league.