dict, testes e métodos especiais em Python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "20/07/2016 - por Gabriel Marcondes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# dict, testes e métodos especiais em Python\n",
    "\n",
    "Vamos fazer um bem-bolado de Python: inspirado pela explicação dada no [excelente livro do Luciano Ramalho, _Fluent Python_](http://shop.oreilly.com/product/0636920032519.do \"Fluent Python, na O'Reilly\"), vamos implementar uma classe similar ao `dict` do Python, com a filosofia de TDD (test-driven development) e aprendendo como o interpretador usa os métodos especiais.\n",
    "\n",
    "## testes\n",
    "\n",
    "No desenvolvimento orientado a testes, a gente escreve os testes antes de escrever o código (ou deveria, né?). O ciclo é: escreve testes, roda testes; se os testes falharem escreve código, se passarem escreve mais testes. É importante, e óbvio, que os testes cubram todas as funcionalidades esperadas do futuro código, incluindo os casos de erro.\n",
    "\n",
    "Não vamos usar nenhum framework de testes aqui, vamos apenas usar o assert padrão do Python, assim não teremos dependência nenhuma pra rodar nosso código. Para se aprofundar mais em testes, recomendo que estude algo como o [py.test](http://docs.pytest.org/en/latest/ \"py.test\").\n",
    "\n",
    "Comecemos com alguns testes bem simples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'MeuDicionario' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m-----------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m           Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-1-7c08b2bb1319>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# testes\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0md\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMeuDicionario\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"chave\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m\"valor\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"chave\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"valor\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'MeuDicionario' is not defined"
     ]
    }
   ],
   "source": [
    "# testes\n",
    "d = MeuDicionario()\n",
    "d[\"chave\"] = \"valor\"\n",
    "assert d[\"chave\"] == \"valor\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Claro que o teste iria falhar, pois sequer implementamos a classe. E se o teste falhou, vamos escrever código."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'MeuDicionario' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m-----------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m           Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-2-a8d4ecf80135>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;31m# testes\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0md\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMeuDicionario\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"chave\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m\"valor\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      8\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"chave\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"valor\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: 'MeuDicionario' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "# código\n",
    "class MeuDicionario:\n",
    "    pass\n",
    "\n",
    "# testes\n",
    "d = MeuDicionario()\n",
    "d[\"chave\"] = \"valor\"\n",
    "assert d[\"chave\"] == \"valor\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Agora o erro acontece na segunda linha dos testes, afinal não implementamos \"item assignment\" na nossa classe. Já deu pra sacar qual é a do TDD, né? Vamos falar um pouco de como funciona um dicionário, agora."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## hash tables and hash maps\n",
    "\n",
    "O tipo de estrutura de dados que precisamos aprender primeiro é o _hash table_. Basicamente é um grande array vazio, onde vamos inserindo dados em posições __calculadas__ por uma função _hash_ (uma função que \"espalha\" valores) a partir do dado original. Assim, quando queremos achar se um valor está nessa tabela, não precisamos procurar por todo o array: calculamos a posição esperada e verificamos a presença já sabendo onde ele estará. O ganho é termos um tempo de pesquisa constante, independente do tamanho dos dados, em troca de gastarmos mais espaço na memória para guardá-los.\n",
    "\n",
    "Baseado no _hash table_ podemos construir o _hash map_, que é o uso de uma hash table para guardarmos uma estrutura de _mapeamento_.\n",
    "\n",
    "Então isso será o `MeuDicionario`: grandes arrays vazios, onde vamos inserir os pares chave-valor na posição calculada pela função _hash_ do Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## métodos especiais\n",
    "\n",
    "Outra coisa que precisamos saber é como o Python procura por código para os seus operadores. Pela mensagem de erro do último teste, podemos ver que o operador [] procura pela funcionalidade de `item assignment`. Esta e outras funcionalidades relacionadas aos operadores da linguagem são implementadas nos _métodos especiais_, métodos com nomes específicos, começados e terminados com dois underlines. Por exemplo, o operador de soma `+` irá procurar pelo método `__add__`.\n",
    "\n",
    "Você pode ver [aqui](https://docs.python.org/3/reference/datamodel.html#basic-customization \"Documentação Oficial\") com mais detalhes a explicação de cada método especial e quando cada um é chamado. No nosso caso, queremos o operador de item assignment, então implementaremos o `__setitem__`.\n",
    "\n",
    "Vamos começar inicializando nosso grande array vazio e implementando o método `__setitem__`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'MeuDicionario' object is not subscriptable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m-----------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m           Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-af90d4a998a6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0md\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMeuDicionario\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"chave\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m\"valor\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"chave\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"valor\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'MeuDicionario' object is not subscriptable"
     ]
    }
   ],
   "source": [
    "class MeuDicionario:\n",
    "    def __init__(self):\n",
    "        self._tamanho = 128\n",
    "        self._chaves = [None for i in range(128)]\n",
    "        self._valores = [None for i in range(128)]\n",
    "    \n",
    "    def __setitem__(self, chave, valor):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        self._chaves[posicao] = chave\n",
    "        self._valores[posicao] = valor\n",
    "\n",
    "# testes\n",
    "d = MeuDicionario()\n",
    "d[\"chave\"] = \"valor\"\n",
    "assert d[\"chave\"] == \"valor\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Opa! Passamos pelo teste de inserção, mas falhamos na comparação porque não implementamos ainda o método `__getitem__`.\n",
    "\n",
    "Agora que já entendemos como testamos e como implementamos, vamos expandir os testes para mais casos de uso do nosso dicionário. Vamos querer os métodos de listar as chaves e os valores, de verificação de conteúdo e de iteração de itens. Claro, eles vão falhar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'MeuDicionario' object is not subscriptable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m-----------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m           Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-4-2f0b5c5bfbe1>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0md\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMeuDicionario\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"chave\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m\"valor\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"chave\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"valor\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0;34m\"chave\"\u001b[0m \u001b[0;32min\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0;34m\"valor\"\u001b[0m \u001b[0;32min\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvalues\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: 'MeuDicionario' object is not subscriptable"
     ]
    }
   ],
   "source": [
    "class MeuDicionario:\n",
    "    def __init__(self):\n",
    "        self._tamanho = 128\n",
    "        self._chaves = [None for i in range(128)]\n",
    "        self._valores = [None for i in range(128)]\n",
    "    \n",
    "    def __setitem__(self, chave, valor):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        self._chaves[posicao] = chave\n",
    "        self._valores[posicao] = valor\n",
    "\n",
    "# testes\n",
    "d = MeuDicionario()\n",
    "d[\"chave\"] = \"valor\"\n",
    "assert d[\"chave\"] == \"valor\"\n",
    "assert \"chave\" in d\n",
    "assert \"valor\" in d.values()\n",
    "for c, v in d.items():\n",
    "    assert c == \"chave\"\n",
    "    assert v == \"valor\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Os métodos que precisamos são `__getitem__`, `__contains__`, `values`, `items`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sucesso!\n"
     ]
    }
   ],
   "source": [
    "class MeuDicionario:\n",
    "    def __init__(self):\n",
    "        self._tamanho = 128\n",
    "        self._chaves = [None for i in range(128)]\n",
    "        self._valores = [None for i in range(128)]\n",
    "    \n",
    "    def __setitem__(self, chave, valor):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        self._chaves[posicao] = chave\n",
    "        self._valores[posicao] = valor\n",
    "    \n",
    "    def __getitem__(self, chave):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        return self._valores[posicao]\n",
    "    \n",
    "    def __contains__(self, chave):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        return self._chaves[posicao] is not None\n",
    "    \n",
    "    def values(self):\n",
    "        return [valor for valor in self._valores if valor is not None]\n",
    "\n",
    "    def items(self):\n",
    "        for par in zip(self._chaves, self._valores):\n",
    "            if par[0] is not None:\n",
    "                yield par\n",
    "        \n",
    "# testes\n",
    "d = MeuDicionario()\n",
    "d[\"chave\"] = \"valor\"\n",
    "assert d[\"chave\"] == \"valor\"\n",
    "assert \"chave\" in d\n",
    "assert \"valor\" in d.values()\n",
    "for c, v in d.items():\n",
    "    assert c == \"chave\"\n",
    "    assert v == \"valor\"\n",
    "\n",
    "print(\"sucesso!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deu tudo certo! Passamos em todos os testes, mas cá entre nós, nossos testes eram muito simples. Existem mais sutilezas nos dicionários, vamos discutir algumas delas.\n",
    "\n",
    "Um problema que pode acontecer é a _colisão de hash_. Quanto mais dados, maior a probabilidade que duas chaves caiam no mesmo hash, porque o array vai enchendo. Então vamos implementar duas coisas novas: aumentar o tamanho do array sempre que ele estiver 30% ocupado, redistribuir os pares depois da expansão, e guardarmos listas de chaves em cada posição, para o caso da colisão ainda acontecer.\n",
    "\n",
    "Para conseguirmos atingir esses cenários, vamos primeiro testar o caso de colisão com um espaço de array reduzido e sem a expansão automática."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "chaves [['chave', 'outra chave']]\n",
      "valores [['valor', 'outro valor']]\n",
      "sucesso!\n"
     ]
    }
   ],
   "source": [
    "class MeuDicionario:\n",
    "    def __init__(self, tamanho_inicial=128):\n",
    "        self._tamanho = tamanho_inicial\n",
    "        self._chaves = [[] for i in range(self._tamanho)]\n",
    "        self._valores = [[] for i in range(self._tamanho)]\n",
    "    \n",
    "    def __setitem__(self, chave, valor):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        self._chaves[posicao].append(chave)\n",
    "        self._valores[posicao].append(valor)\n",
    "    \n",
    "    def __getitem__(self, chave):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        sub_posicao = self._chaves[posicao].index(chave)\n",
    "        return self._valores[posicao][sub_posicao]\n",
    "    \n",
    "    def __contains__(self, chave):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        return chave in self._chaves[posicao]\n",
    "    \n",
    "    def values(self):\n",
    "        for valores in self._valores:\n",
    "            if valores is not None:\n",
    "                for valor in valores:\n",
    "                    yield valor\n",
    "\n",
    "    def items(self):\n",
    "        for par in zip(self._chaves, self._valores):\n",
    "            if par[0]:\n",
    "                for chave, valor in zip(par[0], par[1]):\n",
    "                    yield chave, valor\n",
    "        \n",
    "# testes\n",
    "d = MeuDicionario(tamanho_inicial=1)\n",
    "d[\"chave\"] = \"valor\"\n",
    "assert d[\"chave\"] == \"valor\"\n",
    "assert \"chave\" in d\n",
    "assert \"valor\" in d.values()\n",
    "for c, v in d.items():\n",
    "    assert c == \"chave\"\n",
    "    assert v == \"valor\"\n",
    "\n",
    "d[\"outra chave\"] = \"outro valor\"\n",
    "assert d[\"chave\"] == \"valor\"\n",
    "assert d[\"outra chave\"] == \"outro valor\"\n",
    "print(\"chaves\", d._chaves)\n",
    "print(\"valores\", d._valores)\n",
    "\n",
    "print(\"sucesso!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imprimimos os arrays de chaves e valores para verificarmos que a colisão aconteceu, e mesmo assim os pares foram preservados, já que os testes passaram. Vamos agora implementar a expansão automática. Cada vez que formos inserir um novo item, vamos verificar se o array já está mais de 30% ocupado, e se for o caso, aumentaremos em 50% o tamanho do array, retirando todos os itens e recolocando-os nas suas novas posições."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "expandindo!\n",
      "chaves [['chave', 'outra chave'], [], [], []]\n",
      "valores [['valor', 'outro valor'], [], [], []]\n",
      "sucesso!\n"
     ]
    }
   ],
   "source": [
    "class MeuDicionario:\n",
    "    def __init__(self, tamanho_inicial=128):\n",
    "        self._tamanho = tamanho_inicial\n",
    "        self._ocupacao = 0\n",
    "        self._chaves = [[] for i in range(self._tamanho)]\n",
    "        self._valores = [[] for i in range(self._tamanho)]\n",
    "        \n",
    "    def _expandir(self):\n",
    "        print(\"expandindo!\")\n",
    "        pares_existentes = list(self.items())\n",
    "        self._tamanho = int(1.5 * self._tamanho)\n",
    "        self._chaves = [[] for i in range(self._tamanho)]\n",
    "        self._valores = [[] for i in range(self._tamanho)]\n",
    "        for chave, valor in pares_existentes:\n",
    "            self[chave] = valor\n",
    "    \n",
    "    def __setitem__(self, chave, valor):\n",
    "        if self._ocupacao / self._tamanho > 0.3:\n",
    "            self._expandir()        \n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        self._chaves[posicao].append(chave)\n",
    "        self._valores[posicao].append(valor)\n",
    "        self._ocupacao += 1\n",
    "    \n",
    "    def __getitem__(self, chave):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        sub_posicao = self._chaves[posicao].index(chave)\n",
    "        return self._valores[posicao][sub_posicao]\n",
    "    \n",
    "    def __contains__(self, chave):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        return chave in self._chaves[posicao]\n",
    "    \n",
    "    def values(self):\n",
    "        for valores in self._valores:\n",
    "            if valores is not None:\n",
    "                for valor in valores:\n",
    "                    yield valor\n",
    "\n",
    "    def items(self):\n",
    "        for par in zip(self._chaves, self._valores):\n",
    "            if par[0]:\n",
    "                for chave, valor in zip(par[0], par[1]):\n",
    "                    yield chave, valor\n",
    "        \n",
    "# testes\n",
    "d = MeuDicionario(tamanho_inicial=3)\n",
    "d[\"chave\"] = \"valor\"\n",
    "assert d[\"chave\"] == \"valor\"\n",
    "assert \"chave\" in d\n",
    "assert \"valor\" in d.values()\n",
    "for c, v in d.items():\n",
    "    assert c == \"chave\"\n",
    "    assert v == \"valor\"\n",
    "\n",
    "d[\"outra chave\"] = \"outro valor\"\n",
    "assert d[\"chave\"] == \"valor\"\n",
    "assert d[\"outra chave\"] == \"outro valor\"\n",
    "print(\"chaves\", d._chaves)\n",
    "print(\"valores\", d._valores)\n",
    "assert d._tamanho > 3\n",
    "\n",
    "print(\"sucesso!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Agora que já temos o dicionário guardando e buscando dados, tratando colisões e se expandindo corretamente, vamos apagar os `print`s e tratar de um caso errado, buscar uma chave não existente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sucesso!\n"
     ]
    }
   ],
   "source": [
    "class MeuDicionario:\n",
    "    def __init__(self, tamanho_inicial=128):\n",
    "        self._tamanho = tamanho_inicial\n",
    "        self._ocupacao = 0\n",
    "        self._chaves = [[] for i in range(self._tamanho)]\n",
    "        self._valores = [[] for i in range(self._tamanho)]\n",
    "        \n",
    "    def _expandir(self):\n",
    "        pares_existentes = list(self.items())\n",
    "        self._tamanho = int(1.5 * self._tamanho)\n",
    "        self._chaves = [[] for i in range(self._tamanho)]\n",
    "        self._valores = [[] for i in range(self._tamanho)]\n",
    "        for chave, valor in pares_existentes:\n",
    "            self[chave] = valor\n",
    "    \n",
    "    def __setitem__(self, chave, valor):\n",
    "        if self._ocupacao / self._tamanho > 0.3:\n",
    "            self._expandir()        \n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        self._chaves[posicao].append(chave)\n",
    "        self._valores[posicao].append(valor)\n",
    "        self._ocupacao += 1\n",
    "    \n",
    "    def __getitem__(self, chave):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        try:\n",
    "            sub_posicao = self._chaves[posicao].index(chave)\n",
    "        except ValueError:\n",
    "            raise KeyError(\"Chave não Encontrada\")\n",
    "        return self._valores[posicao][sub_posicao]\n",
    "    \n",
    "    def __contains__(self, chave):\n",
    "        posicao = hash(chave) % self._tamanho\n",
    "        return chave in self._chaves[posicao]\n",
    "    \n",
    "    def values(self):\n",
    "        for valores in self._valores:\n",
    "            if valores is not None:\n",
    "                for valor in valores:\n",
    "                    yield valor\n",
    "\n",
    "    def items(self):\n",
    "        for par in zip(self._chaves, self._valores):\n",
    "            if par[0]:\n",
    "                for chave, valor in zip(par[0], par[1]):\n",
    "                    yield chave, valor\n",
    "        \n",
    "# testes\n",
    "d = MeuDicionario(tamanho_inicial=3)\n",
    "d[\"chave\"] = \"valor\"\n",
    "assert d[\"chave\"] == \"valor\"\n",
    "assert \"chave\" in d\n",
    "assert \"valor\" in d.values()\n",
    "for c, v in d.items():\n",
    "    assert c == \"chave\"\n",
    "    assert v == \"valor\"\n",
    "\n",
    "d[\"outra chave\"] = \"outro valor\"\n",
    "assert d[\"chave\"] == \"valor\"\n",
    "assert d[\"outra chave\"] == \"outro valor\"\n",
    "assert d._tamanho > 3\n",
    "\n",
    "try:\n",
    "    d[\"chave inexistente\"]\n",
    "except KeyError:\n",
    "    pass  # exceção esperada!\n",
    "except Exception:\n",
    "    raise  # outra exceção, inesperada\n",
    "\n",
    "print(\"sucesso!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## finalizando\n",
    "\n",
    "O `dict` do Python é muito mais complexo do que vimos aqui, claro. Se quiser exercitar, estude a [documentação oficial](https://docs.python.org/3/tutorial/datastructures.html#dictionaries \"Documentação Oficial\") e implemente os outros métodos que não fizemos. Os exemplos de uso da documentação podem ser novos casos de testes. Você pode começar com os métodos de impressão, por exemplo, para que tenhamos uma saída inteligível para o `print(d)`.\n",
    "\n",
    "Os testes, aliás, são nossos melhores amigos. Graças a eles pudemos desenvolver as novas funcionalidades, que envolviam reescrever alguns dos métodos, e verificar logo em seguida que os casos anteriores continuavam funcionando.\n",
    "\n",
    "O código e o [jupyter notebook](http://jupyter.readthedocs.org/ \"Jupyter Notebook\") usados para este post estão [neste repo do github](https://github.com/gabrielmarcondes/dict_post \"Repo no GitHub\")."
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}