"{ Package: 'stx:libbasic2' }"

SequenceableCollection subclass:#Trie

	instanceVariableNames:'value children'

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Ordered'

!

Smalltalk::Dictionary subclass:#Dictionary

	instanceVariableNames:''

	classVariableNames:''

	poolDictionaries:''

	privateIn:Trie

!

Object subclass:#SmallDictionaryWith1Element

	instanceVariableNames:'k1 v1'

	classVariableNames:''

	poolDictionaries:''

	privateIn:Trie

!

Object subclass:#SmallDictionaryWith2Elements

	instanceVariableNames:'k1 k2 v1 v2'

	classVariableNames:''

	poolDictionaries:''

	privateIn:Trie

!

Object subclass:#SmallDictionaryWith3Elements

	instanceVariableNames:'k1 k2 k3 v1 v2 v3'

	classVariableNames:''

	poolDictionaries:''

	privateIn:Trie

!

!Trie class methodsFor:'documentation'!

documentation

"

    A trie is a collection which maps string keys to values (see also SuffixTree and RadixTree).

    It keeps its elements as a tree, where each node's children are indexed by a fragment of the element's key.

    The fragment is a single character in this implementation.

    Thus, insertion and access times are linear to size of the key (the number of characters in the key), 

    not the number of elements in the collection.

    Due to the extra memory required to represent the tree, a Dictionary is usually much faster.

    However, a trie allows for prefix matches and sorted enumerations, which are hard with dictionaries.

    See AATree examples for speed comparison.

    [author:]

        Claus Gittinger

"

!

example

"

                                            [exBegin]

    |t|

    t := Trie new.

    t at:'12345' put:'hallo'.

    t at:'54923' put:'Welt'.

    t at:'1256' put:'bla'.

    t at:'12' put:'zwölf'.

    t at:'123' put:'einszweidrei'.

    t at:'1234' put:'einszweidreivier'.

    t at:'54923'.

    t includesKey:'54923'.  

    t includesKey:'5492'.     

    t size.      

    t.

                                            [exEnd]

                                            [exBegin]

    build a trie of all selectors in the system:

    |t0 t c|

    t0 := Time millisecondsToRun:[

        c := Trie new.

        Smalltalk allClassesDo:[:cls |

            cls instAndClassSelectorsAndMethodsDo:[:sel :mthd |

            ].

        ].

    ].   

    Transcript show:'tOverhead: '; showCR:t0.

    t := Time millisecondsToRun:[

        c := Trie new.

        Smalltalk allClassesDo:[:cls |

            cls instAndClassSelectorsAndMethodsDo:[:sel :mthd |

                (c at:sel ifAbsentPut:[Set new]) add:mthd

            ].

        ].

    ].   

    Transcript show:'tTrie: '; showCR:t.

    t := Time millisecondsToRun:[

        c := Dictionary new.

        Smalltalk allClassesDo:[:cls |

            cls instAndClassSelectorsAndMethodsDo:[:sel :mthd |

                (c at:sel ifAbsentPut:[Set new]) add:mthd

            ].

        ].

    ].

    Transcript show:'tDict: '; showCR:t.

                                            [exEnd]

"

! !

!Trie class methodsFor:'instance creation'!

new

    "return an initialized instance"

    ^ self basicNew initialize.

! !

!Trie methodsFor:'accessing'!

add:aValue 

    ^ self at:aValue put:aValue

    "Created: / 04-08-2012 / 11:31:30 / cg"

!

at:key 

    ^ self at:key ifAbsent:[self error]

    "Created: / 04-08-2012 / 10:44:02 / cg"

!

at:key ifAbsent:exceptionValue 

    ^ self at:key keyIndex:1 ifAbsent:exceptionValue

    "Created: / 04-08-2012 / 10:10:23 / cg"

!

at:key ifAbsentPut:newValue 

    ^ self at:key keyIndex:1 ifAbsentPut:newValue

    "Created: / 04-08-2012 / 17:51:49 / cg"

!

at:key put:anElement

    self at:key keyIndex:1 put:anElement

    "Created: / 04-08-2012 / 10:09:39 / cg"

!

remove:aValue 

    ^ self at:aValue put:nil

    "Created: / 04-08-2012 / 11:32:16 / cg"

! !

!Trie methodsFor:'enumeration'!

do:aBlock

    value notNil ifTrue:[ aBlock value: value ].

    children notNil ifTrue:[

        children do:[:eachNode | eachNode do:aBlock ].

    ].

    "Created: / 04-08-2012 / 11:24:49 / cg"

! !

!Trie methodsFor:'private'!

at:key keyIndex:idx ifAbsent:exceptionalValue

    |childIndex|

    idx > key size ifTrue:[

        "/ at leaf

        value notNil ifTrue:[ ^ value ].

        ^ exceptionalValue value

    ] ifFalse:[

        childIndex := key at:idx.

        ^ (children at:childIndex) at:key keyIndex:idx+1 ifAbsent:exceptionalValue

    ].

    "Created: / 04-08-2012 / 17:58:29 / cg"

