{"id":13172,"date":"2017-09-15T12:17:56","date_gmt":"2017-09-15T10:17:56","guid":{"rendered":"https:\/\/touk.pl\/blog\/?p=13172"},"modified":"2017-09-21T12:41:30","modified_gmt":"2017-09-21T10:41:30","slug":"maintaining-priorityqueue-order-with-java-streams","status":"publish","type":"post","link":"https:\/\/touk.pl\/blog\/2017\/09\/15\/maintaining-priorityqueue-order-with-java-streams\/","title":{"rendered":"Maintaining PriorityQueue Order with Java Streams"},"content":{"rendered":"

The tricky thing about working with PriorityQueues<\/em> is that, ironically, they don’t always behave according to the PriorityQueue<\/em> semantics. <\/p>\n

PriorityQueue Traversal<\/h2>\n

If we have a look at PriorityQueue.iterator()<\/a> documentation, we’ll see that, unintuitively, iterator()<\/em> is not traversing the queue according to its priority order:<\/p>\n

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.<\/strong><\/p><\/blockquote>\n

The same behaviour can be noticed when trying to use Java Stream API for processing PriorityQueue’s<\/em> elements using the instance obtained by the stream()<\/em> method – the Stream<\/em> instance depends on the Spliterator<\/em> instance which doesn’t guarantee the desired traversal order.<\/p>\n

PriorityQueue<String> queue = new PriorityQueue<>(comparing(String::length));\nList<String> content = Arrays.asList(\"1\", \"333\", \"22\", \"55555\", \"4444\");\nqueue.addAll(content);\n\nassertThat(queue.stream())\n  .containsExactlyElementsOf(content);<\/pre>\n
We can see that the insertion order gets preserved regardless of the fact that our queue was expected to be providing Strings<\/em> according to their length.<\/strong><\/p>\n
Solution #1<\/h2>\n
We can use the poll()<\/em> method to fetch elements from the queue according to the priority order.<\/p>\n
So – let’s generate a Stream<\/em> from consecutive elements, returned by the\u00a0poll()<\/em>\u00a0method, using Stream.generate()<\/em> method:<\/p>\n
List<String> result = Stream.generate(queue::poll)\n  .limit(queue.size())\n  .collect(Collectors.toList());\n\nassertThat(result)\n  .containsExactly(\"1\", \"22\", \"333\", \"4444\", \"55555\");\nassertThat(queue)\n  .isEmpty();<\/pre>\n
The problem with this implementation is that it’s not concurrent-modification-friendly.<\/strong> Until Java 9 gets released, we can’t terminate the generated Stream<\/em> dynamically so we need to rely on limiting the Stream<\/em> size to the queue size – which is not perfect because this can change during an actual processing.<\/p>\n
The crucial part of this implementation is that after consuming a Stream<\/em> instance, we end up with a modified queue<\/strong> – the poll()<\/em> method removes the polled element from the queue.<\/p>\n
Eventually, this approach can be extracted to the separate utility method:<\/p>\n
static <T> Stream<T> drainToStream(PriorityQueue<T> queue) {\n    Objects.requireNonNull(queue);\n    return Stream.generate(queue::poll)\n      .limit(queue.size());\n}<\/pre>\n
Java 9<\/h3>\n
Since Java 9, it’ll be possible to rewrite it in a concurrent-friendly manner:<\/p>\n
static <T> Stream<T> drainToStream(PriorityQueue<T> queue) {\n    Objects.requireNonNull(queue);\n    return Stream.generate(queue::poll)\n      .takeWhile(Objects::nonNull)\n}<\/pre>\n
Solution #2<\/h2>\n
The second approach involves simply sorting the Stream<\/em> instance using the same comparator that the queue uses. We need to remember that this will work as long as the queue was initialized using a custom comparator:<\/p>\n
List<String> result = queue.stream()\n  .sorted(queue.comparator())\n  .collect(Collectors.toList());\n\nassertThat(result)\n  .containsExactly(\"1\", \"22\", \"333\", \"4444\", \"55555\");\nassertThat(queue)\n  .isNotEmpty();<\/pre>\n
This approach can be used with any Collection<\/em> type (as long as we can get ahold of the right\u00a0Comparator<\/em> instance).<\/p>\n
If we store Comparable<\/em> objects in the queue and depend on their natural order, this becomes even simpler because we do not need to reach for the Comparator<\/em> instance:<\/p>\n
PriorityQueue<String> queue = new PriorityQueue<>();\nqueue.addAll(Arrays.asList(\"1\", \"333\", \"22\", \"55555\", \"4444\"));\n\nList<String> result = queue.stream()\n  .sorted()\n  .collect(Collectors.toList());\n\nassertThat(result)\n  .containsExactly(\"1\", \"22\", \"333\", \"4444\", \"55555\");\nassertThat(queue)\n  .isNotEmpty();<\/pre>\n
In this case, after consuming a Stream<\/em> instance, our original queue remains intact.<\/strong><\/p>\n
Eventually, this approach can be extracted to the separate utility method:<\/p>\n
static <T> Stream<T> asStream(PriorityQueue<T> queue) {\n    Objects.requireNonNull(queue);\n    Comparator<? super T> comparator = queue.comparator();\n    return comparator != null\n      ? queue.stream().sorted(comparator)\n      : queue.stream().sorted();\n}<\/pre>\n
Conclusion<\/h2>\n
The priority order of the PriorityQueue<\/em> is not preserved when iterating\/traversing so, essentially, we need to create our Stream<\/em> instances ourselves.<\/p>\n
The working code snippets can be found on GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"The tricky thing about working with PriorityQueues is that, ironically, they don’t always behave according to the PriorityQueue…\n","protected":false},"author":68,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11],"tags":[],"class_list":{"0":"post-13172","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-development-design"},"_links":{"self":[{"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/posts\/13172","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/users\/68"}],"replies":[{"embeddable":true,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/comments?post=13172"}],"version-history":[{"count":6,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/posts\/13172\/revisions"}],"predecessor-version":[{"id":13220,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/posts\/13172\/revisions\/13220"}],"wp:attachment":[{"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/media?parent=13172"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/categories?post=13172"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/tags?post=13172"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}