eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'Trie':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: Trie


Inheritance:

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

Package:
stx:libbasic2
Category:
Collections-Ordered
Version:
rev: 1.5 date: 2019/07/31 21:16:28
user: cg
file: Trie.st directory: libbasic2
module: stx stc-classLibrary: libbasic2
Author:
Claus Gittinger

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.


Class protocol:

instance creation
o  new
return an initialized instance


Instance protocol:

accessing
o  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).

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

o  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.

o  at: key ifAbsentPut: newValue

o  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)

o  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.

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

private
o  at: key keyIndex: idx ifAbsent: exceptionalValue
at leaf

o  at: key keyIndex: idx ifAbsentPut: newValue
at leaf

o  at: key keyIndex: idx put: anElement
at leaf

o  includesKey: key keyIndex: idx
at leaf

queries
o  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.

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

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


Private classes:

    SmallDictionaryWith1Element
    SmallDictionaryWith2Elements
    SmallDictionaryWith3Elements


ST/X 7.2.0.0; WebServer 1.670 at bd0aa1f87cdd.unknown:8081; Fri, 16 Apr 2021 12:32:39 GMT