Topics

In this lesson, we are going to introduce the basics of data structures in Python programming language including the following topics:

1. The concepts of Classes and Objects
2. Classes and Objects in Python
3. Data Structures
4. Abstract Data Types (ADTs)

Required Tasks

1. Read Lesson 1
2. Do the tasks of Lab 1
3. Read and do Assignment 1
4. Submit Assignment 1 solutions to the associated Dropbox on MyLearningSpace

Learning Outcomes

By the end of this lesson, you should be able to

• Explain the concepts of classes and objects
• Define and develop classes in Python
• Use a class in Python including instantiating objects in Python
• Define and use methods for a class
• Explain and define ADT and data structure
• Articulate the differences between data structures and ADTs
• Describe one approach for implementing ADTs and data structures in Python

Introduction

In this lesson we assume you are familiar with programming in Python. The purpose of this lesson is to provide you with a very basic introduction to object-oriented programming and the concepts of classes and objects. Note that this course is not a course about object-oriented programming and we are not going to be teaching object orientation in depth. We will be teaching whatever is needed to understand this course. You will get to learn more about object orientation in CP213.

The other purpose of this lesson is to provide you with an introduction to the data structure before we go deeper into these topics in the next lessons.

Classes and Objects

In this section, first we define the concept of classes and objects. Then we talk about how these concepts are implemented in Python programming languages. We present a number of examples, as well.

Concept of Classes and Objects

Classes and objects are the main concepts of object-oriented programming. In object-oriented view, everything is modeled as an object. As an analogy, you can think of objects in the real world: car, light, room, window, etc. could be considered as objects. In an object-oriented programming like Python you can model the problem and its solution using objects.

Every object has:

properties (attributes)

For example, a car has a color. The color is considered one of the properties of this object.

behaviors (methods):

Specifies what an object does. To get an object to do useful work, we need to be able to make a request to the object. For example, to use the car, we need to start the car. Here, start is called one of the methods of the car object.

A class is a template for creating objects. A Class contains variables (called attributes) and functions (called methods).

An object is an instance of a class. A class defines the common attributes and methods of a set of objects whereas an instance object is a specific example of a class.

The Figures below shows an example of a class named Car. The class defines a set of objects that have identical characteristics (attributes) and behaviors (methods). The other Figures shows two instances, or actual objects, of this class.

Car

Properties:
Make
Model
Year
Color

Methods:
Start()
Stop()
Move()
Accelerate()

Image retrieved from Unsplash. Free for use.

Image retrieved from Unsplash.  Free for use.

A class is like a blueprint defining the characteristics and methods of a set of objects. The class does not (usually) specify the value of attributes. Those values are assigned when an object is created.

As another example, a person can be thought of as an object, and we can define a class, named Person, that defines the attributes and behaviors that all persons share, such as:

• a name
• a gender
• a birth date
• a birth place

and methods such as:

• initialize()
• get_first_name()
• get_birth_date()
• set_birth_date()

Thus, Person can be thought of as a class - we have attributes, but no specific values for those attributes.

An instance of a Person has values for these attributes, such as:

• Winston Churchill
• male
• 30 November 1874
• Blenheim Palace, Woodstock, Oxfordshire, Great Britain

An instance of a Person can call the methods of the class, as well.

Categories of Class Methods

As mentioned earlier, classes have methods defined for them. These methods could perform different kinds of operations. When defining a class, there are four general kinds of methods:

constructors

initializes a new instance of a class.

accessors (or getters)

returns values of attributes of an instance of a class

mutators (or setters)

modifies the values of attributes of an instance of a class

iterators

sequentially traverses the contents of an instance of a class

Let's elaborate more on different kinds of methods.

In the example class Person above, the method named initialize() is an example of a constructor. To create an object, we need a way of getting the data into the object. For example, to create a Person object we need the name, gender, birth date, and birth place. The data could be coming from a file, are typed in, or obtained through some other mechanisms. The data are passed to the constructor or obtained by the constructor to create an object.

In the example class Person above, get_first_name() is an example of an accessor and set_birth_date() is an example of a mutator.

The class Person defined above does not have an iterator, since it is a simple data object and the attributes could be accessed (read) through accessors. However, in a more complex class (e.g., a class representing a collection of Person objects), we want a mechanism that will allow us to walk through all of the Person objects in that collection in some order.

Public/Private Attributes and Methods

It is helpful to distinguish the user of a class from the designer of a class. The user of a class, or the client of the class, is the program(mer) that creates an instance of the class (an object), calls methods of the class, and uses the objects of this class in solving the problems and developing the codes. The goal of the user of a class is to use the class in modeling the problem and solution. The user of a class is not interested in how the methods are implemented.

The designer of a class is the one who defines the methods and attributes of the class and makes them available to the user. The goal of the designer is to expose only what is necessary to the user of the class and keep everything else hidden (the details of the implementation). One advantage of this design decision is that the users of the class cannot change/corrupt the hidden part of the class/object. Another advantage is that the class designer can change the hidden portion without worrying about the impact on the user of the class. The class may be used in many programs and there is no need to make change in any of those programs.

As an analogy, the driver of a car is not interested in the details about the car engine. It is also better if the drivers cannot access the components under the hood of the cars and leave it to the experts (designer of the car or those who know the design and repair). In this analogy, the car is the class, the driver is the user of the class and the car company is the designer of the class.

Therefore, the access to the methods and attributes of a class must be controlled. To control the access, the keywords public and private are used. Figure 4 shows access to methods and attributes of a class. If a method/attribute is public, it can be accessed by anyone (user or designer) of the class. It means that a public method can use other public methods and attributes. If a method/attribute is private, it could be accessed only be the designer of the class (e.g., the implementation of the public/private methods of the class). It cannot be accessed by the user of the class. The public/private keywords are used in object-oriented programming languages such and Java and C++. In Python we do not have these keywords, but we enforce the concept. We will talk about it later.

