Practical 11: Abstract Data Types and Custom Structures

tuple      : (2331, 'Aarti Kulkarni', [78, 65, 92])
  the name is student_tuple[1]: Aarti Kulkarni
dictionary : {'roll': 2331, 'name': 'Aarti Kulkarni', 'marks': [78, 65, 92]}
  the name is student_dict['name']: Aarti Kulkarni
class      : Student(2331, 'Aarti Kulkarni', [78, 65, 92])
  the name is s.name: Aarti Kulkarni
  and it can compute: total 235 average 78.33 grade first class

The tuple is the smallest and the least readable. student_tuple[1] is the name, and nothing in the program says so. Change the order of the fields and every use of it is silently wrong. A tuple is also immutable: the marks list inside it can be changed, but the roll number cannot, which is sometimes exactly right and sometimes a nuisance.

The dictionary is readable and unguarded. student_dict["name"] says what it is, which is a real improvement. But nothing stops student_dict["nmae"] = "x" from quietly adding a fourth key, nothing requires a student to have marks at all, and the dictionary cannot compute anything: the total has to be worked out by whoever wants it, everywhere.

The class is the ADT. The fields have names, the operations live with the data, and the rules can be enforced. s.grade() is written once and used everywhere; sum(student_dict["marks"]) is written everywhere and gets changed in one place out of four.

Use a tuple for a value with two or three parts that never changes, such as a coordinate. Use a

dictionary when the keys are not known until the program runs, such as data read from a file.

Use a class when the thing has rules or behaviour, which in this module it always does.

Python has a shorthand that gives a class most of its boilerplate for nothing:

from dataclasses import dataclass

@dataclass
class Student:
    roll: int
    name: str
    marks: list

That writes __init__, __repr__ and __eq__ for you. It is worth knowing and it is not used in this module, because the exercises are about writing the structure, and an examiner asking for a Student ADT wants to see __init__.

Create, update and delete, which need a collection

MU's second bullet asks for the basic operations, and they belong not to one object but to a collection of them. One Book cannot be created and deleted; a catalogue of Books can.

The four operations together are called CRUD: create, read, update, delete.

class Book:
    """A book in a library: the ADT and nothing but the ADT."""

    def __init__(self, isbn, title, author, copies):
        if copies < 0:
            raise ValueError("a book cannot have a negative number of copies")
        self.isbn = isbn
        self.title = title
        self.author = author
        self.copies = copies
        self.out = 0                      # how many are lent out

    def available(self):
        return self.copies - self.out

    def lend(self):
        if self.available() == 0:
            raise ValueError(f"no copy of {self.title!r} is available")
        self.out += 1

    def take_back(self):
        if self.out == 0:
            raise ValueError(f"no copy of {self.title!r} is out")
        self.out -= 1

    def __repr__(self):
        return (f"Book({self.isbn!r}, {self.title!r}, {self.author!r}, "
                f"{self.copies})")


class Library:
    """A collection of Books, with create, read, update and delete."""

    def __init__(self):
        self.books = {}                   # isbn -> Book

    def create(self, isbn, title, author, copies):
        if isbn in self.books:
            raise KeyError(f"{isbn} is already in the catalogue")
        self.books[isbn] = Book(isbn, title, author, copies)
        return self.books[isbn]

    def read(self, isbn):
        if isbn not in self.books:
            raise KeyError(f"{isbn} is not in the catalogue")
        return self.books[isbn]

    def update(self, isbn, **changes):
        book = self.read(isbn)
        for field, value in changes.items():
            if not hasattr(book, field):
                raise KeyError(f"a Book has no field called {field!r}")
            setattr(book, field, value)
        return book

    def delete(self, isbn):
        book = self.read(isbn)
        if book.out:
            raise ValueError(f"{book.title!r} has {book.out} copy out")
        del self.books[isbn]
        return book

    def __len__(self):
        return len(self.books)

    def report(self):
        print(f"  {'isbn':<14}{'title':<32}{'copies':>7}{'out':>5}{'free':>6}")
        for isbn in sorted(self.books):
            b = self.books[isbn]
            print(f"  {b.isbn:<14}{b.title:<32}{b.copies:>7}{b.out:>5}"
                  f"{b.available():>6}")
        print(f"  {len(self)} title(s) in the catalogue")


