Win a copy of GANs in ActionE this week in the AI forum
or WebAssembly in Action in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
  • Knute Snortum
Sheriffs:
  • Liutauras Vilda
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Joe Ess
  • salvin francis
  • fred rosenberger

Sorted Collection that allows duplicates?

 
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

After a short troubleshooting session where I couldn't understand why my in-my-eyes sorted PriorityQueue spat out it's elements in an unsorted manner I read the javadoc and realized that the iterator of the PriorityQueue is free to return elements in any order it likes basically. In other words, a PriorityQueue can't be regarded as a sorted Collection. The reason a TreeSet is not an option is that i need the collection to allow duplicates. And I want it to always be sorted, without using Collections.sort().

I'm not gonna ask about the reasons for this behavior of the PriorityQueue, since the discussion here covers that quite nicely. What I do want to ask, however, is if there are any alternatives out there that I don't know of?

So, to summarize, what I need is a Collection that:

  • allows duplicates
  • is always sorted (by natural order or a Comparator)
  • the Iterator gives me the elements in sorted order


  • Is there such a Collection in the Java API? Or are my requirements too far-fetched? Any suggestions on the best and cleanest way to solve this? And performance is not a concern for me, since in total the collection will never contain more then say a few hundred elements.

    Regards
    /Jimi
     
    Marshal
    Posts: 67412
    257
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I think you are going to have to write your own. What you describe is a List which takes natural ordering rather than insertion order as its ordering. Write a wrapper around a List implementation; use a binary search to find the insertion point in your add(E) method and throw anUnsupportedOperationException from the add(int, E) method. Note your wrapper class will have to implement the List<E> interface too. The add(E) method will run in logn time at the very best.
     
    Sheriff
    Posts: 21842
    105
    Eclipse IDE Spring VI Editor Chrome Java Ubuntu Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:and throw anUnsupportedOperationException from the add(int, E) method. Note your wrapper class will have to implement the List<E> interface too.


    The wrapper class doesn't need to implement List; implement Collection instead. List adds three things that Collection doesn't have:
    1) a specified order
    2) indexing of elements
    3) moving both forward and backward with the ListIterator

    Since you probably won't need 2 or 3, the wrapper only needs to implement Collection. If you implement List you are making it harder for yourself, because add(int, E) isn't the only place where you can break your sorted ordering:
    - addAll(int, Collection) also allows adding at any location (another UnsupportedOperationException)
    - set(int) allows you to overwrite an element with any other element(another UnsupportedOperationException)
    - you need to protect the List returned by subList as well (you can wrap that in a new wrapper instance)
    - you need to protect your ListIterator, it allows adding and replacing elements as well (you'll need another wrapper class)

    And what does List give you that you may want? get(int), indexOf(Object), lastIndexOf(Object), subList(int, int). But do you really need those? Collection doesn't have them, Set doesn't have them, (Priority)Queue doesn't have them.
     
    Jimi Svedenholm
    Ranch Hand
    Posts: 53
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    OK, I have been thinking some more, and have a few options to choose between:

  • 1. Create a new Collection class, keep an internal List and make sure all adds happens at the appropriate index
  • 2. Create a new Iterable class and keep an internal TreeSet<List><T>>
  • 3. Create a new Comparator class that only returns 0 when the elements really are equal according to equals(), then use this comparator together with a TreeSet


  • Option 3 was my first thought, since In my mind that should be quite easy. But it turned out that it was in fact not so easy. What I am trying to sort are objects that implement the interface org.springframework.core.Ordered. There is already a Comparator for Ordered-objects, however if the order number of both objects are the same then the comparator simply returns 0. But I only want it to return 0 if the objects really are equal each other. Because there will be Ordered objects that are far from equal, but with the same order number. If the comparator returns 0 then the TreeSet regards these objects to be equal.

    The problem I'm having is to decide if element e1 should be considered less then or greater then element e2 when e1.getOrder() == e2.getOrder(). What I have done now, in a test implementation, is:

  • A: If e1.equals(e2) return 0
  • B: Otherwise, if compare(e1.getValue(), e2.getValue()) is non-0, return it
  • C: Otherwise, if e1 and e2 implements Comparable and c1.compareTo(e1) is non-0, return it
  • D: Otherwise, do a compare of the hash codes, if non-0 then return it
  • E: [We can assume that we get here quite rarely] Otherwise, compare hashcodes of the element class objects, if non-0 then return it
  • F: Otherwise, we have any more ways of comparing the elements, so we return -1 just in order to return *something*, and not returning 0


  • I have no problem with the somewhat complex steps involved, since it will rarely go all the way down to E or F asuming good hashcode implementations. The problem I have is with last step, F. Because it breaks the contract of Comparable. If a compare(e1, e2) comes down to F, then the result is -1, but the result of compare(e2, e1) is *also* -1! Even if this will hardly ever happen, it *can* happen.

    What do you guys think about this Comparator? It felt "just wrong" when I wrote it, but I also don't like the way that org.springframework.core.OrderComparator is written since it can consider non-equal objects (as by o1.equals(o2)) to be equal (by returning 0). Or, when I think about it, my *real* pet peve is the Set interface, that clearly states that it regards objects as equal if the compare/compareTo results in 0. What it should do, if you ask me, is to do a subsequent call o1.equals(o2) and only consider them as duplicates if it returns true.

    But since the Set-implementations aren't gonna change any time soon (or not at all) in this regard, I'm starting to lean to option 2 above since it is simpler then option 1 and cleaner then option 3.

    /Jimi
     
    Campbell Ritchie
    Marshal
    Posts: 67412
    257
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    A Comparator consistent with equals does sound a good idea, but if you use it with a TreeSet you won't get any duplicates.
     
    Jimi Svedenholm
    Ranch Hand
    Posts: 53
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:A Comparator consistent with equals does sound a good idea, but if you use it with a TreeSet you won't get any duplicates.



    Well, there are two different kinds of equality/duplicity here*. A comparator considers two elements equal if the "compare-calculation" results in 0. And this is apparently the only equals-check that a SortedSet does. But the way I see it, this narrow definition of equals is inadequate. The objects are only "equal" in the eyes of the comparator, but the SortedSet should only use the comparator for sorting, not duplicity checks. If two elements have a "compareTo-result" of 0 but where equals() returns false then it should simply regard that as "not duplicates, but the order is irrelevant".

    But maybe someone can explain the reason behind this in-my-eyes flawed feature of SortedSet? Why does it trust the compare/compareTo in regards to duplicity-check without doing a proper equals() check? I have read the javadoc, but all it says is that thats the way it is implemented. Performance?

    So, to go back to my original post. When I talked about duplicates I meant duplicates according from the comparators point of view, and the reason I used that definition was that this is the definition that SortedSet uses. I have no reason to put true duplicates (ie where o1.equals(o2)) in the collection.

    The solution I'm leaning towards now is to create my own Collection (ie "implements Collection<T>") that has an internal ArrayList<T>. This collection simply delegates all method calls to the ArrayList, but before the toArray- and iterator methods are called I sort the ArrayList using the provided Comparator. A bonus result of this compared to "option 3" above is that this solution have no problem with mutable elements where the field(s) that is used for comparison can change after it has been added to the collection. A SortedSet could would probably not be able to deal with this scenario elegantly.

    Any comments on this solution?

    /Jimi

    * Three if you consider '==', but that is just a special case of equals().
     
    Marshal
    Posts: 24940
    61
    Eclipse IDE Firefox Browser MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    There's nothing to stop you from using both compareTo and equals in your Collection, just like the Set and Map implementations use both hashCode and equals.

    So you could have an ArrayList in your collection; when something calls your Collection's "add" method you do a binary search to find out where it's going to be added to the ArrayList (using the compareTo method). Then before you add it you use the equals method to see if you really want to add it, or whether it's equal to the entries at (or near?) where you would add it.
     
    Jimi Svedenholm
    Ranch Hand
    Posts: 53
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Paul Clapham wrote:There's nothing to stop you from using both compareTo and equals in your Collection, just like the Set and Map implementations use both hashCode and equals.



    Yes, of course there is nothing stopping me from writing my own Collection, and that is in fact what I have done now. What I wanted to know was why SortedSet doesn't do this. They don't give any explanation in the javadoc.


    So you could have an ArrayList in your collection; when something calls your Collection's "add" method you do a binary search to find out where it's going to be added to the ArrayList (using the compareTo method). Then before you add it you use the equals method to see if you really want to add it, or whether it's equal to the entries at (or near?) where you would add it.



    I decided to instead only sort the internal ArrayList when needed (ie before calls to toArray() and iterator()). I consider that solution to be a little bit simpler then your suggestion, and thus less prone to errors. And performance wise I am sure that it is "good enough" for most usage.

    /Jimi
     
    Evacuate the building! Here, take this tiny ad with you:
    Java file APIs (DOC, XLS, PDF, and many more)
    https://products.aspose.com/total/java
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!