Hi Avi,

The attached changeset fixes the problem.  The cause appears to have 
been that #at: could modify the tree in a bad way if you give it a key 
smaller smaller than any already in the tree (and possibly in other 
cases; I'm not sure if these exist, what they are, and if this changeset 
addresses them).

I don't claim that this changeset provides optimal factoring of the 
code; it is just the simplest way that I thought of to fix the problem.  
I also haven't tested it extensively (I haven't even proven it correct ;-)

Sorry for not being more thorough; time is tight right now.
Josh



Joshua Gargus wrote:

> Oops, seems like there is still a problem.  Attached is some workspace 
> code with a logged sequence of adds/removes that causes an error.  I 
> don't have time to dig into it immediately, but will soon since I need 
> it working within a week.
>
> Josh
>
>
> Avi Bryant wrote:
>
>> On Thu, 23 Dec 2004 01:37:04 -0500, Joshua Gargus <schwa at fastmail.us> 
>> wrote:
>>  
>>
>>> Hi,
>>>
>>> The following code results in an error:
>>>
>>> | tree |
>>> tree := BTree new.
>>> 1 to: 15 do: [:i | tree at: i put: i].
>>> 1 to: 15 do: [:i | tree removeKey: i]
>>>   
>>
>>
>> Hi Josh,
>>
>> Sorry for the delay on this - I've integrated your (off list) fix and
>> put the result at http://beta4.com/mc/Collections-BTree-avi.43.mcz. 
>> Once SqueakMap comes back online I'll release it there too.
>>
>> Avi
>>
>>  
>>
>
>

-------------- next part --------------
'From Squeak3.7 of ''4 September 2004'' [latest update: #5989] on 17 January 2005 at 11:16:13 pm'!
"Change Set:		BTree-fixes
Date:			17 January 2005
Author:			Joshua Gargus

#at:ifAbsent: was causing problems if you look for a key smaller than any other keys in the tree; in such a case, it would cause a change in the tree.  This changeset makes it so that #at:ifAbsent: does not change the tree at all, regardless of whether the key is found."!


!BTree methodsFor: 'accessing' stamp: 'jcg 1/17/2005 23:09'!
at: aMagnitude ifAbsent: errorBlock
	| leaf |
	leaf _ root existingLeafForKey: aMagnitude.
	leaf ifNil: [^ errorBlock value].
	^ leaf valueForKey: aMagnitude ifAbsent: errorBlock! !


!BTreeInteriorNode methodsFor: 'as yet unclassified' stamp: 'jcg 1/17/2005 22:59'!
existingChildForKey: aMagnitude
	"Unlike #childForKey:, this method looks for a child, but doesn't mess with the tree if it doesn't exist."
	| index |
	index _ keys findIndexForKey: aMagnitude.
	index = 0 
		ifTrue: [^ nil]
		ifFalse: [^ self at: index].! !

!BTreeInteriorNode methodsFor: 'as yet unclassified' stamp: 'jcg 1/17/2005 23:00'!
existingLeafForKey: aMagnitude
	"Unlike #leafForKey:, this method looks for a leaf but doesn't mess with the tree if it doesn't exist."
	| child |
	child _ self existingChildForKey: aMagnitude.
	^ child ifNotNil: [child existingLeafForKey: aMagnitude]! !


!BTreeLeafNode methodsFor: 'as yet unclassified' stamp: 'jcg 1/17/2005 23:08'!
existingLeafForKey: aMagnitude
	^ self! !