# Algoritmos e Estruturas de dados 2

## Professor Coelho

<hr>



### Informações Básicas : 

* Bibliografia :
  * https://algs4.cs.princeton.edu
  * Sedgewick
* Linguagem principal : Java, C também ( "mas foda-se a linguagem", COELHO, THE)
* Monitores
* **3 provas e várias provinhas de 10 minutos (toda terça)** 
* A nota das provinhas entra como psub
* **Instalar o ambiente de programação algs4**

<hr>



* # Aula 01

  * Interface : É uma fronteira entre a implementação de uma biblioteca e o programa que usa a biblioteca. Ou seja, ele define estruturas de dados, nomes de função, constantes... é basicamente uma API. O cliente não precisa saber como as coisas são implementadas, por isso a interface faz essa certa separação
  * Cliente : É o programa que chama alguma função de uma biblioteca
  * Implementação : Explicita como as funções definidas na interface são feitas de fato.



* Bag (saco) : Estrutura de dados que tem as seguintes operações : 

  * add() : coloco um item

  * iterar :  procurar todos os itens

    O saco pode ser usado para implementação de grafos.



     

* Podemos definir a API de um saco de inteiros : (fazer em casa, é de boa, até porque o coelho não fez em aula e eu fiquei com preguiça rs mas é uma interface, tipo um .h)

* Podemos definir a implementação da API : 

  ```java
  
  import java.util.Iterator; // puxa as ferramentas do java pra fazer um iterador, primeiro passo
  
  public class Bag<Item> implements Iterable<Item> { // garante que vou implementar algo iterável
      private Node first; // instanciando um objeto da classe node, não tem problema estanciar antes de definir a classe Node
      private int n;
      private Node current;
      private class Node { // subclasse
          /*public Node (Integer item, Node next) {
              this.item = item;
              this.next = next;
          }
          Eu poderia ter feito assim tambem, mas dai eu teria que sempre escrever um "new" antes de criar um novo nó, exemplo : 
          	private current = new Node();
          */
          private Item item;
          private Node next;
      }
      public Bag<Item>() { // metodo construtor
          first = null;
          n = 0;
      }
      
      public void add(Integer item) {
          Node oldfirst = first;
          first = new Node();
          first.item = item;
          first.next = oldfirst;
          n++;
      }
      
      public int size() {
          return n;
      }
      
      public boolean isEmpty() { // boolean retorn true ou false
          return n == 0;
      }
      
      public Iterator<Item> iterator() {
          return new BagIterator();
      }
      
      private Class BagIterator 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;
          }
          
          public void remove() {
              throw new UnsupportedOperationException();
          }
          
      }
      
      
      /*  
      			 	Métodos sem usar o iterator : 
      public void startIterator() {
          current = first;
      }
      
      public boolean hasNext() {
          return current != null; // aqui não é interessante colocar um current.next == null porque dá problema caso eu tente acessar o proximo de uma lista vazia
      }
      
      public Item next() {
          Item item = current.item;
          current = current.next;
          return item;
      }
      */
  }
  ```

  	Como fazer uma classe iteravel : 

    - importo o java.util.iterator
    - Garanto que minha classe implementa um iteravel (implements iterable<Item>)
    - Implemente um método iterável



* Podemos definir um cliente do saco de inteiros > 

  ```java
  import edu.princeton.cs.algs4.StdOut;
  public class cliente { 
      public static void main(string[] args) { 
          Bag<Integer> bag = new bag<Integer>(); 
          for (int i = 10; i < 20; i++) {
              bag.add(i);
          }
          
          StdOut.println(bag.size());
          Iterator<Integer>it = bag.iterator();
          
  
          
          for(Integer valor:bag) { // basicamente eu pego um valor dentro de bag.valor e vou iterando
              StdOut.println(valor);
          }
          /* 		Versão sem o iterador utilizado totalmente
          while(it.hasNext()) {
  			Integer valor = it.next();
              StdOut.println(valor)
          }
          
          */
          
          
          /*
          	Versão sem usar iterator
          bag.startIterator(4);
          while(bag.hasNext()) {
              Integer valor = bag.next();
              stdOut.println(valor);
          }*/
      }
  }
  
  /* GLOSSARIO DO JAVA : 
  
  	Estilo : Usamos camelCase em geral, nomes de função começam em letra minúscula e Nomes de objeto começam em maiúsculo (checar isso)
  	linha1 e linha2, public : Denota que aquilo que está designado por "public" faz parte da API
  	
  	linha1, Cliente : aqui, o "cliente" denota em qual arquivo esse trecho tem que estar (no cliente.java).
  	
  	linha2, public static : O public static mostra que é função.
  	
  	linha2, string[]args : ssim que eu defino o main, como se fosse no C. ele toma como argumento um vetor de strings
  	
  	linha3, new bagInteger() : o bagInteger é a classe, o new instancia um novo objeto chamando o método construtor(que nem no js, python...)
  	
  	linha10, integer : é a mesma coisa que fazer um int*, ele se refere a o endereço, chamamos esse tipo de dado de variavel de referencia (como se fosse um ponteiro) : as variaveis de referencia são referenciadas pelo tipo de dado mas com a primeira letra maiúscula (Integer, Boolean, Float...).
  
  */
  ```





* A api permite apenas um iterador, mas queremos vários.