Program 2

Classes, Overloaded Operators, and Iterators

ICS-33: Intermediate Programming


Introduction This programming assignment is designed first to ensure that you know how to write a simple (numeric-like) class that overloads many of the standard Python operators by defining various double-underscore methods. It also ensures that you know how to write a class that implements iterators, by defining both the __iter__ and __next__ methods. Finally it ensure that you know how to write iterator decorators by using special generators (similar to functions, but using yield instead of return) in a module.

There are three separate parts to this assignment. In the first part you will write a module defining a single, large numeric-like class that overloads many operators (including those performing arithmetic and relational comparisons). In the second part you will write a medium-size class, which defines various methods, including some double-underscore methods and specifically the iterator protocol methods (__iter__ and __next__). In the third part you will write a module that defines various iterator decorators implemented by generators: each iterator decorator has argument(s) that are iterators and is itself used an iterator.

You should download the program2 project folder and unzip it to produce an Eclipse project with three modules. You will write classes in the first two modules, which can be tested in the standard driver using the batch self-check files I supplied; you will write generators in the third module, which can also be tested by a batch self-check I supplied, but can are tested by a special generatordriver.py module included in this project. Eventually you will submit each of the three modules you write separately to Checkmate.

It is recommend that you work on this assignment in pairs, with someone in your lab section. Try to find someone who lives near you, with similar programming skills, and work habits/schedule: e.g., talk about whether you prefer to work mornings, nights, or weekends; what kind of commitment you will make to submit program early.

Only one student should submit all parts of the the assignment, but both students' UCInetID and name should appear in a comment at the top of each submitted .py file. A special grading program reads this information. The format is a comment starting with Submitter and Partner (when working with a partner), followed by a colon, followed by the student's UCInetID (in all lower-case), followed by the student's name in parentheses (last name, comma, first name -capitalized appropriately). If you omit this information, or do not follow this exact form, it will require extra work for us to grade your program, so we will deduct points.

For example if Romeo Montague (whose UCInetID is romeo1) submitted a program that he worked on with his partner Juliet Capulet (whose UCInetID is jcapulet) the comment at the top of each .py file would appear as:

# Submitter: romeo1(Montague, Romeo)
# Partner  : jcapulet(Capulet, Juliet)
# We certify that we worked cooperatively on this programming
#   assignment, according to the rules for pair programming
If you do not know what the terms cooperatively and/or rules for pair programming mean, please read about Pair Programming before starting this assignment. Please turn in each program as you finish it, so that I can more accurately assess the progress of the class as a whole during this assignment.

Print this document and carefully read it, marking any parts that contain important detailed information that you find (for review before you turn in the files). The code you write should be as compact and elegant as possible, using appropriate Python idioms.


Problem #1: Polynomial Class (operators)

Problem Summary:

Write a class named Poly that represents and defines operators for polynomial objects, which are represented by a dictionary whose keys are non-negative powers of x and whose associated values are the non-zero coefficients of these terms. Operators will typically be defined to work on polynomials, or between a polynomial and a numeric (int or float) value. When we perform arithmetic on polynomials (like adding two polynomials), the result is often another polynomial. The Poly class will be be immutable except for one helper method: _add_term (and the __setitem__ and __delitem__ methods). All other methods will not mutate the polynomial; the methods that must return a polynomial (like adding polynomials) will return a newly constructed Poly object.

