On Tue, Oct 02, 2012 at 04:06:57PM +0200, Robin Haberkorn wrote:
Hey!
Secondly, arrays/maps are not the only higher-level (aggregate) data type in ChucK. There are also classes, which are well suited for record/structure-like use cases.
Yes, that is true. I meant "build in" structure but should have been more clear. I remember somebody doing a implementation of lists in a class, as a proof of concept, even.
Regarding the question of iterating maps: Of course that would be nice. But doing this by simply having a method that returns all keys as an array is inefficient, since that requires a complete traversal of the RB-tree (O(n)) to get all keys, followed by RB-tree accesses (O(log(n))) for every key. That is a complexity of O(n*(log(n) + 1)) for a complete iteration while it is theoretically possible in O(n). Doing it in O(n) however requires you to have a concept of iterators and iterator-loops, adding much complexity to the language. In the simplest case you need a special for-loop, like for (key, value in map) {...}
So, you are proposing a sort of "for-each" that would do the iterating for us? Thanks for the explanation, I had no idea it was so expensive. Kas.