week06_unit_testing_with_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext ipython_pytest\n",
    "\n",
    "# Run this cell once before trying to run any cell containing a pytest\n",
    "# Ignore the message that the extension is already loaded if it appears; you do not need\n",
    "# to reload the extension if it is already loaded."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 06 Functions\n",
    "\n",
    "Unit testing is the process of testing units of source code. A unit of code is the smallest testable part of a piece of software. For our purposes, the units are Python functions.\n",
    "\n",
    "The textbook does not discuss this topic in any detail, and for most students, testing in previous courses \n",
    "amounts to writing a small program and manually inspecting the output of the program. This notebook discusses\n",
    "writing tests using the `pytest` framework. Using a testing framework has many advantages compared to\n",
    "manual testing:\n",
    "\n",
    "* a test framework typically produces a summary of the test results indicating which tests passed and which\n",
    "tests failed; the programmer does not need to manually inspect the output of a program to determine the\n",
    "test results\n",
    "* tools exist that allow tests to be run automatically\n",
    "    * for example, many professional workplaces require their programmers to check their code into a\n",
    "    centralized [version control system](https://en.wikipedia.org/wiki/Version_control); such systems\n",
    "    can be configured to automatically run test suites whenever code is checked into the system\n",
    "* test frameworks typically allow the programmer or tester to choose which tests should run; there is no\n",
    "easy way to select tests to run when manually inspecting the output of a program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `pytest`\n",
    "\n",
    "[`pytest` home page](https://docs.pytest.org/en/stable/)\n",
    "\n",
    "The unit test framework that is part of the Python standard is called `unittest`. Unfortunately, `unittest` is\n",
    "not suitable for the purposes of CISC121 because it requires knowledge of object-oriented Python.\n",
    "\n",
    "`pytest` does not require object-oriented Python and is easily accessible for CISC121 students. Because it is\n",
    "a third-party framework, students will need to install it.\n",
    "\n",
    "**Installing `pytest`**\n",
    "\n",
    "1. In Windows, open a Command Prompt (the `cmd` program). On Mac, open a terminal (the `Terminal` program).\n",
    "2. In the Command Prompt or terminal type the following command:\n",
    "\n",
    "  ```\n",
    "  pip3 install -U pytest\n",
    "  ```\n",
    "  \n",
    "  \n",
    "3. Check that the correct version has been installed correctly by typing the following command:\n",
    "\n",
    "  ```\n",
    "  pytest --version\n",
    "  ```\n",
    "  \n",
    " You should see the output `pytest 6.2.2` (you might see a version number greater than 6.2.2 depending on\n",
    " when you are reading this document).\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unit testing basics\n",
    "\n",
    "> Program testing can be a very effective way to show the presence of bugs, but it is hopelessly inadequate \n",
    "> for showing their absence.\n",
    ">\n",
    "> Edsger W. Dijkstra\n",
    "\n",
    "Programmers try to write correct code, but it is very challenging to prove that a piece of code is correct\n",
    "(the field of study that tries to do is called [formal methods](https://en.wikipedia.org/wiki/Formal_methods)). Instead, most programmers rely on testing to try to find errors in their\n",
    "code.\n",
    " \n",
    "When testing a function, we test that the contract of the function is upheld. In other words, we use\n",
    "test cases where the input argument values satisfy the preconditions of the function and then test that the\n",
    "postconditions of the function are satisfied.\n",
    "\n",
    "Writing a unit test for a Python function is simple in principle:\n",
    "\n",
    "1. Choose a set of input arguments for the function.\n",
    "2. If the function returns one or more values, determine what the expected return values are for the chosen\n",
    "set of input arguments.\n",
    "3. If the function has a side effect, determine what the expected side effect is.\n",
    "4. Call the function with the chosen set of input arguments and determine if:\n",
    "    * the actual return values are equal to the expected return values\n",
    "    * the actual side effects are equal to the expected side effects\n",
    "    \n",
    " A set of input arguments, the expected return values, and the expected side effects make up a *test case*.\n",
    " Testing one function typically requires using multiple test cases. Determining how many test cases\n",
    " are needed is beyond the scope of this notebook, but we can explore this problem somewhat with a few\n",
    " exercises."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1** Consider a function having one parameter where the parameter type is a boolean value. How many\n",
    "possible test cases exist for the function?\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    The input argument to the function can be either True or False, so there are two possible test cases.\n",
    "</div>\n",
    "\n",
    "**Exercise 2** Consider a function having two parameters where both parameter types are boolean values. How\n",
    "many possible test cases exist for the function?\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    The first input argument to the function can be either True or False and the second\n",
    "    input argument to the function can be either True or False, so there are 2*2 = 4 possible\n",
    "    test cases.\n",
    "</div>\n",
    "\n",
    "**Exercise 3** Consider a function having three parameters where all the parameter types are boolean values.\n",
    "How many possible test cases exist for the function?\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    2*2*2 = 8. If there are n boolean parameters then there are 2-to-the-power-n possible test cases.\n",
    "</div>\n",
    "\n",
    "\n",
    "**Exercise 4** Most Python implementations use a 64-bit representation for float values; this means that\n",
    "there are $2^{64}$ distinct float values. Consider a function having two parameters where both parameter types are float values. How many possible test cases exist for the function?\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    2-to-the-power-128 = 340,282,366,920,938,463,463,374,607,431,768,211,456 possible test cases (which\n",
    "    is a lot).\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example: Testing a function having one return value\n",
    "\n",
    "Consider the `is_prime` function from the course textbook (renamed to use PEP8 function naming convention):\n",
    "\n",
    "```python\n",
    "def is_prime(n):\n",
    "    if n < 2: \n",
    "        return False\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        if n % i == 0: \n",
    "            return False\n",
    "        i += 1\n",
    "    return True\n",
    "```\n",
    "\n",
    "To test the function, we first define a test case by choosing an input argument value and corresponding\n",
    "expected return value. A quick inspection of the function indicates that any input argument value less than\n",
    "$2$ results in `False` being returned by the method, which is the correct result. The return value for\n",
    "arguments greater than or equal $2$ is less clear. Let's begin with the test case where the input\n",
    "argument value is $2$ and the expected return value is `True`.\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    Using pytest in a Jupyter notebook is a bit more complicated because pytest is not part of the standard\n",
    "    Python library. This notebook uses a Jupyter extension named <tt>ipython_pytest</tt> (the source code\n",
    "    which is available <a href=\"https://github.com/akaihola/ipython_pytest\">here</a>). To use the extension,\n",
    "    there is a cell at the top of this notebook contining the line <tt>%load_ext ipython_pytest</tt>\n",
    "    which directs Jupyter to load the extension. Inside a cell where we want to run a pytest test,\n",
    "    we use <tt>%%pytest</tt> which is a Jupyter notebook command defined by the <tt>ipython_pytest</tt>\n",
    "    extension that runs <tt>pytest</tt> using the tests defined in the cell.\n",
    "</div>\n",
    "\n",
    "\n",
    "To write a unit test using `pytest` (outside of a Jupyter notebook) we import the `pytest` module and then\n",
    "define one or more test functions whose names begins with `test` or ends with `test`. For example, our test\n",
    "case can be implemented as shown below; run the two cells below to see the output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext ipython_pytest\n",
    "\n",
    "# Run this cell once before trying to run any cell containing a pytest\n",
    "# Ignore the message that the extension is already loaded if it appears; you do not need\n",
    "# to reload the extension if it is already loaded."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "# Outside of a Jupyter notebook you would import pytest:\n",
    "# import pytest\n",
    "\n",
    "def is_prime(n):\n",
    "    if n < 2: \n",
    "        return False\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        if n % i == 0: \n",
    "            return False\n",
    "        i += 1\n",
    "    return True\n",
    "\n",
    "\n",
    "# test function names need to start or end with test\n",
    "def test_is_prime_2_true():\n",
    "    assert is_prime(2) == True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output should have a line containing `1 passed` indicating that the test case has passed.\n",
    "\n",
    "The Python `assert` statement has the form:\n",
    "\n",
    "`assert` *expr*\n",
    "\n",
    "where *expr* is any Python expression whose value can be converted to `True` or `False`. If *expr* evaluates\n",
    "to `True` then the `assert` statement does nothing. If *expr* evaluates to `False` then an `AssertionError`\n",
    "is raised. In a unit test, `pytest` handles the `AssertionError` and notes that the test has failed.\n",
    "\n",
    "Let's intentionally introduce an error into `is_prime` to see what a failed test looks like; run the \n",
    "following cell to see the output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def is_prime(n):\n",
    "    # intentional error on next line\n",
    "    if n <= 2: \n",
    "        return False\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        if n % i == 0: \n",
    "            return False\n",
    "        i += 1\n",
    "    return True\n",
    "\n",
    "\n",
    "def test_is_prime_2_true():\n",
    "    n = 2\n",
    "    assert is_prime(n) == True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `pytest` output now indicates that the test has failed. In particular, it shows the input\n",
    "arguments to the function (`is_prime(2)`), the expected return value (`True`), and the actual\n",
    "return value (`False`). For the programmer, knowing what input values cause a function to fail\n",
    "is valuable information when debugging the function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have one test case where the expected return value is `True`. We should also create a test case where\n",
    "the expected return value is `False`. The smallest non-prime number is $4$, so we can add a second\n",
    "test case where the input argument value is $4$ and the expected return value is `False`; run the cell\n",
    "below to see the output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def is_prime(n):\n",
    "    if n < 2: \n",
    "        return False\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        if n % i == 0: \n",
    "            return False\n",
    "        i += 1\n",
    "    return True\n",
    "\n",
    "\n",
    "def test_is_prime_2_true():\n",
    "    n = 2\n",
    "    assert is_prime(n) == True\n",
    "    \n",
    "def test_is_prime_4_false():\n",
    "    n = 4\n",
    "    assert is_prime(n) == False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At this point the reader should realize that tests for the `is_prime` function fall into one of two\n",
    "categories: Those where the expected return value is `False` and those where the expected return\n",
    "value is `True`. Instead of testing a single value in each test function, we can test multiple \n",
    "different input arguments using a single function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def is_prime(n):\n",
    "    if n < 2: \n",
    "        return False\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        if n % i == 0: \n",
    "            return False\n",
    "        i += 1\n",
    "    return True\n",
    "\n",
    "\n",
    "def test_is_prime_true():\n",
    "    N = [2, 3, 5, 7, 11, 13, 17]\n",
    "    for n in N:\n",
    "        assert is_prime(n) == True\n",
    "    \n",
    "def test_is_prime_false():\n",
    "    N = [4, 6, 8, 9, 10, 12, 14]\n",
    "    for n in N:\n",
    "        assert is_prime(n) == False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The disadvantage with this approach is that a test written this way will stop on the first test case\n",
    "that fails; the remaining test cases will not be run. A better way to write such tests is to use\n",
    "a [*parameterized test*](https://docs.pytest.org/en/stable/parametrize.html) but this is beyond the\n",
    "scope of CISC121."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With a bit of reflection, it should be clear to the reader why unit testing cannot prove that the\n",
    "`is_prime` function is correct: There are an infinite number of possible input arguments to test!\n",
    "Even worse, for very large input values, we have no good way to determine what the expected\n",
    "return value should be."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 5** Write a small number of tests for the textbook function in the following cell. The function\n",
    "is supposed to compute the length of the hypotenuse of a right triangle with sides of lengths `a` and `b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "import math\n",
    "\n",
    "def hypot(a, b):\n",
    "    return math.sqrt(a * a + b * b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "import math\n",
    "\n",
    "def hypot(a, b):\n",
    "    return math.sqrt(a * a + b * b)\n",
    "\n",
    "def test_hypot_0_0():\n",
    "    assert hypot(0, 0) == 0\n",
    "    \n",
    "def test_hypot_1_1():\n",
    "    assert hypot(1, 1) == math.sqrt(2)\n",
    "    \n",
    "def test_hypot_3_4():\n",
    "    assert hypot(3, 4) == 5\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example: Testing a function that has a side effect\n",
    "\n",
    "A function has a side effect if it has some observable effect besides returning a value. Printing a value\n",
    "is an example of a side effect. Changing the state of mutable input argument (such as a list) is another\n",
    "example of a side effect.\n",
    "\n",
    "Consider the textbook function `exchange` that swaps two elements of a list:\n",
    "\n",
    "```python\n",
    "def exchange(a, i, j):\n",
    "    \"\"\"\n",
    "    Swaps two elements of a list.\n",
    "    \n",
    "    Swaps the elements a[i] and a[j] of the list a.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    a : list\n",
    "        A list\n",
    "    i : int\n",
    "        Index of an element to swap\n",
    "    j : int\n",
    "        Index of a second element to swap\n",
    "        \n",
    "    Raises\n",
    "    ------\n",
    "    IndexError\n",
    "        If `i` or `j` is out of range.\n",
    "    \"\"\"\n",
    "    \n",
    "    temp = a[i]\n",
    "    a[i] = a[j]\n",
    "    a[j] = temp\n",
    "```\n",
    "\n",
    "After calling `exchange` every element of `a` should be unchanged except for the elements at indexes\n",
    "`i` and `j` which should be swapped.\n",
    "\n",
    "Testing a function with side effects is similar to testing a function with a return value. One\n",
    "difference is that we probably have to call the function that is being tested before the `assert` statement\n",
    "to cause the side effect to occur.\n",
    "\n",
    "Let's write a test for `exchange` where we swap the elements of a list of length 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def exchange(a, i, j):\n",
    "    temp = a[i]\n",
    "    a[i] = a[j]\n",
    "    a[j] = temp\n",
    "    \n",
    "def test_exchange_len2():\n",
    "    '''\n",
    "    Test for list of length 2.\n",
    "    '''\n",
    "    \n",
    "    # input arguments\n",
    "    a = ['x', 'y']\n",
    "    i = 0\n",
    "    j = 1\n",
    "    \n",
    "    # expected list\n",
    "    exp = ['y', 'x']\n",
    "    \n",
    "    # call the method to cause the side effect\n",
    "    exchange(a, i, j)\n",
    "    \n",
    "    assert a == exp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For CISC121, the above test is a good attempt at writing a unit test for the `exchange` function. It sets up\n",
    "the input arguments and the expected side effect correctly, calls the `exchange` function using the test case\n",
    "arguments, and then tests if the modified list `a` is equal to the expected list `exp`.\n",
    "\n",
    "A second test case that would be useful to include is a case where the indexes `i` and `j` are equal\n",
    "(corresponding to the case where no exchange actually occurs); given the existing test, it is easy\n",
    "to write such a test case:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def exchange(a, i, j):\n",
    "    temp = a[i]\n",
    "    a[i] = a[j]\n",
    "    a[j] = temp\n",
    "    \n",
    "def test_exchange_len2():\n",
    "    '''\n",
    "    Test for list of length 2.\n",
    "    '''\n",
    "    \n",
    "    # input arguments\n",
    "    a = ['x', 'y']\n",
    "    i = 0\n",
    "    j = 1\n",
    "    \n",
    "    # expected list\n",
    "    exp = ['y', 'x']\n",
    "    \n",
    "    # call the method to cause the side effect\n",
    "    exchange(a, i, j)\n",
    "    \n",
    "    assert a == exp\n",
    "    \n",
    "def test_exchange_len2_same_indexes():\n",
    "    '''\n",
    "    Test for list of length 2 with same indexes.\n",
    "    '''\n",
    "    \n",
    "    # input arguments\n",
    "    a = ['x', 'y']\n",
    "    i = 1\n",
    "    j = 1\n",
    "    \n",
    "    # expected list\n",
    "    exp = ['x', 'y']\n",
    "    \n",
    "    # call the method to cause the side effect\n",
    "    exchange(a, i, j)\n",
    "    \n",
    "    assert a == exp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above tests are useful, but they are technically asserting the wrong condition. See the sections near\n",
    "the end of this notebook starting with the cell titled **Extra material: How the exchange tests could\n",
    "be better** for details."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 6** Write a small number of tests for the function `min_to_front` in the following cell. The\n",
    "function contract is that it moves the smallest element of the list to the front of the list and puts the\n",
    "element that was at the front of the list somewhere else in the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def min_to_front(a):\n",
    "    if len(a) == 0:\n",
    "        raise ValueError('min_to_front(): no minimum element in an empty list')\n",
    "    \n",
    "    if len(a) == 1:\n",
    "        # list of length 1 already has its minimum element at the front of the list\n",
    "        return\n",
    "    \n",
    "    min_elem = a[0]\n",
    "    min_index = 0\n",
    "    for i in range(1, len(a)):\n",
    "        ai = a[i]\n",
    "        if ai < min_elem:\n",
    "            min_elem = ai\n",
    "            min_index = i\n",
    "    front = a[0]\n",
    "    a.pop(min_index)\n",
    "    a[0] = min_elem\n",
    "    a.append(front)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "    There are two postconditions that need to be tested in this exercise. First, you need to test if the\n",
    "    smallest elemenet is moved to the front of the list. Second, you need to test if all of the other\n",
    "    elements are still in the list.<br /><br />\n",
    "    Testing the second postcondition is tricky. For CISC121, it would be acceptable if you examined\n",
    "    how min_to_front works: It moves the smallest element to the front of the list, and moves the old\n",
    "    front element to the back of the list. It does not change the relative order of the other elements,\n",
    "    so you don't have to test if those elements are still in the list.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def min_to_front(a):\n",
    "    if len(a) == 0:\n",
    "        raise ValueError('min_to_front(): no minimum element in an empty list')\n",
    "    \n",
    "    if len(a) == 1:\n",
    "        # list of length 1 already has its minimum element at the front of the list\n",
    "        return\n",
    "        \n",
    "    min_elem = a[0]\n",
    "    min_index = 0\n",
    "    for i in range(1, len(a)):\n",
    "        ai = a[i]\n",
    "        if ai < min_elem:\n",
    "            min_elem = ai\n",
    "            min_index = i\n",
    "    front = a[0]\n",
    "    a.pop(min_index)\n",
    "    a[0] = min_elem\n",
    "    a.append(front)\n",
    "\n",
    "def test_min_to_front_len1():\n",
    "    min_val = 1\n",
    "    a = [min_val]\n",
    "    min_to_front(a)\n",
    "    assert a[0] == min_val\n",
    "\n",
    "\n",
    "def test_min_to_front_len3():\n",
    "    min_val = 1\n",
    "    a = [100, min_val, 200]\n",
    "    old_front = a[0]\n",
    "    min_to_front(a)\n",
    "    assert a[0] == min_val\n",
    "    assert a[-1] == old_front"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example: Testing a slightly more complicated function\n",
    "\n",
    "The above examples are useful for introducing the concept of unit testing using `pyttest` but the tested\n",
    "functions are already correctly implemented. Consider the following function that is supposed to return\n",
    "the second largest element in a list having at least 2 elements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def second_largest(a):\n",
    "    '''\n",
    "    Return the second largest element in a list.\n",
    "    \n",
    "    The list `a` is assumed to have at least two elements that can be compared\n",
    "    using the >= operator.\n",
    "    '''\n",
    "    \n",
    "    # look at the first two elements\n",
    "    largest = max(a[0], a[1])\n",
    "    second = min(a[0], a[1])\n",
    "    \n",
    "    # look at the remaining elements\n",
    "    for i in range(2, len(a)):\n",
    "        elem = a[i]\n",
    "        if elem >= largest:\n",
    "            second = largest\n",
    "            largest = elem\n",
    "    return second"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Following the previous examples, we can easily write a unit test by creating a list with two or more elements\n",
    "and setting the expected return value to be equal to the second largest element of the input list. The\n",
    "following cell shows three different tests:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def second_largest(a):\n",
    "    '''\n",
    "    Return the second largest element in a list.\n",
    "    \n",
    "    The list `a` is assumed to have at least two elements that can be compared\n",
    "    using the >= operator.\n",
    "    '''\n",
    "    \n",
    "    # look at the first two elements\n",
    "    largest = max(a[0], a[1])\n",
    "    second = min(a[0], a[1])\n",
    "    \n",
    "    # look at the remaining elements\n",
    "    for i in range(2, len(a)):\n",
    "        elem = a[i]\n",
    "        if elem >= largest:\n",
    "            second = largest\n",
    "            largest = elem\n",
    "    return second\n",
    "\n",
    "\n",
    "def test_list_len2_1():\n",
    "    a = [1, 2]\n",
    "    exp = 1\n",
    "    assert second_largest(a) == exp\n",
    "    \n",
    "def test_list_len2_2():\n",
    "    a = [2, 1]\n",
    "    exp = 1\n",
    "    assert second_largest(a) == exp\n",
    "\n",
    "def test_list_len5():\n",
    "    a = [1, 8, 10, 5, 12]\n",
    "    exp = 10\n",
    "    assert second_largest(a) == exp\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function passes all three test cases but there is an error in the function.\n",
    "\n",
    "**Exercise 7** Can you find the error in the function `second_largest`?\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    The answer is in the next paragraph.\n",
    "</div>\n",
    "\n",
    "The error in the function `second_largest` is that it assigns a value to `second` only when a new largest\n",
    "value is found in the list; this means that the function will fail to find the correct second largest\n",
    "value if it comes after the largest value in the list.\n",
    "\n",
    "Note that the second test case uses a list where the second largest element comes after the largest\n",
    "element, but the function is written in such a way that it works correctly for lists of length 2.\n",
    "\n",
    "Adding a fourth test case will reveal the error:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def second_largest(a):\n",
    "    '''\n",
    "    Return the second largest element in a list.\n",
    "    \n",
    "    The list `a` is assumed to have at least two elements that can be compared\n",
    "    using the >= operator.\n",
    "    '''\n",
    "    \n",
    "    # look at the first two elements\n",
    "    largest = max(a[0], a[1])\n",
    "    second = min(a[0], a[1])\n",
    "    \n",
    "    # look at the remaining elements\n",
    "    for i in range(2, len(a)):\n",
    "        elem = a[i]\n",
    "        if elem >= largest:\n",
    "            second = largest\n",
    "            largest = elem\n",
    "    return second\n",
    "\n",
    "\n",
    "def test_list_len2_1():\n",
    "    a = [1, 2]\n",
    "    exp = 1\n",
    "    assert second_largest(a) == exp\n",
    "    \n",
    "def test_list_len2_2():\n",
    "    a = [2, 1]\n",
    "    exp = 1\n",
    "    assert second_largest(a) == exp\n",
    "\n",
    "def test_list_len5_1():\n",
    "    a = [1, 8, 10, 5, 12]\n",
    "    exp = 10\n",
    "    assert second_largest(a) == exp\n",
    "    \n",
    "def test_list_len5_2():\n",
    "    a = [1, 8, 10, 5, 9]\n",
    "    exp = 9\n",
    "    assert second_largest(a) == exp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This example again illustrates why it is impossible to use testing to prove that a method is correct: There\n",
    "are an infinite number of input lists and we cannot possibly test them all. If we fail to use a test case\n",
    "that reveals an error then we may erroneously conclude that the function is correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Extra material: How the `exchange` tests could be better\n",
    "\n",
    "The `exchange` test shown earlier in this notebook does not actually correctly test the behavior of\n",
    "`exchange`. `exchange` is supposed to swap two elements of a list; in other words, after `exchange(a, i, j)`\n",
    "finishes running:\n",
    "\n",
    "* the element at `a[i]` should refer to the same object that `a[j]` referred to immediately before `exchange` was called\n",
    "* the element at `a[j]` should refer to the same object that `a[i]` referred to immediately before `exchange` was called\n",
    "* every element in `a` not at index `i` or `j` should refer to the same object that it referred to immediately before `exchange` was called\n",
    "\n",
    "The test written for `exchange` uses `==` to test if the list `a` is equal to a list where the elements\n",
    "have been correctly swapped. Unfortunately, `==` tests if two objects are equal. For a list, `==` tests\n",
    "if all of the corresponding elements of two lists are equal. Here is an example of two lists that are equal,\n",
    "but do not contain references to the same objects:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = ['hello world']\n",
    "b = ['hello world']\n",
    "print('equal lists?:', a == b)\n",
    "print('same elements?:', a[0] is b[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test if two references refer to the same object we can use the Python operator `is`. Re-writing the\n",
    "previous version of the test leads to the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def exchange(a, i, j):\n",
    "    temp = a[i]\n",
    "    a[i] = a[j]\n",
    "    a[j] = temp\n",
    "    \n",
    "def test_exchange_len2():\n",
    "    # input arguments\n",
    "    a = ['x', 'y']\n",
    "    i = 0\n",
    "    j = 1\n",
    "    \n",
    "    # copy of a\n",
    "    copy = a[:]\n",
    "    \n",
    "    # call the method to cause the side effect\n",
    "    exchange(a, i, j)\n",
    "    \n",
    "    assert a[i] is copy[j]\n",
    "    assert a[j] is copy[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above test, the list `copy` is a copy of the list `a` before the swap occurs: `copy[0]` and `a[0]`\n",
    "are references to the same object, and `copy[1]` and `a[1]` are references to the same object.\n",
    "Calling `exchange` modifies the list `a` but does not modify the list `copy`. After calling `exchange`,\n",
    "`a[i]` and `copy[j]` should refer to the same object, and `a[j]` and `copy[i]` should refer to the same\n",
    "object. Notice the use of `is` in the test to test that the references refer to the same object instead of\n",
    "using `==` to test if the objects are equal.\n",
    "\n",
    "Now let's write a test using a slightly longer list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def exchange(a, i, j):\n",
    "    temp = a[i]\n",
    "    a[i] = a[j]\n",
    "    a[j] = temp\n",
    "    \n",
    "    \n",
    "def test_exchange_len2():\n",
    "    # input arguments\n",
    "    a = ['x', 'y']\n",
    "    i = 0\n",
    "    j = 1\n",
    "    \n",
    "    # copy of a\n",
    "    copy = a[:]\n",
    "    \n",
    "    # call the method to cause the side effect\n",
    "    exchange(a, i, j)\n",
    "    \n",
    "    assert a[i] is copy[j]\n",
    "    assert a[j] is copy[i]\n",
    "    \n",
    "    \n",
    "def test_exchange_len3():\n",
    "    # input arguments\n",
    "    a = ['x', 'y', 'z']\n",
    "    i = 1\n",
    "    j = 2\n",
    "    \n",
    "    # copy of a\n",
    "    copy = a[:]\n",
    "    \n",
    "    # call the method to cause the side effect\n",
    "    exchange(a, i, j)\n",
    "    \n",
    "    for k in range(0, len(a)):\n",
    "        if k == i:\n",
    "            assert a[k] is copy[j]\n",
    "        elif k == j:\n",
    "            assert a[k] is copy[i]\n",
    "        else:\n",
    "            assert a[k] is copy[k]\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For lists longer than length 2 we should test that the elements whose indexes are not equal to `i` or `j` are\n",
    "unchanged by the `exchange` function, so there is now a third `assert` statement.\n",
    "\n",
    "The observant reader will recognize that both of the tests above differ only in the input arguments that are\n",
    "used. We should refactor the common code into a separate function like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%pytest\n",
    "\n",
    "def exchange(a, i, j):\n",
    "    temp = a[i]\n",
    "    a[i] = a[j]\n",
    "    a[j] = temp\n",
    "\n",
    "\n",
    "def exchange_test_impl(a, i, j):\n",
    "    # copy of a\n",
    "    copy = a[:]\n",
    "    \n",
    "    # call the method to cause the side effect\n",
    "    exchange(a, i, j)\n",
    "    \n",
    "    for k in range(0, len(a)):\n",
    "        if k == i:\n",
    "            assert a[k] is copy[j]\n",
    "        elif k == j:\n",
    "            assert a[k] is copy[i]\n",
    "        else:\n",
    "            assert a[k] is copy[k]\n",
    "    \n",
    "def test_exchange_len2():\n",
    "    # input arguments\n",
    "    a = ['x', 'y']\n",
    "    i = 0\n",
    "    j = 1\n",
    "    # call the test implementation\n",
    "    exchange_test_impl(a, i, j)\n",
    "    \n",
    "    \n",
    "def test_exchange_len3():\n",
    "    # input arguments\n",
    "    a = ['x', 'y', 'z']\n",
    "    i = 1\n",
    "    j = 2\n",
    "    # call the test implementation\n",
    "    exchange_test_impl(a, i, j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `exchange_test_impl` is the function that actually implements the testing logic (the `_impl`\n",
    "is an abbreviation of *implementation*). We have to be careful when naming this function not to start \n",
    "or end the name with `test` otherwise `pytest` will think that it is a separate test function."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}