Public/Private methods and attributes of a class and how they are accessed. The user (client) of a class can only access public methods and attributes. The private methods and attributes can only be accessed within the class, i.e., by public/private methods and attributes.

Defining Classes

A minimum Python class definition requires only two parts:

• The name of the class
• The class constructor. The constructor is always named __init__. (Underscores play an important role in Python variable in method naming, as we will see.)

The following is the general format for defining a class:

          
class Name:
    def __init__(self[, param,]):
        ...

        

The constructor, __init__, like all class methods (and Python functions in general), starts with the keyword def.

All class methods, including the constructor, must have at least one parameter, the self parameter. Other parameters can be defined as required. The square bracket in the above code, [, param,], indicates what follows is optional. A method may or may not have any parameters other than self. In a constructor, the parameters are generally used to initialize class attributes.

Class methods are indented within the class definition in order to show that they belong to the class. Listing 1 shows an example of defining a class. In CP164 we generally make the module name match the class name. Thus the Number class is defined in a PyDev module named Number.py.

class Number:
    def __init__(self, value):
        self.value = value
        return

Class Attributes

Class attributes are generally defined within the class constructor. An attribute is defined by putting the class keyword self in front of it. In the example of Listing 1, value is one attribute of class Number.

This attribute, value , may now be used anywhere within the class, but must be preceded by self keyword. Without self , the named variable is treated as a simple variable instead. Note that in this example the parameter named value matches the attribute name. However, Python can distinguish them because the class attributes are always preceded by the self keyword.

Creating Objects

To create an object, we need to call a constructor. The constructor is called not by using the name __init__, but by using the name of the class. Thus you create a new object with the following syntax:

object = Name([argument,])

Note that even though self is shown as the first parameter to the constructor, as shown in Listing 1, self is never actually used as an argument. Only the rest of the constructor parameters require matching arguments.

The class methods documentation have a Use: description that shows how to call the method.

Importing a class

To use a class defined in another module, we need to import that class. A class can be imported with the following syntax:

from module import class

Listing 2, shows an example of using class Number defined in Code Listing 1 in another Python module:

from Number import Number
example = Number(0)

Class Methods

Classes can also contain methods which are functions that belong to the class. Each instance of class, an object, has access to these functions.

In Python most class methods are declared and used the same way as standard Python functions with the following special requirements:

• Class methods require the keyword self as the first (or only) parameter
• Class methods may use class attributes by preceding them with self
• Class methods are called by preceding them with the name of an object

The following example defines a method for the Number class, named square and then calls the method from an instance of the class:

class Number:

    def __init__(self, value):
        """
        -------------------------------------------------------
        Creates a Number object.
        Use: target = Number(value)
        -------------------------------------------------------
        Parameters:
            value - an integer (int)
        Returns:
            A Number object (Number)
        -------------------------------------------------------
        """
        self.value = value
        return

    def square(self):
        """
        -------------------------------------------------------
        Returns the square of the value in a Number object.
        Use: answer = number.square()
        -------------------------------------------------------
        Returns:
            answer - square of self.value (int)
        -------------------------------------------------------
        """
        answer = self.value * self.value
        return answer

example = Number(5)
answer = example.square()

Note that the method needs no further parameters because it is squaring and returning the value of its value attribute.

self Parameter

Note that the first parameter in all of the methods of a class is self. However, when we call the methods we are not passing any argument in place of the self parameter. The only parameters we pass to a method when calling the method are the ones that match those to the right of self.

In the example of Number class, when we create an object by calling the constructor, we are passing one argument, while the constructor has two parameters. In addition, there is no extra parameter in square method, so we do not pass any argument to this method.

Accessing Attributes

Object attributes can be accessed simply by using the following syntax:

object.attribute

example = Number(5)

print(example.value)
example.value = 0
example.value = int(input("Enter a new value: "))

The Eclipse IDE helps here by providing a drop down list of all available attributes and methods after typing object name, just as it does with function libraries. If you are using Eclipse, once you type object name followed by a period you get a list of methods and attributes available to the objects as shown in the following Figure.

Screenshot taken by Masoomeh Rudafshani

Public/Private Attributes and Methods

Python does not have any way to make attributes and methods truly private or inaccessible from outside the class. In this course, we use a naming convention to distinguish public and private attributes and methods.

Attributes and methods that begin with '_' or '__' (i.e. either single or double underscores), should be treated as private and not be accessed from outside the class definition. By convention, they are considered to be private attributes and methods accessible only by other class methods.

This naming convention merely designates a status that you as a programmer should respect, in the same way that naming a constant with all capital letters does not make a Python variable truly constant, but does require you to treat it as a constant.

The Student Class

In the following, we have provided an example of a class in Python. The class is more complex and has many methods. We will explain different parts of this class in the following.

"""
-------------------------------------------------------
Student class definition.
Stores simple student data.
-------------------------------------------------------
Author:  David Brown
ID:      999999999
Email:   dbrown@wlu.ca
__updated__ = "2023-05-10"
-------------------------------------------------------
"""


