Les hash-sets sont des collections mutables et non ordonnées qui stockent chaque valeur au plus une fois. La recherche, l'insertion et la suppression sont toutes en O(1) en moyenne. Ils sont définis dans [hash-sets] et implémentent le protocole sets.
Littéraux de hash-set
HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }
HS{ } est le littéral vide. Comme les autres littéraux Factor, c'est un objet partagé : toutes les références à HS{ } dans le code source pointent vers le même ensemble. HS{ } clone te donne une nouvelle copie indépendante à chaque appel.
À partir d'une séquence
>hash-set ( seq -- set ) ! build a fresh set from a sequence
Quand tu as déjà les valeurs dans une séquence, >hash-set les convertit en une seule étape, en supprimant les doublons.
USING: hash-sets prettyprint ;
{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }
Ajoute et supprime
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
Ces trois mots modifient l'ensemble en place ; aucun ne renvoie quoi que ce soit sur la pile.
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 est la forme groupée : il ajoute chaque élément d'une séquence, en ignorant les doublons exactement comme adjoin le fait un par un.
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)
Interroge l'ensemble
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? est le test d'appartenance du protocole des ensembles. Il est distinct de member? (de sequences), qui effectue un parcours linéaire d'une séquence. Pour un hash-set, in? est une recherche dans une table de hachage : O(1) en moyenne, tout l'intérêt d'utiliser un hash-set.
null? indique si l'ensemble ne contient aucun élément : c'est la façon directe de demander « est-ce vide ? » plutôt que de comparer cardinality à zéro.
: 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
Combine des ensembles
union ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff ( set1 set2 -- set )
set-like ( set exemplar -- set' )
union correspond à « tous les éléments de l'un ou de l'autre » ; intersect à « les éléments présents dans les deux » ; diff à « les éléments de set1 qui ne sont pas dans set2 ». Chacune renvoie un nouvel ensemble sans modifier ses entrées.
set-like convertit set vers le type de exemplar. Les implémentations par défaut de union/intersect/diff l'utilisent pour que le résultat ait le type du récepteur : <my-set> <hash-set> union renvoie un my-set, et non un hash-set.
Pourquoi c'est important
Les hash-sets vont naturellement de pair avec les tables de hachage pour le parcours de graphe : une table de hachage associe chaque nœud à ses voisins, et un hash-set garde la trace des nœuds déjà visités pour que la recherche ne boucle pas et ne répète pas de travail. Le parcours est alors une file plus ces deux structures, modifiées en place au fur et à mesure que l'on progresse vers l'extérieur.
Exercice d'apprentissage
