src/lib/trie.slate

   1 collections define: #Trie
   2   &parents: {OrderedTree. NoDuplicatesCollection. Mapping}
   3   &slots: {#element}.
   4 "A trie is a Set of Sequences encoded as a left-to-right element search tree.
   5 At nodes whose path represents a Sequence that is an element, the node is
   6 tagged with the element. To use a Trie as a Set, the element should be the
   7 Sequence itself, handled by the add:/remove: protocol; otherwise it can be
   8 used as a Dictionary."
   9 "element: Records the element that the trie node encodes, if it does at all. The
  10 element should consist of the sequence of all the keys used in order to access
  11 the given node. As a result, trie nodes must be root-aware."
  12 Trie children := IdentityDictionary new.
  13 "Uses a Mapping of Sequence elements to the next Node."
  14
  15 t@(Trie traits) new &capacity: n
  16 "Tries are generally 'narrow' Trees."
  17 [n ifNil: [n := 3]. resend].
  18
  19 t@(Trie traits) acceptsKey: _
  20 [False].
  21
  22 t@(Trie traits) acceptsKey: _@(Sequence traits)
  23 "This is not quite true, since any key will work that responds to at:
  24 appropriately when given 0..n of integers and has a size."
  25 [True].
  26
  27 t@(Trie traits) includes: s@(Sequence traits)
  28 "Treat the trie as a set of its keys. Searching for values is more expensive."
  29 [
  30   (t at: s) isNotNil
  31 ].
  32
  33 t@(Trie traits) size
  34 [
  35   t children
  36     inject: t children size
  37     into: [| :sum :each | sum + each size]
  38 ].
  39
  40 t@(Trie traits) nodeFor: seq
  41 "Returns the Trie node for the given Sequence."
  42 [| node |
  43   node := t.
  44   seq do: [| :each | node := node children at: each ifAbsent: []].
  45   node
  46 ].
  47
  48 t@(Trie traits) at: s@(Sequence traits)
  49 "Search from here each of the elements of the sequence in turn."
  50 [
  51   (t nodeFor: s) ifNotNilDo: #element `er
  52 ].
  53
  54 t@(Trie traits) nearestNodeFor: seq
  55 "Returns the Trie node that completes the greatest part of the Sequence."
  56 [| node next cursor |
  57   node := t.
  58   next := t.
  59   cursor := 0.
  60   [next isNil] whileFalse:
  61     [(next := node children at: (seq at: cursor) ifAbsent: [])
  62        ifNotNil: [node := next. cursor += 1]].
  63   node
  64 ].
  65
  66 t@(Trie traits) at: s@(Sequence traits) put: obj
  67 "Traverse down the Trie, adding nodes once an element isn't found.
  68 Annotate the final node with the given element."
  69 [| node next cursor |
  70   node := t.
  71   next := t.
  72   cursor := 0.
  73   [next isNil \/ [cursor = s size]] whileFalse:
  74     [(next := node children at: (s at: cursor) ifAbsent: [])
  75        ifNotNil: [node := next. cursor += 1]].
  76   "node is now at the last existing relevant Trie node.
  77   cursor is the index within the Sequence of the next element to add."
  78   cursor below: s size do:
  79     [| :index |
  80       next := t new.
  81       node children at: (s at: index) put: next.
  82       next treeParent := node.
  83       node := next].
  84   node element := obj.
  85   obj
  86 ].
  87
  88 t@(Trie traits) add: s@(Sequence traits)
  89 "Treat the trie as a Set."
  90 [
  91   t at: s put: s
  92 ].
  93
  94 t@(Trie traits) remove: s@(Sequence traits)
  95 "Search the trie for the sequence, stop at the last found, then recursively
  96   delete nodes with no element but the argument and move back up the tree.
  97   This returns the keyed value if there is one."
  98 [| next node lastPoint temp |
  99   node := t.
 100   next := t.
 101   lastPoint := 0.
 102   [next isNil] whileFalse:
 103     [s doWithIndex:
 104        [| :each :index |
 105         next := node children at: each ifAbsent: [].
 106         next ifNotNil: [lastPoint := index. node := next]]].
 107   node element := Nil.
 108   [node element isNil /\ [node children size <= 1]] whileTrue:
 109     [temp := node.
 110      (node := node treeParent) ifNil: [^ s] ifNotNil:
 111        [node children keysAndValuesRemove:
 112           [| :key :value | value == temp].
 113         temp treeParent := Nil]].
 114   s
 115 ].