TreeMultimap + duplicate key-value pairs allowed

[Leandro Costa]

I need to store samples during a certain time period, removing old samples when they get out of the configured time-window.

I was thinking about using a TreeMultimap<timestamp, Sample>, a thread running in background to remove old samples.

The problem is that it is possible to have equal samples in a same timestamp, but TreeMultimap doesn't allow duplicate key-value pairs.

Does anyone see a good solution for this problem?

[Louis Wasserman]

Not other than "ensure timestamps are unique," not really.  Or -- perhaps simplest of all -- just use a normal Queue, without resorting to tree structures at all.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

--
guava-...@googlegroups.com
Project site: http://guava-libraries.googlecode.com
This group: http://groups.google.com/group/guava-discuss
 
This list is for general discussion.
To report an issue: http://code.google.com/p/guava-libraries/issues/entry
To get help: http://stackoverflow.com/questions/ask (use the tag "guava")

[Patrick Julien]

Sounds to me like you're problem is already solved.  If a timestamp is old enough to be evicted, then it's also time to evict all values with the same key.  If you're evicting the oldest data, using map.asMap().headMap(k) will yield what you need to clear.

[Leandro Costa]

Timestamps may not be unique (a lot of events may happen inside the same timestamp).

And... yes, the best solution until now is a PriorityBlockingQueue<Map.Entry<Long, Sample>>.

This is  an acceptable solution if it's not likely to have more than one event in a same timestamp.

And it's important to have samples in order, because thet may not be enqueued in the same order of their events.

I'd like to know if guava has some collection which may be easily modified to work as a multimap with sorted keys and duplicate key-value pairs allowed (I've just read about LinkedListMultimap, but it's not what I need, since keys's order is preserved). 

[]'s

[Louis Wasserman]

I mean, you could always use

Multimaps.newListMultimap(new TreeMap<Long, Collection<Sample>>(), new Supplier<List<Sample>>() { public List<Sample> get() {return Lists.newArrayList();}});

but it's not as if you can get access to the sortedness of the Map in that case.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[David Beaumont]

Can you ensure that your keys are unique/well ordered by having a 2nd
sequence number in them (eg, using an atomic integer/long count) ?

I doesn't sound like you actually need to bucket by time stamp, just
that time stamp isn't unique enough for you.

If you could ever risk overflow of the sequence number (> 2^64 items
seems unlikely) then you'd have to reset it at some time stamp
boundary, but apart from that it should work.

public static class UniqueTimeStamp implements Comparable<UniqueTimeStamp> {
private final long timestamp;
private final int/long sequenceNumber; // unique per time stamp

... you know the rest ...

}

Just a thought,
David

--
David Beaumont :: Africa Mobile Engineering :: Google
Google Switzerland GmbH., Brandschenkestrasse 110, CH-8002, Zürich - Switzerland
Tel +41 44 668 1800 :: Fax +41 44 668 1818

[Leandro Costa]

Thanks Louis, Multimaps.newListMultimap is really great!

Taking a look at AbstractMultimap right now, and I'm just wondering if it would be a good idea to have access to the raw map structure used in its constructor.

Multimaps.newListMultimap allows us to use any java.util.Map implementation we need, but it doesn't allow us to take advantage of this implementation.

In this case, for instance, we may want to iterate by the TreeMap in descending order (since java.util.TreeMap Implements java.util.NavigableMap). What do you think?

[]'s

[Louis Wasserman]

Taking a look at AbstractMultimap right now, and I'm just wondering if it would be a good idea to have access to the raw map structure used in its constructor.

Multimaps.newListMultimap allows us to use any java.util.Map implementation we need, but it doesn't allow us to take advantage of this implementation.

In this case, for instance, we may want to iterate by the TreeMap in descending order (since java.util.TreeMap Implements java.util.NavigableMap). What do you think?

I think that's probably a bad idea.  The semantics of what the Multimaps.newListMultimap implementation actually does with the underlying Map is not specified -- and with good reason, because that implementation might change over time.

[Leandro Costa]

Yes, you are right: Multimaps.newListMultimap() may have its implementation changed,

but even so it would be necessary to keep the concrete java.util.Map unchanged inside, since it was chosen by the programmer.

Of course this is not a big deal, if it is so important to access the original Map as it is, it's still possible to maintain a reference to it.

[Louis Wasserman]

On Tue, May 22, 2012 at 10:57 AM, Leandro Costa <leandr...@gmail.com> wrote:

Yes, you are right: Multimaps.newListMultimap() may have its implementation changed,

but even so it would be necessary to keep the concrete java.util.Map unchanged inside, since it was chosen by the programmer.

Of course this is not a big deal, if it is so important to access the original Map as it is, it's still possible to maintain a reference to it.

But you shouldn't, as implied by the Javadoc: "Note: the multimap assumes complete ownership over of map and the lists returned by factory. Those objects should not be manually updated, they should be empty when provided, and they should not use soft, weak, or phantom references."

Here's an example: perhaps Multimaps.newListMultimap might keep empty Lists in the map, or it might not.  No guarantees are made on that subject, and you can't depend on how the multimap is implemented in the backing Map.

[Leandro Costa]

That's a good example, now I understand.

Thank you Louis!

[]'s