Intro to Computer Science

☰

Unit 6: Additional Data Structures: Dictionaries and Classes

Table of Contents

6.0. Overview

We've used loops and conditionals in writing programs, and an important data structure for that has been the list. Now we're going to consider two additional types of data structures: the dictionary (or hash), in Python referred to as dict, and the class, which will be used to organize objects, part of an important computer science topics, Object-Oriented Programing (OOP).

6.1. Dictionaries

One of the most important data types that we haven't yet discussed is the dict, for "dictionary." Dictionaries are used for manipulating unordered key-value pairs of information.

Let's see what that means.

6.1.0. Review of Lists

Recall that a list is a collection of items, stored in some order, with each element of the list referred to by the name of the list and its index.

6.1.0.1. Example 1. shoppinglist

If shoppinglist = ["apples", "bananas", "cheese", "detergent", "eggs"], then shoppinglist[2] refers to the third element on the list, "cheese".

6.1.0.2. Example 2. contacts

In the Address Book program we kept track of our contacts as a list of lists:

contacts = [["Bush, Jill", "jbush@windwardschool.org", "NA"], ["Fletch", "cfletcher@polytechnic.org","626-666-HELL"], ["Kiely, Owen", "okiely@polytechnic.org","NA"] ]

In this example, the second items on the list, contacts[1] is the list ["Fletch", "cfletcher@polytechnic.org","626-666-HELL"], and the phone number for that contact would be contacts[1][2].

Note that we're keeping track of the name, email, and phone number in a certain order: 0, 1, 2. If I want to get the email for any contact, I'll always be getting the second item on that contacts list, because that's the order that I've decided to use for this program.

6.1.1. Definition of a dictionary

Definition: Dictionary

A dictionary is a data type in Python that is an unordered collection of key-value pairs. Some programming languages refer to a dictionary as a hash table.

An example of a simple dictionary might be this one, which tracks point-values for Scrabble letters:

scores = {"a": 1, "c": 3, "b": 3, "e": 1, "d": 2, "g": 2, "f": 4, "i": 1, "h": 4, "k": 5, "j": 8, "m": 3, "l": 1, "o": 1, "n": 1, "q": 10, "p": 3, "s": 1, "r": 1, "u": 1, "t": 1, "w": 4, "v": 4, "y": 4, "x": 8, "z": 10}

Each value before a colon above is called the "key" a unique value that cannot be shared with any other keys. The value after each colon is the "value" associated with that key—values do not have to be unique.

Once the dictionary scores has been created, we can identify the value of any letter as follows:

>>> print(scores["j"]) 8 >>>

Note that the dict data type stores its key-value pairs in an unordered format:

>>> print(scores) {'w': 4, 'i': 1, 'c': 3, 't': 1, 'x': 8, 'j': 8, 'a': 1, 'p': 3, 'f': 4, 'g': 2, 'h': 4, 'v': 4, 'r': 1, 'k': 5, 'l': 1, 'm': 3, 'b': 3, 'z': 10, 'o': 1, 'u': 1, 'e': 1, 'q': 10, 'd': 2, 's': 1, 'y': 4, 'n': 1} >>>

The only way to reference the "value" is by using its associated, unique key.

word = input("Enter a Scrabble word and I'll tell you its value") word_sum = 0 for letter in word: sum = sum + scores[letter] print("The value of the word is", sum)

6.1.1.1. Example: contacts

In the Address Book program, we could keep track of our contacts as a list of dictionaries:

contacts = [ {"name" : "Bush, Jill", "email" : "jbush@windwardschool.org", "phone" : "NA"}, {"name" : "Fletch", "email" : "cfletcher@polytechnic.org", "phone" : "626-666-HELL"}, {"name" : "Kiely, Owen", "email" : "okiely@polytechnic.org", "phone" : "NA"} ]

In this example, the second items on the contacts[1] list still represents Fletch, but the contact details are referred to by their dictionary key rather than by the index of the list. Fletch's phone number would be referred to by contacts[1]["phone"].

Dictionaries are enormously useful in computer science. Their primary advantage is that, because they don't have to be maintained in any order (like a list is), they can be stored and accessed much more quickly.

6.1.2. Dictionary Methods

There are a number of dict methods that can come in handy:

