{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1331faa1",
   "metadata": {},
   "source": [
    "You can order print and ebook versions of *Think Python 3e* from\n",
    "[Bookshop.org](https://bookshop.org/a/98697/9781098155438) and\n",
    "[Amazon](https://www.amazon.com/_/dp/1098155432?smid=ATVPDKIKX0DER&_encoding=UTF8&tag=oreilly20-20&_encoding=UTF8&tag=greenteapre01-20&linkCode=ur2&linkId=e2a529f94920295d27ec8a06e757dc7c&camp=1789&creative=9325)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "31b6f97a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\n",
    "    \"\"\"Download a file if it isn't already here, and return its filename.\"\"\"\n",
    "    filename = basename(url)\n",
    "    if not exists(filename):\n",
    "        from urllib.request import urlretrieve\n",
    "\n",
    "        local, _ = urlretrieve(url, filename)\n",
    "        print(\"Downloaded \" + str(local))\n",
    "    return filename\n",
    "\n",
    "download('https://github.com/porttack/working-in-python/raw/v3/working_in_python.py');\n",
    "download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
    "\n",
    "import working_in_python\n",
    "# apcsp:begin type=\"note\" chapter=\"13\"\n",
    "working_in_python.enable_docstring_reminders()\n",
    "# apcsp:end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3ee5c27",
   "metadata": {
    "tags": []
   },
   "source": [
    "Credit: Photos downloaded from [Lorem Picsum](https://picsum.photos/), a service that provides placeholder images.\n",
    "The name is a reference to \"lorem ipsum\", which is a name for placeholder text.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9b246dc6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# This cell downloads an archive file that contains the the files we'll\n",
    "# use for the examples in this chapter.\n",
    "\n",
    "download('https://github.com/AllenDowney/ThinkPython/raw/v3/photos.zip');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "23792899",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# WARNING: This cell removes the photos/ directory if it already exists.\n",
    "# Any files already in the photos/ directory will be deleted.\n",
    "\n",
    "# !rm -rf photos/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "713dfeb0",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "!unzip -o photos.zip"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92934cb0",
   "metadata": {},
   "source": [
    "# Files and Databases\n",
    "\n",
    "Most of the programs we have seen so far are **ephemeral** in the sense that they run for a short time and produce output, but when they end, their data disappears.\n",
    "Each time you run an ephemeral program, it starts with a clean slate.\n",
    "\n",
    "Other programs are **persistent**: they run for a long time (or all the time); they keep at least some of their data in long-term storage; and if they shut down and restart, they pick up where they left off.\n",
    "\n",
    "A simple way for programs to maintain their data is by reading and writing text files.\n",
    "A more versatile alternative is to store data in a database.\n",
    "Databases are specialized files that can be read and written more efficiently than text files, and they provide additional capabilities.\n",
    "\n",
    "In this chapter, we'll write programs that read and write text files and databases, and as an exercise you'll write a program that searches a collection of photos for duplicates.\n",
    "But before you can work with a file, you have to find it, so we'll start with file names, paths, and directories."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75cec7ca",
   "metadata": {},
   "source": [
    "## Filenames and paths\n",
    "\n",
    "Files are organized into **directories**, also called \"folders\".\n",
    "Every running program has a **current working directory**, which is the default directory for most operations.\n",
    "For example, when you open a file, Python looks for it in the current working directory.\n",
    "\n",
    "The `os` module provides functions for working with files and directories (\"os\" stands for \"operating system\"). \n",
    "It provides a function called `getcwd` that gets the name of the current working directory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4fdb528a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this cell replaces `os.cwd` with a function that returns a fake path\n",
    "\n",
    "import os\n",
    "\n",
    "def getcwd():\n",
    "    return \"/home/dinsdale\"\n",
    "\n",
    "os.getcwd = getcwd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c7b209f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "\n",
    "os.getcwd()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c55575f",
   "metadata": {},
   "source": [
    "The result in this example is the home directory of a user named `dinsdale`.\n",
    "A string like `'/home/dinsdale'` that identifies a file or directory is called a **path**.\n",
    "\n",
    "A simple filename like `'memo.txt'` is also considered a path, but it is a **relative path** because it specifies a file name relative to the current directory.\n",
    "In this example, the current directory is `/home/dinsdale`, so `'memo.txt'` is equivalent to the complete path `'/home/dinsdale/memo.txt'`.\n",
    "\n",
    "A path that begins with `/` does not depend on the current directory -- it is called an **absolute path**. \n",
    "To find the absolute path to a file, you can use `abspath`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "66a15e44",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.path.abspath('memo.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1a0cf04",
   "metadata": {},
   "source": [
    "The `os` module provides other functions for working with filenames and paths.\n",
    "`listdir` returns a list of the contents of the given directory, including files and other directories.\n",
    "Here's an example that lists the contents of a directory named `photos`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a22d2675",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.listdir('photos')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab160f29",
   "metadata": {},
   "source": [
    "This directory contains a text file named `notes.txt` and three directories.\n",
    "The directories contain image files in the JPEG format."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a217eac7",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.listdir('photos/jan-2023')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06b27c85",
   "metadata": {},
   "source": [
    "To check whether a file or directory exists, we can use `os.path.exists`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "aa56aeac",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.path.exists('photos')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "9049009a",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.path.exists('photos/apr-2023')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d41f235c",
   "metadata": {},
   "source": [
    "To check whether a path refers to a file or directory, we can use `isdir`, which return `True` if a path refers to a directory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "0feddb06",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.path.isdir('photos')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bd70cc9",
   "metadata": {},
   "source": [
    "And `isfile` which returns `True` if a path refers to a file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "e9f6a762",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.path.isfile('photos/notes.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6933c18",
   "metadata": {},
   "source": [
    "One challenge of working with paths is that they look different on different operating systems.\n",
    "On macOS and UNIX systems like Linux, the directory and file names in a path are separated by a forward slash, `/`.\n",
    "Windows uses a backward slash, `\\`.\n",
    "So, if you you run these examples on Windows, you will see backward slashes in the paths, and you'll have to replace the forward slashes in the examples.\n",
    "\n",
    "Or, to write code that works on both systems, you can use `os.path.join`, which joins directory and filenames into a path using a forward or backward slash, depending on which operating system you are using."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "eb738376",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.path.join('photos', 'jan-2023', 'photo1.jpg')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a665cf9",
   "metadata": {},
   "source": [
    "Later in this chapter we'll use these functions to search a set of directories and find all of the image files."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31a96ba4",
   "metadata": {},
   "source": [
    "## f-strings\n",
    "\n",
    "One way for programs to store data is to write it to a text file.\n",
    "For example, suppose you are a camel spotter, and you want to record the number of camels you have seen during a period of observation.\n",
    "And suppose that in one and a half years, you have spotted `23` camels.\n",
    "The data in your camel-spotting book might look like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "23e7a6a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_years = 1.5\n",
    "num_camels = 23"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f652aaac",
   "metadata": {},
   "source": [
    "To write this data to a file, you can use the `write` method, which we saw in Chapter 8.\n",
    "The argument of `write` has to be a string, so if we want to put other values in a file, we have to convert them to strings.\n",
    "The easiest way to do that is with the built-in function `str`.\n",
    "\n",
    "Here's what that looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "174d4f83",
   "metadata": {},
   "outputs": [],
   "source": [
    "writer = open('camel-spotting-book.txt', 'w')\n",
    "writer.write(str(num_years))\n",
    "writer.write(str(num_camels))\n",
    "writer.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "307c22d2",
   "metadata": {},
   "source": [
    "That works, but `write` doesn't add a space or newline unless you include it explicitly.\n",
    "If we read back the file, we see that the two numbers are run together."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "5209eda3",
   "metadata": {},
   "outputs": [],
   "source": [
    "open('camel-spotting-book.txt').read()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8008ecdc",
   "metadata": {},
   "source": [
    "At the very least, we should add whitespace between the numbers.\n",
    "And while we're at it, let's add some explanatory text.\n",
    "\n",
    "To write a combination of strings and other values, we can use an **f-string**, which is a string that has the letter `f` before the opening quotation mark, and contains one or more Python expressions in curly braces.\n",
    "The following f-string contains one expression, which is a variable name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "0f202d66",
   "metadata": {},
   "outputs": [],
   "source": [
    "f'I have spotted {num_camels} camels'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3fb0556",
   "metadata": {},
   "source": [
    "The result is a string where the expression has been evaluated and replaced with the result.\n",
    "There can be more than one expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "33c5f77f",
   "metadata": {},
   "outputs": [],
   "source": [
    "f'In {num_years} years I have spotted {num_camels} camels'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bace1539",
   "metadata": {},
   "source": [
    "And the expressions can contain operators and function calls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "1fe7111c",
   "metadata": {},
   "outputs": [],
   "source": [
    "line = f'In {round(num_years * 12)} months I have spotted {num_camels} camels'\n",
    "line"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc6fa094",
   "metadata": {},
   "source": [
    "So we could write the data to a text file like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "bc06e90a",
   "metadata": {},
   "outputs": [],
   "source": [
    "writer = open('camel-spotting-book.txt', 'w')\n",
    "writer.write(f'Years of observation: {num_years}\\n')\n",
    "writer.write(f'Camels spotted: {num_camels}\\n')\n",
    "writer.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f916d561",
   "metadata": {},
   "source": [
    "Both f-strings end with the sequence `\\n`, which adds a newline character.\n",
    "\n",
    "We can read the file back like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "8d9eaf8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "data = open('camel-spotting-book.txt').read()\n",
    "print(data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3bf6913",
   "metadata": {},
   "source": [
    "In an f-string, an expression in curly brace is converted to a string, so you can include lists, dictionaries, and other types."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "ae3060c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = [1, 2, 3]\n",
    "d = {'one': 1}\n",
    "f'Here is a list {t} and a dictionary {d}'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "838ef132",
   "metadata": {
    "tags": []
   },
   "source": [
    "If a f-string contains an invalid expression, the result is an error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "26ca3d1b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "\n",
    "f'This is not a valid expression {t + 2}'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbbaaed3",
   "metadata": {},
   "source": [
    "## YAML\n",
    "\n",
    "One of the reasons programs read and write files is to store **configuration data**, which is information that specifies what the program should do and how.\n",
    "\n",
    "For example, in a program that searches for duplicate photos, we might have a dictionary called `config` that contains the name of the directory to search, the name of another directory where it should store the results, and a list of file extensions it should use to identify image files.\n",
    "\n",
    "Here's what it might look like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "5bb69e1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "config = {\n",
    "    'photo_dir': 'photos',\n",
    "    'data_dir': 'photo_info',\n",
    "    'extensions': ['jpg', 'jpeg'],\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1667bb96",
   "metadata": {},
   "source": [
    "To write this data in a text file, we could use f-strings, as in the previous section. But it is easier to use a module called `yaml` that is designed for just this sort of thing.\n",
    "\n",
    "The `yaml` module provides functions to work with YAML files, which are text files formatted to be easy for humans *and* programs to read and write.\n",
    "\n",
    "Here's an example that uses the `dump` function to write the `config` dictionary to a YAML file. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "0090a29f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this cell installs the pyyaml package, which provides the yaml module\n",
    "\n",
    "try:\n",
    "    import yaml\n",
    "except ImportError:\n",
    "    !pip install pyyaml"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "97079479",
   "metadata": {},
   "outputs": [],
   "source": [
    "import yaml\n",
    "\n",
    "config_filename = 'config.yaml'\n",
    "writer = open(config_filename, 'w')\n",
    "yaml.dump(config, writer)\n",
    "writer.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92d1b7ff",
   "metadata": {},
   "source": [
    "If we read back the contents of the file, we can see what the YAML format looks like."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "8646dd2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "readback = open(config_filename).read()\n",
    "print(readback)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33cdfd2c",
   "metadata": {},
   "source": [
    "Now, we can use `safe_load` to read back the YAML file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "e8ce2e4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "reader = open(config_filename)\n",
    "config_readback = yaml.safe_load(reader)\n",
    "config_readback"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca55764f",
   "metadata": {},
   "source": [
    "The result is new dictionary that contains the same information as the original, but it is not the same dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "871d6ad5",
   "metadata": {},
   "outputs": [],
   "source": [
    "config is config_readback"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "969ad306",
   "metadata": {},
   "source": [
    "Converting an object like a dictionary to a string is called **serialization**.\n",
    "Converting the string back to an object is called **deserialization**.\n",
    "If you serialize and then deserialize an object, the result should be equivalent to the original."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e130cf8",
   "metadata": {},
   "source": [
    "## Shelve\n",
    "\n",
    "So far we've been reading and writing text files -- now let's consider databases.\n",
    "A **database** is a file that is organized for storing data.\n",
    "Some databases are organized like a table with rows and columns of information.\n",
    "Others are organized like a dictionary that maps from keys to values; they are sometimes called **key-value stores**.\n",
    "\n",
    "The `shelve` module provides functions for creating and updating a key-value store called a \"shelf\".\n",
    "As an example, we'll create a shelf to contain captions for the figures in the `photos` directory.\n",
    "We'll use the `config` dictionary to get the name of the directory where we should put the shelf."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "70a6d625",
   "metadata": {},
   "outputs": [],
   "source": [
    "config['data_dir']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e6cfb65",
   "metadata": {},
   "source": [
    "We can use `os.makedirs` to create this directory, if it doesn't already exist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "fd070fa7",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.makedirs(config['data_dir'], exist_ok=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6352f83f",
   "metadata": {},
   "source": [
    "And `os.path.join` to make a path that includes the name of the directory and the name of the shelf file, `captions`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "f5aeb7ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "db_file = os.path.join(config['data_dir'], 'captions')\n",
    "db_file"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbb08679",
   "metadata": {},
   "source": [
    "Now we can use `shelve.open` to open the shelf file.\n",
    "The argument `c` indicates that the file should be created if necessary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "291ea875",
   "metadata": {},
   "outputs": [],
   "source": [
    "import shelve\n",
    "\n",
    "db = shelve.open(db_file, 'c')\n",
    "db"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47685eb7",
   "metadata": {
    "tags": []
   },
   "source": [
    "If you get an error like `db type could not be determined`, the most likely cause is that a file with the same name already exists but is not a valid shelve database (for example, it may be corrupted or created by something else).\n",
    "\n",
    "In that case, the simplest solution is to delete the existing file and run the code again so that `shelve.open` can create a new database."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e4a2fb3",
   "metadata": {},
   "source": [
    "The return value is officially a `DbfilenameShelf` object, more casually called a shelf object.\n",
    "\n",
    "The shelf object behaves in many ways like a dictionary.\n",
    "For example, we can use the bracket operator to add an item, which is a mapping from a key to a value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "b3f6d6ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "key = 'jan-2023/photo1.jpg' \n",
    "db[key] = 'Cat nose'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36fd5e3a",
   "metadata": {},
   "source": [
    "In this example, the key is the path to an image file and the value is a string that describes the image.\n",
    "\n",
    "We also use the bracket operator to look up a key and get the corresponding value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "d4e06b19",
   "metadata": {},
   "outputs": [],
   "source": [
    "value = db[key]\n",
    "value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9b252a7",
   "metadata": {},
   "source": [
    "If you make another assignment to an existing key, `shelve` replaces the old value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "89a0936c",
   "metadata": {},
   "outputs": [],
   "source": [
    "db[key] = 'Close up view of a cat nose'\n",
    "db[key]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "003eacbc",
   "metadata": {},
   "source": [
    "Some dictionary methods, like `keys`, `values` and `items`, also work with shelf objects."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "7d0c4cff",
   "metadata": {},
   "outputs": [],
   "source": [
    "list(db.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "a9db327d",
   "metadata": {},
   "outputs": [],
   "source": [
    "list(db.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "056e0bd9",
   "metadata": {},
   "source": [
    "We can use the `in` operator to check whether a key appears in the shelf."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "cc81ed95",
   "metadata": {},
   "outputs": [],
   "source": [
    "key in db"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "982740b4",
   "metadata": {},
   "source": [
    "And we can use a `for` statement to loop through the keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "68ff774e",
   "metadata": {},
   "outputs": [],
   "source": [
    "for key in db:\n",
    "    print(key, ':', db[key])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b67a0ddc",
   "metadata": {},
   "source": [
    "As with other files, you should close the database when you are done."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "2b411885",
   "metadata": {},
   "outputs": [],
   "source": [
    "db.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1e08b41",
   "metadata": {},
   "source": [
    "Now if we list the contents of the data directory, we see two files."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "4806720c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# When you open a shelve file, a backup file is created that has the suffix `.bak`.\n",
    "# If you run this notebook more than once, you might see that file left behind.\n",
    "# This cell removes it so the output shown in the book is correct.\n",
    "\n",
    "!rm -f photo_info/captions.bak"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "59eb2dde",
   "metadata": {},
   "outputs": [],
   "source": [
    "os.listdir(config['data_dir'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97453006",
   "metadata": {},
   "source": [
    "`captions.dat` contains the data we just stored.\n",
    "`captions.dir` contains information about the organization of the database that makes it more efficient to access.\n",
    "The suffix `dir` stands for \"directory\", but it has nothing to do with the directories we've been working with that contain files."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0033e4f5",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Storing data structures\n",
    "\n",
    "In the previous example, the keys and values in the shelf are strings.\n",
    "But we can also use a shelf to contain data structures like lists and dictionaries.\n",
    "\n",
    "As an example, let's revisit the anagram example from an exercise in [Chapter 11](section_exercise_11).\n",
    "Recall that we made a dictionary that maps from a sorted string of letters to the\n",
    "list of words that can be spelled with those letters.\n",
    "For example, the key `'opst'` maps to the list `['opts', 'post', 'pots', 'spot', 'stop', 'tops']`.\n",
    "\n",
    "We'll use the following function to sort the letters in a word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "8819b211",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sort_word(word):\n",
    "    return ''.join(sorted(word))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c24316c",
   "metadata": {},
   "source": [
    "And here's an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "fc8f1434",
   "metadata": {},
   "outputs": [],
   "source": [
    "word = 'pots'\n",
    "key = sort_word(word)\n",
    "key"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c5d7555",
   "metadata": {},
   "source": [
    "Now let's open a shelf called `anagram_map`.\n",
    "The argument `'n'` means we should always create a new, empty shelf, even if one already exists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "f2f17f05",
   "metadata": {},
   "outputs": [],
   "source": [
    "db = shelve.open('anagram_map', 'n')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b495e79",
   "metadata": {},
   "source": [
    "Now we can add an item to the shelf like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "b918dcfe",
   "metadata": {},
   "outputs": [],
   "source": [
    "db[key] = [word]\n",
    "db[key]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f058dff1",
   "metadata": {},
   "source": [
    "In this item, the key is a string and the value is a list of strings.\n",
    "\n",
    "Now suppose we find another word that contains the same letters, like `tops`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "e0d728e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "word = 'tops'\n",
    "key = sort_word(word)\n",
    "key"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a215367d",
   "metadata": {},
   "source": [
    "The key is the same as in the previous example, so we want to append a second word to the same list of strings.\n",
    "Here's how we would do it if `db` were a dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "12e39086",
   "metadata": {},
   "outputs": [],
   "source": [
    "db[key].append(word)          # INCORRECT"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1a83f39",
   "metadata": {},
   "source": [
    "But if we run that and then look up the key in the shelf, it looks like it has not been updated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "b0dc42e0",
   "metadata": {},
   "outputs": [],
   "source": [
    "db[key]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32a56de9",
   "metadata": {},
   "source": [
    "Here's the problem: when we look up the key, we get a list of strings, but if we modify the list of strings, it does not affect the shelf.\n",
    "If we want to update the shelf, we have to read the old value, update it, and then write the new value back to the shelf."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "b4105610",
   "metadata": {},
   "outputs": [],
   "source": [
    "anagram_list = db[key]\n",
    "anagram_list.append(word)\n",
    "db[key] = anagram_list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a054f537",
   "metadata": {},
   "source": [
    "Now the value in the shelf is updated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "4f737cd9",
   "metadata": {},
   "outputs": [],
   "source": [
    "db[key]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca02c0d7",
   "metadata": {},
   "source": [
    "As an exercise, you can finish this example by reading the word list and storing all of the anagrams in a shelf."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "5395780f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "db.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1336e56",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Checking for equivalent files\n",
    "\n",
    "Now let's get back to the goal of this chapter: searching for different files that contain the same data.\n",
    "One way to check is to read the contents of both files and compare.\n",
    "\n",
    "If the files contain images, we have to open them with mode `'rb'`, where `'r'` means we want to read the contents and `'b'` indicates **binary mode**.\n",
    "In binary mode, the contents are not interpreted as text -- they are treated as a sequence of bytes.\n",
    "\n",
    "Here's an example that opens and reads an image file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "a3104fc7",
   "metadata": {},
   "outputs": [],
   "source": [
    "path1 = 'photos/jan-2023/photo1.jpg'\n",
    "data1 = open(path1, 'rb').read()\n",
    "type(data1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36687da2",
   "metadata": {},
   "source": [
    "The result from `read` is a `bytes` object -- as the name suggests, it contains a sequence of bytes.\n",
    "\n",
    "In general the contents of an image file and not human-readable.\n",
    "But if we read the contents from a second file, we can use the `==` operator to compare."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "fd6dd21d",
   "metadata": {},
   "outputs": [],
   "source": [
    "path2 = 'photos/jan-2023/photo2.jpg'\n",
    "data2 = open(path2, 'rb').read()\n",
    "data1 == data2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36006cd4",
   "metadata": {},
   "source": [
    "These two files are not equivalent.\n",
    "\n",
    "Let's encapsulate what we have so far in a function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "b1c8643c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def same_contents(path1, path2):\n",
    "    data1 = open(path1, 'rb').read()\n",
    "    data2 = open(path2, 'rb').read()\n",
    "    return data1 == data2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4e08850",
   "metadata": {},
   "source": [
    "If we have only two files, this function is a good option.\n",
    "But suppose we have a large number of files and we want to know whether any two of them contain the same data.\n",
    "It would be inefficient to compare every pair of files.\n",
    "\n",
    "An alternative is to use a **hash function**, which takes the contents of a file and computes a **digest**, which is usually a large integer.\n",
    "If two files contain the same data, they will have the same digest.\n",
    "If two files differ, they will *almost always* have different digests.\n",
    "\n",
    "The `hashlib` module provides several hash functions -- the one we'll use is called `md5`.\n",
    "We'll start by using `hashlib.md5` to create a `HASH` object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "c03198fc",
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib\n",
    "\n",
    "md5_hash = hashlib.md5()\n",
    "type(md5_hash)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8e480f0",
   "metadata": {},
   "source": [
    "The `HASH` object provides an `update` method that takes the contents of the file as an argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "1567ec9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "md5_hash.update(data1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86bd6bc0",
   "metadata": {},
   "source": [
    "Now we can use `hexdigest` to get the digest as a string of hexadecimal digits that represent an integer in base 16."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "b2e61e76",
   "metadata": {},
   "outputs": [],
   "source": [
    "digest = md5_hash.hexdigest()\n",
    "digest"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9b4b347",
   "metadata": {},
   "source": [
    "The following function encapsulates these steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "330def4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def md5_digest(filename):\n",
    "    data = open(filename, 'rb').read()\n",
    "    md5_hash = hashlib.md5()\n",
    "    md5_hash.update(data)\n",
    "    digest = md5_hash.hexdigest()\n",
    "    return digest"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "914b85b2",
   "metadata": {},
   "source": [
    "If we hash the contents of a different file, we can confirm that we get a different digest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "eae2d207",
   "metadata": {},
   "outputs": [],
   "source": [
    "filename2 = 'photos/feb-2023/photo2.jpg'\n",
    "md5_digest(filename2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "deeabdde",
   "metadata": {},
   "source": [
    "Now we have almost everything we need to find equivalent files.\n",
    "The last step is to search a directory and find all of the images files."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "129475df",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Walking directories\n",
    "\n",
    "The following function takes as an argument the directory we want to search.\n",
    "It uses `listdir` to loop through the contents of the directory.\n",
    "When it finds a file, it prints its complete path.\n",
    "When it finds a directory, it calls itself recursively to search the subdirectory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "c84a64db",
   "metadata": {},
   "outputs": [],
   "source": [
    "def walk(dirname):\n",
    "    for name in os.listdir(dirname):\n",
    "        path = os.path.join(dirname, name)\n",
    "\n",
    "        if os.path.isfile(path):\n",
    "            print(path)\n",
    "        elif os.path.isdir(path):\n",
    "            walk(path)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "faaf5b25",
   "metadata": {},
   "source": [
    "We can use it like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "f1c60f6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "walk('photos')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "897c66bf",
   "metadata": {},
   "source": [
    "The order of the results depends on details of the operating system."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7853f18",
   "metadata": {},
   "source": [
    "## Debugging\n",
    "\n",
    "When you are reading and writing files, you might run into problems with whitespace.\n",
    "These errors can be hard to debug because whitespace characters are normally invisible.\n",
    "For example, here's a string that contains spaces, a tab represented by the sequence `\\t`, and a newline represented by the sequence `\\n`.\n",
    "When we print it, we don't see the whitespace characters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "15d7425a",
   "metadata": {},
   "outputs": [],
   "source": [
    "s = '1 2\\t 3\\n 4'\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49bbebe6",
   "metadata": {},
   "source": [
    "The built-in function `repr` can help. It takes any object as an argument and returns a string representation of the object.\n",
    "For strings, it represents whitespace characters with backslash sequences."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "61feff85",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(repr(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "790cf8dd",
   "metadata": {},
   "source": [
    "This can be helpful for debugging.\n",
    "\n",
    "One other problem you might run into is that different systems use different characters to indicate the end of a line. Some systems use a newline, represented `\\n`. Others use a return character, represented `\\r`. \n",
    "Some use both. If you move files between different systems, these\n",
    "inconsistencies can cause problems.\n",
    "\n",
    "File name capitalization is another issue you might encounter if you work with different operating systems.\n",
    "In macOS and UNIX, file names can contain lowercase and uppercase letters, digits, and most symbols.\n",
    "But many Windows applications ignore the difference between lowercase and uppercase letters, and several symbols that are allowed in macOS and UNIX are not allowed in Windows."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf063639",
   "metadata": {},
   "source": [
    "## Glossary\n",
    "\n",
    "**ephemeral:**\n",
    "An ephemeral program typically runs for a short time and, when it ends, its data are lost.\n",
    "\n",
    "**persistent:**\n",
    " A persistent program runs indefinitely and keeps at least some of its data in permanent storage.\n",
    "\n",
    "**directory:**\n",
    "A collection of files and other directories.\n",
    "\n",
    "**current working directory:**\n",
    "The default directory used by a program unless another directory is specified.\n",
    "\n",
    "**path:**\n",
    " A string that specifies a sequence of directories, often leading to a file.\n",
    "\n",
    "**relative path:**\n",
    "A path that starts from the current working directory, or some other specified directory.\n",
    "\n",
    "**absolute path:**\n",
    "A path that does not depend on the current directory.\n",
    "\n",
    "**f-string:**\n",
    "A string that has the letter `f` before the opening quotation mark, and contains one or more expressions in curly braces.\n",
    "\n",
    "**configuration data:**\n",
    "Data, often stored in a file, that specifies what a program should do and how.\n",
    "\n",
    "**serialization:**\n",
    "Converting an object to a string.\n",
    "\n",
    "**deserialization:**\n",
    "Converting a string to an object.\n",
    "\n",
    "**database:**\n",
    " A file whose contents are organized to perform certain operations efficiently.\n",
    "\n",
    "**key-value stores:**\n",
    "A database whose contents are organized like a dictionary with keys that correspond to values.\n",
    "\n",
    "**binary mode:**\n",
    "A way of opening a file so the contents are interpreted as sequence of bytes rather than a sequence of characters.\n",
    "\n",
    "**hash function:**\n",
    "A function that takes and object and computes an integer, which is sometimes called a digest.\n",
    "\n",
    "**digest:**\n",
    "The result of a hash function, especially when it is used to check whether two objects are the same."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "484ce2d2",
   "metadata": {},
   "source": [
    "<!-- apcsp:begin type=\"glossary\" chapter=\"13\" -->\n",
    "**See also:** the [full vocabulary glossary](https://python.porttack.com/alignment/ap-vocabulary-glossary.html) collects every term in this book, alphabetized, alongside the complete AP CSP exam vocabulary list.\n",
    "<!-- apcsp:end -->"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67941fdd",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "bd885ba1",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# This cell tells Jupyter to provide detailed debugging information\n",
    "# when a runtime error occurs. Run it before working on the exercises.\n",
    "\n",
    "%xmode Verbose"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a537173",
   "metadata": {},
   "source": [
    "### Ask a virtual assistant\n",
    "\n",
    "There are several topics that came up in this chapter that I did not explain in detail.\n",
    "Here are some questions you can ask a virtual assistant to get more information. \n",
    "\n",
    "* \"What are the differences between ephemeral and persistent programs?\"\n",
    "\n",
    "* \"What are some examples of persistent programs?\"\n",
    "\n",
    "* \"What's the difference between a relative path and an absolute path?\"\n",
    "\n",
    "* \"Why does the `yaml` module have functions called `load` and `safe_load`?\"\n",
    "\n",
    "* \"When I write a Python shelf, what are the files with suffixes `dat` and `dir`?\"\n",
    "\n",
    "* \"Other than key-values stores, what other kinds of databases are there?\"\n",
    "\n",
    "* \"When I read a file, what's the difference between binary mode and text mode?\"\n",
    "\n",
    "* \"What are the differences between a bytes object and a string?\"\n",
    "\n",
    "* \"What is a hash function?\"\n",
    "\n",
    "* \"What is an MD5 digest?\"\n",
    "\n",
    "As always, if you get stuck on any of the following exercises, consider asking a VA for help.  Along with your question, you might want to paste in the relevant functions from this chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7586e1e9",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Write a function called `replace_all` that takes as arguments a pattern string, a replacement string, and two filenames.\n",
    "It should read the first file and write the contents into the second file (creating it if necessary).\n",
    "If the pattern string appears anywhere in the contents, it should be replaced with the replacement string."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85844afb",
   "metadata": {},
   "source": [
    "Here's an outline of the function to get you started."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "1e598e70",
   "metadata": {},
   "outputs": [],
   "source": [
    "def replace_all(old, new, source_path, dest_path):\n",
    "    # read the contents of the source file\n",
    "    reader = open(source_path)\n",
    "\n",
    "    # replace the old string with the new\n",
    "    \n",
    "    # write the result into the destination file\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "d3774d1a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7f37245c",
   "metadata": {},
   "source": [
    "To test your function, read the file `photos/notes.txt`, replace `'photos'` with `'images'`, and write the result to the file `photos/new_notes.txt`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "3b80dfd8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "source_path = 'photos/notes.txt'\n",
    "open(source_path).read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "4b67579f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "dest_path = 'photos/new_notes.txt'\n",
    "old = 'photos'\n",
    "new = 'images'\n",
    "replace_all(old, new, source_path, dest_path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "1d990225",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "open(dest_path).read()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b2589a4",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "In [a previous section](section_storing_data_structure), we used the `shelve` module to make a key-value store that maps from a sorted string of letters to a list of anagrams.\n",
    "To finish the example, write a function called `add_word` that takes as arguments a string and a shelf object.\n",
    "\n",
    "It should sort the letters of the word to make a key, then check whether the key is already in the shelf. If not, it should make a list that contains the new word and add it to the shelf. If so, it should append the new word to the existing value. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "1c2fff95",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "07cb454f",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use this loop to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "8008cde6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "a6b5e51a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "word_list = open('words.txt').read().split()\n",
    "\n",
    "db = shelve.open('anagram_map', 'n')\n",
    "for word in word_list:\n",
    "    add_word(word, db)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40342366",
   "metadata": {
    "tags": []
   },
   "source": [
    "If everything is working, you should be able to look up a key like `'opst'` and get a list of words that can be spelled with those letters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "ffefe13e",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "db['opst']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "7eb54fbc",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "for key, value in db.items():\n",
    "    if len(value) > 8:\n",
    "        print(value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "ac784df7",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "db.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "228e977c",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "In a large collection of files, there may be more than one copy of the same file, stored in different directories or with different file names.\n",
    "The goal of this exercise is to search for duplicates.\n",
    "As an example, we'll work with image files in the `photos` directory.\n",
    "\n",
    "Here's how it will work:\n",
    "\n",
    "* We'll use the `walk` function from [](section_walking_directories) to search this directory for files that end with one of the extensions in `config['extensions']`.\n",
    "\n",
    "* For each file, we'll use `md5_digest` from [](section_md5_digest) to compute a digest of the contents.\n",
    "\n",
    "* Using a shelf, we'll make a mapping from each digest to a list of paths with that digest.\n",
    "\n",
    "* Finally, we'll search the shelf for any digests that map to multiple files.\n",
    "\n",
    "* If we find any, we'll use `same_contents` to confirm that the files contain the same data."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f5365da",
   "metadata": {},
   "source": [
    "I'll suggest some functions to write first, then we'll bring it all together.\n",
    "\n",
    "1. To identify image files, write a function called `is_image` that takes a path and a list of file extensions, and returns `True` if the path ends with one of the extensions in the list. Hint: Use `os.path.splitext` -- or ask a virtual assistant to write this function for you."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "03b6acf9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "dde4b5c8",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use `doctest` to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "21c33092",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from doctest import run_docstring_examples\n",
    "\n",
    "def run_doctests(func):\n",
    "    run_docstring_examples(func, globals(), name=func.__name__)\n",
    "\n",
    "run_doctests(is_image)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a7c8f49",
   "metadata": {},
   "source": [
    "2. Write a function called `add_path` that takes as arguments a path and a shelf. It should use `md5_digest` to compute a digest of the file contents. Then it should update the shelf, either creating a new item that maps from the digest to a list containing the path, or appending the path to the list if it exists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "31c056a9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "08223a21",
   "metadata": {},
   "source": [
    "3. Write a version of `walk` called `walk_images` that takes a directory and walks through the files in the directory and its subdirectories. For each file, it should use `is_image` to check whether it's an image file and `add_path` to add it to the shelf."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "e54d6993",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "1ea76a52",
   "metadata": {},
   "source": [
    "When everything is working, you can use the following program to create the shelf, search the `photos` directory and add paths to the shelf, and then check whether there are multiple files with the same digest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "c31ba5b6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "db = shelve.open('photos/digests', 'n')\n",
    "walk_images('photos')\n",
    "\n",
    "for digest, paths in db.items():\n",
    "    if len(paths) > 1:\n",
    "        print(paths)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "102d4d10",
   "metadata": {},
   "source": [
    "You should find one pair of files that have the same digest.\n",
    "Use `same_contents` to check whether they contain the same data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "d7c7e679",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6a6b5a7",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a7f4edf8",
   "metadata": {
    "tags": []
   },
   "source": [
    "<!-- apcsp:begin type=\"note\" chapter=\"13\" -->\n",
    "**Working in Python** — modified by Eric Brown for a high school Computer Science Principles class. Source and modifications: [github.com/porttack/working-in-python](https://github.com/porttack/working-in-python)\n",
    "\n",
    "---\n",
    "<!-- apcsp:end -->\n",
    "\n",
    "[Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html)\n",
    "\n",
    "Copyright 2024 [Allen B. Downey](https://allendowney.com)\n",
    "\n",
    "Code license: [MIT License](https://mit-license.org/)\n",
    "\n",
    "Text license: [Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-nc-sa/4.0/)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}