Class: Trie

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • enumeration
  • private
  • queries
• Private classes

Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--Trie

Package:

stx:libbasic2

Category:

Collections-Ordered

Version:

rev: 1.7 date: 2021/01/20 14:04:14

user: cg

file: Trie.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Description:

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.

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]

Class protocol:

 new

return an initialized instance

Instance protocol:

 add: aValue

(comment from inherited method)
append the argument, anObject to the collection.
Return the argument, anObject.

Notice that this modifies the receiver, NOT a copy.
Also note that it may be a slow operation for some collections,
due to the grow:-message, which is inefficient for fixed size
collections (i.e. for Strings and Arrays it is not recommended).

 at: key

(comment from inherited method)
return the indexed instance variable with index, anInteger;
this method can be redefined in subclasses.

 at: key ifAbsent: exceptionValue

(comment from inherited method)
return the element at index if valid.
If the index is invalid, return the result from exceptionValue.
NOTICE:
in ST-80, this message is only defined for Dictionaries,
however, having a common protocol with indexed collections
often simplifies things.

 at: key ifAbsentPut: newValue

 at: key put: anElement

(comment from inherited method)
store the 2nd arg, anObject as indexed instvar with index, anInteger.
this method can be redefined in subclasses. Returns anObject (sigh)

 remove: aValue

(comment from inherited method)
search for the first element, which is equal to anObject;
if found, remove and return it.
If not found, report a 'value not found'-error.
Uses equality compare (=) to search for the occurrence.

 do: aBlock

(comment from inherited method)
evaluate the argument, aBlock for every element in the collection in
sequence order.

 at: key keyIndex: idx ifAbsent: exceptionalValue

at leaf

 at: key keyIndex: idx ifAbsentPut: newValue

at leaf

 at: key keyIndex: idx put: anElement

at leaf

 includesKey: key keyIndex: idx

at leaf

 includesKey: key

(comment from inherited method)
return true, if anIndex is a valid key.
NOTICE: in ST-80, this message is only defined for Dictionaries,
however, having a common protocol with indexed collections
often simplifies things.

 isEmpty

(comment from inherited method)
return true, if the receiver is empty

 size

(comment from inherited method)
return the number of elements in the collection.
concrete implementations must define this

Private classes:

    SmallDictionaryWith1Element
    SmallDictionaryWith2Elements
    SmallDictionaryWith3Elements