len(d) # Number of elements in d d[k] # Item in d with key k d[k] = v # Set item in d with key k to v del d[k] # Delete item k from dictionary d d.clear() # Remove all items from dictionary d d.has_key(k) # Return 1 if d has key k, 0 otherwise d.items() # Return a list of (key, value) pairs d.keys() # Return a list of keys in d d.values() # Return a list of values in d d.get(k) # Same as d[k]

5.1.3. Common Use of Dictionaries

A common use of a dictionary is to tabulate frequencies for a series of values.

Trace through this code or try it out on the computer and see how it works.

#!/usr/bin/env python3 """ letter_frequencies.py Keeps track of the number of times each letter appears in a string of text. """ # Get an input string from the user sentence = input("Enter a sentence: ") # Split string up into a list of letters letters = [] for letter in sentence: letters.append(letter.lower()) # Put the letters into a dictonary by frequency count letter_counts = {} for letter in letters: if letter in letter_counts.keys(): letter_counts[letter] += 1 else: letter_counts[letter] = 1 # Print out the results for letter in sorted(letter_counts.keys()): print("{0:15s}|{1:3d}".format(letter, letter_counts[letter]))

Sorting dictionaries by value

Dictionaries aren't designed to be sorted—the reason they're so fast is because their order isn't maintained in the computer's memory—but sometimes you do want to sort them, either in order of their keys or their values.

Here's how you sort a dictionary (by creating a list of key-value pairs):

s = sorted(word_dict.items(), key=lambda word_dict: word_dict[1])

6.1.4. AddressBook, with Dictionaries

Now that we know a little bit about how dictionaries work, let's revisit the addressbook.py program and convert it to use dictionaries instead of lists.

Address Book, with Dictionaries

Get a copy of the Address Book with Dictionaries assignment and use it to create a new version of your Address Book program.

6.2. Object-Oriented Programming: Objects, Classes, Instances

Object-oriented programming is an exceptionally bad idea that could only have originated in California.

--Edsger Dijkstra

6.2.0. Objects, Classes, Instances

Object-oriented programming is a way of analyzing problems and developing program solutions that make use of objects. This is a confusing topic for some people at first—the theory can be a bit abstract—so we’re going to approach it by looking at a series of examples: some examples that you've already seen (perhaps without knowing about it), some abstract but common-sense examples, and then some examples that are more concrete.

You should also know that learning about object-oriented programming is, at first, very much an exercise in vocabulary. Part of learning about OOP is learning how to use a few special terms.

Objects

An object is a "thing" in a programming language—an "entity"—that has both attributes (values that describe the object) and methods (actions that you can do to an object, or behaviors that the object has).

Examples of built-in objects in Python:

In fact, everything in Python is an object.

Okay, so we've got these objects that belong to classes. So what?

Classes

A class is specific group of objects that all share some qualities in common.

Examples:

An instance is a single object from a given class. So every object is an instance of a class.

Examples of various types of classes:

Note that there are no actual classes called Card or Canine built into Python. The cool thing about OOP is that object-oriented programming provides you with the ability to create classes like these to be used in your own programs.

6.2.1. Attributes and Methods

Okay, so I've got a bunch of instances of these different classes. Now what?

Attributes and Methods

Objects have attributes and methods.

Hint: You can easily tell attributes and methods for an object because of the dot that separates the instance and the attribute or method.

Also: You can distinguish between attributes and methods by the parentheses () that are placed after methods. This is because methods are really just functions for an object, and functions have to have parentheses to enclose their parameters.

6.2.1.0. Example 1

The Card class—one that we're going to make up for a card-playing program, maybe—is used to define a specific object, an instance of that class called card1. The class description identifies attributes that Cards share:

The Card class will also have some methods that we can use to interact with the card:

One way of visualizing a class is by using a diagram such as this one here. The class name is given at the top, the attributes are listed below that (sometimes with an underscore _ at the beginning, which is just a way of visually confirming that these are a different kind of variable), and the methods listed below that.

Note that there may be other attributes of a Card that either aren't important to us (so we ignore it) or are better suited for other classes. For example, the "King of Hearts" is sometimes called "the Dead King" because the sword that he's holding might be seen as going through his head. This isn't important to us in our Card class so we just ignore it.

What about the material the Card is made of? The pattern on the back? The state of the card (new and stiff, or old)? These qualities probably aren't of any interest to us in our Card class, but if they were, it would be more appropriate to use those as attributes for a Deck class. In that case, we'd have a Deck object made up of Card objects.

