Merge pull request #424 from ufobat/patch-1

Create priority-queue.pl6

1 files changed, 41 insertions, 0 deletions

diff --git a/challenge-018/martin-barth/perl6/ch-2.p6 b/challenge-018/martin-barth/perl6/ch-2.p6
new file mode 100644
index 0000000000..ca50cd29a2
--- /dev/null
+++ b/challenge-018/martin-barth/perl6/ch-2.p6
@@ -0,0 +1,41 @@
+class PriorityQueue {
+    class Item {
+        has Real $.prio;
+        has Any $.element;
+    }
+    has @.elements;
+
+    method insert-with-priority(Real:D $prio, Any:D $element) {
+        my $item = Item.new(:$prio, :$element);
+        my $new_pos = self!find-pos($prio, 0, @!elements.elems);
+        @!elements.splice($new_pos, 0, $item);
+    }
+
+    method !find-pos($prio, Int $start, Int $end) {
+        my $pos = (($start + $end) / 2);
+        if $pos < 0 {
+            return 0;
+        } else {
+            if $start == $end {
+                return $start;
+            } else {
+                $pos = $pos.Int;
+                my $item = @!elements[$pos];
+                if $item.prio < $prio {
+                    return self!find-pos($prio, $start, $pos);
+                } else {
+                    return self!find-pos($prio, $pos+1, $end);
+                }
+            }
+        }
+    }
+
+    method is-empty(--> Bool) {
+        return @!elements.elems == 0;
+    }
+
+    method pull-highest-priority-element(--> Any) {
+        fail if self.is-empty;
+        return @!elements.shift.element;
+    }
+}