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:
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:
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:Note that the dict data type stores its key-value pairs in an unordered format:
The only way to reference the "value" is by using its associated, unique key.
6.1.1.1. Example: contacts
In the Address Book program, we could keep track of our contacts as a list of dictionaries:
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:
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.
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):
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:
- the value 7 (an object that belongs to the class int)
- the string "Richard" (an object that belongs to the class str)
- a function called initialize_graphics (an object that belongs to the class function)
- a list called myFriends that contains ["Bob","Dave","Jill"] (an object that belongs to the class lst)
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:
- integers
- strings
- cars
- insects
- computers
- planets
- 2-dimensional grid
- cards
- decks of cards
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:
- [1,2,3] is an object, and an instance of the class list.
- "joey" is an object, and an instance of the class string.
- If a = 3, a is an object, and an instance of the class int.
- The "3 of Hearts" is an object, and an instance of the class Card.
- A "chessboard" is an object, and an instance of the class Grid2D
- myDog is an object, and an instance of the class Canine.
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.
- An attribute stores information about an object in a variable. Attributes may also be called instance variables.
- A method is something that you can do to the object.
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:
- suit
- value
- blackjack_value
The Card class will also have some methods that we can use to interact with the card:
- .getSuit()
- .getValue()
- .getBlackjackValue()
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:
- milesDriven
- fuelInTank
- gasMileage
The Car class will also have some methods that we can use to interact with the car:
- .fillTank(gallons)
- .drive(distance)
- .getGasAmount()
- .getMilesDriven()
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.
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?
Q2. What do you think this statement might do?
Q3. What might this program statement do?
Q4. What does myCoin.status represent?
Q5. What does a diagram of this class look like?
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.
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.
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:
- Identify the salient attributes and methods of a counter
- Write a Counter class
- 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?
What will be the initial values of these variables?
What methods will we need to interact with our pizza (view or modify these variables)?
Based on our initial thoughts on the design of this pizza, we can now think about writing the class in Python.
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:
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:
- Define a class
- Write a main() function that constructs an object of a class, a manipulates it.
The next thing we're going to try is:
- Writing a new class to represent the idea of an object moving in space
- Write a main() function to make sure it works
- 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.
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.
- Create a new directory called ball_demo somewhere convenient.
- Drag a copy of the ball.py file (with its description of the Ball class) into that folder.
- 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.
- import the ball module
- In the main() function, create a Ball object with some initial x and y position, some initial velX and velY, and some radius.
- 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
- Print the ball's state so that you can observe its position and velocity changing over time.
Once you've learned a little about how the Ball class works, let's try using it in a graphics program.