• Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorting a collection of elements that each refer to their predecessor  RSS feed

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

I am trying to find a way to sort a collection of elements. These elements are all of the same type, and refer to each other, in such a way that each of them refer to their predecessor (the elements have an id, and a 'previousId', which refers to the id of the previous element. The first element is indicated with previousId = null).
Given that the collection has these elements in random order (unsorted), how can I sort them to be able to display them in the right order? Is it possible to sort them using a comparator, or should I look for alternatives?

Cheers,
Kjeld
 
Paul Clapham
Sheriff
Posts: 22813
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A comparator would have to answer the question "Given an arbitrary pair of your elements, which should come first?" I don't see how it could do that, based on what you've said. So yes, I would suggest looking for alternatives.
 
Kjeld Sigtermans
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, now I am thinking what if the comparator returns 0 if the two elements do not refer to each other, returns 1 if element B refers to A, or -1 if A refers to B? Something like that. I haven't tried it yet.
 
Paul Clapham
Sheriff
Posts: 22813
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your Comparator can't say that two elements are equal if they don't refer to each other. Because they aren't, are they?
 
Kjeld Sigtermans
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I believe equality of classes in Java is how we define them to be, and furthermore, a comparator's results are not per se based on some sort of equality, so I don't agree on that part.
However, the solution I mentioned before does not work. I hoped it would. So now I'm trying something other than using a comparator.

 
Kjeld Sigtermans
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have come up with the code herebelow. The method 'sortManually()' works for me.
The for statement iterates through each element in the original list. The element is always added to a new, sorted list, it is just a question at what index.
The inline statement clarified (gotta love 'em): when the reference (the other element this element refers to) is null, the element is placed at the very beginning. Otherwise, when the reference already exists in the new list, this element is placed just after it. Otherwise, the element is just placed at the end.
This code assumes all elements are each referred to by one other element, or not at all.

 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

I don't think sorting is the best option here -- at least, not by using the Comparable/Comparator. The concept of using comparable assumes that it can be done quickly, that you can determine order simply by looking at any two elements. In this case, it is done by iterating the entire list -- which is already ordered. This is ordering a list that is already ordered, in order to get the same ordering in another format, so it can be iterated, so it can be printed.

It may be much easier to just iterate through the list, and somehow covert the "previousID" fields into some sort of linked list, so it can be iterated. In other words, convert the already ordered list that is using an id system to use a list of references -- no re-sorting needed.

Henry
 
Paul Clapham
Sheriff
Posts: 22813
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would just dump all of the elements into a Map whose key was the "previous element" reference. Then you can start with the null key and get the last element; from that you can get the next-to-last element; and so on. This gives you the elements sequentially in reverse order.
 
Kjeld Sigtermans
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks. I really like the map solution and also the idea of leaving the collection unsorted: I could create my own List implementation of unsorted elements, with an iterator that returns them in the correct order. I am going to try that.

Cheers, K

 
Jayesh A Lalwani
Rancher
Posts: 2762
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul's solution is a variation on Bucket Sort, and it seems to me that you won't get better than this. The average case performance is O(n+k) where n = number of elements and k = number of elements that have children. So, it's O(n). The only bad part is that the hashmap might become very large, but it should be fine in Java since it only stores references

However, you can come up with a slightly better algorithm if you change the definition of ID. Let's say, a particular node can have only 256 children. and id = parentid*256 + position of node within the parent. You can easily use this to implement a Comparator that you can use in a QUickSort. Actually.. umm... simple integer comparison will do the trick
 
Kjeld Sigtermans
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, I created a class called a 'Chain'. It implements Iterable and therefore provides an iterator. For now it only has one other method, add(final T predecessor, final T successor), with which predecessor-successor pairs can be added to the chain.
For example, when adding pairs (B, C) and (A, B) and (null, A), the iterator will return A, B, C. When providing an element that 'breaks the chain', like (D, E), the iterator just stops at C and will never show D or E, because no successor refers to D.
It is not allowed to add the same predecessor twice (illegal argument). When the precedessor is null, it depicts the successor is the first element that should be returned by the iterator. A successor can never be null (illegal argument).

I can now utilize the Chain class in my test class (see previous code posted here above) like this:

It returns the elements in the correct order.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!