Details

  1. Define a class named Poly in a module named poly.py

  2. Define an __init__ method that has an arbitrary number (zero or more) of 2-tuple arguments: each will store the coefficient and power of one term in the polynomial. Note that the coefficient is the first value in the 2-tuple; the power is the second value in the 2-tuple. For example, writing Poly( (3, 2), (-2, 1), (4, 0) ) represents the polynomial 3x2 - 2x + 4; recall that x^0 = 1. Finally, note that all the terms in the argument must appear in decreasing order, based on the the value of the power.

    IMPORTANT: Store a polynomial as a dictionary (dict) of terms: use each power as a key, whose associated value is its coefficient. The example polynomial above would be stored as a dictionary that might print as {1: -2, 2: 3, 0: 4}; it can print the key: value terms in any order, because order is unimportant in dictionaries. Name this dictionary self.terms, so that the tests can access it by that name.

    This dictionary should never store a coefficient of 0 for any power; if a coefficient of 0 is specified for a power, just omit it from the dictionary (and raise no exception). Also, the __init__ method should raise an AssertionError with an appropiate message if the argument(s) violate any of the following conditions:

    • Each coefficient must be an int or float value.
    • Each power must be an int whose value is >= 0.
    • Powers must appear in decreasing order in the arguments.

    For example, in my code writing Poly( (3, 'abc') ) raises AssertionError with the message Poly.__init__: illegal power in term: (3, abc).

  3. Define a __repr__ method that returns a string, which when passed to eval returns a newly constructed Poly with the same value as the object __repr__ was called on.

    For p = Poly((3, 2), (-2, 1), (4, 0)), calling repr(p) returns the string 'Poly((3, 2), (-2, 1), (4, 0))'; note that the order of the terms matters, because the powers in the arguments to Poly must be decreasing.

  4. Define a __str__ method that returns a string that nicely displays a polynomial, using all the standard mathematical abbreviations for coefficients and powers (ordered from highest to lowest power). Specifically

    • A polynomial with no terms returns 0
    • Polynomial terms are separated by either + or - (with one space on each side of the sign); the +/- depends on the sign of the second term, whose coefficient will always appear unsigned (the term with the highest power will appear signed)
    • A term with coefficient c and power p appears as cx^p (except in the special cases listed below)
      • A term whose power is 0 omits the x^0 and appears as just c
      • A term whose coefficient is plus or minus 1 or plus or minus 1.0 (and whose power is not 0) omits that coefficient and appears just x^p

    For example, if p = Poly( (-3, 2), (-1, 1), (4, 0) ), then calling str(p) returns the string '-3x^2 - x + 4'. Note that no coefficients in a polynomial will be 0, but str(Poly()) (a polynomial constructed with no terms) will appear as 0. Hint: My code used a nested function: it first computed terms with non-signed/negatively signed coefficients always separated by +, and then substituted for the pattern + -.

    IMPORTANT: Many of the self-checks in the bsc1.txt file check this string representation of a polynomial, so it must be computed correctly or many operators will fail.

  5. Define a __bool__ method that returns True if the Poly represents any polynomial that is not 0.

  6. Define a __len__ method that returns the higest power in the polynomial. For the polynomial 3x5 + 2x2 - 1, its length is 5. As a special case, a polynomial with no terms represents 0 and should return a length of 0; 0 would also be returned by any polynomial that is constant.

  7. Define a __call__ method that takes one numeric (int or float) argument: it returns the value produced by evaluating the polynomial with that value substituted for x. For example if p is 3x2 - x + 4, then p(2) returns 3*22 - 1*2 + 4 which is 14. Hint: I wrote 1 line, using the sum function iterating over a comprehension.

  8. Define an __iter__ method that produces 2-tuples (containing a coefficient followed by its power), such that the powers of the tuples are decreasing: for example if p is 3x2 - x + 4, then iterating over the p produces the tuple (3, 2) followed by (-1, 1) followed (4, 0).

    Important: Once you have written __iter__, you may be able to simplify slightly the repr and str methods written earlier.

  9. The following three methods are all similar in structure. You might find it useful to call these methods implicitly (using indexing) in the other operators you are asked to define below; but doing so is not necessary.
    • Define a __getitem__ method whose argument is any power; it returns the coefficient associated with that power. If the argument is not an integer or is < 0, raise a TypeError exception with an appropriate message. If the argument is not a power in the polynomial's dictionary, return the int 0. For example, if p is the polynomial 3x2 + 4, then p[2] returns 3 and p[1] returns 0.

    • Define a __setitem__ method whose arguments are any power and its new coefficient; it associates the power with the coefficient, whether or not that power is already in the polynomial dictionary. If the power argument is not an integer or is < 0, raise a TypeError exception with an appropriate message. If the coefficient argument is equal to 0, don't create/change that term, but instead delete it from the dictonary, if it is present, because no coefficients of 0 should appear in the polynomial. This method can mutate the state of a polynomial.

    • Define a __delitem__ method whose argument is any power; it deletes that power (and its associated coefficient) from the polynomial if it is present (if the power is not present, the polynomial remains unchanged). If the argument is not an integer or is < 0, raise a TypeError exception with an appropriate message. This method can mutate the state of a polynomial.

  10. Define the helper method _add_term which take a Poly object (as the self parameter) and a coefficient and power as arguments that specify the term: the coefficient must be numeric (int or float) and the power must be an int that is >= 0; otherwise raise a TypeError exception with an appropriate message. It mutates the Poly object to include (add in) the specified term according to the following rules: (1) if the power is not in the polynomial and the coefficient is not 0, it is added along with the coefficient; (2) if the power is in the polynomial, the coefficient is added to existing coefficient for that power, but (2a)and if the resulting sum/coefficient is 0 that power is deleted from the polynomial.

    (1) If the polynomial is 3x2 + 4, then adding a term with coefficient -2 and power 1 (-2x) would produce the polynomial 3x2 -2x + 4.

    (2) If the polynomial is 3x2 + 4, then adding a term with coefficient 2 and power 2 (2x2) would produce the polynomial 5x2 + 4.

    (2a) If the polynomial is 3x2 + 4, then adding a term with coefficient -3 and power 2 (-3x2) would produce the polynomial 4.

    You can call the _add_term helper method when defining the + and * operators specified below.

  11. Define methods for the + and - prefix operators and the abs function. Hint: I wrote each in 1 line, using a comprehension.

  12. Define a differentiate method; it returns the derivative of the polynomial. The derivative of a polynomial is a polynomial with each term cxp in the original polynomial tranformed to the term cpxp-1.

  13. Define an integrate method that takes a numeric (int or float) argument whose default value is 0; it returns the integral of the polynomial The integral of a polynomial is a polynomial with each term cxp in the original polynomial tranformed to the term c/(p+1)xp+1 added to the constant term specified by the argument.

  14. Define an def_integrate method that takes two numeric (int or float) arguments; it returns the area under the curve specified by the polynomial between the first and second argument.

  15. Define all the underscore methods needed to ensure the prefix +/- work correctly: + returns a new polynomial with the same coefficients and powers; - returns a new polynomial with negated coefficients for all the powers.

  16. Define all the underscore methods needed to ensure that the add, subtract, and multiply operators produce the correct answers when their operands are any combination of a Poly object with a Poly, int, or float object.

    If Python tries to apply an arithmetic operator to a Poly object and any other type of value, raise the standard TypeError exception with the standard messsage about unsupported operand types: see what 1+'a' produces in the Python interpreter.

    Recall that none of these operators mutate their operands. Each produces a new polynomial and returns it as a result: we can compute such a polynomial by constructing an empty polynomial and then iterating over the operand polynomials and adding terms (see the _add_term method, which has all the needed properties) to the constructed polynomial. You can use an int/float value directly, or you can convert it to a polynomial first: 5 is equivalent to Poly( (5,0) ) in that its coefficient is 5 and its power for x is 0.

    • When adding two polynomials, the result has all the powers of each operand; if a power appears in both operands, its coefficient in the resulting polynomial is the sum of the operand coefficients (although if the coefficients sum to 0, that power will not appear in the polynomial).

      For example, adding 3x3 + 2x2 + 4 with x3 - 2x2 + x + 2 produces 4x3 + x + 6.

    • When multiplying two Polynomials, the resulting Polynomial has terms for every term in the first operand multiplied by every term in the second operand. Iterate over terms in each operand and determine the coefficient and power for adding the resulting term they produce.

      For example, multiplying 3x2 + 2x + 1 by x + 2 produces 3x3 + 8x2 + 5x + 2. This calculation is illustrated in the table below.

      Term in Left Operand
      3x2 + 2x + 1
      Term in Right Operand
      x + 2
      Resulting Term Added into Product
      3x2 x 3x3
      3x2 2 6x2
      2x x 2x2
      2x 2 4x
      1 x x
      1 2 2

      In the result, 3x3 comes from the 1st term added to the product, 8x2 comes from the 2nd and 3rd terms added to the product, 5x comes from the 4th and 5th terms added to the product, 2 comes from the 6th/last term added to the product.

    Note that both + and * are commutative: for Polynomials a and b, a+b produces the same Polynomial as b+a, and a*b produces the same Polynomial as b*a. Commutivity and the use of the negation operator can make programming these methods simpler.

  17. Define all the underscore methods needed to ensure that the exponentiate operator (**) produces the correct answers when their left operand is a Poly object and their right operand is restricted to be a non-negative int object. Use repeated multiplication to solve this problem. In any other case, raise the standard TypeError exception with the standard messsage about unsupported operand types.

  18. Python automatically provides meanings for +=, -=, *=, and **=.

  19. Define all the underscore methods needed to ensure that we can compare Poly objects using the six standard relational operators, with any combination of a Poly object and a Poly, int, or float object.

    If Python tries to apply a relational operator to an Poly object and any other type of value, raise the standard TypeError exception with the standard messsage about unsupported operand types: see what 1<'a' produces in the Python interpreter.

    For == two Poly objects are equal if they have the same terms; they != if any terms are different. Likewise, an int or float is == or != based on whether the polynomial is a constant with that numeric value.

    For <, <=, >, >= the rules are more complex: they depend on the highest power in each polynomial and possibly the coefficent of the highest powers. Polynomial p1 is less than polynomial p2 if either its highest power is less or both polynomials have the same highest power and p1's coeffient is less than p2's coefficient.

  20. Define a __setattr__ method that ensures objects in the Poly class cannot have new attributes added. The methods that you will write should never bind any instance name (except in __init__, which initializes terms) but exclusively returns newly constructed Poly objects with the correct values. If an attempt is made to add new attributes to an object (by defining a new attribute or rebinding an existing attribute), raise an AssertionError with an appropriate message. Do not attempt to solve this part of the problem until all other parts are working correctly.

