.. -*- coding: utf-8 -*-

Dicionários
===========

Dicionários são a estrutura de dados mais importantes do universo! |:smirk:|
Nada como exagerar para chamar a atenção. |:smile:|
Dicionários são muito usados e têm um papel primordial em várias aplicações cotidianas.
Dependendo do contexto, dicionários também são chamados de *Tabelas de Símbolos* (*Symbol Tables*), 
*Vetores Associativos* (*Associative arrays*) e *Mapas* (*Maps*).

.. image:: ./imgs/dicionario.*
  :width: 1022
  :height: 834        
  :scale: 40	  
  :alt: By Sailko - Own work, CC BY 3.0 
  :align: center	
  :target: https://commons.wikimedia.org/w/index.php?curid=57477584


Objetivos de aprendizagem
-------------------------

Aprender conceitos que envolvem dicionários.
Implementar algumas versões de dicionários para nos tornarmos melhores usuários de dicionários que são nativos em várias linguagens de programação.

Praticar, ao longo do caminho, rudimentos de análise de algoritmos e análise experimental de algoritmos.
Tudo isso terá como pano de fundo o problema de contar a frequência de cada palavra em uma lista de palavras (dada através de um arquivo). Na solução desse problema o uso de dicionários tem um papel soberano.


Introdução
----------

Um **dicionário** é uma tabela com duas colunas:  
uma coluna de **chaves** (= *keys*) e uma de **valores** (= *values*).
Dizemos que cada linha da tabela 
é um **item** do dicionário, 
formado por um par chave-valor.  
Portanto, cada item associa um valor a uma chave.

Um exemplo simples é a tabela que associa os nomes de todas as alunas e alunos da USP aos seus números USP.

.. math::

    \begin{array}{ll}
    \text{chave} &  \text{valor} \\ \hline 
    8536152     & \text{Antonia Silva } \\ 
    7210629     & \text{Arthur Costa } \\
    8536339     & \text{Bruna Correia } \\
    8536002     & \text{Maria Lima } \\
    8067490     & \text{ Bruno Aires } \\
    8536106     & \text{Caio Oliveira } \\
    7581374     & \text{Gabriela Lima } \\
    8535922     & \text{Marina Sales } \\
    5992240     & \text{Wellington Lima} \\ 
    8536023     & \text{Ana Ferreira } \\
    \vdots      & \vdots 
    \end{array}

Um outro exemplo de dicionário é a tabela que associa as palavras em um texto ao número de vezes que cada palavra ocorre no texto.
Para o texto abaixo (que se encontra sem acentos para simplificar seu processamento):

::
   
    Fracassei em tudo o que tentei na vida.
    Tentei alfabetizar as criancas brasileiras, nao consegui.
    Tentei salvar os indios, nao consegui.
    Tentei fazer uma universidade seria e fracassei.
    Tentei fazer o Brasil desenvolver-se autonomamente e fracassei.
    Mas os fracassos sao minhas vitorias.
    Eu detestaria estar no lugar de quem me venceu
    Darci Ribeiro

    
temos o dicionário

.. math::
   
    \begin{array}{lc}
    \text{ chave }&  \text{valor} \\ \hline 
    \text{ fracassei}& 3\\
    \text{ em}& 1\\
    \text{ tudo}& 1\\
    \text{ o}& 2\\
    \text{ que}& 1\\
    \text{ tentei}& 5\\
    \text{ na}& 1\\
    \text{ vida}& 1\\
    \text{ alfabetizar}& 1\\
    \text{ as}& 1\\
    \text{ crianças}& 1\\
    \text{ brasileiras}& 1\\
    \text{ não}& 2\\
    \text{ consegui}& 2\\
    \text{ salvar}& 1\\
    \text{ os}& 2\\
    \text{ fazer}& 2\\
    \text{ uma}& 1\\
    \text{ universidade}& 1\\
    \text{ índios}& 1\\
    \text{ séria}& 1
    \end{array}
    \quad\quad\quad\quad\quad
    \begin{array}{lc}
    \text{ chave }&  \text{valor} \\ \hline 
    \text{ e}& 2\\
    \text{ brasil}& 1\\
    \text{ desenvolver}& 1\\
    \text{ se}& 1\\
    \text{ autonomamente}& 1\\
    \text{ mas}& 1\\
    \text{ fracassos}& 1\\
    \text{ são}& 1\\
    \text{ minhas}& 1\\
    \text{ vitórias}& 1\\
    \text{ eu}& 1\\
    \text{ detestaria}& 1\\
    \text{ estar}& 1\\
    \text{ no}& 1\\
    \text{ lugar}& 1\\
    \text{ de}& 1\\
    \text{ quem}& 1\\
    \text{ me}& 1\\
    \text{ venceu}& 1\\
    \text{ darci}& 1\\
    \text{ ribeiro}& 1
    \end{array}
        