class Student:

    def __init__(self, student_id, surname, forename, birth_date):
        """
        -------------------------------------------------------
        Initializes the student attributes.
        Use: student = Student(student_id, surname, forename, birth_date)
        -------------------------------------------------------
        Parameters:
            student_id - 9 digit student ID (str)
            surname - student family (str)
            forename - student given name (str)
            birth_date - a student birth date of the form YYYY-MM-DD (str)
        Returns:
            A Student object.
        -------------------------------------------------------
        """
        assert len(student_id) == 9 and student_id.isdigit(), \
            "Student ID must be a 9 digit string"

        self.student_id = student_id
        self.surname = surname
        self.forename = forename
        self.birth_date = birth_date

    def __str__(self):
        """
        -------------------------------------------------------
        Returns a string version of a student in the format
        id
        surname, forename
        Use: print(student)
        Use: print(f"{student}")
        Use: string = str(student)
        -------------------------------------------------------
        Returns:
            string - a formatted version of the student data (str)
        -------------------------------------------------------
        """
        string = f"""{self.student_id}
{self.surname}, {self.forename}, {self.birth_date}"""
        return string

    def __eq__(self, target):
        """
        -------------------------------------------------------
        Compares against another student for equality.
        Use: source == target
        -------------------------------------------------------
        Parameters:
            target - other student to compare to (Student)
        Returns:
            result - True if student IDs match, False otherwise (boolean)
        -------------------------------------------------------
        """
        result = self.student_id == target.student_id
        return result

    def __lt__(self, target):
        """
        -------------------------------------------------------
        Determines if this student precedes another.
        If student IDs don't match (using already defined == operator),
        compares students by name then by ID.
        Use: source < target
        -------------------------------------------------------
        Parameters:
            target - other student to compare to (Student)
        Returns:
            result - True if student less than target, False otherwise (boolean)
        -------------------------------------------------------
        """
        if self == target:
            result = False
        else:
            # Compare the data values by putting them into tuples.
            result = \
                (self.surname.lower(), self.forename.lower(), self.student_id) < \
                (target.surname.lower(), target.forename.lower(), target.student_id)
        return result

    def __le__(self, target):
        """
        -------------------------------------------------------
        Determines if this student precedes is or equal to another.
        Uses already defined == and < operators.
        Use: source <= target
        -------------------------------------------------------
        Parameters:
            target - other student to compare to (Student)
        Returns:
            result - True if student less than or equal to target,
                False otherwise (boolean)
        -------------------------------------------------------
        """
        result = (self == target or self < target)
        return result

    def login(self):
        """
        -------------------------------------------------------
        Generates and returns a Laurier-compatible Network login.
        Use: login = student.login()
        -------------------------------------------------------
        Returns:
            result - a Network login consisting of the first four
                characters of surname and the last four digits of student)id.
                Total with is 8, special characters (" ", "'", "-") are replaced
                with 'x'. (str)
        -------------------------------------------------------
        """
        # Convert to lower case and get first four characters.
        result = self.surname.lower()[:4]
        # Replace trailing spaces with 'x'.
        result = f"{result:x<4}"
        # Replace special characters with 'x'.
        result = result.replace(' ', 'x')
        result = result.replace("'", 'x')
        result = result.replace("-", 'x')
        # Add the last four digits of the ID number.
        result += self.student_id[-4:]
        return result

    def email(self):
        """
        -------------------------------------------------------
        Generates and returns a Laurier-compatible email address.
        Use: email = student.email()
        -------------------------------------------------------
        Returns:
            result - a Laurier email address of the form
                login@mylaurier.ca (str)
        -------------------------------------------------------
        """
        result = self.login() + "@mylaurier.ca"
        return result

    def write(self, fv):
        """
        -------------------------------------------------------
        Writes this student's attributes to an already open
        comma-delimited file.
        Use: student.write(fv)
        -------------------------------------------------------
        Parameters:
            fv - a file variable, open for writing or appending (file)
        Returns:
            None
        -------------------------------------------------------
        """
        string = f"{self.student_id},{self.surname},{self.forename},{self.birth_date}"
        print(string, file=fv)
        return

This is the complete code for class Student. The name of the class is Student, and that matches the actual name of the file containing the code. That is one of the naming rules that we will be following throughout this course.

We are not going to use this class throughout the term, but the good thing about this example is that you should understand what makes you a student and how you can translate that into a Python class.

Let's explain different parts of the code.

Lines 1-11 contain documentation. The class definition starts at line 14. The keyword class is starts defining the class. The name of the class is followed by a colon. Everything that is part of the Student class is indented inside the class keyword. The part that is not indented (line 54) is part of a big string. This is a formatted string. We do not want space in front of string. All of the methods are indented.

The point of having an assertion statement inside the constructor is to make sure as much as possible that the data being sent to the constructor is in the correct format. So, for example, the assertion statement in line 31 says the length of the student_id must be nine and that the student_id must contain only digits.

The following code creates a sample Student object named s1:

from Student import Student

s1 = Student("123456789", "Brown", "David", "M", "1962-10-25")

You are going to see assertion statements in this course, but you do not have to write them.

Magic Methods

Python has rules about what methods must be or can be defined in a class to do special things. These methods doing special things are called magic methods. Python identifies special methods by surrounding their names with double underscores, as we have already seen with the __init__ constructor method.

The special methods are not called by their names, but instead are called using familiar Python functions or operators. The __init__ constructor, for example, is never called by the name __init__, but rather by simply using the name of the class as the constructor call. Here, we will be talking about a number of magic methods used in Student class. They are: __init__, __str__, __eq__, __lt__, and __le__ methods. The Use: part of the method docstring explains how to call the magic method.

The __init__ method: Creating a Student object

To create a Student object, we need to have a constructor method defined. In Listing 4, Lines 20-42 define the constructor of Student class. In the __init__ method of Student object, we are passing four parameters: student_id, surname, forename, and birth_date. In the documentation part (lines 21-33) of Listing 4, we have described what these values should be.

The only way to create a Student object is to call the Student constructor and pass it the proper parameters. The following string contains Student data:

"123456789,Brown,David,1962-10-25"

but this string is not a Student object.

If, however, we call the Student constructor and pass it this same data, as shown in Listing 1, then the variable some_student is a Student object, because it was created by calling the Student constructor.

from Student import Student
some_student = Student("123456789", "Brown", "David", "1962-10-25")

Getting Constructor Arguments From the Keyboard

When creating an object, we need to pass the required parameters to the constructor. The data could be read from a file, or might be hard coded in the program. The program may ask the user to enter data as the example below. The point here is that where the data comes from or the names of the parameters we pass to the constructor are not important as long as we have the correct data.

