Integer bTree Implementation

BlitzMax Forums/BlitzMax Programming/Integer bTree Implementation

beanage

(Posted 2009) [#1]

Hey, thought you might find this useful?

Its a very straightforward binary tree, but unlike the TMap it takes integers as values and keys. I was fed up with this String.FromInt/ToInt. Currently only for little Endian.

[Edit:] Added a GetNumElements Function, removed some white spaces

'------------------------------------------------------------------
'Simple binary tree implementation (32b little endian integer keys)
'------------------------------------------------------------------

'#####################
'      C 2009 by
'    B.e.A.n.A.g.e.
'       L.a.b.s.
'#####################

'History:
'------------------------------------------------------------------
'1.0 < Release
'1.1 < Added BTreeGetNumElements(); reformatted code
'------------------------------------------------------------------

SuperStrict

Type BTree

	'Everything in here is absolutely private!
	Field _0		:BTree
	Field _1		:BTree
	
	Field _count	:Int	= 0
	
	Field _key		:Int	= 0
	Field _value	:Int	= 0
	Field _level	:Int	= -1
	
	Method _Insert0( key_:Int,value_:Int )
	
		If _0
			_0._Insert	key_, value_
			
		Else
			_0		= New BTree
			_0._key	= _key
			_0._level	= _level+ 1
			_0._Insert	key_, value_
			
		End If
	
	End Method
	
	Method _Insert1( key_:Int,value_:Int )
	
		If _1
			_1._Insert	key_, value_
			
		Else
			_1		= New BTree
			_1._key	= _key| ( 1 Shl ( _level+ 1 ) )
			_1._level	= _level+ 1
			_1._Insert	key_, value_
			
		End If
	
	End Method
	
	Method _ValueForKey:Int( key_:Int ) 'key here shifts right by level
	
		If ( key_& ( _key Shr _level ) )= key_	Return	_value
		
		Local	next_	:Int	= key_ Shr ( _level> -1 )
		If ( next_& 1 ) And _1
			Return	_1._ValueForKey( next_ )
			
		ElseIf _0
			If _level	= 31	DebugStop(); Return	0
			Return	_0._ValueForKey( next_ )
		
		End If
		
		Return	0
	
	End Method
	
	Method _Insert( key_:Int,value_:Int )
	
		_count	:+ 1
		
		If _key= key_	_value= value_; Return
		
		Local	next_	:Int	= key_ Shr ( ( ( _level> -1 )* _level )+ ( _level> -1 ) )
		If next_& 1
			_Insert1	key_, value_
		Else
			_Insert0	key_, value_
		End If
	
	End Method

End Type

'Thats the public stuff

Function CreateBTree:BTree()

	Return New BTree

End Function

Function BTreeInsert( tree_:BTree, key_:Int, value_:Int )

	tree_._Insert	key_, value_

End Function

Function BTreeValueForKey:Int( tree_:BTree, key_:Int )

	Return tree_._ValueForKey( key_ )

End Function

Function BTreeGetNumElements:Int( tree_:BTree )

	Return tree_._count

End Function

P.S.: How can I put something into the codearchs?

plash

(Posted 2009) [#2]

P.S.: How can I put something into the codearchs?

Go to the Code Archives page, click a category, and hit the link near the top of the page.

EDIT: Might I just add one little note: Your formatting makes the code very hard to read.

beanage

(Posted 2009) [#3]

Your formatting makes the code very hard to read.

Do you mean the _* / *_ variable notation, or the missing parentheses for imperatives? .. propably both? I actually found this notation to be really handy (*_ for params, _* for private Methods and Fields). Those missing parantheses are lazyness indeed.

dmaz	(Posted 2009) [#4]

for me it's not the parentheses, I myself tend to only use them when needed. it's all the white space everywhere and all underscores.

plash

(Posted 2009) [#5]

Particularly the unnecessary whitespace and, yes, your use of underscores. Usually non-parentheses'ing calls to methods or functions isn't an issue, but I find it best to use them on every calls, whether it returns a value or not.

beanage

(Posted 2009) [#6]

I previously programmed in lisp, and.. I just enjoy it when I dont have to type brackets.. nevermind me.

This underscore notation can lead to horrible typos in addition. The reason I do it, is this:

In the first place, what I hate to do, is using some odd name for a method parameter, because otherwise I would get double identifier errors. The underscore notation resolves this.
Second, it clarifies: When you type an underscore, you access something private, and if the _* is right its a private member, and if it is *_ left, it is a parameter.
Last but not least, you never have to worry about whether the local identifier you just declare might be in use anywhere else in a distant inclusion or inherited type, etc.

[Edit:] Oh, and it allowed me for this [_0], [_1] nice notation^^ :)

plash

(Posted 2009) [#7]

I use m_* for fields and no prefix or affix for variables or parameters.
Directly using underscores before or after a variable/parameter/field certainly does get confusing, which is why I don't do it.

dmaz	(Posted 2009) [#8]

you never have to worry about whether the local identifier you just declare might be in use anywhere else in a distant inclusion or inherited type

sure you do... many people do use the underscore so it's hardly any safer... personally, I'm not a fan of private variables unless the compiler implements properties. who's to say my subclass doesn't need access to those?

nice job btw.... I don't mean to beat on somebody who gives code to the community! :)

beanage

(Posted 2009) [#9]

Ok, I removed some white lines and added a BTreeGetNumElements() Function.

Czar Flavius

(Posted 2009) [#10]

You can use self as one way to avoid confusion with duplicate names.

Method duplicatenames(bob:Int)
	Self.bob = bob
End Method

Apart from setter functions (where the parameters are to set up the member variables, so it's intuitive they'd have the same name).. if you have parameters with the same name as member variables, you probably haven't chosen your names very well. For _Insert0, why not call the parameters new_key and new_value or something? Or newKey and newValue, although personally I hate that style >:)

Perhaps in the editor the tabs line up neatly, but in that codebox all the random spacing gives me a headache. :(

beanage

(Posted 2009) [#11]

Perhaps in the editor the tabs line up neatly

Yap indeed.
What is a standard tab size most ppl use? Because it really looks clean and tidy in my IDE .. another reason why I love this leaving out parentheses..

xlsior

(Posted 2009) [#12]

What is a standard tab size most ppl use?

I'm using 4 as my tab size.

To me, the most odd-looking thing about your code snippet is the whitespace between the variable and their types, for example:

	Field _0		:BTree

Pretty much everyone else just uses:

	Field _0:BTree