Classe Dicio 
------------

Um pouco mais precisamente, um **dicionário** é um Tipo de Dados ou classe que consiste em um conjunto de itens, sendo cada item um par ``(chave, valor)``, munido de duas operações fundamentais:

* ``put()``, que **insere** um novo item no conjunto,  e
* ``get()``, que **busca** o valor associado a uma dada chave.

Para ilustrar o uso da classe ``Dicio``, considere a função ``crie_dicionario()`` como abaixo.
Nesse caso constumamos dizer que ``crie_dicionário()`` é **cliente** da classe ``Dicio``.

.. comentario: não seria melhor remover o parâmetro n e incluir n = len(lst)?

.. code:: python

    def crie_dicionario(lst, n):
        '''(list, int) -> Dicio
        RECEBE uma lista lst e um inteiro n.
        CRIA e RETORNA um dicionário em que cada chave é um elemento da lista[0:n] 
        e o valor associado é o número de vezes que o item ocorre lst[0:n].
        '''
        # cria um dicionário vazio
        dicio = Dicio()
        for i in range(n):
            # pega o valor associado a chave lst[i]
            valor = dicio.get(lst[i])
            # se valor == None, lst[i] não estava no dicionário
            if valor == None:
                # insira o item (lst[i], 1) no dicionário
                dicio[lst[i]] = 1
            else:
                # atualize o item no dicionário
                dicio[lst[i]] = valor + 1
        return dicio
        

Comportamento
-------------

Ao ser **criado**, um objeto ``Dicio`` representa um dicionário vazio.

.. code:: python

    In [2]: d = Dicio()

    In [3]: print(d) # note a linha vazia a seguir


    In [4]:

Como sempre, a string utilizada quando escrevemos ``print(d)`` é aquela retornada pelo método mágico ``__str__()``
que **retorna** uma string que representa ``d``.

Um item, ou seja, par ``(chave, valor)`` pode ser **inserido** em um dicionário de duas formas diferentes.
Uma delas é usando o método ``put()``:

.. code:: python
                
    In [4]: d.put('fracassei', 3)

    In [5]: d.put('em', 1)

    In [6]: d.put('tudo', 1)

    In [7]: print(d)
    fracassei: 3
    em: 1
    tudo: 1
        
A outra maneira é semelhante a mudarmos o valor de um elemento de uma lista.
Esse comportamento é de responsabilidade do já visto método mágico ``__setitem__()``.

.. code:: python
                
    In [8]: d['o'] = 2 

    In [9]: d['que'] = 3

    In [10]: d['tentei'] = 4

    In [11]: print(d)
    fracassei: 3
    em: 1
    tudo: 1
    o: 2
    que: 3
    tentei: 4

Bacana, né?! |:sunglasses:|

Podemos **atualizar** o valor associado a uma chave procedendo da mesma forma que inserimos
um item no dicionário.

.. code:: python
                
    In [12]: d.put('o', 2)

    In [13]: d['que'] = 1 

    In [14]: d['tentei'] = 5

    In [15]: print(d)
    fracassei: 3
    em: 1
    tudo: 1
    o: 2
    que: 1
    tentei: 5
    
Para obtermos, ou, como dizem, **buscar** o valor associado a uma chave usamos o método ``get()``.