from Student import Student

s_id = input("Student ID: ")
s_sn = input("Family name: ")
s_fn = input("First name: ")
s_bd = input("Birth Date (YYYY-MM-DD): ")

student = Student(s_id, s_sn, s_fn, s_bd)
print()
print(student)

The above example (with appropriate data) generates the following output:

Student ID: 123456789
Family name: Rudafshani
First name: Masoomeh
Birth Date (YYYY-MM-DD): 1990-12-12

123456789
Rudafshani, Masoomeh, 1990-12-12

The __str__ Method

When defined in a class, the __str__ method returns a string version of the attributes of an object. This string can be used anywhere that a Python string can be used - in printing, concatenation, string processing, etc.

After defining the __str__ method as shown in the Student class definition, you get the following output when printing the Student object:

123456789
Brown, David, 1962-10-25

Note the use of the Python docstring in the Student definition of __str__ to create a multi-line string. You can use string formatting with a docstring just as you would with a single-line string. The major drawback with a docstring is that the code indenting can be messed up.

The only parameter to __str__ is self.

            
s1 = Student("987654321", "Brown", "Tasmin", "1995-06-01")
s2 = Student("123456789", "Brown", "David", "1962-10-25")
students = [s1, s2]
students.sort()
print(students)

          

Traceback (most recent call last):
  File "test.py", line 23, in <module>
    students.sort()
TypeError: '<' not supported between instances of 'Student' and 'Student'

from Student import Student

s1 = Student("123456789", "Brown", "David", "1962-10-25")
s2 = Student("987654321", "Brown", "Tasmin", "1995-06-01")

if s1 < s2:
    print(f"{s1.forename} {s1.surname} comes first!")
elif s2 < s1:
    print("{s2.forename} {s2.surname} comes first!")
else:
    print("The students are the same!")

The __eq__ Method

The first boolean method is the __eq__ method. It is often necessary to be able to compare two objects for equality. Defining a __eq__ method for a class allows you to compare any two objects of the same class with the standard == operator. The implementation is a very simple object comparison, comparing only the student_id of the two objects. The method takes another Student object, called target, as a parameter.

We never call __eq__ method by that name. In order to use this method, we use the == operator, as the method docstring notes:

          
        -------------------------------------------------------
        Compares against another student for equality.
        Use: student == target
        -------------------------------------------------------

If you create an __eq__ method for a class you do not need to create a __ne__ (not equal: !=) method as well, for Python automatically determines the negation of the == operator.

Now we can compare two Student objects as in the following examples:

          
if student1 == student2:
    ...
if student1 != student2:
    ...

        

In both examples it is the methods of student1 that are being called because student2 is on the right side of the == operator and is treated as the target parameter.

Two things might not be equal but it does not tell us which one comes first. We need two other magic methods: __lt__ and __le__.

The __lt__ Method

Defining a __lt__ method for a class allows you to use the < operator to compare two objects, as well as its negation, the >= operator. This method is defined in the Student class, and like the __ne__ method, the negation of __lt__, __ge__ (>=), is automatically defined by Python.

Now we can compare two Student objects as in the following examples:

          
if student1 < student2:
    ...
if student1 >= student2:
    ...

        

Note that the code for __lt__ method uses a Python shortcut to compare the names and IDs of two Student objects:

          
            result = \
                (self.surname.lower(), self.forename.lower(), self.student_id) < \
                (target.surname.lower(), target.forename.lower(), target.student_id)

        

By putting the string values into tuples, the function then compares the two tuples to determine its result. When comparing the Student attribute tuples, Python simply compares the elements of each tuple one after the other, in effect duplicating the following code. Although this longer code is perfectly acceptable, the tuple shortcut is a nice one.

if self.surname.lower() < target.surname.lower():
    result = True
elif self.surname.lower() == target.surname.lower():
    if self.forename.lower() < target.forename.lower():
        result = True
    elif self.forename.lower() == target.forename.lower():
        if self.student_id < target.student_id:
            result = True
        else:
            result = False
    else:
        result = False
else:
    result = False

The __le__ Method

To complete the full set of boolean methods on a Student object, we need to define a method that allows the use of the <= and > operators. Because of the existing methods, __lt__ and __eq__, the __le__ method is particularly easy to define. This method is defined in the Student class. The __le__ method relies upon the previous two methods to determine its result. Like the __ne__ method, the negation of __le__, __gt__ (>), is automatically defined by Python.

Now we can compare two Student objects as in the following examples:

          
if student1 <= student2:
    ...
if student1 > student2:
    ...

        

Having defined all of the boolean operators ( ==, !=, <, >, <=, >= ) for the Student class, we can now use Python's built in list sort method to sort a list of Student objects.

Python has a number of other magic methods, some of which will be covered later in the course.

The Food Class

In this section we provide another example of a class in Python named Food. The purpose is to present some other details of object-oriented programming that you will need throughout this course. In addition, the Food class is a data storage class and we will use it with our data structures throughout the term. The Food class has a number of attributes and methods that will be explained in the following:

"""
-------------------------------------------------------
Food class definition.
-------------------------------------------------------
Author:  David Brown
ID:      123456789
Email:   dbrown@wlu.ca
__updated__ = "2023-05-10"
-------------------------------------------------------
"""


