2281
|
1 |
"{ Package: 'stx:libbasic2' }"
|
|
2 |
|
4098
|
3 |
"{ NameSpace: Smalltalk }"
|
|
4 |
|
4363
|
5 |
KeyedCollection subclass:#BTree
|
2281
|
6 |
instanceVariableNames:'root'
|
|
7 |
classVariableNames:''
|
|
8 |
poolDictionaries:''
|
2768
|
9 |
category:'Collections-Ordered-Trees'
|
2281
|
10 |
!
|
|
11 |
|
|
12 |
Object subclass:#BTreeKeys
|
|
13 |
instanceVariableNames:''
|
|
14 |
classVariableNames:''
|
|
15 |
poolDictionaries:''
|
|
16 |
privateIn:BTree
|
|
17 |
!
|
|
18 |
|
|
19 |
BTree::BTreeKeys variableSubclass:#BTreeKeysArray
|
|
20 |
instanceVariableNames:''
|
|
21 |
classVariableNames:''
|
|
22 |
poolDictionaries:''
|
|
23 |
privateIn:BTree
|
|
24 |
!
|
|
25 |
|
|
26 |
Object variableSubclass:#BTreeNode
|
|
27 |
instanceVariableNames:'parent keys'
|
|
28 |
classVariableNames:''
|
|
29 |
poolDictionaries:''
|
|
30 |
privateIn:BTree
|
|
31 |
!
|
|
32 |
|
|
33 |
BTree::BTreeNode variableSubclass:#BTreeInteriorNode
|
|
34 |
instanceVariableNames:''
|
|
35 |
classVariableNames:''
|
|
36 |
poolDictionaries:''
|
|
37 |
privateIn:BTree::BTreeNode
|
|
38 |
!
|
|
39 |
|
|
40 |
BTree::BTreeNode variableSubclass:#BTreeLeafNode
|
|
41 |
instanceVariableNames:''
|
|
42 |
classVariableNames:''
|
|
43 |
poolDictionaries:''
|
|
44 |
privateIn:BTree
|
|
45 |
!
|
|
46 |
|
|
47 |
BTree::BTreeKeys subclass:#BTreeStringKeys
|
|
48 |
instanceVariableNames:'keys prefix abbreviations'
|
|
49 |
classVariableNames:''
|
|
50 |
poolDictionaries:''
|
|
51 |
privateIn:BTree
|
|
52 |
!
|
|
53 |
|
|
54 |
!BTree class methodsFor:'documentation'!
|
|
55 |
|
|
56 |
documentation
|
|
57 |
"
|
4123
|
58 |
BTree and TSTree
|
|
59 |
|
2281
|
60 |
A bunch of collection classes that are useful for building large indices of things.
|
|
61 |
It's especially geared towards people using OODBs like GOODS, but can be used it in the image too:
|
|
62 |
the BTree class is great for when you need to select numeric keys by range,
|
|
63 |
and TSTree makes a solid basis for full-text search.
|
|
64 |
TreeSet has an interesting optimized #intersection: that lets you compare two collections without
|
|
65 |
looking at every item of either.
|
|
66 |
I'm also going to be rolling some code in here from Benjamin Pollack specifically aimed at indexing
|
|
67 |
by date ranges, which lets you do quick queries of all the events that overlap with a specific week,
|
|
68 |
for instance.
|
|
69 |
|
|
70 |
This is an implementation of the BTree data structure as a Smalltalk collection.
|
|
71 |
It provides log(n) inserts, deletes, and retrieves of values by key.
|
|
72 |
The keys have to be sortable (ie, Magnitudes).
|
|
73 |
|
|
74 |
This is useful in situations where you want to minimize the number and size of individual objects
|
|
75 |
that need to be accessed when using a large collection - for example, when objects are being swapped
|
|
76 |
out to an object database such as GOODS.
|
|
77 |
It is probably not a good choice for a collection that will be kept entirely in memory.
|
|
78 |
|
|
79 |
|
|
80 |
What you get: efficient sorted iteration through the keys, possibly limited to
|
|
81 |
a given range. For example, if you store a list of people keyed by their
|
|
82 |
birthdate, and then want to find everyone born in a certain year, in order of
|
|
83 |
birth, you can do that very fast.
|
|
84 |
|
|
85 |
Also in the BTree package is a TSTree, which has similar properties for String
|
|
86 |
keys. So as well as keeping them sorted, you can do efficient lookups of all
|
|
87 |
the keys with a given prefix. One other neat trick TSTree can do is a certain
|
|
88 |
amount of fuzzy matching (eg find all keys with an edit distance of 3 from
|
|
89 |
'foo') which makes it especially useful for spell checking and similar
|
|
90 |
applications.
|
|
91 |
|
|
92 |
[author:]
|
|
93 |
Avi Bryant
|
|
94 |
|
|
95 |
[license:]
|
|
96 |
Dual licensed under both SqueakL and MIT.
|
|
97 |
This enables both base Squeak inclusion and 100% reuse.
|
|
98 |
"
|
2413
|
99 |
!
|
|
100 |
|
|
101 |
examples
|
|
102 |
"
|
|
103 |
|coll|
|
|
104 |
|
|
105 |
coll := BTree new.
|
|
106 |
(1 to:10) do:[:i | coll at:(i printString) put:(i squared) ].
|
|
107 |
coll inspect.
|
|
108 |
coll at:'10'
|
|
109 |
"
|
2281
|
110 |
! !
|
|
111 |
|
2803
|
112 |
!BTree class methodsFor:'instance creation'!
|
2281
|
113 |
|
|
114 |
keys: aBTreeKeys
|
|
115 |
^ self basicNew initializeWithKeys: aBTreeKeys
|
|
116 |
!
|
|
117 |
|
|
118 |
new
|
|
119 |
^ self order: 5
|
|
120 |
!
|
|
121 |
|
|
122 |
order: aNumber
|
|
123 |
^ self keys: (BTreeKeysArray new: aNumber)
|
|
124 |
! !
|
|
125 |
|
|
126 |
!BTree methodsFor:'accessing'!
|
|
127 |
|
|
128 |
at: aMagnitude ifAbsent: errorBlock
|
|
129 |
| leaf |
|
2699
|
130 |
leaf := root existingLeafForKey: aMagnitude.
|
|
131 |
leaf isNil ifTrue: [^ errorBlock value].
|
2281
|
132 |
^ leaf valueForKey: aMagnitude ifAbsent: errorBlock
|
2699
|
133 |
|
|
134 |
"Modified (format): / 18-11-2011 / 14:10:16 / cg"
|
2281
|
135 |
!
|
|
136 |
|
|
137 |
depth
|
|
138 |
^ root depth
|
|
139 |
!
|
|
140 |
|
|
141 |
keys
|
|
142 |
^ Array streamContents:
|
|
143 |
[:s |
|
|
144 |
self keysDo: [:k | s nextPut: k]]
|
|
145 |
!
|
|
146 |
|
|
147 |
order
|
|
148 |
^ root size
|
|
149 |
!
|
|
150 |
|
|
151 |
values
|
|
152 |
^ Array streamContents:
|
|
153 |
[:s |
|
|
154 |
self keysAndValuesDo: [:k :v | s nextPut: v]]
|
|
155 |
! !
|
|
156 |
|
|
157 |
!BTree methodsFor:'adding'!
|
|
158 |
|
|
159 |
at: aMagnitude put: anObject
|
|
160 |
| leaf |
|
|
161 |
leaf _ root leafForKey: aMagnitude.
|
|
162 |
leaf insertKey: aMagnitude value: anObject.
|
|
163 |
root _ leaf root.
|
|
164 |
^ anObject
|
|
165 |
!
|
|
166 |
|
|
167 |
removeKey: aMagnitude
|
|
168 |
| leaf |
|
|
169 |
leaf _ root leafForKey: aMagnitude.
|
|
170 |
leaf removeKey: aMagnitude.
|
|
171 |
root _ leaf root
|
|
172 |
! !
|
|
173 |
|
|
174 |
!BTree methodsFor:'enumerating'!
|
|
175 |
|
|
176 |
commonKeysWith: aTree keysAndValuesDo: aBlock
|
|
177 |
^ aTree depth < self depth
|
|
178 |
ifTrue: [aTree root commonKeysWith: root keysAndValuesDo: aBlock flip: true]
|
|
179 |
ifFalse: [root commonKeysWith: aTree root keysAndValuesDo: aBlock flip: false]
|
|
180 |
!
|
|
181 |
|
|
182 |
do: aBlock
|
|
183 |
root allLeavesDo: [:ea | ea valuesDo: aBlock]
|
|
184 |
!
|
|
185 |
|
|
186 |
from: start to: end do: aBlock
|
|
187 |
self from: start to: end keysAndValuesDo: [:k :v | aBlock value: v]
|
|
188 |
!
|
|
189 |
|
|
190 |
from: start to: end keysAndValuesDo: aBlock
|
|
191 |
root leavesFrom: start to: end do:
|
|
192 |
[:ea |
|
|
193 |
ea keysAndValuesDo:
|
|
194 |
[:k :v |
|
|
195 |
(k between: start and: end) ifTrue:
|
|
196 |
[aBlock value: k value: v]]]
|
|
197 |
!
|
|
198 |
|
|
199 |
keysAndValuesDo: aBlock
|
|
200 |
root allLeavesDo: [:ea | ea keysAndValuesDo: aBlock]
|
|
201 |
!
|
|
202 |
|
|
203 |
keysDo: aBlock
|
2487
|
204 |
"evaluate the argument, aBlock for every key in the collection."
|
|
205 |
|
|
206 |
root allLeavesDo: [:ea | ea keysDo: aBlock]
|
|
207 |
|
|
208 |
"Modified: / 24-08-2010 / 10:13:24 / cg"
|
2281
|
209 |
! !
|
|
210 |
|
|
211 |
!BTree methodsFor:'initialize-release'!
|
|
212 |
|
|
213 |
initializeWithKeys: aBTreeKeys
|
|
214 |
aBTreeKeys size > 3 ifFalse: [self error: 'The BTree order must be at least 4'].
|
|
215 |
root _ BTreeLeafNode keys: aBTreeKeys
|
|
216 |
! !
|
|
217 |
|
|
218 |
!BTree methodsFor:'private'!
|
|
219 |
|
|
220 |
root
|
|
221 |
^ root
|
|
222 |
! !
|
|
223 |
|
3016
|
224 |
!BTree methodsFor:'testing'!
|
|
225 |
|
|
226 |
isFixedSize
|
|
227 |
"return true if the receiver cannot grow"
|
|
228 |
|
|
229 |
^ false
|
|
230 |
! !
|
|
231 |
|
2281
|
232 |
!BTree::BTreeKeys class methodsFor:'documentation'!
|
|
233 |
|
|
234 |
documentation
|
|
235 |
"
|
|
236 |
[author:]
|
|
237 |
Avi Bryant
|
|
238 |
|
|
239 |
[license:]
|
|
240 |
Dual licensed under both SqueakL and MIT.
|
|
241 |
This enables both base Squeak inclusion and 100% reuse.
|
|
242 |
"
|
|
243 |
! !
|
|
244 |
|
2586
|
245 |
!BTree::BTreeKeys methodsFor:'accessing'!
|
|
246 |
|
|
247 |
first
|
|
248 |
^ self at:1
|
|
249 |
|
|
250 |
"Modified (format): / 02-08-2011 / 09:19:05 / cg"
|
|
251 |
! !
|
|
252 |
|
2281
|
253 |
!BTree::BTreeKeys methodsFor:'as yet unclassified'!
|
|
254 |
|
2586
|
255 |
emptyCopy
|
|
256 |
^ self class new:self size
|
|
257 |
|
|
258 |
"Modified (format): / 02-08-2011 / 09:19:22 / cg"
|
|
259 |
!
|
|
260 |
|
|
261 |
findIndexForKey:aMagnitude
|
|
262 |
self
|
|
263 |
withIndexDo:[:key :i |
|
|
264 |
(key isNil or:[ key > aMagnitude ]) ifTrue:[
|
|
265 |
^ i - 1
|
|
266 |
]
|
|
267 |
].
|
|
268 |
^ self size
|
|
269 |
|
|
270 |
"Modified (format): / 02-08-2011 / 09:19:10 / cg"
|
|
271 |
!
|
|
272 |
|
|
273 |
shiftLeftTo:index
|
|
274 |
index to:self size - 1 by:1 do:[:i |
|
|
275 |
self at:i put:(self at:i + 1)
|
|
276 |
].
|
|
277 |
self at:self size put:nil.
|
|
278 |
|
|
279 |
"Modified (format): / 02-08-2011 / 09:18:52 / cg"
|
|
280 |
!
|
|
281 |
|
|
282 |
shiftRightFrom:index
|
|
283 |
self size to:index + 1 by:-1 do:[:i |
|
|
284 |
self at:i put:(self at:i - 1)
|
|
285 |
]
|
|
286 |
|
|
287 |
"Modified (format): / 02-08-2011 / 09:18:57 / cg"
|
|
288 |
! !
|
|
289 |
|
|
290 |
!BTree::BTreeKeys methodsFor:'enumeration'!
|
|
291 |
|
|
292 |
withIndexDo:aBlock
|
|
293 |
1 to:self size do:[:i |
|
|
294 |
aBlock value:(self at:i) value:i
|
|
295 |
]
|
|
296 |
|
|
297 |
"Modified (format): / 02-08-2011 / 09:19:01 / cg"
|
|
298 |
! !
|
|
299 |
|
|
300 |
!BTree::BTreeKeys methodsFor:'queries'!
|
|
301 |
|
2281
|
302 |
canGrow
|
2586
|
303 |
^ (self at:self size) isNil
|
|
304 |
|
|
305 |
"Modified (format): / 02-08-2011 / 09:19:27 / cg"
|
2281
|
306 |
!
|
|
307 |
|
|
308 |
canShrink
|
2586
|
309 |
^ (self at:self size // 2 + 1) notNil
|
2281
|
310 |
|
2586
|
311 |
"Modified (format): / 02-08-2011 / 09:19:23 / cg"
|
2281
|
312 |
! !
|
|
313 |
|
|
314 |
!BTree::BTreeKeysArray class methodsFor:'documentation'!
|
|
315 |
|
|
316 |
documentation
|
|
317 |
"
|
|
318 |
[author:]
|
|
319 |
Avi Bryant
|
|
320 |
|
|
321 |
[license:]
|
|
322 |
Dual licensed under both SqueakL and MIT.
|
|
323 |
This enables both base Squeak inclusion and 100% reuse.
|
|
324 |
"
|
|
325 |
! !
|
|
326 |
|
|
327 |
!BTree::BTreeNode class methodsFor:'as yet unclassified'!
|
|
328 |
|
|
329 |
keys: anArray
|
|
330 |
^ (self new: (anArray size)) keys: anArray
|
|
331 |
! !
|
|
332 |
|
|
333 |
!BTree::BTreeNode class methodsFor:'documentation'!
|
|
334 |
|
|
335 |
documentation
|
|
336 |
"
|
|
337 |
[author:]
|
|
338 |
Avi Bryant
|
|
339 |
|
|
340 |
[license:]
|
|
341 |
Dual licensed under both SqueakL and MIT.
|
|
342 |
This enables both base Squeak inclusion and 100% reuse.
|
|
343 |
"
|
|
344 |
! !
|
|
345 |
|
|
346 |
!BTree::BTreeNode methodsFor:'accessing'!
|
|
347 |
|
|
348 |
children
|
|
349 |
^ Array streamContents: [:s | self childrenDo: [:ea | s nextPut: ea]]
|
|
350 |
!
|
|
351 |
|
|
352 |
depth
|
|
353 |
^ parent ifNil: [1] ifNotNil: [1 + parent depth]
|
|
354 |
!
|
|
355 |
|
|
356 |
firstKey
|
|
357 |
^ keys first
|
|
358 |
!
|
|
359 |
|
|
360 |
parent
|
|
361 |
^ parent
|
|
362 |
!
|
|
363 |
|
|
364 |
parent: aBTreeNode
|
|
365 |
parent _ aBTreeNode
|
|
366 |
!
|
|
367 |
|
|
368 |
root
|
|
369 |
^ parent
|
|
370 |
ifNil: [self]
|
|
371 |
ifNotNil: [parent root]
|
|
372 |
!
|
|
373 |
|
|
374 |
values
|
|
375 |
^ Array streamContents: [:s | self valuesDo: [:ea | s nextPut: ea]]
|
|
376 |
! !
|
|
377 |
|
|
378 |
!BTree::BTreeNode methodsFor:'enumerating'!
|
|
379 |
|
|
380 |
allChildrenDo: aBlock
|
|
381 |
self childrenDo:
|
|
382 |
[:ea |
|
|
383 |
aBlock value: ea.
|
|
384 |
ea allChildrenDo: aBlock]
|
|
385 |
!
|
|
386 |
|
|
387 |
allLeavesDo: aBlock
|
|
388 |
self withAllChildrenDo: [:ea | ea isLeaf ifTrue: [aBlock value: ea]]
|
|
389 |
!
|
|
390 |
|
|
391 |
childrenDo: aBlock
|
|
392 |
self subclassResponsibility
|
|
393 |
!
|
|
394 |
|
|
395 |
keysAndValuesDo: aBlock
|
2466
|
396 |
keys withIndexDo:
|
|
397 |
[:key :i |
|
|
398 |
key notNil ifTrue: [aBlock value: key value: (self at: i)]]
|
|
399 |
|
|
400 |
"Modified: / 08-08-2010 / 14:39:17 / cg"
|
2281
|
401 |
!
|
|
402 |
|
|
403 |
keysDo: aBlock
|
2586
|
404 |
keys withIndexDo:[:key :i |
|
|
405 |
key isNil ifTrue:[^ self].
|
|
406 |
aBlock value: key
|
|
407 |
]
|
|
408 |
|
|
409 |
"Modified: / 02-08-2011 / 09:17:49 / cg"
|
2281
|
410 |
!
|
|
411 |
|
|
412 |
leavesFrom: start to: end do: aBlock
|
|
413 |
self subclassResponsibility
|
|
414 |
!
|
|
415 |
|
|
416 |
valuesDo: aBlock
|
|
417 |
self keysAndValuesDo: [:k :v | aBlock value: v]
|
|
418 |
!
|
|
419 |
|
|
420 |
withAllChildrenDo: aBlock
|
|
421 |
aBlock value: self.
|
|
422 |
self allChildrenDo: aBlock.
|
|
423 |
! !
|
|
424 |
|
|
425 |
!BTree::BTreeNode methodsFor:'inserting'!
|
|
426 |
|
|
427 |
insertKey: aMagnitude value: anObject
|
|
428 |
| index key |
|
|
429 |
index _ keys findIndexForKey: aMagnitude.
|
|
430 |
index = 0 ifTrue:
|
|
431 |
[self canGrow
|
|
432 |
ifTrue:
|
|
433 |
[self shiftRightFrom: 1.
|
|
434 |
^ self insertKey: aMagnitude value: anObject at: 1]
|
|
435 |
ifFalse:
|
|
436 |
[self split.
|
|
437 |
^ (parent childForKey: aMagnitude) insertKey: aMagnitude value: anObject]].
|
|
438 |
|
|
439 |
key _ keys at: index.
|
|
440 |
key = aMagnitude ifTrue:
|
|
441 |
[^ self insertKey: aMagnitude value: anObject at: index].
|
|
442 |
index < self size ifTrue:
|
|
443 |
[key _ keys at: index + 1.
|
|
444 |
key
|
|
445 |
ifNil: [^ self insertKey: aMagnitude value: anObject at: index+1]
|
|
446 |
ifNotNil:
|
|
447 |
[self canGrow ifTrue:
|
|
448 |
[self shiftRightFrom: index+1.
|
|
449 |
^ self insertKey: aMagnitude value: anObject at: index+1]]].
|
|
450 |
|
|
451 |
"otherwise"
|
|
452 |
self split.
|
|
453 |
^ (parent childForKey: aMagnitude) insertKey: aMagnitude value: anObject
|
|
454 |
! !
|
|
455 |
|
|
456 |
!BTree::BTreeNode methodsFor:'private'!
|
|
457 |
|
|
458 |
ensureParent
|
2699
|
459 |
parent isNil ifTrue:[
|
|
460 |
parent := BTreeInteriorNode keys: keys emptyCopy.
|
|
461 |
parent insertKey: self firstKey value: self
|
|
462 |
].
|
|
463 |
^ parent
|
|
464 |
|
|
465 |
"Modified: / 18-11-2011 / 14:11:11 / cg"
|
2281
|
466 |
!
|
|
467 |
|
|
468 |
grow
|
4314
|
469 |
| sibling |
|
|
470 |
|
|
471 |
parent notNil ifTrue:[
|
|
472 |
sibling := parent nextSiblingForChild: self.
|
|
473 |
sibling isNil ifTrue: ["we're the new root" parent := nil. ^ self].
|
|
474 |
sibling canShrink ifTrue: [
|
|
475 |
self stealFrom: sibling
|
|
476 |
] ifFalse: [
|
|
477 |
self mergeWith: sibling
|
|
478 |
]
|
|
479 |
]
|
2466
|
480 |
|
2699
|
481 |
"Modified: / 18-11-2011 / 14:29:49 / cg"
|
4314
|
482 |
"Modified (format): / 10-02-2017 / 15:16:10 / cg"
|
2281
|
483 |
!
|
|
484 |
|
|
485 |
insertKey: aMagnitude value: anObject at: index
|
|
486 |
keys at: index put: aMagnitude.
|
|
487 |
self at: index put: anObject
|
|
488 |
!
|
|
489 |
|
|
490 |
keys: anArray
|
|
491 |
keys _ anArray
|
|
492 |
!
|
|
493 |
|
|
494 |
mergeWith: aNode
|
|
495 |
| oldKey |
|
|
496 |
oldKey _ self firstKey.
|
|
497 |
aNode keysAndValuesDo:
|
|
498 |
[:k :v |
|
|
499 |
self insertKey: k value: v].
|
|
500 |
parent removeKey: aNode firstKey.
|
|
501 |
parent updateKey: oldKey to: self firstKey.
|
|
502 |
!
|
|
503 |
|
|
504 |
shiftLeftTo: index
|
|
505 |
keys shiftLeftTo: index.
|
|
506 |
index to: self size - 1 by: 1 do:
|
|
507 |
[:i |
|
|
508 |
self at: i put: (self at: i+1)].
|
|
509 |
self at: self size put: nil.
|
|
510 |
!
|
|
511 |
|
|
512 |
shiftRightFrom: index
|
|
513 |
keys shiftRightFrom: index.
|
|
514 |
self size to: index+1 by: -1 do:
|
|
515 |
[:i |
|
|
516 |
self at: i put: (self at: i-1)]
|
|
517 |
!
|
|
518 |
|
|
519 |
split
|
|
520 |
| other midpoint |
|
|
521 |
other _ self class keys: keys emptyCopy.
|
|
522 |
midpoint _ self size // 2 + 1.
|
|
523 |
midpoint to: self size do:
|
|
524 |
[:i |
|
|
525 |
other insertKey: (keys at: i) value: (self at: i) at: (i - midpoint + 1).
|
|
526 |
keys at: i put: nil.
|
|
527 |
self at: i put: nil].
|
|
528 |
|
|
529 |
self ensureParent insertKey: other firstKey value: other
|
|
530 |
!
|
|
531 |
|
|
532 |
stealFrom: aNode
|
2466
|
533 |
| key value |
|
|
534 |
aNode firstKey > self firstKey
|
|
535 |
ifTrue: [value := aNode at: 1. key := aNode firstKey]
|
|
536 |
ifFalse:
|
|
537 |
[aNode keysAndValuesDo: [:k :v | key := k. value := v].
|
|
538 |
parent notNil ifTrue: [parent updateKey: self firstKey to: key]].
|
|
539 |
self insertKey: key value: value.
|
|
540 |
aNode removeKey: key
|
|
541 |
|
|
542 |
"Modified: / 08-08-2010 / 14:39:50 / cg"
|
2281
|
543 |
! !
|
|
544 |
|
|
545 |
!BTree::BTreeNode methodsFor:'removing'!
|
|
546 |
|
|
547 |
removeKey: aMagnitude
|
2466
|
548 |
| index key |
|
|
549 |
self canShrink ifFalse: [self grow].
|
|
550 |
|
|
551 |
index := keys findIndexForKey: aMagnitude.
|
|
552 |
key := keys at: index.
|
|
553 |
key = aMagnitude ifFalse: [^ self error: 'No such key'].
|
|
554 |
|
|
555 |
self shiftLeftTo: index.
|
|
556 |
|
|
557 |
index = 1 ifTrue: [parent notNil ifTrue: [parent updateKey: key to: self firstKey]]
|
|
558 |
|
|
559 |
"Modified: / 08-08-2010 / 14:39:29 / cg"
|
2281
|
560 |
! !
|
|
561 |
|
|
562 |
!BTree::BTreeNode methodsFor:'testing'!
|
|
563 |
|
|
564 |
canGrow
|
|
565 |
^ keys canGrow
|
|
566 |
!
|
|
567 |
|
|
568 |
canShrink
|
|
569 |
^ keys canShrink
|
|
570 |
!
|
|
571 |
|
|
572 |
isLeaf
|
|
573 |
self subclassResponsibility
|
|
574 |
! !
|
|
575 |
|
|
576 |
!BTree::BTreeNode::BTreeInteriorNode class methodsFor:'documentation'!
|
|
577 |
|
|
578 |
documentation
|
|
579 |
"
|
|
580 |
[author:]
|
|
581 |
Avi Bryant
|
|
582 |
|
|
583 |
[license:]
|
|
584 |
Dual licensed under both SqueakL and MIT.
|
|
585 |
This enables both base Squeak inclusion and 100% reuse.
|
|
586 |
"
|
|
587 |
! !
|
|
588 |
|
2803
|
589 |
!BTree::BTreeNode::BTreeInteriorNode methodsFor:'accessing'!
|
2281
|
590 |
|
|
591 |
childForKey: aMagnitude
|
|
592 |
| index |
|
|
593 |
index _ keys findIndexForKey: aMagnitude.
|
|
594 |
index = 0 ifTrue:
|
|
595 |
[keys at: 1 put: aMagnitude.
|
|
596 |
^ self at: 1].
|
|
597 |
^ self at: index
|
|
598 |
|
|
599 |
!
|
|
600 |
|
|
601 |
existingChildForKey: aMagnitude
|
|
602 |
"Unlike #childForKey:, this method looks for a child, but doesn't mess with the tree if it doesn't exist."
|
|
603 |
| index |
|
|
604 |
index _ keys findIndexForKey: aMagnitude.
|
|
605 |
index = 0
|
|
606 |
ifTrue: [^ nil]
|
|
607 |
ifFalse: [^ self at: index].
|
|
608 |
!
|
|
609 |
|
|
610 |
existingLeafForKey: aMagnitude
|
|
611 |
"Unlike #leafForKey:, this method looks for a leaf but doesn't mess with the tree if it doesn't exist."
|
|
612 |
| child |
|
2466
|
613 |
child := self existingChildForKey: aMagnitude.
|
4210
|
614 |
^ child notNil
|
|
615 |
ifTrue: [child existingLeafForKey: aMagnitude]
|
|
616 |
ifFalse:[nil]
|
2466
|
617 |
|
4210
|
618 |
"Modified: / 19-11-2016 / 12:20:31 / cg"
|
2281
|
619 |
!
|
|
620 |
|
2803
|
621 |
insertKey: aMagnitude value: anObject at: index
|
|
622 |
super insertKey: aMagnitude value: anObject at: index.
|
|
623 |
anObject parent: self
|
|
624 |
!
|
|
625 |
|
|
626 |
updateKey: oldMagnitude to: newMagnitude
|
|
627 |
keys withIndexDo:
|
|
628 |
[:key :i |
|
|
629 |
key = oldMagnitude ifTrue:
|
|
630 |
[(i = 1 and: [parent notNil]) ifTrue:
|
|
631 |
[parent updateKey: oldMagnitude to: newMagnitude].
|
|
632 |
^ keys at: i put: newMagnitude]].
|
|
633 |
self error: 'No such key'
|
|
634 |
! !
|
|
635 |
|
|
636 |
!BTree::BTreeNode::BTreeInteriorNode methodsFor:'enumerating'!
|
|
637 |
|
|
638 |
childrenDo: aBlock
|
|
639 |
self valuesDo: aBlock
|
|
640 |
!
|
|
641 |
|
|
642 |
leavesFrom: start to: end do: aBlock
|
|
643 |
| startIndex endIndex |
|
|
644 |
startIndex _ (keys findIndexForKey: start) max: 1.
|
|
645 |
endIndex _ (keys findIndexForKey: end).
|
|
646 |
startIndex to: endIndex do: [:i | (self at: i) leavesFrom: start to: end do: aBlock]
|
|
647 |
! !
|
|
648 |
|
|
649 |
!BTree::BTreeNode::BTreeInteriorNode methodsFor:'misc'!
|
|
650 |
|
|
651 |
commonKeysWith: aNode keysAndValuesDo: aBlock flip: aBoolean
|
3041
|
652 |
| index |
|
|
653 |
aNode firstKey < self firstKey ifTrue: [^ aNode commonKeysWith: self keysAndValuesDo: aBlock flip: aBoolean not].
|
|
654 |
index := (keys findIndexForKey: aNode firstKey) max: 1.
|
|
655 |
index to: self size do: [:i |
|
|
656 |
|c|
|
|
657 |
|
|
658 |
(c := self at: i) notNil ifTrue:[
|
|
659 |
c commonKeysWith: aNode keysAndValuesDo: aBlock flip: aBoolean
|
|
660 |
]
|
|
661 |
]
|
2803
|
662 |
! !
|
|
663 |
|
|
664 |
!BTree::BTreeNode::BTreeInteriorNode methodsFor:'queries'!
|
|
665 |
|
|
666 |
depth
|
|
667 |
^ 1 + self firstChild depth
|
|
668 |
!
|
|
669 |
|
2281
|
670 |
firstChild
|
|
671 |
self childrenDo: [:ea | ^ ea].
|
|
672 |
self error: 'No children'.
|
|
673 |
!
|
|
674 |
|
|
675 |
isLeaf
|
|
676 |
^ false
|
|
677 |
!
|
|
678 |
|
|
679 |
leafForKey: aMagnitude
|
|
680 |
^ (self childForKey: aMagnitude) leafForKey: aMagnitude
|
|
681 |
!
|
|
682 |
|
|
683 |
nextSiblingForChild: aNode
|
|
684 |
| index |
|
|
685 |
index _ keys findIndexForKey: aNode firstKey.
|
|
686 |
^ (index = self size or: [(keys at: index+1) isNil])
|
|
687 |
ifTrue: [index = 1 ifFalse: [self at: index - 1] ifTrue: [nil]]
|
|
688 |
ifFalse: [self at: index + 1]
|
|
689 |
! !
|
|
690 |
|
|
691 |
!BTree::BTreeLeafNode class methodsFor:'documentation'!
|
|
692 |
|
|
693 |
documentation
|
|
694 |
"
|
|
695 |
[author:]
|
|
696 |
Avi Bryant
|
|
697 |
|
|
698 |
[license:]
|
|
699 |
Dual licensed under both SqueakL and MIT.
|
|
700 |
This enables both base Squeak inclusion and 100% reuse.
|
|
701 |
"
|
|
702 |
! !
|
|
703 |
|
|
704 |
!BTree::BTreeLeafNode methodsFor:'as yet unclassified'!
|
|
705 |
|
|
706 |
childrenDo: aBlock
|
|
707 |
"no children"
|
|
708 |
!
|
|
709 |
|
|
710 |
commonKeysWith: aNode keysAndValuesDo: aBlock flip: aBoolean
|
2395
|
711 |
| index key block leaf advanceKey last |
|
4112
|
712 |
|
4111
|
713 |
aBoolean
|
|
714 |
ifTrue: [ block := [:k :v1 :v2 | aBlock value: k value: v2 value: v1] ]
|
|
715 |
ifFalse: [ block := aBlock ].
|
2281
|
716 |
|
2699
|
717 |
index := 0.
|
|
718 |
advanceKey :=
|
|
719 |
[index := index + 1.
|
2395
|
720 |
index > self size ifTrue: [^ self].
|
2699
|
721 |
key := keys at: index.
|
|
722 |
key isNil ifTrue: [^ self]].
|
|
723 |
last := self lastKey.
|
2395
|
724 |
|
|
725 |
advanceKey value.
|
2396
|
726 |
[key < aNode firstKey] whileTrue: [advanceKey value ].
|
2395
|
727 |
|
|
728 |
[
|
2699
|
729 |
leaf := aNode existingLeafForKey: key.
|
2396
|
730 |
leaf lastKey < key
|
|
731 |
ifTrue: [advanceKey value ]
|
|
732 |
ifFalse:[
|
|
733 |
leaf keysAndValuesDo: [:otherKey :otherValue |
|
|
734 |
otherKey > last ifTrue: [^ self].
|
|
735 |
[key < otherKey] whileTrue: [advanceKey value ].
|
|
736 |
key = otherKey ifTrue: [block value: key value: (self at: index) value: otherValue]
|
|
737 |
].
|
|
738 |
key > leaf lastKey ifFalse: [advanceKey value ]
|
|
739 |
]
|
2395
|
740 |
] loop
|
2699
|
741 |
|
|
742 |
"Modified (format): / 18-11-2011 / 14:10:45 / cg"
|
2281
|
743 |
!
|
|
744 |
|
|
745 |
existingLeafForKey: aMagnitude
|
|
746 |
^ self
|
|
747 |
!
|
|
748 |
|
|
749 |
keys
|
|
750 |
^ Array streamContents: [:s | self keysDo: [:ea | s nextPut: ea]]
|
|
751 |
!
|
|
752 |
|
|
753 |
lastKey
|
|
754 |
| last |
|
|
755 |
last _ nil.
|
|
756 |
self keysDo: [:k | last _ k].
|
|
757 |
^ last
|
|
758 |
!
|
|
759 |
|
|
760 |
leafForKey: aMagnitude
|
|
761 |
^ self
|
|
762 |
!
|
|
763 |
|
|
764 |
leavesFrom: start to: end do: aBlock
|
|
765 |
aBlock value: self
|
|
766 |
!
|
|
767 |
|
|
768 |
valueForKey: aMagnitude ifAbsent: errorBlock
|
2393
|
769 |
| i |
|
|
770 |
i _ keys findIndexForKey: aMagnitude.
|
|
771 |
(i > 0 and: [(keys at: i) = aMagnitude])
|
|
772 |
ifTrue: [^ self at: i].
|
|
773 |
^ errorBlock value
|
2281
|
774 |
!
|
|
775 |
|
|
776 |
valueForKey: aMagnitude ifPresent: aBlock
|
2394
|
777 |
^ aBlock value: (self valueForKey: aMagnitude ifAbsent: [nil])
|
2281
|
778 |
! !
|
|
779 |
|
2803
|
780 |
!BTree::BTreeLeafNode methodsFor:'queries'!
|
|
781 |
|
|
782 |
depth
|
|
783 |
^ 1
|
|
784 |
!
|
|
785 |
|
|
786 |
isLeaf
|
|
787 |
^ true
|
|
788 |
! !
|
|
789 |
|
2281
|
790 |
!BTree::BTreeStringKeys class methodsFor:'as yet unclassified'!
|
|
791 |
|
|
792 |
new
|
|
793 |
^ self new: 8
|
|
794 |
!
|
|
795 |
|
|
796 |
new: aNumber
|
|
797 |
^ self basicNew initializeWithSize: aNumber
|
|
798 |
! !
|
|
799 |
|
|
800 |
!BTree::BTreeStringKeys class methodsFor:'documentation'!
|
|
801 |
|
|
802 |
documentation
|
|
803 |
"
|
|
804 |
[author:]
|
|
805 |
Avi Bryant
|
|
806 |
|
|
807 |
[license:]
|
|
808 |
Dual licensed under both SqueakL and MIT.
|
|
809 |
This enables both base Squeak inclusion and 100% reuse.
|
|
810 |
"
|
|
811 |
! !
|
|
812 |
|
|
813 |
!BTree::BTreeStringKeys methodsFor:'as yet unclassified'!
|
|
814 |
|
|
815 |
abbreviationSize
|
|
816 |
^ 3
|
|
817 |
!
|
|
818 |
|
|
819 |
abbreviationsAndIndicesDo: aBlock
|
|
820 |
| stream |
|
|
821 |
stream _ abbreviations readStream.
|
|
822 |
1 to: self size do:
|
|
823 |
[:i |
|
|
824 |
stream atEnd
|
|
825 |
ifFalse: [aBlock value: prefix, (stream next: self abbreviationSize) value: i]
|
|
826 |
ifTrue: [aBlock value: nil value: i]]
|
|
827 |
!
|
|
828 |
|
|
829 |
at: aNumber
|
|
830 |
^ keys at: aNumber
|
|
831 |
!
|
|
832 |
|
|
833 |
at: aNumber put: aString
|
|
834 |
keys at: aNumber put: aString.
|
|
835 |
prefix _ self nilPrefix.
|
|
836 |
!
|
|
837 |
|
|
838 |
buildAbbreviationsFrom: readStreams
|
|
839 |
| nextChars |
|
|
840 |
1 to: self abbreviationSize do:
|
|
841 |
[:i |
|
|
842 |
nextChars _ readStreams collect: [:ea | ea next ifNil: [Character value: 0]].
|
|
843 |
nextChars withIndexDo:
|
|
844 |
[:c :j |
|
|
845 |
abbreviations at: (j-1 * self abbreviationSize) + i put: c]].
|
|
846 |
^ abbreviations
|
|
847 |
!
|
|
848 |
|
|
849 |
extractPrefixFrom: readStreams
|
3118
|
850 |
| prefixStream nextChars |
|
4098
|
851 |
prefixStream := '' writeStream.
|
3118
|
852 |
|
|
853 |
[readStreams anySatisfy: [:ea | ea atEnd]] whileFalse:
|
|
854 |
[nextChars _ readStreams collect: [:ea | ea next].
|
|
855 |
(nextChars conform: [:ea | ea = nextChars first])
|
|
856 |
ifTrue: [prefixStream nextPut: nextChars first]
|
|
857 |
ifFalse: [readStreams do: [:ea | ea skip: -1]. ^ prefixStream contents]].
|
|
858 |
^ prefixStream contents
|
2281
|
859 |
!
|
|
860 |
|
|
861 |
findIndexForKey: aString
|
|
862 |
| stream str diff |
|
|
863 |
prefix = self nilPrefix ifTrue: [self rebuildAbbreviations].
|
|
864 |
stream _ aString readStream.
|
|
865 |
str _ stream nextAvailable: prefix size + self abbreviationSize.
|
|
866 |
diff _ prefix size + self abbreviationSize - str size.
|
|
867 |
str _ str, (String new: diff).
|
|
868 |
self abbreviationsAndIndicesDo:
|
|
869 |
[:abbr :i |
|
2699
|
870 |
abbr isNil ifTrue: [^ i - 1].
|
2281
|
871 |
str < abbr ifTrue: [^ i - 1].
|
|
872 |
str = abbr ifTrue: [^ super findIndexForKey: aString]].
|
|
873 |
^ self size
|
2699
|
874 |
|
|
875 |
"Modified: / 18-11-2011 / 14:30:07 / cg"
|
2281
|
876 |
!
|
|
877 |
|
|
878 |
initializeWithSize: aNumber
|
|
879 |
keys _ Array new: aNumber.
|
|
880 |
prefix _ self nilPrefix.
|
|
881 |
!
|
|
882 |
|
|
883 |
nilPrefix
|
|
884 |
^ '^^^'
|
|
885 |
!
|
|
886 |
|
|
887 |
rebuildAbbreviations
|
|
888 |
| keyStreams filled |
|
|
889 |
filled _ keys count: [:ea | ea notNil].
|
|
890 |
abbreviations _ String new: (filled * self abbreviationSize).
|
|
891 |
filled = 0 ifTrue: [prefix _ ''. ^ self ].
|
|
892 |
keyStreams _ (1 to: filled) collect: [:i | (keys at: i) readStream].
|
|
893 |
|
|
894 |
prefix _ self extractPrefixFrom: keyStreams.
|
|
895 |
abbreviations _ self buildAbbreviationsFrom: keyStreams.
|
|
896 |
!
|
|
897 |
|
|
898 |
size
|
|
899 |
^ keys size
|
|
900 |
! !
|
|
901 |
|
|
902 |
!BTree class methodsFor:'documentation'!
|
|
903 |
|
4111
|
904 |
version
|
|
905 |
^ '$Header$'
|
|
906 |
!
|
|
907 |
|
2281
|
908 |
version_CVS
|
4098
|
909 |
^ '$Header$'
|
2281
|
910 |
! !
|
3016
|
911 |
|