6.2.1.1. Example 2

The Car class (one that we're going to make up) is used to define a specific object, an instance of that class called myToyota. That class describes attributes that Cars share:

The Car class will also have some methods that we can use to interact with the car:

The getGasAmount() method returns the amount of gas in the tank. Because this method is accessing information about the object, it's referred to as an accessor method. Typically, instance variables for an object are not directly accessed except via a method designed to return the value; to interact with this variable, an accessor method like getGasAmount here is used.

>>> myToyota.fillTank(15)

Here we've used the method fillTank to do something to our object—we've added 15 gallons to the tank of the car. Because this method is causing a change in the status of some aspect of the object, it's called a mutator method.

Are you confused yet? Like everything else in programming, it will take a few times practicing all of this before it starts to make a little sense.

6.2.2. Why use objects?

Up to this point we haven't had any need to use objects, and we've written some pretty good programs. So why is the idea of being able to write a class so important all of a sudden?

As our programs become larger and more complex, we'll find that we need to keep track of a larger number of things, and often multiple version of the same kind of thing. Out AddressBook program used a list to keep track of multiple contacts; it's easy to imagine that a Person class could be used as a template for multiple Person objects, all managed by our AddressBook list.

We've just looked at a Card class. A deck of cards might include 52 Card objects. A Bank class might keep track of many BankAccount objects.

There are lots of uses for objects. Learning how to use them to store data is an important part of your computer science education.

6.2.3. The Coin class

It's time to get into this a little more. Without actually digging into the task of writing code for a class just yet, let's look at one that's already been written for you.

The Coin class

The class Coin represents a coin that may be flipped into the air, with a result of "heads" or "tails" when it lands.

Question 1. What does this program statement do?

myCoin = Coin()
Show/hide solution

Q2. What do you think this statement might do?

result = myCoin.flip()
Show/hide solution

Q3. What might this program statement do?

print(myCoin.getState())
Show/hide solution

Q4. What does myCoin.status represent?

Show/hide solution

Q5. What does a diagram of this class look like?

Show/hide solution

6.2.3. Using the Coin class

One of the great features about object-oriented programming is the fact that the messy details of the code can be hidden away from people, an aspect that's called encapsulation. The tricky bits of code that implement a Coin class, or a Card class, can be hidden away, and my code can just use the classes that someone else has written code for.

Here's a small program that shows how to use the Coin class.

#!/usr/bin/env python3 """ coinflipper.py Uses the Coin class to demonstrate coinflipping """ from coin import * # requires that coin.py be in the same directory def main(): print("Let's flip a coin!") myCoin = Coin() # creates a coin object that will be referred # to as "myCoin" print("The coin has an initial state of ",end='') print(myCoin.getState()) # calls an accessor method for i in range(100): print("Flipping the coin to get a ",end='') print(myCoin.flip()) # calls a mutator method and # prints the result returned if __name__ == "__main__": main()

6.2.4. What the Coin class looks like

We're not really at a point where you can run out and write your own class yet, but we're getting close. Let's take a look at the Coin class that we used above, and see how it was written.

#!/usr/bin/env python3 """ coin.py The Coin class An example of a simple class declaration, instance variables, and methods """ import random class Coin: """It's customary to include a comment here describing your class. Here, the class Coin represents a coin that is going to be flipped in the air, with a result of 'heads' or 'tails'. """ def __init__(self): """This 'constructor method' is called when an instance of Coin is created. """ self.status = self.flip() '''There's not much to do in this simple example, but we need to set up the initial status of the coin. We'll do that by calling the flip() method, defined below. ''' def flip(self): """The flip method determines a random state--'heads' or 'tails'--and returns that value as a string. """ # Assign heads or tails to the attribute "status" self.status = random.choice(['heads','tails']) # Return this status for the function call return self.status def getState(self): """Returns the current value of the status of the coin, 'heads' or 'tails', without flipping it. """ return self.status def main(): """Test the coinFlipper by letting it do its thing!""" myCoin = Coin() print(myCoin.getState()) for i in range(10): myCoin.flip() # Flips the coin print(myCoin.getState()) # another way of doing the same thing for i in range(10): print(myCoin.flip()) if __name__ == "__main__": main()

Enter this program, and play around with it a little bit to see if you can understand how the pieces fit together.

6.2.5. Writing the Counter class

Let's write a Counter class that can be used to record a tally of items counted.

Example: The Counter class

With the instructor:

  1. Identify the salient attributes and methods of a counter
  2. Write a Counter class
  3. Write a tester for the Counter class

6.2.6. Writing the Die class

It's not uncommon to need to roll a die in programs—we've already used dice in our programs.

The Die class

Using the Coin class as a model, write a Die class that you can use in programs. The class should have a single instance variable result that stores the current die roll, and a single method .roll() that simulates rolling a six-sided die, stores the result in result, and returns the result so that it can be used.

Once you've written your class, test it in the console by importing the class, creating a Die objects, and showing how to use it.

6.2.7. The Pizza class

Let's work with a slightly more abstract example. The Pizza class describes a model of a Pizza that we can interact with.

You might reasonably ask why we would need to write a Pizza class—what use would a virtual pizza be?

If you're considering opening a pizza restaurant, you might be interested in creating a model or simulation of the restaurant so that you can try to predict expenses, workflow, etc. In this case, our model of the pizza is going to be very simplified. Our pizza is only going to have a very few attributes and methods.

The Pizza class

Our pizza model is going to allow us to keep track of the toppings on our pizza, and how many slices of pizza there are. At the beginning, when the pizza is first "made," it will be unsliced, and it will only have "tomato sauce" and "cheese" on it. We need to be able to add toppings to the pizza, slice the pizza, eat slices from the pizza...

What variables will we need to help us model this pizza?

Show/hide solution

What will be the initial values of these variables?

Show/hide solution

What methods will we need to interact with our pizza (view or modify these variables)?

Show/hide solution

Based on our initial thoughts on the design of this pizza, we can now think about writing the class in Python.

Show/hide solution

Writing a class is kind of like writing a function: we're telling Python that we want to use this code at some point in the future, but not just yet. We won't actually use the class to create a Pizza object until somebody writes a program that creates a variable of the type Pizza:

""" A program that uses the Pizza class. """ import pizza def main(): myDinner = pizza.Pizza() // creates a Pizza object called "myDinner" . . .

Using the Pizza class

Download a copy of the Pizza class and use it in a main program that constructs and interacts with a pizza.

You'll get to try designing, writing, and using your own class in the next project.

6.2.8. The OOP Project

Get a copy of the OOP Project handout and start writing your own class.

6.3. Writing classes, importing classes

Perhaps you've written a brief demonstration on how to:

  1. Define a class
  2. Write a main() function that constructs an object of a class, a manipulates it.

The next thing we're going to try is:

  1. Writing a new class to represent the idea of an object moving in space
  2. Write a main() function to make sure it works
  3. Import our class into a Processing program which will allow us to actually see an object moving in space.

6.3.1. Writing the Ball class

The Ball class

Take a moment to write a class that can be used to track a ball traveling in a two-dimensional (x,y) space. Include "getters" and "setters" for each axis of the ball's position and the ball's velocity, and information about the ball's radius.

The constructor should include parameters for each of those values.

Write a __str__ method that includes a string representation of the Ball that you can use to identify its state in terms of those variables.

Finally, include a .move() that takes a time interval delta_t as a parameter, and uses that information to identify the ball's new x-y position based on how far it has traveled in that time period. Return the new position from that method.

Show/hide solution

5.3.2. Testing the Ball class

We've written our Ball class in the file ball.py and there's a small little tester in the main program that demonstrates the basic functionality.

Often, though, when you've written a class in a file, you'll want to import it into a separate program. Let's see how to do that.

  1. Create a new directory called ball_demo somewhere convenient.
  2. Drag a copy of the ball.py file (with its description of the Ball class) into that folder.
  3. Write a new file in that folder called ball_demo.py. We'll write a program there that allows us to interact with the Ball class.

Writing the ball_demo.py program

This demo will demonstrate the basics of importing the Ball class and getting a main() program running.

  1. import the ball module
  2. In the main() function, create a Ball object with some initial x and y position, some initial velX and velY, and some radius.
  3. Write an infinite loop that calls the move() method repeatedly. You'll need to enter some time period (1 second? 0.2 seconds?) as a parameter
  4. Print the ball's state so that you can observe its position and velocity changing over time.

Show/hide solution

Once you've learned a little about how the Ball class works, let's try using it in a graphics program.

5.3.3. Using the Ball class in a Processing program

5.3.4. Modifying the Processing program