class Food:
    """
    Defines an object for a single food: name, origin, vegetarian, calories.
    """
    # Constants
    ORIGIN = ("Canadian", "Chinese", "Indian", "Ethiopian",
              "Mexican", "Greek", "Japanese", "Italian", "American",
              "Scottish", "New Zealand", "English")

    @staticmethod
    def origins():
        """
        -------------------------------------------------------
        Creates a string list of food origins in the format:
           0 Canadian
           1 Chinese
           2 Indian
           ...
        Use: s = Food.origins()
        Use: print(Food.origins())
        -------------------------------------------------------
        Returns:
            string - A numbered list of valid food origins.
        -------------------------------------------------------
        """

        # your code here

        return

    def __init__(self, name, origin, is_vegetarian, calories):
        """
        -------------------------------------------------------
        Initialize a food object.
        Use: f = Food( name, origin, is_vegetarian, calories )
        -------------------------------------------------------
        Parameters:
            name - food name (str)
            origin - food origin (int)
            is_vegetarian - whether food is vegetarian (boolean)
            calories - caloric content of food (int >= 0)
        Returns:
            A new Food object (Food)
        -------------------------------------------------------
        """
        assert origin in range(len(Food.ORIGIN)), "Invalid origin ID"
        assert is_vegetarian in (True, False, None), "Must be True or False"
        assert calories is None or calories >= 0, "Calories must be >= 0"

        self.name = name
        self.origin = origin
        self.is_vegetarian = is_vegetarian
        self.calories = calories
        return

    def __str__(self):
        """
        -------------------------------------------------------
        Creates a formatted string of food data.
        Use: print(f)
        Use: s = str(f)
        -------------------------------------------------------
        Returns:
            string - the formatted contents of food (str)
        -------------------------------------------------------
        """

        # your code here

        return

    def __eq__(self, target):
        """
        -------------------------------------------------------
        Compares this food against another food for equality.
        Use: f == target
        -------------------------------------------------------
        Parameters:
            target - [right side] food to compare to (Food)
        Returns:
            result - True if name and origin match, False otherwise (boolean)
        -------------------------------------------------------
        """
        result = (self.name.lower(), self.origin) == (
            target.name.lower(), target.origin)
        return result

    def __lt__(self, target):
        """
        -------------------------------------------------------
        Determines if this food comes before another.
        Use: f < target
        -------------------------------------------------------
        Parameters:
            target - [right side] food to compare to (Food)
        Returns:
            result - True if food precedes target, False otherwise (boolean)
        -------------------------------------------------------
        """
        result = (self.name.lower(), self.origin) < \
            (target.name.lower(), target.origin)
        return result

    def __le__(self, target):
        """
        -------------------------------------------------------
        Determines if this food precedes or is or equal to another.
        Use: f <= target
        -------------------------------------------------------
        Parameters:
            target - [right side] food to compare to (Food)
        Returns:
            result - True if this food precedes or is equal to target,
              False otherwise (boolean)
        -------------------------------------------------------
        """
        result = self < target or self == target
        return result

    def write(self, file_variable):
        """
        -------------------------------------------------------
        Writes a single line of food data to an open file.
        Use: f.write(file_variable)
        -------------------------------------------------------
        Parameters:
            file_variable - an open file of food data (file)
        Returns:
            The contents of food are written as a string in the format
              name|origin|is_vegetarian to file_variable.
        -------------------------------------------------------
        """
        print(f"{self.name}|{self.origin}|{self.is_vegetarian}|{self.calories}"),
              file=file_variable)
        return

    def key(self):
        """
        -------------------------------------------------------
        Creates a formatted string of food key data.
        Use: key = f.key()
        -------------------------------------------------------
        Returns:
            the formatted contents of food key (str)
        -------------------------------------------------------
        """
        return f"{self.name}, {self.origin}"

    def __hash__(self):
        """
        -------------------------------------------------------
        Generates a hash value from a food name.
        Use: h = hash(f)
        -------------------------------------------------------
        Returns:
            value - the total of the characters in the name string (int > 0)
        -------------------------------------------------------
        """
        value = 0

        for c in self.name:
            value = value + ord(c)
        return value

Attributes of the Food class

A Food object must contain the following attributes:

name

food name (str)

origin

food origin (int)

is_vegetarian

whether food is vegetarian (boolean)

calories

caloric content of food (int > 0)

Static Variables

The possible values of the origin attribute is specified using a constant named ORIGIN in line 19. Python does not have true constants - it has variables that we pretend cannot be changed. In this case, ORIGIN is one of them. A constant is named in all uppercase (this is a convention not a must). The point of having this constant is that we are not allowed to put any other option as the Food origin (this requirement is enforced with assertion statements in line 59).

Because ORIGIN is defined outside of the __init__ constructor, it is considered a static attribute. Static attributes are attributes that exists at the class level. It means when defining a class you can use these attributes without instantiating an object of the class. In the class Food above, different objects might have different values for name, origin, is_vegetarian, and calories. However there is only one copy of ORIGIN for every instance of the class, i.e. ORIGIN is shared by every Food object. This saves memory and enforces consistency. No Food object can have access to a different list of origins than any other Food object.

Methods of the Food class

The Food class contains the following methods:

__init__

the class constructor that creates Food objects given the appropriate values as parameters

__str__

returns a copy of a Food object as a formatted string

__eq__, __lt__, __le__

various comparison methods

write

writes the contents of a Food object to a file

key and __hash__

will be used and discussed later

A typical food object should be output as a string in the format:

Name:       Ravioli
Origin:     Italian
Vegetarian: False
Calories:   246

The Food Constructor

The only way to create a Food object is to call the Food constructor and pass it the proper parameters (name, origin, is_vegetarian, calories). The following string contains food data:

"Ravioli,7,False,246"

but this string is not a Food object. If, however, we call the Food constructor and pass it this same data, we get a Food object. The following code creates a Food variable namned some_food by calling the Food constructor:

some_food = Food('Ravioli', 7, False, 246)

The assertion statement inside the constructor means that is_vegetarian must be True, False, or None. The origin must be a value that is within the length of ORIGIN list.

The @staticmethod decorator

The @staticmethod decorator means that the function origins can be called from the class directly - you do not need a Food object. In other words, you can call origins as follows:

Food.origins()

One reason for having static methods and static variables is to save space. In this way, only one copy of the static method will reside in memory instead of one copy for each object, as is the case with non-static methods. (You will learn more about static methods and variables in CP213.)