!

at:key keyIndex:idx ifAbsentPut:newValue

    |childIndex node|

    idx > key size ifTrue:[

        "/ at leaf

        value isNil ifTrue:[

            value := newValue value

        ].

        ^ value

    ] ifFalse:[

        childIndex := key at:idx.

        children isNil ifTrue:[

            children := Trie::SmallDictionaryWith1Element new

                            k1:childIndex v1:(node := self class new).

        ] ifFalse:[

            (children includesKey:childIndex) ifFalse:[

                children := children newAt:childIndex put:(node := self class new).

            ] ifTrue:[

                node := children at:childIndex

            ].

        ].

        ^ node at:key keyIndex:idx+1 ifAbsentPut:newValue.

    ]

    "Created: / 04-08-2012 / 17:53:17 / cg"

!

at:key keyIndex:idx put:anElement

    |childIndex node|

    idx > key size ifTrue:[

        "/ at leaf

        value := anElement

    ] ifFalse:[

        childIndex := key at:idx.

        anElement isNil ifTrue:[

            children isNil ifTrue:[^ self ].

            node := children at:childIndex.

            node isNil ifTrue:[^ self].

            node at:key keyIndex:idx+1 put:nil.

            node isEmpty ifTrue:[

                children := children newAt:childIndex put:nil.

            ]

        ] ifFalse:[

            children isNil ifTrue:[

                children := Trie::SmallDictionaryWith1Element new

                                k1:childIndex v1:(node := self class new).

            ] ifFalse:[

                (children includesKey:childIndex) ifFalse:[

                    children := children newAt:childIndex put:(node := self class new).

                ] ifTrue:[

                    node := children at:childIndex

                ].

            ].

            node at:key keyIndex:idx+1 put:anElement.

        ].

    ].

    "Created: / 04-08-2012 / 10:36:44 / cg"

!

includesKey:key keyIndex:idx

    |childIndex node|

    idx > key size ifTrue:[

        "/ at leaf

        ^ value notNil

    ] ifFalse:[

        children isNil ifTrue:[ ^ false ].

        childIndex := key at:idx.

        (children includesKey:childIndex) ifFalse:[^ false].

        node := children at:childIndex.

        ^ node includesKey:key keyIndex:idx+1 

    ].

    "Created: / 04-08-2012 / 18:04:25 / cg"

! !

!Trie methodsFor:'queries'!

includesKey:key 

    ^ self includesKey:key keyIndex:1

    "Created: / 04-08-2012 / 11:32:42 / cg"

!

isEmpty

    ^ value isNil

    and:[ children isEmptyOrNil ]

    "Created: / 04-08-2012 / 11:45:26 / cg"

!

size

    |n|

    n := (value notNil) ifTrue:[1] ifFalse:[0].

    children notNil ifTrue:[

        children do:[:eachChild |

            eachChild notNil ifTrue:[

                n := n + eachChild size

            ]

        ].

    ].

    ^ n

    "Created: / 04-08-2012 / 10:48:45 / cg"

! !

!Trie::Dictionary methodsFor:'accessing'!

newAt:key put:value

    self at:key put:value.

    ^ self

    "Created: / 04-08-2012 / 11:12:39 / cg"

! !

!Trie::SmallDictionaryWith1Element methodsFor:'accessing'!

at:key 

    key = k1 ifTrue:[^ v1 ].

    ^ self error

    "Created: / 04-08-2012 / 11:17:14 / cg"

!

at:key ifAbsent:exceptionValue

    key = k1 ifTrue:[^ v1 ].

    ^ exceptionValue value

    "Created: / 04-08-2012 / 11:00:52 / cg"

!

includesKey:key

    ^ key = k1

    "Created: / 04-08-2012 / 11:13:20 / cg"

!

isEmpty

    ^ k1 isNil

    "Created: / 04-08-2012 / 11:34:12 / cg"

!

k1:k1Arg v1:v1Arg 

    k1 := k1Arg.

    v1 := v1Arg.

!

newAt:key put:value

    key = k1 ifTrue:[ v1 := value. ^ self ].

    ^ Trie::SmallDictionaryWith2Elements new

        k1:k1 v1:v1 k2:key v2:value

    "Created: / 04-08-2012 / 11:02:49 / cg"

!

size

    ^ k1 isNil ifTrue:[0] ifFalse:[1]

    "Created: / 04-08-2012 / 11:54:21 / cg"

! !

!Trie::SmallDictionaryWith1Element methodsFor:'enumeration'!

do:aBlock

    k1 notNil ifTrue:[ aBlock value: v1 ].

    "Created: / 04-08-2012 / 11:19:10 / cg"

! !

