Class Notes Week 14


Topics

Monday Wednesday Friday


Recap

Last week, you created a Counter class to represent a simple counter. You also worked on modifying the Counter class to create a "wrap-around" counter.

Counter class:

The challenging part of this implementation is getting increment() to work correctly. We need to change the value so that when it exceeds high, it "wraps around" to low and continues incrementing. Let's modify the increment() method so it returns the number of times it wraps around.

def increment(self, value):
  self.value = self.value + value

  # subtract while we're too high
  count = 0
  diff = self.high - self.low + 1
  while self.value > self.high:
    self.value = self.value - diff
    count = count + 1
return count

Objects within objects

Another advantage of classes and objects is that they promote code reuse. Because an object encapsulates both a collection of data and methods to manipulate and access that data, they are often easy to reuse for different purposes. You saw an example of this last week with the aquarium exercise. Each Fish object contained a list of graphics objects representing the different parts of the fish. To move a fish, you iterated through the fish parts, moving each graphics object one at a time. Then, you didn't need to worry about each individual fish part; instead you could move the entire fish at once.

Let's use the Counter class to easily define a Clock class to represent time. A clock has hours, minutes, and seconds. For this implementation, we'd like to be able to add time and to display the current time.

Exercise

In clock.py, we've given you a partial implementation of a Clock class that uses Counter objects to represent hours, minutes, and seconds. Implement the addTime(self, seconds) method, which adds a number of seconds to the current time. For example, if the current time is 11:19:30, and you add 95 seconds, the new time should be 11:21:05.


Data Structures

As programs get larger and more complex, they will need to handle more and more data. Programs need to access data in a way that is both easy to use and reasonably fast. A data structure is a collection of data values, along with the functions that can be applied to the data.

Understanding how to store data in a way that makes access/updating efficient is topic that could take multiple semesters to fully understand. It is the primary topic of CS35.

An abstract data type (ADT) is a description of what data is being stored and what functions can be applied to the data, without describing/defining the underlying implementation. An ADT specifies the interface to a data structure without defining the implementation.

Example: maintaining winners

Imagine you are a dog enthusiast, interested in tracking the winning breeds in various dog shows. You maintain a set of dog breeds, with the number of times each breed has won a competition. It would be nice to write a program to help you manage your ever expanding data collection. An example list may look as follows

Cavalier King Charles Spaniel, 2
Pembroke Welsh Corgi, 2
Cardigan Welsh Corgi, 0
Labrador Retriever, 1
Golden Retriever, 4
...

As you collect more stats, you'll need to change the numbers for certain breeds, or add new breeds. If a winner is later disqualified, you may occasionally need to remove dog breeds from your list. You'll also need to search through your winners to find breeds and perhaps create summary reports to share with friends.

The Dictionary ADT

A dictionary is a data structure that stores (key, value) pairs and supports the following operations:

For example, to add a new breed to a Dictionary called winners, you might want to winners.insert("Pug", 3).

Exercise:

On pen and paper, sketch out an implementation of the Dictionary ADT that uses Python lists to store the data. How would you search for a key/value pair by key? How would you insert a key/value pair? How would delete work?


Python dictionaries

The Dictionary ADT is common enough that Python has provided a built-in dictionary data type for you (although the interface we've described above.

Creating a dictionary. To create a dictionary in Pyhton, use curly braces {,}.

dogs = {}  # creates an empty dictionary
winners = {"Corgi": 2, "Cavalier": 1}  # initialize a dictionary

Searching a dictionary.

Accessing key/value pairs in a Python dictionary has syntax similar to list indexing. The difference is that instead of an integer e.g., ls[i], you "index" using the key.

winners["Corgi"]
print("%d Corgi winners" % (winners["Corgi"]))
print("%d American Foxhound winners" % (winners["American Foxhound"]))
...

What happens if a key does not appear in the dictionary? You can check if a key is in a dictionary using the <key> in <dict> syntax, e.g., "Corgi" in winners

Adding key/value pairs.

To insert a key/value pair into your dictionary, also use Python syntax

winners["Whippet"] = 6

Removing key/value pairs.

Use the del command to remove a key/value pair from the dictionary.

print(winners)
del winners["Corgi"]
print(winners)