The Movie Class

The Movie class is another data storage class and we may use it with our data structures throughout the term.

Movie Data

The Movie class must identify appropriate constants:

• first year of allowed movies
• lowest movie rating allowed
• highest movie rating allowed

A Movie object must contain the following attributes:

• title (str)
• year of release [after 1887] (int)
• director (str)
• rating [a number from 0 to 10] (float)
• genres [type of movie] code (list of int)

Handling the genres code is somewhat complex and will be left to a later time.

The Movie class must contain the following methods:

• a constructor that accepts the movie attribute values as parameters
• a string accessor (i.e. converts the movie attributes to a formatted string)
• comparison methods for ==, <, and <=
• a write method that writes a movie's attributes to a file

A typical movie should be output as a string in the format:

Title:    Dark City
Year:     1998
Director: Alex Proyas
Rating:   7.8
Genres:   science fiction

Movies are sorted by title, then by year. Thus, Zulu, 1964, comes before Zulu, 2013.

The outline of the Movie class is:

    
"""
-------------------------------------------------------
Movie class definition.
-------------------------------------------------------
Author:  David Brown
ID:      123456789
Email:   dbrown@wlu.ca
__updated__ = "2023-05-10"
-------------------------------------------------------
"""


class Movie:
    """
    -------------------------------------------------------
    Constants
    -------------------------------------------------------
    """
    MIN_RATING = 0
    MAX_RATING = 10
    FIRST_YEAR = 1888
    GENRES = ("science fiction", "fantasy", "drama",
              "romance", "comedy", "zombie", "action",
              "historical", "horror", "war", "mystery")
    # Defines a range of valid integer genre codes:
    GENRE_CODES = range(len(GENRES))

    @staticmethod
    def genres():
        """
        -------------------------------------------------------
        Creates a string of Movie genres in the format:
         0 science fiction
         1 fantasy
         2 drama
           ...
        10 mystery
        Use: s = Movie.genres()
        Use: print(Movie.genres())
        -------------------------------------------------------
        Returns:
            string - A numbered string of Movie.genres.
        -------------------------------------------------------
        """
        string = ""

        # your code here

        return string

    def __init__(self, title, year, director, rating, genres):
        """
        -------------------------------------------------------
        Initializes a Movie object.
        Use: movie = Movie(title, year, director, rating, genres)
        -------------------------------------------------------
        Parameters:
            title - movie title (str)
            year - year of release (int)
            director - name of director (str)
            rating - rating of 1 - 10 from IMDB (float)
            genres - numbers representing movie genres_list (list of int)
        Returns:
            A new Movie object (Movie)
        -------------------------------------------------------
        """
        assert year >= Movie.FIRST_YEAR, "Movie year must be >= {}".format(
            Movie.FIRST_YEAR)
        assert rating is None or Movie.MIN_RATING <= rating <= Movie.MAX_RATING, \
            "Movie ratings must be between {} and {}".format(
                Movie.MIN_RATING, Movie.MAX_RATING)
        assert genres is None or genres == [] or min(genres) in Movie.GENRE_CODES, "Invalid genre code {}".format(
            min(genres))
        assert genres is None or genres == [] or max(genres) in Movie.GENRE_CODES, "Invalid genre code {}".format(
            max(genres))

        self.title = title
        self.year = year
        self.director = director
        self.rating = rating
        self.genres = genres

    def __str__(self):
        """
        -------------------------------------------------------
        Creates a formatted string of movie data.
        Use: print(movie)
        Use: print( "{}".format(movie))
        Use: string = str(movie)
        -------------------------------------------------------
        Returns:
            string - the formatted contents of movie (str)
        -------------------------------------------------------
        """
        # Generate the list of genres as a string.
        genres_list = self.genres_string()

        # your code here

        return string

    def __eq__(self, other):
        """
        -------------------------------------------------------
        Compares this movie against another movie for equality.
        Use: movie == other
        -------------------------------------------------------
        Parameters:
            other - other movie to compare to (Movie)
        Returns:
            result - True if title and year match, False otherwise (boolean)
        -------------------------------------------------------
        """
        result = (self.title.lower(), self.year) == \
            (other.title.lower(), other.year)
        return result

    def __lt__(self, other):
        """
        -------------------------------------------------------
        Determines if this movie comes before another movie.
        Use: movie < other
        -------------------------------------------------------
        Parameters:
            other - movie to compare to (Movie)
        Returns:
            result - True if movie precedes other, False otherwise (boolean)
        -------------------------------------------------------
        """
        result = (self.title.lower(), self.year) < \
            (other.title.lower(), other.year)
        return result

    def __le__(self, other):
        """
        -------------------------------------------------------
        Determines if this movie precedes or is or equal to another movie.
        Use: movie <= other
        -------------------------------------------------------
        Parameters:
            other - movie to compare to (Movie)
        Returns:
            result - True if this movie precedes or is equal to other,
              False otherwise (boolean)
        -------------------------------------------------------
        """
        result = self < other or self == other
        return result

    def genres_string(self):
        """
        -------------------------------------------------------
        Returns comma delimited string of genres based upon the
        current movie object's integer genres list.
        e.g.: [0, 2] returns "science fiction, drama"
        Use: string = movie.genres_string()
        -------------------------------------------------------
        Returns:
            string - string of genres (str)
        -------------------------------------------------------
        """

        # Your code here

    def genres_list_string(self):
        """
        -------------------------------------------------------
        Returns comma delimited string of genre indexes based upon the
        current movie object's integer genres list.
        e.g.: [0, 2] returns "0,2"
        Use: string = movie.genres_list_string()
        -------------------------------------------------------
        Returns:
            string - string of genre indexes (str)
        -------------------------------------------------------
        """

        # Your code here


    def write(self, fv):
        """
        -------------------------------------------------------
        Writes a single line of movie data to an open file fv
        in the format
              title|year|director|rating|code
        Use: movie.write(fv)
        -------------------------------------------------------
        Parameters:
            fv - an already open file of movie data (file)
        Returns:
            None
        -------------------------------------------------------
        """
        fv.write("{}|{}|{}|{}|{}\n"
              .format(self.title, self.year, self.director,
                      self.rating, self.genres_list_string()))
        return

  

