"{ Package: 'stx:libbasic2' }"

Collection subclass:#TSTree

	instanceVariableNames:'root'

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Ordered-Trees'

!

Object subclass:#TSTreeNode

	instanceVariableNames:'key value low high equal'

	classVariableNames:''

	poolDictionaries:''

	privateIn:TSTree

!

!TSTree class methodsFor:'documentation'!

documentation

"

    A bunch of collection classes that are useful for building large indices of things. 

    It's especially geared towards people using OODBs like GOODS, but can be used it in the image too: 

    the BTree class is great for when you need to select numeric keys by range, 

    and TSTree makes a solid basis for full-text search. 

    TreeSet has an interesting optimized #intersection: that lets you compare two collections without 

    looking at every item of either. 

    I'm also going to be rolling some code in here from Benjamin Pollack specifically aimed at indexing 

    by date ranges, which lets you do quick queries of all the events that overlap with a specific week, 

    for instance. 

    Also in the BTree package is a TSTree, which has similar properties for String 

    keys.  So as well as keeping them sorted, you can do efficient lookups of all 

    the keys with a given prefix.  One other neat trick TSTree can do is a certain 

    amount of fuzzy matching (eg find all keys with an edit distance of 3 from 

    'foo') which makes it especially useful for spell checking and similar 

    applications.

    [author:]

        Avi Bryant

    [license:]

        Dual licensed under both SqueakL and MIT. 

        This enables both base Squeak inclusion and 100% reuse.

"

! !

!TSTree methodsFor:'accessing'!

at: aString

	^ self at: aString ifAbsent: [self error: aString printString, ' not found']

!

at: aString ifAbsent: exceptionBlock

	aString isEmpty ifTrue: [^ exceptionBlock value].

	root ifNil: [^ exceptionBlock value].

	^ (root lookupString: aString startingAt: 1) ifNil: exceptionBlock

!

at: aString ifAbsentPut: exceptionBlock

	^ self at: aString ifAbsent: [self at: aString put: exceptionBlock value]

!

at: aString put: anObject

	aString isEmpty ifTrue: [self error: 'Keys cannot be empty'].

	root ifNil: [root _ TSTreeNode key: aString first].

	root lookupString: aString startingAt: 1 insert: anObject.

	^ anObject

!

removeKey: aString

	^ self removeKey: aString ifAbsent: [self error: 'Could not find key ', aString printString]

!

removeKey: aString ifAbsent: errorBlock

	| val |

	val _ root removeString: aString startingAt: 1.

	root canBeCulled ifTrue: [root _ nil].

	^ val ifNil: errorBlock

!

values

	^ Array streamContents: [:s | self do: [:ea | s nextPut: ea]]

! !

matchesForPrefix: aString

	^ Array streamContents:

		[:s |

		self matchesForPrefix: aString do:

			[:match |

			s nextPut: match]]

!

matchesForPrefix: aString do: aBlock

        aString isEmpty

                ifTrue: [self do: aBlock]

                ifFalse: [root notNil ifTrue: [root matchesForPrefix: aString startingAt: 1 do: aBlock]]

    "Modified: / 08-08-2010 / 15:17:01 / cg"

!

matchesForString: aString distance: aNumber

	^ Array streamContents:

		[:s |

		self matchesForString: aString distance: aNumber do:

			[:match |

			s nextPut: match]]

!

matchesForString: aString distance: aNumber do: aBlock

	self matchesForString: aString distance: aNumber limitNodes: nil do: aBlock

!

matchesForString: aString distance: aNumber limitNodes: maxNodes do: aBlock

	| nodeCount |

	nodeCount _ 0.

	aString isEmpty ifTrue: [^ self].

	root isNil ifTrue: [^ self].

	root matchesForString: aString startingAt: 1 distance: aNumber do: aBlock nodesDo:

		[:ea |

		nodeCount _ nodeCount + 1.

		nodeCount = maxNodes ifTrue: [^ self]]

! !

! !

!TSTree::TSTreeNode class methodsFor:'as yet unclassified'!

key: aCharacter

	^ self basicNew initializeWithKey: aCharacter

! !

!TSTree::TSTreeNode class methodsFor:'documentation'!

documentation

"

    [author:]

        Avi Bryant

    [license:]

        Dual licensed under both SqueakL and MIT. 

        This enables both base Squeak inclusion and 100% reuse.

"

! !

!TSTree::TSTreeNode methodsFor:'private'!

canBeCulled

	^ self value isNil

		and: [low isNil]

		and: [equal isNil]

		and: [high isNil]

