{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Moduł collections\n",
    "\n",
    "### Opis modułu\n",
    "\n",
    "Moduł *collections* zawiera wyspecjalizowane typy danych. Są one\n",
    "alternatywą dla wbudowanych typów danych takich jak `dict`, `list`,\n",
    "`set` i `tuple`.\n",
    "\n",
    "| Nazwa typu       | Opis                                                                        |\n",
    "|------------------|-----------------------------------------------------------------------------|\n",
    "| `namedtuple()`   | Funkcja służąca do tworzenia krotek z nazwanymi polami.                     |\n",
    "| `deque`          | Kontener podobny do listy, z dostępem zarówno od początku, jak i od końca.  |\n",
    "| `Counter`        | Klasa słownika służąca do liczenia obiektów.                                |\n",
    "| `OrderedDict`    | Klasa słownika, która pamięta kolejność, w jakiej dodawano elementy.        |\n",
    "| `defaultdict`    | Klasa słownika, która umożliwia zdefiniowanie brakujących elementów.        |\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### `namedtuple`\n",
    "\n",
    "Nazwane krotki są stosowane wszędzie tam, gdzie potrzebujemy manipulować\n",
    "niewielkimi rekordami, a jednocześnie nie chcemy tworzyć osobnej klasy.\n",
    "\n",
    "Przykładem jest klasa `Point`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "import math\n",
    "\n",
    "Point = namedtuple('Point', 'x y z')\n",
    "\n",
    "def distance(a, b):\n",
    "    return math.sqrt(\n",
    "        (a.x - b.x)**2 +\n",
    "        (a.y - b.y)**2 +\n",
    "        (a.z - b.z)**2\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "39.25557285278104\n"
     ]
    }
   ],
   "source": [
    "a = Point(x=1, y=2, z=3)\n",
    "b = Point(-1, -2, 42)\n",
    "print(distance(a, b))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nazwane krotki przydają się także wtedy, gdy chcemy zwrócić więcej niż\n",
    "jeden obiekt. Funkcja lub metoda może zwrócić kilka obiektów w krotce,\n",
    "ale trzeba wówczas pamiętać, w jakiej kolejności są one zwracane.\n",
    "Alternatywą jest zwrócenie nazwanej krotki:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "\n",
    "Result = namedtuple('Result', 'quotient remainder')\n",
    "\n",
    "def div_mod(a, b):\n",
    "    return Result(quotient=a//b, remainder=a%b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Result(quotient=4, remainder=1)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r = div_mod(9, 2)\n",
    "r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.quotient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.remainder"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deque\n",
    "\n",
    "W niektórych algorytmach stosowane są kolejki FIFO (*first in, first\n",
    "out*). Kolejka jest listą, której nowe elementy są dodawane na jej\n",
    "początku. Z kolei inny wątek może pobierać elementy (odczytywać je\n",
    "i usuwać z listy) z jej końca.\n",
    "\n",
    "Stosowanie listy może spowolnić program, ponieważ dodanie lub usunięcie\n",
    "elementu z początku listy jest operacją kosztowną (złożoność *O(n)*).\n",
    "Dlatego w takich sytuacjach stosuje się wyspecjalizowany kontener\n",
    "`deque`. Jego zaletą jest możliwość szybkiego (w czasie stałym\n",
    "*O(1)*) dodawania i usuwania elementów zarówno z początku, jak i końca.\n",
    "\n",
    "[deque]{.title-ref} udostępnia ten sam interfejs, co listy. Dostępne są również metody `appendleft`, `extendleft` oraz `popleft`, które\n",
    "działają tak samo jak odpowiednio `append`, `extend` i `pop`, ale\n",
    "działają na początku kolekcji zamiast na jej końcu.\n",
    "\n",
    "Na przykład, `appendleft(x)` wstawia obiekt *x* na początek kolejki. Jest\n",
    "to równoważne wywołaniu `insert(0, x))`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "\n",
    "dq = collections.deque('abcdefg')\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(dq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'g'"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['a', 'b', 'd', 'e', 'f', 'g'])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.remove('c')\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "g\n",
      "f\n",
      "e\n",
      "d\n",
      "b\n",
      "a\n"
     ]
    }
   ],
   "source": [
    "while True:\n",
    "    try:\n",
    "        print(dq.pop())\n",
    "    except IndexError:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "b\n",
      "c\n",
      "d\n",
      "e\n",
      "f\n",
      "g\n"
     ]
    }
   ],
   "source": [
    "dq = collections.deque('abcdefg')\n",
    "\n",
    "while True:\n",
    "    try:\n",
    "        print(dq.popleft())\n",
    "    except IndexError:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq = collections.deque(range(10))\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq = collections.deque(range(10))\n",
    "dq.rotate(2)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq = collections.deque(range(10))\n",
    "dq.rotate(-2)\n",
    "dq"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Counter\n",
    "\n",
    "``Counter`` jest klasą ułatwiającą zliczanie elementów.\n",
    "Jest to słownik, którego kluczami są elementy, a wartościami częstość ich występowania.\n",
    "Przy tworzeniu instancji należy przekazać kolekcję elementów, które mają zostać zliczone.\n",
    "\n",
    "Zliczanie znaków występujących w danym napisie można wykonać przy pomocy zwykłego słownika:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'H': 1, 'e': 5, 'l': 3, 'o': 2, ' ': 2, 't': 1, 'h': 1, 'r': 1, ',': 1, 'P': 1, 'p': 1, '!': 1}\n"
     ]
    }
   ],
   "source": [
    "counter = {}\n",
    "\n",
    "for char in \"Hello there, People!\":\n",
    "    if char not in counter:\n",
    "        counter[char] = 1\n",
    "    else:\n",
    "        counter[char] += 1\n",
    "\n",
    "print(counter)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lub szybciej, przy pomocy klasy ``Counter``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({'e': 5, 'l': 3, 'o': 2, ' ': 2, 'H': 1, 't': 1, 'h': 1, 'r': 1, ',': 1, 'P': 1, 'p': 1, '!': 1})\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "counter = Counter(\"Hello there, People!\")\n",
    "\n",
    "print(counter)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "``most_common`` jest metodą umożliwiającą sprawdzenie, które elementy występują najczęściej.\n",
    "Jeśli chcemy znaleźć najczęściej występujące słowa w pliku ``holmes.txt``, możemy wykonać:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('the', 5810), ('and', 3088), ('i', 3038), ('to', 2823), ('of', 2778), ('a', 2700), ('in', 1823), ('that', 1767), ('it', 1749), ('you', 1572)]\n"
     ]
    }
   ],
   "source": [
    "import re\n",
    "\n",
    "words = re.findall('\\w+', open('holmes.txt').read().lower())\n",
    "\n",
    "print(Counter(words).most_common(10))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## OrderedDict\n",
    "\n",
    "Słowniki przechowują pary *(klucz, wartość)*, ale nie pamiętają kolejności, w jakiej poszczególne pary zostały dodane.\n",
    "``OrderedDict`` jest słownikiem, który zapamiętuje tę kolejność.\n",
    "Podczas iterowania po nim, zwraca on klucze w kolejności, w jakiej zostały dodane:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "c\n",
      "b\n",
      "a\n"
     ]
    }
   ],
   "source": [
    "from collections import OrderedDict\n",
    "\n",
    "d = OrderedDict()\n",
    "d['c'] = 1\n",
    "d['b'] = 2\n",
    "d['a'] = 1\n",
    "\n",
    "for k in d:\n",
    "    print(k)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dodatkowo, ten obiekt udostępnia metodę ``popitem``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('a', 1)"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.popitem()  # zwraca ostanio dodaną parę (klucz, wartość) (kolejka LIFO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('c', 1)"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.popitem(last=False)  # zwraca pierwszą dodaną parę (kolejka FIFO)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `defaultdict`\n",
    "\n",
    "``defaultdict`` jest takim słownikiem, w którym użycie klucza nie będącego w tym słowniku powoduje użycie domyślnej wartości zamiast zgłoszenia wyjątku ``KeyError``.\n",
    "\n",
    "Ten obiekt pozwala uprościć kod wykorzystujący ideę multisłownika, to znaczy słownika, w którym jeden klucz może mieć więcej niż jedną wartość.\n",
    "Taki multisłownik może zostać zaimplementowany jako zwykły słownik, którego wartościami jest lista.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_items([('yellow', [1, 3]), ('blue', [2, 4]), ('red', [1])])"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]\n",
    "res = {}\n",
    "\n",
    "for color, item in s:\n",
    "    if color in res:\n",
    "        res[color].append(item)\n",
    "    else:\n",
    "        res[color] = [item, ]\n",
    "\n",
    "res.items()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rozwiązanie z użyciem ``defaultdict`` jest znacznie prostsze.\n",
    "Przy tworzeniu słownika przekazujemy funkcję, która generuje wartość domyślną.\n",
    "W tym przypadku wartością domyślną jest pusta lista, którą generuje wbudowana funkcja ``list``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "defaultdict(<class 'list'>, {'yellow': [1, 3], 'blue': [2, 4], 'red': [1]})\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]\n",
    "\n",
    "d = defaultdict(list)\n",
    "for k, v in s:\n",
    "    d[k].append(v)\n",
    "\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "jb",
   "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.8"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}