Number of Items in Map?
BlitzMax Forums/BlitzMax Beginners Area/Number of Items in Map?
| ||
| There doesn't seem to be a good way of getting the number of items in a Map. There's a method for checking if it's empty, but that isn't good enough for what I'm doing. This is roughly what I'm doing now, is there a better way? Local mvalues:TMapEnumerator = map.values() Local count:Int = 0 For Local v:String = EachIn mvalues count :+ 1 Next |
| ||
| Simplest way, depending on how you want to get this information, might be to extend TMap with a counter that increments when items are added and decrements when they are removed? Would likely be a better way if you're modifying the map frequently and also querying the size frequently. If you don't need to query the size very often, or the map doesn't change (in which case you can store the size anyway), the way you're doing it now will be fine, since performance only matters in hotspots (in which case, the readability and obviousness of this method are definite plus points). A more efficient way to actually count the items in a map without keeping a running total would be to traverse the tree structure top-down (most easily expressed recursively), rather than down-and-up-and-down-and-up... as the enumeration does. |
| ||
| That approach is what I'll go with then. I'm really curious as to how you would manually traverse the tree structure, however, for educational purposes. I use the following as a reference for BM maps http://en.wikibooks.org/wiki/BlitzMax/Modules/Data_structures/Maps It doesn't mention any way to do that, is there more complete documentation somewhere? If you say look at the sourcecode directly, I'm completely ok with that, but I would need to know where to find it for BM. |
| ||
| I'm really curious as to how you would manually traverse the tree structure, however, for educational purposes. The Wikibooks page looks largely like a copy of the BlitzMax built-in documentation, which you can get at from the IDE (sidebar -> Home tab -> Modules -> Data Structures -> doubleclick Maps). At the top of the original documentation page there's a link to the source code for the module. Then you could do something like: Function countSubtree:Int(root:TNode)
If root <> nil
Return 1 + countSubtree(root._left) + countSubtree(root._right)
Else
Return 0
EndIf
End Function
Function countMapItems:Int(m:TMap)
Return countSubtree(m._root)
End Function...which won't actually work as-is, because "nil" is private to the map module, but you can extract the value easily enough (create a new empty map and copy its _root; ta-da, you have TMap's nil value). Doing it with literal recursion like that will be quite slow, due to the large number of function calls, and possibly unsafe for large maps, due to the possibility of stack overflow; but it shows the simplest way to move down the tree. One common way to design these sorts of functions is to start with a recursive definition and then, once the basic method is clear, unwrap the recursion into a local loop (sometimes with an explicit stack; in this case you don't need one since the map contains all the data required for tracing your progress). |
| ||
| wow, I'm using BLIDE and somehow I missed that documentation, thank you for that. The map itself will never contain more than 10 items, but I'll start digging into this, just so I can get a familiarity with it. While I'm at it, do you know of any modules of data structures floating about? I've googled around and haven't really been able to come across anything, but something that has Hashtables, queues, skip lists, and so on? The list and map is good for most things, but I like having a larger variety of data structures to choose from. I've considered writing my own, but I'd really prefer to use one that's been tried and tested, if possible. |
   |