Elementos de Programação
Amílcar Sernadas, Cristina Sernadas e Jaime Ramos

Tipos de dados abstractos: especificação

Desenvolva o diagrama ADJ e especifique os seguintes tipos de dados.

Tipo de dados: nats (números naturais)
zero: representa a constante 0.
suc[n]: devolve o sucessor de n.
plus[m,n]: devolve a soma de m com n.
sub[m,n]: devolve a subtracção natural de m com n (vale m-n se m>n e 0 caso contrário).
mult[m,n]: devolve o produto de m com n.
exp[m,n]: devolve m elevado ao expoente n.
zeroQ[n]: devolve True se n=0 e False caso contrário.
lt[m,n]: devolve True se m<n e False caso contrário.
le[m,n]: devolve True se m≤n e False caso contrário.
gt[m,n]: devolve True se m>n e False caso contrário.
ge[m,n]: devolve True se m≥n e False caso contrário.

Tipo de dados: ints (números inteiros)
zero: representa a constante 0.
suc[z]: devolve o sucessor de z.
pred[z]: devolve o predecessor de z.
plus[z1,z2]: devolve a soma de z1 com z2.
sub[z1,z2]: devolve a diferença entre z1 e z2.
mult[z1,z2]: devolve o produto de z1 com z2.
zeroQ[z]: devolve True se z=0 e False caso contrário.
posQ[z]: devolve True se z>0 e False caso contrário.
negQ[z]: devolve True se z<0 e False caso contrário.
lt[z1,z2]: devolve True se z1<z2 e False caso contrário.
le[z1,z2]: devolve True se z1≤z2 e False caso contrário.
gt[z1,z2]: devolve True se z1>z2 e False caso contrário.
ge[z1,z2]: devolve True se z1≥z2 e False caso contrário.

Tipo de dados: fsets (conjuntos finitos de elementos de tipo T)
emptyset: representa o conjunto vazio.
insert[t,s]: acrescenta t ao conjunto s, retornando s se t já lá estiver.
remove[t,s]: retira t ao conjunto s, retornando s se t não pertencer a s.
union[r,s]: devolve a união dos conjuntos r e s.
intersect[r,s]: devolve a intersecção dos conjuntos r e s.
diff[r,s]: devolve a diferença entre os conjuntos r e s, isto é, o conjunto dos elementos de r que não estão em s.
nelem[s]: devolve o número de elementos em s.
max[s,R]: devolve o maior elemento em s para a ordem R, caso s não seja vazio.
min[s,R]: devolve o menor elemento em s para a ordem R, caso s não seja vazio.
emptyQ[s]: devolve True se s for o conjunto vazio e False caso contrário.
memberQ[t,s]: devolve True se t for um elemento de s e False caso contrário.
subsetQ[r,s]: devolve True se r for um subconjunto de t e False caso contrário.
supersetQ[r,s]: devolve True se r for um sobreconjunto de t e False caso contrário.
map[f,s]: devolve o conjunto de todos os elementos f(x) para x em s.

Tipo de dados: bags
Um saco ou multiconjunto ("bag") é um conjunto em que os elementos podem aparecer repetidos, ou seja, é importante saber também quantas vezes é que um elemento pertence a um saco.  Este tipo de dados pretende representar multiconjuntos de elementos dum tipo genérico T.
newbag: representa o multiconjunto vazio.
insert[t,s]: acrescenta uma cópia de t ao multiconjunto s.
remove[t,s]: retira uma cópia de t ao multiconjunto s, retornando s se t não pertencer a s.
removeall[t,s]: retira todas as cópias de t ao multiconjunto s, retornando s se t não pertencer a s.
union[r,s]: devolve a união dos multiconjuntos r e s.
intersect[r,s]: devolve a intersecção dos multiconjuntos r e s.
diff[r,s]: devolve a diferença entre os multiconjuntos r e s.
nelem[s]: devolve o número de elementos em s.
ncopies[t,s]: devolve o número de cópias de t em s.
ndelem[s]: devolve o número de elementos distintos em s.
emptyQ[s]: devolve True se s for o multiconjunto vazio e False caso contrário.
memberQ[t,s]: devolve True se existir pelo menos uma cópia de t em s e False caso contrário.

Tipo de dados: trees
Uma árvore de pesquisa de registos é uma árvore binária de pesquisa em que cada nó é um registo (tuplo dum tipo não especificado T).  Um dos campos de cada registo é um natural (a chave do registo), relevante para a ordenação.  Para a especificação vamos separar cada registo em duas partes: a sua chave (um natural) e o seu conteúdo (um elemento dum tipo R).
void: representa a árvore vazia.
join[t1,t2,d,k]: devolve a árvore com registo de conteúdo d ("data") e chave k ("key").
root[t]: devolve o conteúdo do registo na raíz da árvore t.
left[t]: devolve a sub-árvore esquerda da árvore t.
right[t]: devolve a sub-árvore direita da árvore t.
voidQ[t]: devolve True se t for a árvore vazia e False caso contrário.
searchkey[t,k]: devolve True se em t existir um registo com chave k e False caso contrário.
findreg[t,k]: devolve o conteúdo do registo associado à chave k em t (não está definido se não existir nenhum registo com chave k na árvore).
addreg[t,d,k]: devolve a árvore que se obtém acrescentando a t um registo com conteúdo d e chave k.
delreg[t,k]: devolve a árvore que se obtém retirando de t um registo com chave k (não está definido se não existir nenhum registo com chave k na árvore).