CODEWITHSUNDEEP
javatreeset
ForguesR
ForguesR

Reputation: 3618

Java non-duplicate ordered list by frequency

Is there a non-duplicate "list" implementation with order by frequency?

For instance : 

TreeSet<String> cities = new TreeSet<String>();

cities.add("NYC");    // Ordered list is [NYC]
cities.add("Boston"); // Ordered list is [Boston, NYC] (alphabetical order)
cities.add("NYC");    // Ordered list is [NYC, Boston] because NYC was added twice
cities.add("Philly"); 
cities.add("Philly");
cities.add("Philly"); // Ordered list is now [Philly, NYC, Boston]

Upvotes: 2

Views: 215

Answers (2)

kajacx
kajacx

Reputation: 12939

I don't think there is any standard library class that could effectively support such functionality. Best implementation depends on how often you want to use which operations (add, remove, find maximum, remove maximum, traverse in-order, ...).

One special case would be if you would only add and remove elements and only from time to time you would want to traverse/list all elements in order, in such case, i suggest following implementation:

For adding and removing, store your data in any Map<String, Integer> (e.g. HashMap or TreeMap) where name maps to frequency, that will allow for fast adding and removing. If you will need to list names by frequency, just pull all data to an List and sort with suitable comparator.

However, the previous implementation fails terribly if you want to for example peek the maximum element after each insertion. In such case, I would use some hybrid structure, for example combine map and heap (use both), map for fast name lookup and heap for selecting element with maximum frequency.

Upvotes: 1

Louis Wasserman
Louis Wasserman

Reputation: 198083

This is tricky with the basic JDK, and not doable with a pure Set, but if third-party libraries are fair game, you might use Guava's Multiset. The method Multisets.copyHighestCountFirst sorts a given multiset by the number of occurrences of each element.

Upvotes: 3

Related Questions