.. code:: python
                
    In [16]: d.get('fracassei')
    Out[16]: 3

    In [17]: d.get('em')
    Out[17]: 1

    In [18]: d.get('tudo')
    Out[18]: 1
        
Podemos ainda manipular dicionários como listas.
Essa característica é de responsabilidade do conhecido método mágico ``__getitem__()``.

.. code:: python

    In [19]: d['o']
    Out[19]: 2

    In [20]: d['que']
    Out[20]: 1

    In [21]: d['tentei']
    Out[21]: 5
                        

Esses métodos **retornam** ``None`` se a chave não estiver no dicionário:

.. code:: python

    In [27]: print(d.get('vida'))
    None

    In [28]: print(d['vida'])
    None
                        
Tenha em mente que as chaves de dicionários não precisam ser da classe ``str`` e nem os valores da classe ``int``.
O que acontece é que, como no problema que trataremos mais a frente, as chaves são da classe ``str`` e os valores são da classe ``int``, os nossos exemplos estão concentrados nesses tipos mas poderia ser diferente:

.. code:: python

    In [29]: d[1] = 'na'

    In [30]: d[2] = 'vida'

    In [31]: print(d)
    fracassei: 3
    em: 1
    tudo: 1
    o: 2
    que: 1
    tentei: 5
    1: na
    2: vida                
                        
Como você pode observar, em um dicionário podemos ter valores repetidos, entrentanto as **chaves são únicas**!
Faz sentido, certo?! |:thinking:|

Para sabermos se uma chave **pertence** a um dicionário podemos utilizar o operador ``in``, de maneira semelhante ao que fazemos
com objetos da classe ``list``. Essa é uma característica patrocinada pelo método mágico ``__contains__()``:

.. code:: python
                
    In [32]: 'tentei' in d
    Out[32]: True

    In [33]: '1' in d
    Out[33]: False

    In [34]: 1 in d
    Out[34]: True

    In [35]: 5 in d
    Out[35]: False
        
Essa funcionalidade nos faz lembrar de **comandos de repetição** como ``for i in range(n): ...`` e 
``for elemento in lista:...``.

Com o patrocínio do método mágico ``__iter__()`` podemos proceder de maneira semelhante com dicionários:

.. code:: python

    In [36]: for chave in d: print(f"{chave}: {d[chave]}")
    fracassei: 3
    em: 1
    tudo: 1
    o: 2
    que: 1
    tentei: 5
    1: na
    2: vida

Dá hora! |:sunglasses:|

Graças ao conhecido método mágico ``__len__()`` podemos saber o número de itens em um dicionário.
Em particular, se ``len(objeto_Dicio)`` é zero, então ``objeto_Dicio`` é um dicinário vazio.

.. code:: python
                
    In [37]: len(d)
    Out[37]: 8

    In [38]: objeto_Dicio = Dicio()

    In [39]: len(objeto_Dicio)
    Out[39]: 0
        
Por fim, objetos da classe ``Dicio`` têm ainda três outros métodos que podem ser bem úteis, inclusive para testarmos nossas implementações.
Esses métodos são:

* ``keys()`` que **retorna a lista de chaves** do dicionário;
* ``values()`` que **retorna a lista de valores** do dicionário; e
* ``items()`` que **retorna a lista dos itens** do dicionário.

.. code:: python

    In [54]: d.keys()
    Out[54]: ['fracassei', 'em', 'tudo', 'o', 'que', 'tentei', 1, 2]

    In [55]: d.values()
    Out[55]: [3, 1, 1, 2, 1, 5, 'na', 'vida']

    In [56]: d.items()
    Out[56]: 
    [('fracassei', 3),
     ('em', 1),
     ('tudo', 1),
     ('o', 2),
     ('que', 1),
     ('tentei', 5),
     (1, 'na'),
     (2, 'vida')]
                       

Implementação
-------------

Passaremos agora à implementação da classe ``Dicio``.
No esqueleto que está adiante há muitos métodos completamente implementados como ``__init__()`` e ``__str__()``.
Observe o comportamento dos métodos implementados.

Você deverá implementar alguns outros métodos que fazem parte do **motor** da classe ``Dicio``.
Em particular você deverá implementar o *método administrativo* ``indice()`` e os métodos ``put()`` e ``get()``.