lib = Library()
lib.create("978-0132126", "Operating System Concepts", "Silberschatz", 3)
lib.create("978-1118290", "Data Structures in Python", "Goodrich", 2)
lib.create("978-8183332", "Data Structures Through Python", "Kanetkar", 1)
print("after three creates")
lib.report()

print()
print("read  : ", lib.read("978-1118290"))
lib.update("978-1118290", copies=5)
print("update: copies of Goodrich now", lib.read("978-1118290").copies)

lib.read("978-8183332").lend()
print("lend  : Kanetkar out", lib.read("978-8183332").out,
      "available", lib.read("978-8183332").available())

print()
for isbn, what in (("978-8183332", "delete a book that is lent out"),
                   ("978-0000000", "read a book that is not there")):
    try:
        lib.delete(isbn)
    except (KeyError, ValueError) as e:
        print(f"{what}: {type(e).__name__}: {e}")

try:
    lib.create("978-0132126", "Operating System Concepts", "Silberschatz", 1)
except KeyError as e:
    print(f"create a book twice: KeyError: {e}")

try:
    Book("978-1", "Nothing", "Nobody", -2)
except ValueError as e:
    print(f"a negative number of copies: ValueError: {e}")

print()
lib.read("978-8183332").take_back()
lib.delete("978-8183332")
print("after taking the copy back and deleting")
lib.report()

after three creates
  isbn          title                            copies  out  free
  978-0132126   Operating System Concepts             3    0     3
  978-1118290   Data Structures in Python             2    0     2
  978-8183332   Data Structures Through Python        1    0     1
  3 title(s) in the catalogue

read  :  Book('978-1118290', 'Data Structures in Python', 'Goodrich', 2)
update: copies of Goodrich now 5
lend  : Kanetkar out 1 available 0

delete a book that is lent out: ValueError: 'Data Structures Through Python' has 1 copy out
read a book that is not there: KeyError: '978-0000000 is not in the catalogue'
create a book twice: KeyError: '978-0132126 is already in the catalogue'
a negative number of copies: ValueError: a book cannot have a negative number of copies

after taking the copy back and deleting
  isbn          title                            copies  out  free
  978-0132126   Operating System Concepts             3    0     3
  978-1118290   Data Structures in Python             5    0     5
  2 title(s) in the catalogue

What that program is careful about

Every operation that can fail, checks, and raises. There are five such checks and the output shows four of them firing:

The rule from [Python for Data Structures: the Tools This Module Uses] is being followed: a failed operation raises and does not return None. And the exception type carries meaning: KeyError for something not present, ValueError for something present and wrong.

update refuses a field that does not exist. hasattr(book, field) is the guard, and without it lib.update(isbn, copyes=5) would add a new attribute called copyes and the real copies would be untouched. The program would print no error and give the wrong answer, which is the dictionary's problem from the last section appearing in a class.

delete returns the book it removed. A delete that returns the deleted object lets a caller undo it, which is how the undo of [Practical 14: Doubly Linked Lists] works.

__len__ makes len(lib) work, which is the first of Python's protocols this module uses. A class that defines __len__ can be measured with len() and is also truthy when non-empty, so if lib: works. __repr__ and __len__ are the two every container in this module defines.

The catalogue is a dictionary keyed by ISBN, so read is one step whatever the size. A list of Books would have to be searched, which is O(n). That is a data structure decision inside the ADT, and no caller can tell: swap the dictionary for a hash table of your own from [Practical 20: Hashing and Collision Handling] and every line outside the class still works. That is what "abstract" means, demonstrated.

What abstraction actually buys

The Employee, MU's third named ADT, is where the benefit is easiest to see.

