Los hash-sets son colecciones mutables y desordenadas que almacenan cada valor como máximo una vez. La búsqueda, la inserción y la eliminación son todas O(1) en promedio. Viven en hash-sets e implementan el protocolo de sets.
Literales de hash-set
HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }
HS{ } es el literal vacío. Como otros literales de Factor, es un objeto compartido: cada referencia a HS{ } en el código fuente apunta al mismo conjunto. HS{ } clone te da una copia nueva e independiente en cada llamada.
Desde una secuencia
>hash-set ( seq -- set ) ! build a fresh set from a sequence
Cuando ya tienes los valores en una secuencia, >hash-set los convierte en un solo paso y descarta los duplicados.
USING: hash-sets prettyprint ;
{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }
Agregar y eliminar
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
Los tres modifican el conjunto; ninguno devuelve nada en la pila.
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 es la forma masiva: agrega cada elemento de una secuencia y omite los duplicados, igual que adjoin lo hace uno a la 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)
Consultar el 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? es la prueba de pertenencia del protocolo de conjuntos. Es distinto de member? (de sequences), que hace un recorrido lineal sobre una secuencia. Para un hash-set, in? es una búsqueda hash, O(1) en promedio, que es el punto central de usar un hash-set.
null? informa si el conjunto no tiene elementos: la forma directa de preguntar «¿está vacío?» en lugar de comparar cardinality con cero.
: 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
Combinar conjuntos
union ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff ( set1 set2 -- set )
set-like ( set exemplar -- set' )
union es «todos los elementos de cualquiera de los dos»; intersect es «elementos en ambos»; diff es «en set1 pero no en set2». Cada uno devuelve un conjunto nuevo sin modificar los conjuntos originales.
set-like convierte set al tipo de exemplar. Las implementaciones predeterminadas de union/intersect/diff lo usan para que el resultado coincida con el tipo del receptor: <my-set> <hash-set> union devuelve un my-set, no un hash-set.
Por qué esto importa
Los hash-sets se combinan de forma natural con las tablas hash para el recorrido de grafos: una tabla hash asigna cada nodo a sus vecinos, y un hash-set registra qué nodos ya se visitaron para que la búsqueda no entre en bucle ni repita trabajo. El recorrido es entonces una cola más las dos estructuras, que se modifican en el lugar a medida que avanzas hacia afuera.
Ejercicio de aprendizaje