Chamamos um método de **administrativo** se ele trabalha atrás do balcão, mantendo as coisas em ordem e funcionando, mas que não são conhecidos pelo público geral, as clientes da classe.
Na verdade, esses métodos administrativos  nem são de interesse desse público.

Para as clientes de uma classe os métodos que importam são aqueles que  fazem parte da chamada **interface de programação do aplicativo**
(`Application Programming Interface <https://en.wikipedia.org/wiki/API>`_, API) da classe.

O arquivo ``main.py`` tem uma função ``main()`` no final que é uma *unidade de teste* para sua classe.

.. raw:: html
         
    <iframe src="https://trinket.io/embed/python3/a044004386?showInstructions=true" width="100%" height="560" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>


Testes
------

Para testar a sua implementação você pode utilizar a função ``main()`` a seguir.

.. code:: python
                
    def main():
        ''' 
        Unidade de teste para a classe Dicio
        '''
        print("Testes para a classe Dicio")
        print("--------------------------\n")
        
        # __init__() e __str__()
        print("crie um dicionário vazio")
        d = Dicio()
        print(f"d:\n{d}") 
        pause() # aprecie a paisagem
        
        # put()
        print("\nteste put()")
        d.put('fracassei', 3)
        d.put('em', 1)
        d.put('tudo', 1)
        print(f"d:\n{d}") 
        pause() # aprecie a paisagem
        
        # __setitem__()
        print("\nteste __setitem__()")
        d['o'] = 2
        d['que'] = 3
        d['tentei'] = 4
        print(f"d:\n{d}") 
        pause() # aprecie a paisagem

        # put() e __setitem__()
        print("\nteste put() e __setitem__()")
        d.put('o', 2)
        d['que'] = 1
        d['tentei'] = 5    
        print(f"d:\n{d}") 
        pause() # aprecie a paisagem

        # get()
        print("\nteste get()")
        print(f"d.get('fracassei')={d.get('fracassei')}")
        print(f"d.get('em')={d.get('em')}")
        print(f"d.get('tudo')={d.get('tudo')}\n")
        pause() # aprecie a paisagem

        # __getitem__()
        print("\nteste __getitem__()")
        print(f"d['o']={d['o']}")
        print(f"d['que']={d['que']}")
        print(f"d['tentei']={d['tentei']}")
        print(f"d.get('vida')={d.get('vida')}")
        print(f"d['vida']={d['vida']}\n")
        pause() # aprecie a paisagem

        # mais __setitem__()
        print("\nmais teste __setitem__()")
        d[1] = 'na'
        d[2] = 'vida'
        print(f"d:\n{d}") 
        pause() # aprecie a paisagem

        # teste __contains__()
        print("\nteste __contains__()")
        print(f"'tentei' in d={'tentei' in d}")
        print(f"'1' in d={'1' in d}")
        print(f"1 in d={1 in d}")
        print(f"5 in d={5 in d}\n")
        pause() # aprecie a paisagem
        
        # teste __iter__()
        print("\nteste __iter__()")
        for chave in d: print(f"{chave}: {d[chave]}")
        pause() # aprecie a paisagem

        # teste __len__()
        print("\nteste __len__()")
        print(f"len(d)={len(d)}")
        dicio_vazio = Dicio()
        print(f"len(dicio_vazio)={len(dicio_vazio)}\n")
        pause() # aprecie a paisagem

        # teste keys(), values() e items()
        print("\nteste keys(), values() e items()")
        print(f"d.keys()={d.keys()}")
        print(f"d.values()={d.values()}")
        print(f"d.items()={d.items()}\n")
        pause() # aprecie a paisagem

        print("FIM")
        

A saída esperada produzida pela função ``main()`` está logo a seguir

