LP 19/10/2011

   # # # # # # # # # # # # # #
  # Linguagens de Programação #
  # Prof. Fernando Pereira    #
  # notasdogarcia.blog.com    #
   # # # # # # # # # # # # # #

		// Vamos falar hoje sobre TADs

  Como definir um tipo?

  É uma descrição de um objeto feito através de seus atributos.

  Porém um tipo "pessoa" é complexo demais para se listar uma a uma cada possível caracteristica.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  Assim um TAD é uma tipo simplificado, voltado para um conjunto de características juntamente com um conjunto de capacidades.

Como definir um conjunto em c?

seja um .h:

#ifndef SET H
#define SET H

#define INTBITS 32

typedef struct
{
  unsigned* vector;
  unsigned size;
} set;

void new(set*, unsigned);
void add(set*, unsigned);
void del(set*, unsigned);
int contains(set*, unsigned);

#endif

Agora seja o .c:

#include <stdlib.h>
#include "set.h"

void new(set* s, unsigned capacity)
{
  s->vector = calloc(1+capacity/INT_BITS, sizeof(unsigned));
  s->size = capacity;
}

void add(set* s, unsigned e)
{
  unsined index = e/INT_BITS;
  unsined offset = e%INT_BITS;
  unsined bit = 1 << offset;
  s -> vector [index] |= bit;
}

int contains(set* s, unsigned e)
{
  unsined index = e/INT_BITS;
  unsined offset = e%INT_BITS;
  unsined bit = 1 << offset;
  return s->vector[index] & bit;
}

// Assim terminamos nosso TAD de unsined integers.

(um mapa de bits que é o que estamos fazendo acima é um arranjo de bits, onde 0 indica que o elemento de seu indice não está presente)

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Em C não há meios de se esconder detalhes de implementação do usuário.
Ex: eu posso chamar set s; s.size para saber o tamanho, ou acessar o vector diretamente também.

    Qual o problema disso e porque pode ser vantajoso esconder esses detalhes do usuário e permitir apenas o uso das funções declaradas para interface?

    Supondo que eu queria mudar a implementação, se eu não tiver certeza de que nenhum dos meus usuários precisa dos detalhes de implementação antigas,
    eu não poderei apagar esses detalhes, e troca-los por sistemas mais eficientes, em outras palavras, eu fico acorrentado a detalhes pouco importantes.

    Assim um TAD é um pouco pior que classes e interfaces pois ele não é capaz de esconder estes detalhes.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Existe um modo de se mudar a interface ( o .h ) adicionando mais detalhes a interface sem alterar a interface original?
  Existem linguagens que permitem extender a interface com outra, em java isso é o extend por exemplo.

  SML Também.
  ex:

signature SET =
sig
  type set
  val new : set
  val add : set -> int -> set
  val contains : set -> int -> bool
  val del : set -> int -> set
end ;

// note que o :> é o implements do SML.
structure FunSet :> SET =
struct
  type set = int -> bool
  val new = fn x => false
  fun add f i = fn x => if x = i then true else f x
  fun contains f i = f i
  fun del f i = fn x => if x = i then false else f x
end ;

// Essa implementação apesar de muito elegante é muito ineficiente né, temos de concordar.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

// nao sei bem pra q isso abaixo se eu for usar eu fico feliz da silva =]
structure S = FunSet ;

val s = S.new ;

val s = S.add

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

bitSet.py:

INT_BITS = 32

def getIndex (element) :
  index = element / INT_BITS
  offset = element % INT_BITS
  bit = << offset
  return (index, bit)

// Espaço de nomes é um sobrenome para os nomes definidos por exemplo em uma determinada classe, assim para referencialos uso o "nome da classe.nome do objeto"

class Set:
  def  init  (self, capacity):
    self.vector = range (1+capacity/INT_BITS)
    for i in range(len(self.vector)):
      self.vector[i] = 0

  def add (self, e):
    (index, bit) = getIndex(e)
    self.vector[index] |= bit

  def delete (self, e):
    (index, bit) = getIndex(e)
    self.vector[index] &= ~bit

  def contains (self, e):
    (index, bit) = getIndex(e)
    return self.vector[index] & bit

// Acabamos de criar uma tabela inteligente, formada por um conjunto de funções que opera sobre o próprio tipo Set
// E ela consegue enchergar o próprio escopo.

pode-se fazer quas qualquer coisa com essa tabela.

s = Set(60)
s.add(4)
print "Contem 4?", s.contains(4)
print "Contem 5?", s.contains(5)
s.delete(4)
print "Contem 4?", s.contains(4)

// Em pyton:
// s.vector[0] é o mesmo que: s["vector"][0]

pode-se acessar membros internos de um objeto, assim como em c. na forma que demonstrei acima.

s.vector[0]=2, é uma operação válida.


outro arquivo:

from Set import INT_BITS, getIndex, Set

def errorAdd(self, e):
  if(e > self.capacity):
    raise IndexError("Arghhhh")
  else:
    (index, bit) = getIndex(element)
    self.vector[index] |= bit
    print "Sucesso!"

Set.add = errorAdd
// note que isso é mudar a implementação de uma das funções de Set!
s = Set(33)
s.add(32)
s.add(33)
(repare que error Add recebe dois parâmetros, no caso um deles seria o próprio s)

def fill(set, b, e, s):
  for i in range(b, e, s):
    set.add(i)

// com a funçào acima pode-se fazer:
fill(s, 1, 10, 3)

class Num:
  def   init  (self, num):
    self.n = num
  def add(self, num):
    self.n += num
  def str (self):
    return str(self.n)

é possivel fazer isso:
n = Num(4)
n.add(5)
fill(n, 1, 10, 3)

Sim, assim estarei somando a n os elementos de 1 a 9 pulando de 3 em 3.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

java:
// Note que esse E é um template, chamado de gerics em java
public interface Set<E>
{
  void add(E element);
  void del (E element);
  boolean contain (E element);
}

// ele mostrou que aqui diferente de python temos como colocar variaveis privadas, e protegidas.
// em java essas tabelas são estaticas e portanto nào mutaveis como em python

public class BoudedBitSet...

em qualquer situação em que se deseja uma classe, pode-se passar um filho dessa classe. Esse é um principio de num sei quem.

para se modificar uma função de uma classe, voce pode re-escrever a classe, fazendo-a herdar todas as classes de Set, e re-implementando as funções que forem do seu
interesse.

é analogo ao que foi feito em python com uma atribuição de função, dentro da tabela da "classe" (acho q em python isso nao chama classe)

Assim se eu busco na nova classe por um errorset que é filho de set, por uma função que não está lá minha busca é delegada para set, pois provavelmente é lá
que encontrarei a função.

// a aula acabou aqui.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *