 ! Copyright (C) 2008 Eric Mertens.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: accessors arrays hints kernel locals math hashtables
-assocs fry sequences ;
+USING: accessors assocs fry hashtables kernel locals math
+sequences ;
 FROM: assocs => change-at ;
 IN: disjoint-sets
 

: link-sets ( p a disjoint-set -- )
    [ set-parent ] [ add-count ] 3bi ; inline

: rank ( a disjoint-set -- r )
    ranks>> at ; inline

: inc-rank ( a disjoint-set -- )
    ranks>> [ 1 + ] change-at ; inline

: representative? ( a disjoint-set -- ? )
    dupd parent = ; inline

PRIVATE>

GENERIC: representative ( a disjoint-set -- p )

M: disjoint-set representative
    2dup representative? [ drop ] [
        [ [ parent ] keep representative dup ] 2keep set-parent
    ] if ;

<PRIVATE

: representatives ( a b disjoint-set -- r r )
    [ representative ] curry bi@ ; inline

: ranks ( a b disjoint-set -- r r )
    [ rank ] curry bi@ ; inline

:: branch ( a b neg zero pos -- )
    a b = zero [ a b < neg pos if ] if ; inline


GENERIC: equiv-set-size ( a disjoint-set -- n )

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

GENERIC: equiv? ( a b disjoint-set -- ? )

