challenge 18 by Jaldhar H. Vyas

2 files changed, 238 insertions, 0 deletions

diff --git a/challenge-018/jaldhar-h-vyas/perl5/ch-2.pl b/challenge-018/jaldhar-h-vyas/perl5/ch-2.pl
new file mode 100755
index 0000000000..826279354d
--- /dev/null
+++ b/challenge-018/jaldhar-h-vyas/perl5/ch-2.pl
@@ -0,0 +1,174 @@
+#!/usr/bin/perl
+
+=head1 NAME
+
+Data::PriorityQueue - A Priority Queue
+
+=cut
+
+package Data::PriorityQueue;
+use Moo;
+use namespace::clean;
+
+=head1 VERSION
+
+Version 0.1
+
+=cut
+
+our $VERSION = '0.1';
+
+=head1 SYNOPSIS
+
+    my $q = Data::PriorityQueue->new();
+
+    $q->insert_with_priority('one', 1);
+
+    say $q->pull_highest_priority_element(); # will print 'one'
+
+    say $q->is_empty ? 'YES' : 'No';  # will print 'YES'
+
+    $q->insert_with_priority('two', 2);
+    $q->insert_with_priority('one', 3);
+    $q->insert_with_priority('three', 3);
+    $q->insert_with_priority('one', 1);
+
+    say $q->pull_highest_priority_element(); # will print 'one'
+
+    $q->clear;
+
+=head1 DESCRIPTION
+
+This is a simple implementation of a Priority Queue.  A priority queue is a
+data structure where the items are sorted in order of numeric priority.
+
+=cut
+
+has _iterator => (
+    is => 'rw',
+    default => 0,
+);
+
+has _queue => (
+    is => 'rw',
+    default => sub { [] } # should use a binary heap really but its all good...
+);
+
+has _size => (
+    is => 'rw',
+    default => 0, 
+);
+
+=head2 METHODS
+
+=head3 clear()
+
+    removes all elements from the priority queue and resets iteration.
+
+=cut
+
+sub clear {
+    my ($self) = @_;
+
+    $self->_queue([]);
+    $self->_size(0);
+    $self->_iterator(0);
+}
+
+=head3 top()
+
+    returns the highest priority element in the queue without removing it.
+
+=cut
+
+sub top {
+    my ($self) = @_;
+
+    return $self->_queue->[0]->{value};
+}
+
+=head3 insert_with_priority($value, $priority)
+
+    Stores scalar C<$value> in the queue with numeric priority C<$priority>.
+
+=cut
+
+sub insert_with_priority {
+    my ($self, $value, $priority) = @_;
+    $priority //= 0;
+
+    my $pos = 0;
+    while (defined $self->_queue->[$pos] &&
+    $self->_queue->[$pos]->{priority} >= $priority) {
+        $pos++;
+    }
+    push @{ $self->_queue }, { value => $value, priority => $priority},
+        splice @{ $self->_queue }, $pos, $self->_size - $pos;
+    $self->_size($self->_size + 1);
+}
+
+=head3 is_empty()
+
+    returns a true value if there are no elements in the priority queue or 
+    false otherwise.
+
+=cut
+
+sub is_empty {
+    my ($self) = @_;
+
+    return $self->_size == 0;
+}
+
+=head3 pull_highest_priority_element()
+
+    Removes the highest priority element from the queue and returns it or C<undef>
+    if the queue is empty.  In the event of two elements having the same
+    priority, returns the one added first.
+
+=cut
+
+sub pull_highest_priority_element {
+    my ($self) = @_;
+
+    if ($self->_size) {
+        my $element = shift @{ $self->_queue };
+        $self->_size($self->_size - 1);
+        return $element->{value};
+    }
+}
+
+
+=head3 size()
+
+    returns the number of elements in the queue.
+
+=cut
+
+sub size {
+    my ($self) = @_;
+
+    return $self->_size;
+}
+
+=head1 AUTHOR
+
+Jaldhar H. Vyas, C<< <jaldhar at braincells.com> >>
+
+=head1 BUGS
+
+For better efficiency the underlying data store should be a binary heap not
+an array.
+
+There should be a way to provide a custom comparison function in case you want
+something other than numeric priority.
+
+=head1 LICENSE AND COPYRIGHT
+
+Copyright 2019,  Consolidated Braincells Inc.
+
+"Do what thou wilt" shall be the whole of the license.
+
+=cut
+
+1;
diff --git a/challenge-018/jaldhar-h-vyas/perl6/ch-2.p6 b/challenge-018/jaldhar-h-vyas/perl6/ch-2.p6
new file mode 100755
index 0000000000..693066c50f
--- /dev/null
+++ b/challenge-018/jaldhar-h-vyas/perl6/ch-2.p6
@@ -0,0 +1,64 @@
+#!/usr/bin/perl6
+
+class Data::PriorityQueue {
+
+    class Element {
+        has Any $.value is rw;
+        has Int $.priority is rw;
+    }
+
+    has Element @!queue = ();
+
+    method clear {
+        @!queue = ();
+    }
+
+    method top() {
+        return @!queue[0].value;
+    }
+
+    method insert_with_priority(Any $value, Int $priority = 0) {
+        my $pos = 0;
+        while $pos < @!queue.elems && @!queue[$pos].priority >= $priority {
+            $pos++;
+        }
+        my @remainder = @!queue.splice($pos, @!queue.elems - $pos);
+        @!queue.push(
+            Element.new(value => $value, priority => $priority),
+        ).append(@remainder);
+    }
+
+    method is_empty() {
+        return @!queue.elems == 0;
+    }
+
+    method pull_highest_priority_element() {
+        if !self.is_empty {
+            return @!queue.shift.value;
+        }
+        return Nil;
+    }
+
+    method size() {
+        return @!queue.elems;
+    }
+
+}
+
+# some random operations
+   my $q = Data::PriorityQueue.new;
+
+    $q.insert_with_priority('one', 1);
+
+    say $q.pull_highest_priority_element(); # will print 'one'
+
+    say $q.is_empty ?? 'YES' !! 'No';  # will print 'YES'
+
+    $q.insert_with_priority('two', 2);
+    $q.insert_with_priority('one', 3);
+    $q.insert_with_priority('three', 3);
+    $q.insert_with_priority('one', 1);
+
+    say $q.pull_highest_priority_element(); # will print 'one'
+
+    $q.clear;