[Tmap is B-tree?]

BlitzMax Forums/BlitzMax Beginners Area/[Tmap is B-tree?]

degac(Posted 2007) [#1]
As I am completely dumb I've googled and find this link
http://slady.net/java/bt/view.php?w=450&h=300
If I correctly understand Tmap is the BlitzMax implementation of a B-Tree - the only difference is that Bmax has only two child (left and right) while the example uses three childs - well I cant' find any better solution!!!
So for everyone who want to understand how a b-tree works this link is a good point to start!

And - of course - the question: how can I retrieve (without counting them) the items in a btree? In List I have CountList() but I can't imagine/find any internal counter or method.


klepto2(Posted 2007) [#2]
Indeed this is the TMap ;)
If you want to go through the items call this

For Local T:TyourType = eachin MapValues(YourMap)
 Print T.yourField
Next


Or instead MapValues you can call MapKeys()


degac(Posted 2007) [#3]
Thanks for the answer, but I want to know if there is a Count() method like in List, or I need to iterate in the map via FOR..EACHIN MapValue/MapKeys like this example
Local counter:int
For Local T:TyourType = eachin MapValues(YourMap)
 counter:+1
Next
print "total item: "+counter



klepto2(Posted 2007) [#4]
Oh, sry It seems I have misunderstood this part ;)
Unfortunatly there is no commonway to retrieve the counter of it. But I suggest something like this:

Type TCountTMap
	Field Map:TMap = New TMap
	Field _count:Int = 0
	
	Method Insert(Key:Object , Value:Object)
		MapInsert(Map , KEy , Value)
		_count:+ 1
	End Method
	
	.
	.
	.
	
	Method Count:Int()
		Return _count
	End Method
End Type


not very elegant but maybe a bit more efficient in the end incomparisonwith iterating through the whole map to get the counter.


Perturbatio(Posted 2007) [#5]
Thanks for the answer, but I want to know if there is a Count() method like in List, or I need to iterate in the map via FOR..EACHIN


There's no in-built counting, but you could add your own:


Type TExMap Extends TMap
	
	Field count:Int
	
	Method Insert( key:Object,value:Object )
		Super.Insert(key, value)
		Count:+1
	End Method
	
	Method Remove( key:Object )
		Super.Remove(key)
		Count:-1
	End Method
	
	Method Clear()
		Super.Clear()
		Count = 0
	End Method
End Type

Global myMap:TExMap = New TExMap

myMap.Insert("test1", "value1")
myMap.Insert("test2", "value2")
myMap.Insert("test3", "value3")
myMap.Insert("test4", "value4")
myMap.Insert("test5", "value5")
myMap.Insert("test6", "value6")
Print myMap.count
myMap.Remove("test4")
Print myMap.count


*EDIT*
Spent too long writing that :)


Gabriel(Posted 2007) [#6]
TList doesn't actually have built in counting either. Well, it does in the sense that there is a method that counts so you don't have to write it yourself. But it doesn't keep a count, it manually iterates and counts them when you ask, so it's no faster than doing it yourself. I know that wasn't the question, but just in case you didn't know.


degac(Posted 2007) [#7]
@Gabriel: yes I know that CountList literally 'counts' the items in the list - so I have a separate counter to remember this.
@Klepto2 & Perturbatio: thanks very much, sweet solution!

After seeing your answers I'm still thinking that a internal counter should be implemented *officialy*, and it should be quite easy to do both for tMap and Tlist.

In any case thank you very much!
byez


Perturbatio(Posted 2007) [#8]
I would suggest using my extend method over Klepto's, mine should allow you to use functions that accept a TMap (i.e. MapValues or whatever it is) since it would be cast as a TMap


Dreamora(Posted 2007) [#9]
Not possible for lists as you can add TLinks after and before others without ever using "list.addlast" so there is no way of ensuring that it is correct.
Especially, you will better NEVER use list.remove to remove an item unless it is not speed critical. Because the fast way of doing this is storing the TLink of the item (returned when added to the list) and call TLink.remove which is a O(1) call while TList iterates and is therefor an O(n) call.

In TMap it should be possible


Otus(Posted 2007) [#10]
If you decide to count them manually, remember that EachIn skips Null values. So if you plan to store Null values, you should either use another looping method, or loop the keys instead of the values. (Assuming you don't have Null as a key, which I doubt is even possible.)