0

I tried to use TreeSet:

Comparator<Product> pc = (p1, p2) -> ((Double) p1.getPrice()).compareTo(p2.getPrice());
Set<Product> products = new TreeSet<>(pc);
products.add(new Product(10));
products.add(new Product(10));

but problem is that it can not contain more than one equal values in terms of Comparator, and so only one of the product will be in products set.

I need some Collection implementation, that will order newly inserted value, allow many equal(in terms of Comparator) values, and have insert complexity log(n) (possibly tree based impl)

Kysil Ivan
  • 917
  • 1
  • 7
  • 15
  • 1
    Do your products have something unique, like a productId? – assylias Feb 08 '17 at 09:27
  • Possible duplicate of [List implementation that maintains ordering](http://stackoverflow.com/questions/10675446/list-implementation-that-maintains-ordering) – shmosel Feb 08 '17 at 09:32
  • 1
    assyliad: no I dont need ID It seems that Guava TreeMultiset is fine for me, but I wonder if I can do it just using Java Collection API. – Kysil Ivan Feb 08 '17 at 09:34
  • 1
    When you say "tree-based", do you really mean *sorted*? The implementation of a collection internally shouldn't really matter to you. – Andy Turner Feb 08 '17 at 09:44
  • 1
    You might find something interesting in [Why is there no SortedList in Java?](http://stackoverflow.com/q/8725387/3788176). – Andy Turner Feb 08 '17 at 09:45
  • For a time complexity comparison for example see http://infotechgems.blogspot.de/2011/11/java-collections-performance-time.html. – René Scheibe Feb 08 '17 at 10:16

3 Answers3

4

A class in the JDK that matches your exact requirements is PriorityQueue. From the documentation:

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

And

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

You can also carry on using TreeSet but provide a Comparator that gives a unique answer. For example, if your Product has a unique name:

Comparator<Product> pc = Comparator.comparing(Product::getPrice)
                         .thenComparing(Comparator.comparing(Product::getName));

Note the use of Comparator.comparing rather than your lambda - it's neater and more robust.

Boris the Spider
  • 59,842
  • 6
  • 106
  • 166
2

In case you really need to order the elements at insert time you can use Guava's TreeMultiset.

Olivier Grégoire
  • 33,839
  • 23
  • 96
  • 137
René Scheibe
  • 1,970
  • 2
  • 14
  • 20
0

So,
PriorityQueue worked for me.

TreeMultiset did not. When I add two different objects:
products.add(new Product(10)); products.add(new Product(10));
it contains two links for first instance, and none for second()

Kysil Ivan
  • 917
  • 1
  • 7
  • 15