!Trie::SmallDictionaryWith2Elements methodsFor:'accessing'!

at:key 

    key = k1 ifTrue:[^ v1 ].

    key = k2 ifTrue:[^ v2 ].

    ^ self error

    "Created: / 04-08-2012 / 11:17:24 / cg"

!

at:key ifAbsent:exceptionValue

    key = k1 ifTrue:[^ v1 ].

    key = k2 ifTrue:[^ v2 ].

    ^ exceptionValue value

    "Created: / 04-08-2012 / 11:01:05 / cg"

!

includesKey:key

    ^ key = k1 or:[ key = k2 ]

    "Created: / 04-08-2012 / 11:13:41 / cg"

!

isEmpty

    ^ k1 isNil and:[ k2 isNil ]

    "Created: / 04-08-2012 / 11:34:34 / cg"

!

k1:k1Arg v1:v1Arg k2:k2Arg v2:v2Arg 

    k1 := k1Arg.

    k2 := k2Arg.

    v1 := v1Arg.

    v2 := v2Arg.

    "Created: / 04-08-2012 / 11:14:16 / cg"

!

newAt:key put:value

    key = k1 ifTrue:[ v1 := value. ^ self ].

    key = k2 ifTrue:[ v2 := value. ^ self ].

    ^ Trie::SmallDictionaryWith3Elements new

        k1:k1 v1:v1 k2:k2 v2:v2 k3:key v3:value

    "Created: / 04-08-2012 / 11:03:16 / cg"

!

size

    ^ (k1 isNil ifTrue:[0] ifFalse:[1]) + (k2 isNil ifTrue:[0] ifFalse:[1])

    "Created: / 04-08-2012 / 11:54:49 / cg"

! !

!Trie::SmallDictionaryWith2Elements methodsFor:'enumeration'!

do:aBlock

    k1 notNil ifTrue:[ aBlock value: v1 ].

    k2 notNil ifTrue:[ aBlock value: v2 ].

    "Created: / 04-08-2012 / 11:19:23 / cg"

! !

!Trie::SmallDictionaryWith3Elements methodsFor:'accessing'!

at:key 

    key = k1 ifTrue:[^ v1 ].

    key = k2 ifTrue:[^ v2 ].

    key = k3 ifTrue:[^ v3 ].

    ^ self error

    "Created: / 04-08-2012 / 11:17:38 / cg"

!

at:key ifAbsent:exceptionValue

    key = k1 ifTrue:[^ v1 ].

    key = k2 ifTrue:[^ v2 ].

    key = k3 ifTrue:[^ v3 ].

    ^ exceptionValue value

    "Created: / 04-08-2012 / 11:01:15 / cg"

!

includesKey:key

    ^ key = k1 or:[ key = k2 or:[ key = k3 ]]

    "Created: / 04-08-2012 / 11:13:54 / cg"

!

isEmpty

    ^ k1 isNil and:[ k2 isNil and:[ k3 isNil ]]

    "Created: / 04-08-2012 / 11:34:48 / cg"

!

k1:k1Arg v1:v1Arg k2:k2Arg v2:v2Arg k3:k3Arg v3:v3Arg 

    k1 := k1Arg.

    k2 := k2Arg.

    k3 := k3Arg.

    v1 := v1Arg.

    v2 := v2Arg.

    v3 := v3Arg.

    "Created: / 04-08-2012 / 11:14:35 / cg"

!

newAt:key put:value

    key = k1 ifTrue:[ v1 := value. ^ self ].

    key = k2 ifTrue:[ v2 := value. ^ self ].

    key = k3 ifTrue:[ v3 := value. ^ self ].

    ^ Trie::Dictionary new

        at:k1 put:v1;

        at:k2 put:v2;

        at:k3 put:v3;

        at:key put:value;

        yourself

    "Created: / 04-08-2012 / 11:04:31 / cg"

!

size

    ^ (k1 isNil ifTrue:[0] ifFalse:[1]) 

        + (k2 isNil ifTrue:[0] ifFalse:[1])

        + (k3 isNil ifTrue:[0] ifFalse:[1])

    "Created: / 04-08-2012 / 11:55:03 / cg"

! !

!Trie::SmallDictionaryWith3Elements methodsFor:'enumeration'!

do:aBlock

    k1 notNil ifTrue:[ aBlock value: v1 ].

    k2 notNil ifTrue:[ aBlock value: v2 ].

    k3 notNil ifTrue:[ aBlock value: v3 ].

    "Created: / 04-08-2012 / 11:19:36 / cg"

! !

!Trie class methodsFor:'documentation'!

version

    ^ '$Header: /cvs/stx/stx/libbasic2/Trie.st,v 1.3 2012-11-13 13:05:13 cg Exp $'

!

version_CVS

    ^ '$Header: /cvs/stx/stx/libbasic2/Trie.st,v 1.3 2012-11-13 13:05:13 cg Exp $'

! !