• Post Reply Bookmark Topic Watch Topic
  • New Topic

Merging two sorted sets into one set without using treeset as the result set  RSS feed

 
praveena satish
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi i have done the below code to merge two sorted set into one,please let me know if i can optimize the code anyways.




Output:
[10, 30, 33, 40, 60, 660]
[13, 34, 40, 240, 550, 900]
[10, 13, 30, 33, 34, 40, 60, 240, 550, 660, 900]
 
Vishakha Lele
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Instead of using iterators, you can simply use addAll() method of the sets which takes entire collection as an argument. Also, sorting and duplicity of the elements is handled in this method.
 
Vishakha Lele
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One correction, if you want the resultant set as sorted, you need to use TreeSet and not LinkedHashSet as its not sorted.
 
Stephan van Hulst
Saloon Keeper
Posts: 7962
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, if you want the result to be a LinkedHashSet, you can just do the following:

If the original sets shouldn't be modified, you can do:
Or:
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I moved your first line out of the code tags because it wasn't code. Look at line 68; there is no need for empty space there.

That method for combining the two sets looks very complicated, particularly the while loop. I am a little worried about the combining two trees like that. You start with two already sorted Sets and iterate them starting from their smallest elements. Let's imagine your original tree set had this architecture:-You get that by adding things in random order, and we are imagining you started with the middle element. Now no element in that tree is more than two levels from the root. Now you are using the Iterator and you add elements starting from the smallest. So you start with your Set having this structure and then you add 13.Then you keep adding.Now, you might be calling that a binary search tree, but every node has its left field pointing to null, and its structure will behave exactly the same as this data structure:-It will behave as if you had turned it into a (sorted) linked list; searches and insertions will no longer run in logn time but in linear time.
Go and find the src.zip file in your Java® installation folder unzip it and open the source for java/util/TreeSet.java and java/util/TreeMap.java. If you follow the details of the TreeSet#addAll method, you find it behaves differently for a TreeSet from other implementations.  I haven't followed the details, but I am pretty sure that adding starts from the middle elements of (??the recipient??) set, so the new elements are fitted into the original tree structure as close as possible to their correct positions and maintain the correct structure of the tree. That is why you shou‍ld use the built‑in methods wherever possible. They have been refined over twenty‑one years of experience to make sure they work correctly.

Stephan: nice solution to create a linked set with concat(). Is the toCollection method Collections.toCollection? OP may not know about the static import you would use for that method. Also where does concat() come from?
 
Stephan van Hulst
Saloon Keeper
Posts: 7962
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Stephan: nice solution to create a linked set with concat(). Is the toCollection method Collections.toCollection? OP may not know about the static import you would use for that method. Also where does concat() come from?

toCollection() comes from Collectors, and concat() comes from Stream.

I have updated my post to give the static imports for both. I prefer to use static imports when working with stream operations, it makes the statement flow more like a story.
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!