support Sorted{Set,Map}s

Issue #11 new
Rob Eden created an issue

Originally reported by Jean-Daniel Fekete

Are SortedSets and Maps for primitive types planned for a futur version? I would be interested to have them for my InfoVis Toolkit (ivtk.sourceforge.net).

Original SF issue

Comments from original issue

Rob Eden

I don't think the performance of these would be all that great because a good deal of array manipulation would have to take place is we implemented it in a similar manner to the current sets/maps. However, memory usage would be better because you wouldn't need all the primitive container objects. Would this fit your purposes?

I'm hesitant because Trove is supposed to be "High performance collections", but this is a frequent request, so I'll think about it, if people aren't expecting it to be a lot faster. It's hard to beat a linked list for sorted structures... but the current method is much nicer on the garbage collector.

Anyway... maybe if you could talk about your goals for such a structure more it would be helpful.

Jean-Daniel Fekete

A Toolkit for Information Visualization has to maintain data structures in memory to allow for fast display and filtering. You can think of it as an in-memory database, except that the tables are column-oriented instead of row-oriented because adding a new column (attribute) is frequent.

Just like databases, I need to maintain indexes on the contents of my columns. Since range queries are very important, having a sorted indexing is very important too. Java red-black trees are almost ok except they don't support duplicate keys and they use objects as keys, not primitive types.

As you write, not much speedup could be expected but completeness is important I think. Otherwise, I'd have to do it by myself. The prefuse toolkit implemented some of it too (prefuse.sf.net in the utils.collections package) so it really seems useful for lots of people.

Rob Eden

I'm going to try to do some playing around to see if I can make this perform well.

Adnan Memon

Any updates on this? Do we have one in 3.x version of Trove?

Rob Eden

Nothing to report. Still an open feature request.

Comments (1)

  1. Log in to comment