!

cullNode: aNode

	low == aNode ifTrue: [^ low _ nil].

	equal == aNode ifTrue: [^ equal _ nil].

	high == aNode ifTrue: [^ high _ nil]

!

do: aBlock

	self nodesDo: [:ea | ea value ifNotNilDo: aBlock]

!

initializeWithKey: aCharacter

	key _ aCharacter

!

lookupString: aString startingAt: i

"inlined for performance"

"

        self

                lookupString: aString

                startingAt: i

                whenFound: [^ value]

                whenNil: [:c | ^ nil]

                recurseWith: [:node :j | ^ node lookupString: aString startingAt: j]"

        | char |

        char := aString at: i.

        char = key

                ifTrue:

                        [aString size = i

                                ifTrue: [^ value]

                                ifFalse: [^ equal notNil ifTrue: [equal lookupString: aString startingAt: i+1] ifFalse:[nil]]]

                ifFalse:

                        [char < key

                                ifTrue: [^ low notNil ifTrue: [low lookupString: aString startingAt: i] ifFalse:[nil]]

                                ifFalse: [^ high notNil ifTrue: [high lookupString: aString startingAt: i] ifFalse:[nil]]]

    "Modified: / 08-08-2010 / 15:18:03 / cg"

!

lookupString: aString startingAt: i insert: anObject

	self

		lookupString: aString

		startingAt: i

		whenFound: [self value: anObject]

		whenNil: [:c | self newNodeWithKey: c]

		recurseWith: [:node :j | node lookupString: aString startingAt: j insert: anObject]

!

lookupString: aString startingAt: i whenFound: foundBlock whenNil: nilBlock recurseWith: recurseBlock

	| char |

	char := aString at: i.

	char = key

		ifTrue:

			[aString size = i

				ifTrue: [foundBlock value]

				ifFalse: [equal ifNil: [equal := nilBlock value: (aString at: i+1)].

						 recurseBlock value: equal value: i+1]]

		ifFalse:

			[char < key

				ifTrue: [low ifNil: [low := nilBlock value: char].

						recurseBlock value: low value: i]

				ifFalse: [high ifNil: [high := nilBlock value: char].

						recurseBlock value: high value: i]]

!

matchesForPrefix: aString startingAt: i do: aBlock

        self

                lookupString: aString

                startingAt: i

                whenFound: [value notNil ifTrue: [aBlock value: value].  equal notNil ifTrue: [equal do: aBlock]]

                whenNil: [:c | ^ self]

                recurseWith: [:n :j | n matchesForPrefix: aString startingAt: j do: aBlock]

    "Modified: / 08-08-2010 / 15:18:44 / cg"

!

matchesForString: aString startingAt: i distance: d do: aBlock nodesDo: nodeBlock

        | char d2 |

        nodeBlock value: self.

        d < 0 ifTrue: [^ self].

        char := aString at: i.

        (d > 0 or: [char < key])

                ifTrue: [low notNil ifTrue: [low matchesForString: aString startingAt: i distance: d do: aBlock nodesDo: nodeBlock]].

        d2 := char = key ifTrue: [d] ifFalse: [d-1].

        (i + d2 = aString size and: [value notNil]) ifTrue: [aBlock value: value].

        equal ifNotNil: [equal matchesForString: aString startingAt: (i+1 min: aString size) distance: d2 do: aBlock nodesDo: nodeBlock].

        (d > 0 or: [char > key])

                ifTrue: [high notNil ifTrue: [high matchesForString: aString startingAt: i distance: d do: aBlock nodesDo: nodeBlock]]

    "Modified: / 08-08-2010 / 15:18:57 / cg"

!

newNodeWithKey: aCharacter

	^ self class key: aCharacter

!

nodesDo: aBlock

        aBlock value: self.

        low notNil ifTrue: [low nodesDo: aBlock].

        equal notNil ifTrue: [equal nodesDo: aBlock].

        high notNil ifTrue: [high nodesDo: aBlock]

    "Modified: / 08-08-2010 / 15:19:05 / cg"

!

removeString: aString startingAt: i

	| val |

	self

		lookupString: aString

		startingAt: i

		whenFound: [val _ self value. self value: nil]

		whenNil: [:c | ^ nil]

		recurseWith:

			[:node :j |

			val _ node removeString: aString startingAt: j.

			node canBeCulled ifTrue:

				[self cullNode: node]].

	^ val

!

value

	^ value

!

value: anObject

	value _ anObject

! !

!TSTree class methodsFor:'documentation'!

version_CVS

! !