# a primitive type: what it is and what you may do with it are fixed
n = 42
print("an int:", n, "of type", type(n).__name__)
print("  everything it can do is built in:", n + 1, n * 2, n ** 2)

# an abstract data type: WHAT it does is declared, HOW is hidden
class Employee:
    """Name, basic pay and a rule for the allowance. The rule is hidden."""

    HRA_RATE = 0.20
    DA_RATE = 0.10

    def __init__(self, name, basic):
        self.name = name
        self._basic = basic          # the single underscore says: not yours

    def basic(self):
        return self._basic

    def allowances(self):
        return self._basic * (Employee.HRA_RATE + Employee.DA_RATE)

    def gross(self):
        return self._basic + self.allowances()

    def raise_by(self, per_cent):
        if per_cent < 0:
            raise ValueError("a raise cannot be negative")
        self._basic = self._basic * (1 + per_cent / 100)

    def __repr__(self):
        return f"Employee({self.name!r}, {self._basic:.2f})"


e = Employee("R. Deshmukh", 30000)
print()
print("an Employee:", e)
print(f"  basic {e.basic():.2f}, allowances {e.allowances():.2f}, "
      f"gross {e.gross():.2f}")
e.raise_by(10)
print("after a 10 per cent raise:", e)
print(f"  gross is now {e.gross():.2f}")

print()
print("what makes it ABSTRACT:")
print("  the caller asks for gross() and never computes it")
print("  the two rates could become a table from a database")
print("  and not one line of the caller would change")

an int: 42 of type int
  everything it can do is built in: 43 84 1764

an Employee: Employee('R. Deshmukh', 30000.00)
  basic 30000.00, allowances 9000.00, gross 39000.00
after a 10 per cent raise: Employee('R. Deshmukh', 33000.00)
  gross is now 42900.00

what makes it ABSTRACT:
  the caller asks for gross() and never computes it
  the two rates could become a table from a database
  and not one line of the caller would change

_basic has one leading underscore. In Python that is a convention and not a lock: it means "this is not part of what I promise, do not touch it". Nothing stops a caller from writing e._basic = 0, and the underscore tells them that if they do, and it breaks later, that is their fault. Java would write private; Python writes an underscore and trusts you.

The caller never computes the gross pay. It asks. So when the allowance rule changes, and in India it changes every few years, one class changes and nothing else does. Had the caller been computing basic * 1.30 itself, in eleven places, the change would be eleven edits and one of them would be missed.

raise_by enforces a rule that an int cannot. A plain number for the basic pay would happily take a negative raise. The ADT refuses it.

Those three paragraphs are the answer to "what is the advantage of an abstract data type", and they are worth four marks:

1. Encapsulation. The data and the operations on it are in one place, so a rule is written

once.

1. Information hiding. The representation is private, so it can change without breaking

callers.

1. A validated state. The type can refuse a value that makes no sense, which a primitive

cannot.

1. Reuse. The type can be used anywhere without being re-understood.

Procedure

1. Write the three Students. Run it, then change the order of the tuple's fields and note that

student_tuple[1] now gives the wrong thing with no error.

1. Add a passed() method to the class that returns True when every mark is 40 or more.
2. Write the Library. Run it and check all four error messages appear.
3. Remove the hasattr check from update, call lib.update(isbn, copyes=9), and print the

catalogue. Nothing complains and nothing changed.

1. Replace the dictionary in Library with a list of Books and rewrite read to search it.

Confirm that no code outside the class changes.

1. Write the Employee. Change HRA_RATE to 0.25 and note that only one line moved.
2. Try e._basic = -100 and then e.gross(). The underscore is a convention, not a lock.

Result

The abstract data types Student, Book and Employee were modelled as classes. The Student was built as a tuple, a dictionary and a class and the three compared: only the class can name its fields, carry its own operations and enforce a rule. A Library of Books implemented create, read, update and delete over a collection, with five failure cases each raising the appropriate exception, and the representation inside it was shown to be replaceable without changing a line outside. The Employee showed the three benefits of abstraction: the allowance rule is written once, the representation is hidden behind an underscore, and a negative raise is refused.