Testing

The poly.py module includes a script does some simple polynomial calculations and then calls driver.driver(). The project folder contains a bsc1.txt file (examine it) to use for batch-self-checking your class. These are rigorous but not exhaustive tests. Incrementally write and test your class: for example, getting one arithmetic (or relational) operator working correctly will create a pattern for the others.

Note that when exceptions are raised, they are printed by the driver but the Command: prompt sometimes appears misplaced.

I have written other code at the bottom of our poly.py module, before calling the driver, to test the Poly class: e.g., when testing + we can just define two Polys and print their sum; you can write other testing code here. You can also type such code into the driver as illustrated below, but if you want to perform the same test over and over again when debugging, it it better to put this code before the driver is called. Notice the default for each command is the command previously entered.

  Driver started
  Command[!]: from poly import Poly
  Command[from poly import Poly]: p1 = Poly((3,2), (-2,1), (4,0))
  Command[p1 = Poly((3,2), (-2,1), (4,0))]: print(p1)
  3x^2 - 2x + 4
  Command[print(p1)]: print(p1 + p1 + 2)
  6x^2 - 4x + 10
  Command[print(p1 + p1 + 2)]: print(p1**3)
  27x^6 - 54x^5 + 144x^4 - 152x^3 + 192x^2 - 96x + 64
  Command[print(p1**3)]: print(p1.integrate())
  x^3 - x^2 + 4.0x
  Command[print(p1.integrate())]: print(p1.def_integrate(0,2))
  12.0
  Command[print(p1.def_integrate(0,2))]: quit
  Driver stopped

