Programming project 4

Download the archive pp4.zip. It contains all the files for this project.

In this project you will implement an abstract data type to represent a continuous piecewise linear function.

Our ADT is called PieceWiseLinear, and can be used as follows:

>>> from pwlf import PieceWiseLinear
>>> f = PieceWiseLinear(1, 3, 7, 5)

The constructor takes four arguments \(x_{0}, y_{0}, x_{1}, y_{1}\), and creates a piecewise linear function \(f\) over the domain \([x_{0}, x_{1}]\), with \(f(x_{0}) = y_{0}\) and \(f(x_{1}) = y_{1}\).

In the example above, the function is defined on the interval \([1, 7]\), with \(f(1) = 3\) and \(f(7) = 5\).

We can obtain the domain of a function using the domain method:

>>> f.domain()
(1, 7)

And, of course, we can evaluate the function \(f(x)\) for various values of \(x\). When \(x\) is not in the domain, we get an error, of course:

>>> f(1)
3.0
>>> f(3)
3.6666666666666665
>>> f(7)
5.0
>>> f(0)
ValueError: argument is not in domain
>>> f(8)
ValueError: argument is not in domain

Note: evaluating a function with the function call syntax works if we define the magic __call__ method for our objects.

To make more interesting piecewise linear functions (with more than one piece), we can use the join method. It returns a new function (the object itself remains unchanged), which combines two functions:

>>> g = PieceWiseLinear(7, 5, 13, 2)
>>> f1 = f.join(g)
>>> f1.domain()
(1, 13)
>>> for x in [1, 3, 7, 8, 13]:
...   print(f1(x))
... 
3.0
3.6666666666666665
5.0
4.5
2.0

Note that join is only allowed when the domains are consecutive, and the combined function will be continuous:

>>> g1 = PieceWiseLinear(12, 2, 19, 3)
>>> f1.join(g1)
ValueError: domains are not contiguous
>>> g2 = PieceWiseLinear(13, 3, 19, 3)
>>> f1.join(g2)
ValueError: discontinuity at connection point

Using join, we can build piecewise linear functions with many pieces:

>>> g3 = PieceWiseLinear(13, 2, 19, 3)
>>> g4 = PieceWiseLinear(19, 3, 21, -5)
>>> f2 = f1.join(g3.join(g4))
>>> f2.domain()
(1, 21)

Of course we provide a nice string conversion for PieceWiseLinear objects:

>>> print(f)
(1,3)..(7,5)
>>> print(f1)
(1,3)..(7,5)..(13,2)
>>> print(f2)
(1,3)..(7,5)..(13,2)..(19,3)..(21,-5)

Note: To format numbers in the way that our test scripts except it, you must use the %g formatting specifier. You should format the coordinates of each breakpoint \((x,y)\) using the expression

  "(%g,%g)" % (x,y)

We can also do arithmetic operations on our functions. First, we can multiply them with a number:

>>> print(f2)
(1,3)..(7,5)..(13,2)..(19,3)..(21,-5)
>>> f3 = 3 * f2
>>> print(f3)
(1,9)..(7,15)..(13,6)..(19,9)..(21,-15)
>>> f2(10)
3.5
>>> f3(10)
10.5

Note: we can make this work my defining the magic method __rmul__ on the PieceWiseLinear object. The expression n * f calls the method f.__rmul__(n).

Note that the function f2 is not modified by the multiplication in any way.

Second, we can add or subtract a constant to a function:

>>> f4 = f3 - 10
>>> f5 = f3 + 99
>>> print(f4)
(1,-1)..(7,5)..(13,-4)..(19,-1)..(21,-25)
>>> print(f5)
(1,108)..(7,114)..(13,105)..(19,108)..(21,84)

To make this work, you need to implement the method add_number in the given template. (It will be called from the magic methods __add__ and __sub__ after checking the type of the right hand side.) The second argument is a multiplication factor for the constant, for addition it will be +1, for subtraction it will be -1.

Note that again the function f3 is not modified by the addition/subtraction in any way.

Finally, it is possible to add or subtract two PieceWiseLinear objects. For this to work, the domains of the two functions need to overlap in an interval. It is not necessary for the two functions to have the same domain, they also do not need to have the same breakpoints:

>>> print(f4)
(1,-1)..(7,5)..(13,-4)..(19,-1)..(21,-25)
>>> g5 = PieceWiseLinear(0, 0, 15, 8)
>>> f6 = f4 + g5
>>> print(f6)
(1,-0.466667)..(7,8.73333)..(13,2.93333)..(15,5)
>>> f6.domain()
(1, 15)

Note that the domain of the sum is the intersection of the two domains. The intersection cannot just be a point:

>>> g6 = PieceWiseLinear(15, 0, 16, 1)
>>> f6 + g6
ValueError: domains do not overlap

To make this work, you need to implement the method add_pwlf in the template. Again, the second argument is a multiplication factor, and will be either +1 or -1.

Start from the template code pwlf.py, which already defines all the right methods and provides some error checking of arguments.

When you are done, you can run pwlf.py to see the following test output:

$ python3 pwlf.py 
f1 = (1,-1)..(3,1)
f2 = (3,1)..(7,-5)
f1(1) = -1
f1(2) = 0
f1(3) = 1
f2(3) = 1
f2(5) = -2
f2(7) = -5
f = (1,-1)..(3,1)..(7,-5)
f(1) = -1
f(2) = 0
f(3) = 1
f(5) = -2
f(7) = -5
Domain of f1 = (1, 3), domain of f2 = (3, 7), domain of f = (1, 7)
g1 = f + 2 = (1,1)..(3,3)..(7,-3)
g2 = f - 6 = (1,-7)..(3,-5)..(7,-11)
g3 = 3 * f = (1,-3)..(3,3)..(7,-15)
h1 = 5 * f + 3 = (1,-2)..(3,8)..(7,-22)
h2 = 0.5 * f - 2 = (1,-2.5)..(3,-1.5)..(7,-4.5)
g = h1 + h2 = (1,-4.5)..(3,6.5)..(7,-26.5)
d = (0,0)..(2,19)..(6,12)
e1 = g + d = (1,5)..(2,20)..(3,23.75)..(6,-6.25)
e2 = g - d = (1,-14)..(2,-18)..(3,-10.75)..(6,-30.25)
g(1) = -4.5, d(1) = 9.5, e1(1) = 5, e2(1) = -14
g(2) = 1, d(2) = 19, e1(2) = 20, e2(2) = -18
g(3) = 6.5, d(3) = 17.25, e1(3) = 23.75, e2(3) = -10.75
g(4) = -1.75, d(4) = 15.5, e1(4) = 13.75, e2(4) = -17.25
g(5) = -10, d(5) = 13.75, e1(5) = 3.75, e2(5) = -23.75
g(6) = -18.25, d(6) = 12, e1(6) = -6.25, e2(6) = -30.25

For more thorough testing, including testing of the error messages, use the unit test script test_pwlf.py.

Submission: Upload your file pwlf.py to the submission server.