Where marks are lost

• Saying an ADT is a class. A class is one way of implementing one. The ADT is the description

of the operations and their meanings.

• Not distinguishing the ADT from the data structure. A Stack is an ADT; an array is a data

structure; a Stack over an array is one implementation.

• Only the data, with no operations. A class with __init__ and nothing else is a record, not

an ADT.

• No validation. The whole answer to "why not just use an int" is that a type of your own can

refuse a wrong value.

• Returning None from a failed create or delete instead of raising.
• Using KeyError and ValueError interchangeably. Not present is a KeyError; present and

wrong is a ValueError.

• No __repr__, so the examiner sees a list of memory addresses.
• Writing update so that a misspelled field silently creates a new one.

For the journal

Write the aim, MU's own wording, and the definitions of abstract data type and data structure in your own words, because the first question is always one of those. Then the Student three ways with its output, and one sentence on which you would use and why. Then the Library program in full with its run, including the four error lines, because the failure cases are what distinguish a complete answer. Then the Employee and the four advantages of abstraction as a list. The conclusion: an ADT declares what a type does and hides how it does it, which is what lets the representation change and what lets the type enforce rules a primitive cannot.

Quick revision

• An abstract data type is the values and the operations, with the implementation unspecified.

A data structure is a way of laying the values out. One ADT, many structures.

• Primitive types come from the language, hold one value, and cannot enforce a rule. An ADT is

yours, holds several values and behaviour, and can.

• Tuple: small, ordered, immutable, unnamed fields. Dictionary: named keys, no rules, no

behaviour. Class: named fields, its own operations, and it can refuse a bad value.

• CRUD is create, read, update, delete, and they belong to a collection, not to one object.
• A failed operation raises. KeyError for not present, ValueError for present and wrong.
• update checks with hasattr that the field exists, or a misspelling silently adds a new one.
• A leading underscore means "not part of the promise". It is a convention, not a lock.
• __repr__ for a readable printout, __len__ so that len() and truthiness work.
• The four advantages: encapsulation, information hiding, a validated state, and reuse.
• The Library's catalogue is a dictionary, and could be a list or a hash table, and no caller

would know. That is abstraction in one sentence.

Questions you should be able to answer

1. Define an abstract data type. A description of a type by the values it can hold and the operations on it, with what each operation takes, gives and requires, and with nothing said about how the values are stored.

2. What is the difference between an ADT and a data structure? The ADT is the contract: what the operations are and what they mean. The data structure is the implementation: how the values are laid out in memory. One ADT can be implemented by several structures.

3. Give three differences between a primitive type and an abstract data type. A primitive comes from the language and an ADT from you; a primitive holds one value and an ADT holds several plus behaviour; a primitive cannot refuse a meaningless value and an ADT can.

4. Why model a Student as a class rather than a dictionary? Because the class names its fields, so a misspelling is an error rather than a new key; it carries its own operations, so the total and the grade are written once; and it can enforce rules, such as refusing a negative mark.

5. What are the four basic operations on a collection, and why do they not belong to one object? Create, read, update and delete. One Book cannot be created or deleted; the catalogue that holds it can.

6. lib.update(isbn, copyes=5) is called by mistake. What should happen, and what happens without a guard? It should raise a KeyError naming the unknown field. Without the hasattr guard it adds a new attribute called copyes, changes nothing that matters, and reports no error.

7. What does a single leading underscore on an attribute mean in Python? That it is not part of the class's promise and a caller should not use it. It is a convention: nothing prevents access, and a caller who relies on it has no complaint when it changes.

8. The Library keeps its books in a dictionary. What would change if it kept them in a list? Inside the class, read would have to search, so it would go from one step to O(n). Outside the class, nothing at all. That is what information hiding means.

9. Name the four advantages of using an abstract data type. Encapsulation, so the data and its operations are together; information hiding, so the representation can change; a validated state, so a meaningless value can be refused; and reuse, because the type can be used without being re-understood.