Problem #2: Bag Class (iterators)

Problem Summary:

Write a class that represents and defines methods, operators, and iterators for a Bag class. Bags are similar to sets, and have similar operations (of which we will implement just the most important) but they can store multiple copies of items. Fundamentally, we will store bags as dictionaries (use defaultdict) whose elements are keys and whose values are the number of times the key occurs in the bag. You must store Bags using this data type as specified

Details

  • Define a class named Bag in a module named bag.py

  • Define an __init__ method that has one parameter, an iterable of values that initalize the bag. Writing Bag() constructs an empty bag. Writing Bag(['d','a','b','d','c','b','d']) construct a bag with one 'a', two 'b's, one 'c', and three 'd's.

  • Define a __repr__ method that returns a string, which when passed to eval returns a newly constructed bag with the same value (==) to the object __repr__ was called on. For example, for the Bag in the discussion of __init__ the __repr__ method would print its result as Bag(['a', 'c', 'b', 'b', 'd', 'd', 'd']). Bags like sets are not sorted, so these 7 values can appear in any order. We might require that information in the list is sorted, but not all values we might put in a bag may be ordered (and therefore not sortable).

  • Define a __str__ method that returns a string that more compactly shows a bag. For example, for the Bag in the discussion of __init__ the __str__ method would print its result as Bag(a[1], c[1], b[2], d[3]). Bags like sets are not sorted, so these 7 values can appear in any order.

  • Define a __len__ method that returns the total number of values in the Bag. For example, for the Bag in the discussion of __init__ the __len__ method would return 7.

  • Define a unique method that returns the number of different (unique) values in the Bag. For example, for the Bag in the discussion of __init__ the unique method would return 4, because there are four different values in the Bag; contrast this method with __len__.

  • Define a __contains__ method that returns whether or not its argument is in the Bag (one or more times).

  • Define a count method that returns the number of times its argument is in the Bag: 0 if the argument is not in the Bag.

  • Define an add method that adds its argument to the Bag: if that value is already in the Bag, its count is incremented by 1; if it is not already in the Bag, it is added to the Bag with a count of 1.

  • remove removes its argument from the Bag: if that value is already in the Bag, its count is decremented by 1 (and if the count reduces to 0 it is removed from the dict; if it is not in the Bag, raise a ValueError exception, with an appropriate message that includes the value that could not be removed.

  • Define __eq__/__ne__ methods that return whether one Bag is equal/not equal to another: contains the same values the same number of times. Comparing a Bag for equality to a non-Bag should raise a TypeError. Be careful and ensure that this method does not change either Bag.

  • Define an __iter__ method that that returns an object on which next can be called to produce every value in the Bag: all len of them. For example, for the Bag in the discussion of __init__, the following code
      for i in x:
          print(i,end='')
    would print
      acbbddd
    Bags like sets are not sorted, so these 7 values can appear in any order.

    Ensure that the iterator produces those values in the Bag at the time the iterator starts executing; so mutating the Bag during iteration will not affect what values it produces.

    Hint: I defined a generator as the class method to do this job.

I have shown only examples of Bags storing strings, because they are convenient to write. But bags can store any type of data. The __repr__, __str__, and __iter__/__next__ methods must be written independently: neither should call the other to get things done.

Testing

The bag.py module includes a script that calls driver.driver(). The project folder contains a bsc2.txt file (examine it) to use for batch-self-checking your class. These are rigorous but not exhaustive tests. Incrementally write and test your class; check each method as you write it.

Note that when exceptions are raised, they are printed by the driver but the Command: prompt sometimes appears misplaced.

You can write other code at the bottom of your bag.py module to test the Bag class, or type code into the driver as illustrated below. Notice the default for each command is the command previously entered.

  Driver started
  Command[!]: from bag import Bag
  Command[from bag import Bag]: b = Bag(['d','a','b','d','c','b','d'])
  Command[b = Bag(['d','a','b','d','c','b','d'])]: print(b)
  Bag(a[1], b[2], c[1], d[3])
  Command[len(b)]: print(len(b))
  7
  Command[print(len(b))]: print(b.count('d'))
  3
  Command[print(b.count('d'))]: quit
  Driver stopped

Problem #3: Module of Decorators (iterators)

Problem Summary:

Write the following iterator decorators (iterators that operate on iterators) using Python generators. Write each function to be self contained, not calling any other functions or generators and do not use itertools.py module (or any other module that would trivialize this code); you may also not call the zip function.

Note that the argument passed to these generators can be anything that we can iterate: that includes strings, lists, tuples, dictionaries, and other generators: so, you cannot compute the len of the parameter because although strings, lists, tuples, and dictionariess have simple to compute lengths, generators don't.

Define space-efficient functions. They should not create temporary/local lists or tuples with all the values in their iterable parameters.

  • transform takes any iterable and any function whose domain includes all the iterated values: it produces transformed (by the function) values. For example
      for i in transform('abCdeFg',str.upper):
          print(i,end='')
    produces the values 'A', 'B', 'C', 'D', 'E', 'F', and 'G'.

  • running_count takes any iterable and any predicate function (taking one argument and returning a bool value): it produces a running count of how many values up to (and including) the one just iterated over, satisfied the predicate. For example
      for i in count('bananastand', lambda x : x in 'aeiou'): # is vowel
        print(i,end=' ')
    produces the values 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, and 4.

  • n_with_pad takes any iterable, an int n and a pad (whose default value is None): it produces the first n values from the iterable, padded by pad if there are fewer than n values in the iterable.
      for i n_with_pad('abcdefg',3):
        print(i,end=' ')
    produces the values 'a', 'b' and 'c'
      for i n_with_pad('abcdefg',10,'?'):
        print(i,end=' ')
    produces the values 'a', 'b', 'c', 'd', 'e', 'f', 'g', '?', '?' and '?'. Hint: use a for loop with a try/catch and explicit calls to iter and next.

  • sequence takes any number of iterables as parameters: it produces all the values in the first iterable, followed by all in the second, ... , all values in the last iterable. For example
      for i in sequence('abcd','ef','ghij'):
          print(i,end='')
    produces the values 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', and 'j'.

  • alternate takes any number of iterables as parameters: it produces the first value from the first parameter, then the first value from the the second parameter, ..., then the first value from the last parameter; then the second value from the first parameter, then the second value from the the second parameter, ..., then the second value from the last parameter; etc. If an iteratable produces no more values, it disappears from the alternation, and the process continues until there are no more iterables left.
      for i in alternate('abcde','fg','hijk'):
          print(i,end='')
    produces the values 'a', 'f', 'h', 'b', 'g', 'i', 'c', 'j', 'd', k, and 'e'. Hint: use a for loop nested in while loop with a try/catch and explicit calls to iter and next, along with a list of still active iteratables.

    Testing

    The generator.py module includes a script that calls driver.driver(). The project folder contains a bsc3.txt file (examine it) to use for batch-self-checking your class. These are rigorous but not exhaustive tests. Incrementally write and test your class; check each function as you write it.

    I have also provided the generatordriver.py module, which has the same tests as bsc3.txt but in a form more amenable for debugging these generators.