Diário do Farol

Hash-sets são coleções mutáveis e sem ordem que guardam cada valor no máximo uma vez. Busca, inserção e remoção são todas O(1) em média. Elas ficam em hash-sets e implementam o protocolo sets.

Literais de hash-set

HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }

HS{ } é o literal vazio. Como outros literais de Factor, ele é um objeto compartilhado: toda referência a HS{ } no código-fonte aponta para o mesmo conjunto. HS{ } clone dá a você uma cópia nova e independente a cada chamada.

A partir de uma sequência

>hash-set ( seq -- set )    ! build a fresh set from a sequence

Quando você já tem os valores em uma sequência, >hash-set os converte de uma vez só, descartando as duplicatas.

USING: hash-sets prettyprint ;

{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }

Adicionar e remover

adjoin     ( elt set -- )    ! insert in place; no-op if already present
adjoin-all ( seq set -- )    ! insert every element of seq in place
delete     ( elt set -- )    ! remove in place; no-op if absent

As três modificam o conjunto; nenhuma retorna nada na pilha.

USING: hash-sets kernel sets ;

HS{ } clone
"NS-1024" over adjoin
"WB-203"  over adjoin
"NS-1024" over adjoin    ! duplicate — no effect
.                        ! => HS{ "NS-1024" "WB-203" }

adjoin-all é a forma em massa: ela adiciona cada elemento de uma sequência, pulando as duplicatas assim como adjoin faz um de cada vez.

USING: hash-sets kernel sets ;

HS{ "NS-1024" } clone
{ "WB-203" "NS-1024" "QR-7" } over adjoin-all
.                        ! => HS{ "QR-7" "NS-1024" "WB-203" }  (order not guaranteed)

Consultando o conjunto

in?         ( elt set -- ? )   ! is elt in the set?
null?       ( set -- ? )       ! is the set empty?
cardinality ( set -- n )       ! number of elements
members     ( set -- seq )     ! enumerate as a sequence

in? é o teste de pertencimento do protocolo de conjuntos. Ele é diferente de member? (de sequences), que faz uma busca linear em uma sequência. Para um hash-set, in? é uma busca em hash, O(1) em média, que é justamente o motivo de usar um hash-set.

null? informa se o conjunto não tem elementos: é a forma direta de perguntar "isto está vazio?" em vez de comparar cardinality com zero.

: my-log ( -- set ) HS{ "NS-1024" "WB-203" } ;

"NS-1024" my-log in? .   ! => t
"X-99"    my-log in? .   ! => f
my-log null? .           ! => f
HS{ } clone null? .      ! => t
my-log cardinality .     ! => 2

Combinando conjuntos

union     ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff      ( set1 set2 -- set )
set-like  ( set exemplar -- set' )

union é "todos os elementos de qualquer um dos dois"; intersect é "os elementos que estão em ambos"; diff é "os que estão em set1 mas não em set2". Cada uma retorna um novo conjunto sem modificar os conjuntos de entrada.

set-like converte set para o tipo de exemplar. As implementações padrão de union/intersect/diff usam isso para fazer o resultado corresponder ao tipo do receptor: <my-set> <hash-set> union retorna um my-set, não um hash-set.

Por que isso importa

Hash-sets combinam naturalmente com hashtables para percorrer grafos: uma hashtable mapeia cada nó para seus vizinhos, e um hash-set registra quais nós já foram visitados, para que a busca não entre em loop nem repita trabalho. A travessia é então uma fila mais as duas estruturas, modificadas no lugar conforme você avança para fora.