{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "title",
   "metadata": {},
   "source": [
    "# ADT Basics\n",
    "\n",
    "This section introduces the central design idea of the chapter: separate what a collection does from how it is implemented.\n",
    "\n",
    "```text\n",
    "Outline\n",
    "\n",
    "Abstract Types and Implementations\n",
    "  o Interface vs. implementation\n",
    "  o Common Python examples\n",
    "Operation Tradeoffs\n",
    "  o Access, search, insert, delete\n",
    "  o Choosing by workload\n",
    "Summary\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "interface",
   "metadata": {},
   "source": [
    "## Abstract Types and Implementations\n",
    "\n",
    "An **abstract data type** defines behavior. It says what operations are supported and what each operation means. A **concrete implementation** says how values are stored and how each operation is performed.\n",
    "\n",
    "| Abstract idea | Required behavior | Possible Python implementation |\n",
    "| --- | --- | --- |\n",
    "| Stack | Add and remove from the same end | `list` |\n",
    "| Queue | Add at the back, remove from the front | `collections.deque` |\n",
    "| Set | Store unique values and test membership | `set` |\n",
    "| Map | Associate keys with values | `dict` |\n",
    "| Graph | Store nodes and relationships | `dict[str, list[str]]` |\n",
    "\n",
    "The important design question is not which container looks familiar. The important question is which operations the problem needs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "membership-demo",
   "metadata": {},
   "outputs": [],
   "source": [
    "names_list = [\"alice\", \"bob\", \"charlie\"]\n",
    "names_set = {\"alice\", \"bob\", \"charlie\"}\n",
    "\n",
    "print(\"bob\" in names_list)\n",
    "print(\"bob\" in names_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exercise-interface",
   "metadata": {
    "tags": [
     "thebe-interactive"
    ]
   },
   "outputs": [],
   "source": [
    "### Exercise: Choose an Implementation\n",
    "# A program needs to keep a unique collection of product IDs and frequently\n",
    "# check whether an ID has already appeared.\n",
    "#\n",
    "# 1. Choose a Python implementation: list, tuple, set, or dict.\n",
    "# 2. Create the collection with the values 101, 102, 103.\n",
    "# 3. Check whether 102 is in the collection.\n",
    "### Your code starts here.\n",
    "\n",
    "\n",
    "\n",
    "### Your code ends here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "solution-interface",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "### Solution\n",
    "product_ids = {101, 102, 103}\n",
    "print(102 in product_ids)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "tradeoffs",
   "metadata": {},
   "source": [
    "## Operation Tradeoffs\n",
    "\n",
    "A data structure is a tradeoff. One structure may make lookup easy but insertion expensive. Another may make insertion easy but searching slower.\n",
    "\n",
    "| Need | Usually choose | Reason |\n",
    "| --- | --- | --- |\n",
    "| Preserve order | `list` | Natural sequence behavior |\n",
    "| Fast membership checks | `set` | Designed for `in` checks |\n",
    "| Key-value lookup | `dict` | Direct lookup by key |\n",
    "| Add/remove at both ends | `deque` | Efficient front and back operations |\n",
    "| Parent-child hierarchy | tree | Models nested relationships |\n",
    "| Many-to-many relationships | graph | Models general connections |\n",
    "\n",
    "Before coding, write down the operations your program will perform most often."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "tradeoff-demo",
   "metadata": {},
   "outputs": [],
   "source": [
    "inventory = {\n",
    "    \"apple\": 10,\n",
    "    \"banana\": 5,\n",
    "    \"cherry\": 12,\n",
    "}\n",
    "\n",
    "item = \"banana\"\n",
    "print(item, inventory[item])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exercise-tradeoffs",
   "metadata": {
    "tags": [
     "thebe-interactive"
    ]
   },
   "outputs": [],
   "source": [
    "### Exercise: Build a Lookup Table\n",
    "# Create a dictionary that maps these employee names to departments:\n",
    "# alice -> Analytics\n",
    "# bob -> Operations\n",
    "# charlie -> Finance\n",
    "#\n",
    "# Then print bob's department.\n",
    "### Your code starts here.\n",
    "\n",
    "\n",
    "\n",
    "### Your code ends here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "solution-tradeoffs",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "### Solution\n",
    "departments = {\n",
    "    \"alice\": \"Analytics\",\n",
    "    \"bob\": \"Operations\",\n",
    "    \"charlie\": \"Finance\",\n",
    "}\n",
    "\n",
    "print(departments[\"bob\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "summary",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "Abstract data types focus on behavior. Concrete implementations focus on storage and execution. Good data-structure choices start with the operations the program needs most."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}