The only way to create a Movie object is to call the Movie constructor and pass it the proper parameters. The following string contains movie data:

Dark City,1998,Alex Proyas,7.8,0

but this string is not a Movie object.

If, however, we call the Movie constructor and pass it this same data:

    
from Movie import Movie

some_movie = Movie('Dark City', 1998, 'Alex Proyas', 7.8, [0])

  

then the variable some_movie is a Movie object, because it was created by calling the Movie constructor.

Data Structures

The basic concept behind a data structure is that we need some mechanism to store data and perform certain operations on those data efficiently. For example, we may want to be able to store the data and randomly collect pieces of data efficiently. Sometimes, we want to store it so that we pick data off the top or off the bottom efficiently. In some instances, there is some kind of priority to have the data stored and retrieved.

Different data structures would do that work for us. A lot of programming languages already have these data structures built-in. Examples of data structures are arrays, linked lists, binary search trees, heaps, graphs, and hash tables. The point of this course is to look under the hood and see how these data structures are developed. In addition, we are going to learn how to use these data structures in solving problems. We will learn that how these data structures help us in solving problems more efficiently compared to the case where not using them. To summarize:

• a data structure is a group of related data items. All we mean by related is that we are going to have a particular chunk of data. We could be working with data about people, data about movies, simple integers, etc. These are all related data. Data structure is a way of grouping this data together.
• data structures organize data in a program.
• lists and tuples are simple Python data structures: You already worked with data structures in Python if you have worked with lists and tuples. You have done lists in CP104 (perhaps you have worked with tuples, which are lists that cannot be changed). A list is a data structure built into Python and we are going to create our own list because we want to see what is going on under the hood.

Abstract Data Types

In computer science, a data type is an attribute of data which defines what operations can be done on the data, what the meaning of the data is, and how the data values can be stored (Reference: Data type). Example of data types are integer, floating point, character and boolean. These data types are usually referred to as built-in data types. They are available in a programming language and the programmer can use them. In some programming languages, the programmer specifies the type of a variable.

An Abstract Data Type (ADT) describes a collection of data and a set of operations on those data. It does not specify how the set of operations is implemented. It is a data type defined by its behavior from the point of view of the user of the data (the user specifies what functionality should be provided). In the same way that integer, float, and boolean have a set of characteristics and operations associated with them, the abstract data types have operations associated with them.

Example: Priority Queue ADT

An ADT is a conceptual idea and we can discuss ADTs without looking at a single line of code. As an example, we are going to look at an ADT called a Priority Queue. We have chosen the Priority Queue as an example because pretty much all of us are aware what a priority queue is if we know how a hospital emergency room works.

The Priority Queue ADT refers to:

• A collection of prioritized items.
• Items are removed from a priority queue in order of their priority, highest priority first.
• New items may be added to a priority queue at any time. Items of equal priority are removed in order of their addition to the priority queue.

