disjoint-set
Factor handbook » The language » Collections » Disjoint sets

Next:

<disjoint-set> ( -- disjoint-set )

Vocabulary
disjoint-sets

Definition

USING: hashtables ;

IN: disjoint-sets

TUPLE: disjoint-set
    { parents hashtable read-only initial: H{ } }
    { ranks hashtable read-only initial: H{ } }
    { counts hashtable read-only initial: H{ } } ;

Methods

USING: accessors assocs disjoint-sets kernel ;

M: disjoint-set add-atom
    [ dupd parents>> set-at ] [ [ 0 ] 2dip ranks>> set-at ]
    [ [ 1 ] 2dip counts>> set-at ] 2tri ;


USING: accessors disjoint-sets kernel ;

M: disjoint-set clone
    [ parents>> ] [ ranks>> ] [ counts>> ] tri [ clone ] tri@
    disjoint-set boa ;


USING: accessors assocs disjoint-sets ;

M: disjoint-set disjoint-set-member? parents>> key? ;


USING: accessors assocs disjoint-sets ;

M: disjoint-set disjoint-set-members parents>> keys ;


USING: disjoint-sets disjoint-sets.private kernel ;

M:: disjoint-set equate ( a b disjoint-set -- )
    a b disjoint-set representatives 2dup =
    [ 2drop ] [
        2dup disjoint-set ranks
        [ swap ] [ over disjoint-set inc-rank ] [ ] branch
        disjoint-set link-sets
    ] if ;


USING: accessors assocs disjoint-sets kernel ;

M: disjoint-set equiv-set-size
    [ representative ] keep counts>> at ;


USING: disjoint-sets disjoint-sets.private kernel ;

M: disjoint-set equiv? representatives = ;


USING: accessors assocs disjoint-sets disjoint-sets.private
kernel ;

M:: disjoint-set representative ( a disjoint-set -- p )
    a disjoint-set parents>> at :> p a p =
    [ a ] [
        p disjoint-set representative
        [ a disjoint-set set-parent ] keep
    ] if ;