Sacos

Livro de Sedgewick e Wayne: sec.1.3, p.120.  Website do livro: resumo sec.1.3, slides.  Veja também a página algs4.cs.​princeton.edu/​code/, que tem o código fonte, a documentação, e dados de teste de todos os programas do livro.

Saco (= bag) e sua API

• Uma saco (= bag) é um ADT que consiste em uma coleção de coisas munida de duas operações:  add, que insere uma coisa na coleção, e iterate, que percorre as coisas da coleção (ou seja, examina as coisas uma a uma). A ordem em que o iterador percorre as coisas não é especificada e está fora do controle do cliente.
• Como de hábito, as coisas de que um saco é feito serão chamadas itens.
• Diferentemente de um conjunto matemático, os itens de um saco não precisam ser distintos dois a dois.
• API de um saco de itens:

  public class Bag<Item> implements Iterable<Item>
  	Bag()	cria um saco de Items vazio
  void	add(Item item)	coloca item neste saco
  Iterator<Item>	iterator()	um iterador que percorre os itens do saco
  boolean	isEmpty()	este saco está vazio?
  int	size()	número de Items neste saco

• O método iterator() implementa a operação iterate:  para processar, um a um, todos os itens de uma instância saco de Bag, um cliente deve dizer

     Iterator<Item> itr = saco.iterator();
     while (itr.hasNext()) {
        Item x = itr.next();
        ...      // processamento de x
     }
  

• Felizmente, o cliente pode abreviar esse bloco de código por uma instrução muito simples conhecida como foreach:

     for (Item x : saco) { 
        ...     // processamento de x
     }
  

  (Leia para cada x no saco faça ....)

Exemplo de cliente

• O seguinte cliente de saco calcula a média e o desvio padrão de números dados na entrada padrão:

  public class Stats {
  
     public static void main(String[] args) {
        Bag<Integer> bag = new Bag<Integer>();
        while (!StdIn.isEmpty())
           bag.add(StdIn.readInt());
  
        int N = bag.size();
        double soma = 0.0;
        for (int x : bag)
           soma += x;
        double media = soma/N;
        soma = 0.0;
        for (int x : bag)
           soma += (x - media)*(x - media);
        double desvpad = Math.sqrt(soma/(N-1));
        StdOut.printf("Media: %.2f\n", media);
        StdOut.printf("Desv padrao: %.2f\n", desvpad);
     }
  }
  

• O saco bag armazena os dados, permitindo que eles sejam examinados mais de uma vez.  Sem isso, o problema seria mais difícil de resolver.
• Teste:

  % javac Stats.java
  
  % java Stats < randAints10K.txt
  Media 26.80
  Desv padrao: 8.16
  
  % java Stats < randBints10K.txt
  Media 26.65
  Desv padrao: 6.24
  

• (Se estiver curioso, veja os histogramas dos arquivos randAints10K.txt e randBints10K.txt produzidos pelo programa MeuHistograma.java.)

Saco implementado em lista ligada

• Classe Bag: saco implementado com lista ligada:

  import java.util.Iterator;
  
  public class Bag<Item> implements Iterable<Item> {
  
     private Node first;
  
     private class Node {
        private Item item;
        private Node next;
     }
  
     public Bag() {  // construtor
        first = null;
     }
  
     public void add(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
     }
  
     public Iterator<Item> iterator() {
        return new ListIterator();
     }
  
     private class ListIterator implements Iterator<Item> {
  
        private Node current = first;
  
        public boolean hasNext() {
           return current != null;
        }
  
        public Item next() {
           Item item = current.item;
           current = current.next;
           return item;
        }
     }
  }
  

• A linha import java.util.Iterator no início do código é necessária para que o código tenha acesso à interface Iterable de Java. Também é necessário dizer implements Iterable<Item>  ao declarar a classe Bag.
• O construtor Bag() é redundante nesse caso porque first é automaticamente inicializado com null ao ser declarado.
• Deveríamos ter acrescentado um método main() à classe Bag para servir de cliente de teste, como fizemos na classe QueueL.
• O website do livro tem implementações mais completas: veja a classe LinkedBag e a correspondente API.  A classe Bag é uma implementação mais profissional; veja também a API correspondente.

Exercícios

1. Acrescente um método main() à classe Bag para servir de cliente de teste.
2. Escreva uma implementação de saco em um vetor com redimensionamento.  Depois de escrever seu código, confira com código de ResizingArrayBag no website livro. Veja também a correspondentes APIs.
3. Escreva uma implementação do iterador nas classes StackRA e StackL.
4. Escreva uma implementação do iterador nas classes QueueRA e QueueL.