I wish to have a set of Objects and booleans that mark an object as "visited" or not. Naturally I thought of Map that will tell me if an object is already visited or not. But I want them to be sorted too, so that whenever I ask "Who is the 'smallest' object visited?". The calculation wouldn't be too difficult, max O(n) on that data structure. In my very specific case I'm asking about Date object, but it's irrelevant. Objects can be added to that data structure at any moment, and will be entered with 'false' values.
-
1do you need something like docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html ?Anton Sarov– Anton Sarov2015-04-29 11:55:00 +00:00Commented Apr 29, 2015 at 11:55
-
1One way to achieve it would be to write a custom comparator for your object and use a TreeSet to keep the visited data in sorted order. Maintain the visited and unvisited date objects separately.Bhoot– Bhoot2015-04-29 11:57:15 +00:00Commented Apr 29, 2015 at 11:57
Add a comment
|
3 Answers
Use a SortedSet. When an object is visited, add it to the set. To find out if an object was visited, just use set.contains(). To find the smallest object:
T smallest = set.isEmpty() ? null : set.iterator().next();
Comments
You could use a map of <Boolean, TreeSet<Object>>, where you keep all of the visited objects in the set mapped to true and visa-versa (assuming you're not dealing with duplicate objects). I believe that insertion into a TreeSet runs in O(n) time, and to get the "smallest" object visited, you would use first(), which runs in O(1) time.
Comments
What you need is guava's TreeMultiset, please read about the Multiset, a TreeMultiset implementation maintains the ordering of its elements. You can write a custom Comparator - in first place you could have most frequently visited object.
https://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained
If you use it you won't have structures like
Collection<Something, Something>
and also sorting would be out of the box after implementing a Comparator.
