Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Perhaps there's a name for what I want, but I'm not aware of it. I need something similar to a LinkedHashMap in Java, but where it returns the 'previous' value if there's no value at the specified key.

That is, I have a list of objects stored by an integer key (which is in units of time in my case):

; key->value
10->A
15->B
20->C

So, if I were to query for a value for key 0-9, it would return null. The special part is if I queried for something 10 <= i <= 14 it would return A. Or, for i >= 20, it would return C.

Is there a data structure for this?

share|improve this question
    
I don't know if there is an implemented one but you could probably extend the existing one to do this. Whether it will meet your performance goals or not without a rewrite I don't know... –  Rig Oct 3 '13 at 19:11
1  
+1 for the great question. Most people with three low-digit rep ask the "please do my homework" type of question. Not the case here. –  user61852 Oct 3 '13 at 19:30

2 Answers 2

up vote 33 down vote accepted

You are looking for a NavigableMap. This is a subtype of SortedMap that also has some functions available besides the nature of the map being sorted. Note that the Navigable map "is intended to supersede the SortedMap interface." (Java SE 6 Collections Framework Enhancements). Everything that currently implements SortedMap implements NavigableMap and this is likely to remain true.

In particular, the method floorKey(K key) which "returns the greatest key less than or equal to the given key, or null if there is no such key.

This is just one of many methods that allow you to get specific keys or submaps of the map.

  • ceiling / floor (the entry that is higher / lower than the parameter)
  • access of keys or map in descending order
  • head / tail (the entries less / greater than a given key)
  • higher / lower (the next key that is higher or lower than parameter)
  • submap (given two keys, return the map that is between the two keys)

Java has two implementations of the NavigableMap - the TreeMap and the ConcurrentSkipListMap.

If you look at the idea/implementation of a skip list you will see why it would work really well with such a structure and its queries.

share|improve this answer
    
1+ great answer. Never thought such an specific Map existed in the Java API. –  user61852 Oct 3 '13 at 19:31
    
@user61852 My favorite datatype is the skip list and I poked around with it. When I saw it implemented in 1.6 I looked into what all it provided and noticed the interfaces that it had and thus my familiarity with it. –  MichaelT Oct 3 '13 at 19:33
    
That's the kind of things that convince me Java is one of the best designed languages you can find. –  user61852 Oct 3 '13 at 19:35
1  
Note that while this appears to address OP's issue, it doesn't act like the LinkedHashMap that he mentions. Neither TreeMap nor ConcurrentSkipListMap are ordered by insertion time like LinkedHashMap, rather they are ordered by a Comparator or the key's Natural Ordering if they implement Comparable. –  MikeFHay Oct 4 '13 at 12:02
1  
Very good point. The floor operation is what I was looking for, the comparator I can add easily. And in my case it works out much nicer to implement the comparator instead of reinventing the wheel. Thanks. –  Nick Oct 4 '13 at 12:58

What you are looking for is a symbol table that supports ordered operations. And in your case it is the floor operation.

The hash implementation of a symbol table is the fastest, but it doesn't offer those ordered operations.

But tree implementation of symbol tables does. An example of that in Java is the TreeMap class

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.