collision-node

Vocabulary

persistent.hashtables.nodes

Definition

USING: arrays math ;

IN: persistent.hashtables.nodes

TUPLE: collision-node
    { hashcode fixnum read-only initial: 0 }
    { leaves array read-only initial: { } } ;

Methods

USING: kernel persistent.hashtables.nodes
persistent.hashtables.nodes.collision ;

M:: collision-node (entry-at)
    ( key hashcode collision-node -- entry )
    key hashcode collision-node find-index nip ;


USING: accessors kernel persistent.hashtables.nodes
persistent.hashtables.nodes.collision persistent.sequences
sequences ;

M:: collision-node (new-at)
    ( shift value key hashcode collision-node -- node' added-leaf )
    hashcode collision-node hashcode>> eq? [
        key hashcode collision-node find-index
        :> ( idx leaf-node ) idx [
            value leaf-node value>> =
            [ collision-node f ] [
                hashcode value key hashcode <leaf-node>
                idx collision-node leaves>> new-nth
                <collision-node> f
            ] if
        ] [
            value key hashcode <leaf-node>
            :> new-leaf-node hashcode collision-node leaves>>
            new-leaf-node suffix <collision-node> new-leaf-node
        ] if
    ]
    [ shift collision-node value key hashcode make-bitmap-node ]
    if ;


USING: accessors kernel persistent.hashtables.nodes
persistent.hashtables.nodes.collision ;

M:: collision-node (pluck-at)
    ( key hashcode collision-node -- node' )
    hashcode collision-node hashcode>> eq? [
        key hashcode collision-node find-index drop :> idx idx [
            idx collision-node leaves>> smash
            [ collision-node hashcode>> <collision-node> ] when
        ] [ collision-node ] if
    ] [ collision-node ] if ;


USING: accessors persistent.hashtables.nodes ;

M: collision-node >alist% leaves>> >alist-each% ;