requires: {#LinkedCollection. #Dictionary}. provides: {#OrderedTree. #Trie}. collections addSlot: #OrderedTree valued: LinkedCollection derive. "A Tree node, linking to its parent node and storing its children in a Sequence." OrderedTree addSlot: #treeParent. "The parent node, Nil for top-level nodes." OrderedTree addSlot: #children valued: ExtensibleSequence newEmpty. "The sub-nodes, stored in an ExtensibleSequence by default." ot@(OrderedTree traits) clear [ ot children: (ot children newEmpty). ot ]. ot@(OrderedTree traits) newSize: n [| newOT | newOT: ot clone. newOT children: (ot children newSize: n). newOT ]. ot@(OrderedTree traits) newFor: obj [| newOT | newOT: ot clone. newOT children: ot children newEmpty. newOT add: obj. newOT ]. ot@(OrderedTree traits) newForAll: c@(Collection traits) [| newOT | newOT: ot clone. newOT children: (ot children newSizeOf: c). c do: [| :each | newOT add: each]. newOT ]. ot@(OrderedTree traits) siblings "Return all children of the node's parent, excepting the original node. Answer Nil if there is no parent or the wrong parent." [ ot treeParent ifNil: [ExtensibleSequence newEmpty] ifNotNil: [| result | result: ot treeParent children clone. result remove: ot ifAbsent: [^ Nil]. result] ]. ot@(OrderedTree traits) previousSibling [ ot treeParent ifNotNilDo: [| :p | p children before: ot] ]. ot@(OrderedTree traits) nextSibling [ ot treeParent ifNotNilDo: [| :p | p children after: ot] ]. ot@(OrderedTree traits) raise [ ot treeParent children move: ot to: 0 ]. ot@(OrderedTree traits) bury [| siblings | siblings: ot treeParent children. siblings move: ot to: siblings size - 1. ot ]. ch@(OrderedTree traits) reparentTo: ot@(OrderedTree traits) "Handle the aspect of unsetting any parent link and backlink as necessary. Avoid adding to the new parent, since the position matters." [ ch treeParent ifNotNil: [ch treeParent remove: ch]. ch treeParent: ot ]. ot@(OrderedTree traits) add: ch@(OrderedTree traits) "Add a tree node as a child, and set the parent back-link." [ ot children add: ch. ch reparentTo: ot. ot ]. ot@(OrderedTree traits) remove: ch@(OrderedTree traits) "Remove the tree node as a child, making sure to remove the parent link." [ ot children remove: ch ifAbsent: [^ Nil]. ch treeParent: Nil. ot ]. ot@(OrderedTree traits) remove: ch@(OrderedTree traits) ifAbsent: block [ ot children remove: ch ifAbsent: [block value] ]. ot@(OrderedTree traits) isEmpty [ ot children isEmpty ]. collections addSlot: #Trie valued: (OrderedTree deriveWith: {NoDuplicatesCollection. Mapping}). "A trie is a Set of Sequences encoded as a left-to-right element search tree. At nodes whose path represents a Sequence that is an element, the node is tagged with the element. To use a Trie as a Set, the element should be the Sequence itself, handled by the add:/remove: protocol; otherwise it can be used as a Dictionary." Trie addSlot: #element valued: Nil. "Records the element that the trie node encodes, if it does at all. The element should consist of the sequence of all the keys used in order to access the given node. As a result, trie nodes must be root-aware." Trie children: IdentityDictionary newEmpty. "Uses a Mapping of Sequence elements to the next Node." t@(Trie traits) newEmpty "Tries are generally 'narrow' Trees." [t newSize: 3]. t@(Trie traits) acceptsKey: _ [False]. t@(Trie traits) acceptsKey: _@(Sequence traits) "This is not quite true, since any key will work that responds to at: appropriately when given 0..n of integers and has a size." [True]. t@(Trie traits) includes: s@(Sequence traits) "Treat the trie as a set of its keys. Searching for values is more expensive." [ (t at: s) isNotNil ]. t@(Trie traits) size [ t children inject: t children size into: [| :sum :each | sum + each size] ]. t@(Trie traits) nodeFor: seq "Returns the Trie node for the given Sequence." [| here | here: t. seq do: [| :each | here: (here children at: each ifAbsent: [])]. here ]. t@(Trie traits) at: s@(Sequence traits) "Search from here each of the elements of the sequence in turn." [ (t nodeFor: s) ifNotNilDo: [| :node | node element] ]. t@(Trie traits) nearestNodeFor: seq "Returns the Trie node that completes the greatest part of the Sequence." [| here next cursor | here: t. next: t. cursor: 0. [next isNil] whileFalse: [next: (here children at: (seq at: cursor) ifAbsent: []). next ifNotNil: [here: next. cursor: cursor + 1]]. here ]. t@(Trie traits) at: s@(Sequence traits) put: obj "Traverse down the Trie, adding nodes once an element isn't found. Annotate the final node with the given element." [| here next cursor | here: t. next: t. cursor: 0. [next isNil or: [cursor = s size]] whileFalse: [next: (here children at: (s at: cursor) ifAbsent: []). next ifNotNil: [here: next. cursor: cursor + 1]]. "here is now at the last existing relevant Trie node. cursor is the index within the Sequence of the next element to add." cursor below: s size do: [| :index | next: t newEmpty. here children at: (s at: index) put: next. next treeParent: here. here: next]. here element: obj. obj ]. t@(Trie traits) add: s@(Sequence traits) "Treat the trie as a Set." [ t at: s put: s ]. t@(Trie traits) remove: s@(Sequence traits) "Search the trie for the sequence, stop at the last found, then recursively delete nodes with no element but the argument and move back up the tree. This returns the keyed value if there is one." [| next here lastPoint | here: t. next: t. lastPoint: 0. [next isNil] whileFalse: [s doWithIndex: [| :each :index | next: (here children at: each ifAbsent: []). next ifNotNil: [lastPoint: index. here: next]]]. here element: Nil. [here element isNil and: [here children size <= 1]] whileTrue: [| temp | temp: here. here: here treeParent. here ifNil: [^ s] ifNotNil: [here children keysAndValuesRemove: [| :key :value | value == temp]. temp treeParent: Nil]]. s ].