An emergency waiting room is a real-world example of a priority queue. Patients go through triage (the process of determining the priority of patients' treatments based on the severity of their condition) before being seen by a doctor. Those with the worst conditions get highest priority. If two or more patients have equally bad conditions the patients are seen in the order in which they arrived at the emergency waiting room. So the patients in an emergency room are a collection of prioritized items that are removed from the collection based on their priority and can be added to the collection at any time (You can enter the waiting room any time you want).

Image retrieved from Unsplash. Free for use.

Priority Queue Methods

When we define an ADT, we need to define its operations (methods). Here are some of the methods for Priority Queue ADT:

Initialize

Define an empty priority queue.

Size

Return the number of items in a priority queue.

Is Empty

Determine if the priority queue is empty or not.

Add

Add a new item to the priority queue.

Remove

Remove the item with the highest priority from the queue.

Peek

Return the item with the highest priority in the priority queue without removing that item from the priority queue. (i.e. answers this question: who's next?)

All the ADTs have similar methods for adding or removing data items, but the methods are named differently in various ADTs. As we learn ADTs throughout this course, we get to know the method names in different ADTs.

Abstract Data Type as a Class

ADTs are an abstract concept, so the question is how we implement an ADT?

We are going to use Python classes in order to implement our abstract data types. ADTs can be implemented as classes in object-oriented programming languages . Both classes and ADTs describe a set of objects that have identical characteristics and behaviors. The difference is that classes can be implemented only in object-oriented programming languages; however, ADTs can be implemented in most procedural programming languages.

Not all languages are object oriented. Not all languages have classes. Python has classes, Java has classes. C does not. That does not mean we cannot define an abstract data type in C. It just means we have to use a different approach. When we get to CP264, you are taught C, and you'll understand that different approach, but it is not something we deal with now.

Characteristics of ADTs

Modularity

A module packages a collection of entities and controls how those entities can be used. A program is modular if it is divided into well-designed modules (e.g., functions).

Modularity is important because it is easier to fix a function that has a lone job compared to a function that does plenty of jobs. The idea of modularity means testing is easier. And if you can test easier, chances are you write better code.

Classes provide modularity. They provide a number of public methods to the user and The same is with ADT. The specifies a set of operations to be used by the user of ADT without user being The user can use them as a black box.

Information Hiding

Refers to hiding the internal mechanisms of a module from external programmers so that private information cannot be accessed or modified. In the context of ADTs or classes, it means that we do not need to know what is under the hood when we use an ADT or a class.

Analogy: you can drive a car and not know whether it is a gas engine under the hood or an electrical car. What you should know is when you press the accelerator, it moves. When you press the brake it stops and that is what is important to you as the driver. Mechanics need to know under the hood but a driver does not care. All you know is knowing how to operate the car. In this analogy, the car is the ADT, the driver is the user of ADT, and car engine is the data structure. The same holds for ADTs. The user of an ADT just needs to know the functions provided by the ADT (its interface).

Interface

The part of a module that is visible to an external programmer. Interface is tied up with information hiding in the sense that the user of a module may not be able to see the code under the hood. Both ADTs and classes provide methods (interfaces) that is used by the user.

In the car analogy, the interfaces are: pressing a specific pedal to make the car go, pressing a specific pedal to make the car stop, turning the wheel in certain direction to make it go left or go right.

Encapsulation

The grouping of an entity and its associated methods together in a module (both ADTs and classes provide encapsulation). Encapsulation could be implemented in pretty much every language; it is certainly easier in some languages, such as object-oriented languages than others.

ADTs vs Data Structures

In this section, we are going to discuss the similarities and difference between ADTs and data structures. Both ADT and data structure are similar in the sense that they are designed to hold multiple pieces of data. The data could be simple values such as integers or strings, or more complex data, such as Student or Food objects.

They are different in the sense that ADT describes the functionality it performs, but it does not provide any implementation. ADT is an abstract concept because it has the concept of a data structure without having to actually implement it. However, a data structure is a concrete representation of the data and specifies how the data is stored and how the algorithms for various operations on the data are implemented.

The following figure shows the relationship between an ADT and a data structure. As you see ADT specifies the interfaces (public methods) that are used by the user of the ADT. An ADT uses a data structure for implementing its methods (for storing, retrieving and manipulating data). Arrays and linked-lists are the most common data structures used for implementing ADTs methods and we will talk about them in more details in following lessons. The point is that the methods should work regardless of the data structure used. The developed of ADT is able to modify the implementation without affecting the user of ADT. In other words, the details of the implementations are not relevant to the user of the ADT.

Having said that, the details of implementations determine the performance of ADT methods. Therefore, depending on the application, a user may want to know the underlying implementation to choose the most efficient ADT implementation. Later in the course we learn about different data structures, we learn about mechanisms to measure efficiency of an ADT method implementation (algorithm), and we can compare the efficiency of ADT methods implemented using different data structures.

Created by Masoomeh Rudafshani. Used with permission.

Implementations of Data, Data Structures and Abstract Data Types in Python

A data structure holds data items and we need to know how the data items are represented. In this course, Python classes are also used for defining custom data types such as Student and Food. These classes are designed to hold a single piece of data. That data may have many attributes and methods, both of those attributes and methods taken together designed to represent a single data item.

Data structures are collection of data and they include details about how data is stored, retrieved, and manipulated. Usually arrays or linked lists are used for storing a collection of data. In arrays, data items are stored in contiguous locations in memory. In linked lists, each data item is stored in a separate place in memory and it points to the locations of the next data items. We will learn in more details about these data structures.

We use Python classes for implementing data structures in this course. The class for a data element is a simpler class than a class representing a data structure. Data items have attributes and methods. Data structures also have attributes and methods. However, a data structure is designed to hold multiple pieces of data items and it does not matter whether that data is simply integer, string, Student, or Food. The data structures that we create should get properly designed and work with any kind of data.

ADTs are also implemented using Python classes in this course. An implementation of an ADT must hold multiple pieces of data, whether simple values such as integers or strings, or more complex objects such as Student or Food objects. An implementation of an ADT must have the following properties when used in a Python program:

• It must be initialized before it can be used: We must be able to create an instance of an ADT which is empty. The ADT acts as a container for data and it should be created before we can put data in it. That's why all the ADTs have methods such as initialize, is empty (to check if the ADT is empty or not), is full, etc.
• An instance of an ADT should work with one type of data only. All that means is if we have a priority queue and the priority queue contains Food objects, then every piece of data in the priority queue is Food object. We cannot mix Food and Movie objects in one ADT.
• The ADT may be used only through its methods: It means that if we want to add a piece of data to the ADT, we have to use the add method or whatever the equivalent name is. If we want to remove something, we must use the remove method. If we want to count how many items are in the ADT, but there is no count method, then we cannot count the number of items. The ADT puts restrictions on what you can and cannot do based upon what its methods are.
• The effect of ADT methods are implementation independent. In other words, programs that use an ADT should be able to use different implementations of an ADT interchangeably; i.e. the internal implementation of the ADT should be invisible to the external program that uses it. Defining ADTs as a class provide this opportunity by providing the attributes and methods of the class defined and accessible to the user of the class and at the same time hiding the internal of the class from the user of the class.

car analogy: If we take the engine of a car out and put a new engine in, the driver neither knows nor cares. The driver may notice a performance difference, but the car still operates the same way. The driver still uses the same interface: turns the steering wheel in order to turn left or right, presses the accelerator, and presses the brakes. The fact that there is a different engine under the hood is completely irrelevant. In this analogy: a car is an ADT, driver is the user of ADT, and the engine is the data structure and the internal details of the implementations of the ADT.

There are numerous ADTs and data structures definitions in computer science. (See for example the list at Wikipedia's List of data structures.) In CP164 we will be working with the following ADTs:

• stacks
• queues
• priority queues
• lists

and the following data structures:

• arrays
• linked list
• doubly linked list
• binary search trees
• hash tables

We will be implementing these ADTs and data structures using Python classes. We will design some of these ADTs with more than one underlying data structure.

Summary

In this lesson we introduced the concept of classes and objects in general and how they are implemented in the Python programming language. We also talked about data structures and ADTs. ADTs are an abstract representation of a collection of data items along with the operation on those data. ADTs have no specific implementation; data structures are used to implement ADTs.

References

1. Thinking in Java, Bruce Eckel, 2007, Prentice Hall Professional
2. Geeks for Geeks