::
   
    Testes para a classe Dicio
    --------------------------

    crie um dicionário vazio
    d:

    Tecle ENTER para continuar: 

    teste put()
    d:
    fracassei: 3
    em: 1
    tudo: 1

    Tecle ENTER para continuar: 

    teste __setitem__()
    d:
    fracassei: 3
    em: 1
    tudo: 1
    o: 2
    que: 3
    tentei: 4

    Tecle ENTER para continuar: 

    teste put() e __setitem__()
    d:
    fracassei: 3
    em: 1
    tudo: 1
    o: 2
    que: 1
    tentei: 5

    Tecle ENTER para continuar: 

    teste get()
    d.get('fracassei')=3
    d.get('em')=1
    d.get('tudo')=1

    Tecle ENTER para continuar: 

    teste __getitem__()
    d['o']=2
    d['que']=1
    d['tentei']=5
    d.get('vida')=None
    d['vida']=None

    Tecle ENTER para continuar: 

    mais teste __setitem__()
    d:
    fracassei: 3
    em: 1
    tudo: 1
    o: 2
    que: 1
    tentei: 5
    1: na
    2: vida

    Tecle ENTER para continuar: 

    teste __contains__()
    'tentei' in d=True
    '1' in d=False
    1 in d=True
    5 in d=False

    Tecle ENTER para continuar: 

    teste __iter__()
    fracassei: 3
    em: 1
    tudo: 1
    o: 2
    que: 1
    tentei: 5
    1: na
    2: vida
    Tecle ENTER para continuar: 

    teste __len__()
    len(d)=8
    len(dicio_vazio)=0

    Tecle ENTER para continuar: 

    teste keys(), values() e items()
    d.keys()=['fracassei', 'em', 'tudo', 'o', 'que', 'tentei', 1, 2]
    d.values()=[3, 1, 1, 2, 1, 5, 'na', 'vida']
    d.items()=[('fracassei', 3), ('em', 1), ('tudo', 1), ('o', 2), ('que', 1), ('tentei', 5), (1, 'na'), (2, 'vida')]

    Tecle ENTER para continuar: 
    FIM
        


Arquivos
--------

Para testar essa implementação e medir sua eficiência é desejável que criemos dicionários automaticamente a partir de arquivos.
A função que nos ajudará nessa tarefa é a ``pegue_palavras()``:

.. code:: python
		
    def pegue_palavras(nome_arq):
        '''(str) -> list
        RECEBE uma string nome_arq que é o nome de um arquivo.
        RETORNA uma lista com as strings que correspondem às palavras que estão no arquivo.
        PRÉ-CONDIÇÃO: as palavras no arquivo devem estar separadas por ' ' ou '\n'.
        '''
        try:
            # abra o arquivo
            arq_entrada = open(nome_arq, 'r', encoding='utf-8') 
        except:
            print(f"ERRO: arquivo '{nome_arq}' não encontrado.")
            return None

        print("lendo as palavras do arquivo")
        # LEIA o texto no arquivo
        texto = arq_entrada.read()

        # FECHE o arquivo
        arq_entrada.close()

        # FIM da leitura
        print("leitura encerrada")
        
        # CRIE lista de palavras
        print("criando listas de palavras...")
        lst_pals = texto.split()
        print("lista de palavras criada")

        return lst_pals

        
Alguns arquivos foram preparados sob medida para que ``pegue_palavras()`` retorne a lista de palavras contidas neles.
Esses arquivos têm a extensão ``.pal`` e podem ser baixados `daqui <https://www.ime.usp.br/~coelho/mac0122-2022/dicionarios/pal/>`_.
São eles

.. math::

    \begin{array}{lcccl}
    \text{ arquivo } &  \text{tamanho} & \text{palavras} & \text{diferentes} & \text{comentário}\\ \hline 
    \text{darci.pal} &      348B       &     54          &      42           & \text{Darci Ribeiro}\\
    \text{pessoa.pal} &     401B       &     61          &      37           & \text{Fernando Pessoa}\\
    \text{jeff.pal} &       1.4K       &    228          &     135           & \text{Independência dos Estados Unidos}\\
    \text{world192.pal} &   1.9M       &   286335        &   19782           & \text{The world factbook 1992}\\    
    \text{hugo.pal} &       3.1M       &   576733        &   22876           & \text{Os Miseráveis, Victor Hugo}
    \end{array}