Perl Weekly Challenge 111.2 - Binary Matrix Search with comments #Raku #Rakulang

111.2.raku

use Test;

my @M =
    [  1,  2,  3,  5,  7 ],
    [  9, 11, 15, 19, 20 ],
    [ 23, 24, 25, 29, 31 ],
    [ 32, 33, 39, 40, 42 ],
    [ 45, 47, 48, 49, 50 ];

# A multi sub implementing a binary search. multi subs are a mechanism
# for having multiple subroutines with the same name, but different
# signatures. The dispatcher decides at runtime and chose the best fit
# for any given set of arguments.

# The first candidate is doing the work
# The second candidate is for catching the error cases
multi bsearch
(
    # The input array to be searched
    @val,
    # Gets passed a value to be compared to the sought value,
    # it is expected to return Less, Same or More (or -1, 0, 1)
    &cmp,
    # The start index for the binary search, defaults to 0, must be 0 or greater
    $frm where $frm >= 0 = 0,
    # The end index for the binary search, defaults to the number
    # of elements of the input array, must be smaller
    $end where $frm <= $end = @val.end
)
{
    # calculate the middle and store it in $mid
    # look up the $mid-th element and see how it compares
    # by passing it into the comparator
    given @val[ my $mid = ( $frm + $end ) div 2 ].&cmp
    {
        # return the index when we have a hit,
        when Same { $mid }
        # otherwise search the remaining halfs, depending
        # on the comparison
        when Less { bsearch( @val, &cmp, $mid.succ, $end ) }
        default   { bsearch( @val, &cmp, $frm, $mid.pred ) }

        # If you know the "normal" algorithm you might miss
        # the edge case logic and boundary checks that are
        # ususally here. Not needed. If for example $frm gets
        # bigger than $end, then the candidate does not
        # fit anymore and our catchall error multi below gets
        # called
    }
}

multi bsearch(|) { -1 }

# Implementing the binary matrix search
sub msearch( $val, @m )
{
   # These create closures over $val which expects a value to compare to $val
   # as first argument when called

   # The first one is to search for the x-coordinate
   # We have a hit when $value is in between the first and the last element
   # Otherwise we return the result of the comparison of the last element to our value
   my &x = { .head <= $val <= .tail ?? Same !! .head cmp $val };

   # This one just looks for equality and is used to find our y coordinate
   my &y = { .item cmp $val };

   # The inner bsearch searches for x using the closure above,
   # uses x to look up the inner array, and bsearch that for y.
   # if y is greater than -1, we have hit an return True
   # otherwise we return False
   bsearch( @m[ bsearch( @m, &x ) ], &y ) > -1;

   # Note, here too we don't have any if then logic.
   # in conservative code you would first look for x, see if that is
   # bigger than -1 and only then try continue the search
   #
   # Again the multi comes into play.
   # Raku is lazy and even so lazy that it only throws exceptions if
   # you force it to, eg by looking at a result.
   # Here, if the inner bsearch returns -1, because it does not find anything,
   # the code will try to look up the -1th index, which is an error, and that will create
   # a Failure. The outer call to bsearch will then have that Failure as first
   # argument, which does not fit the workhorse candidate and so everything works
   # out beautifully.
   # If we add an additional candidate like
   # multi bsearch( Failure, Block ) { say "Here is why I fail"; -1 }
   # we can see that flow happening.
}

.Int.say for map *.&msearch( @M ), 0, 35, 39, 150;

ok 1  == bsearch( @M, { .head <= 15 <= .tail ?? Same !! .head cmp 15 } );
ok 2  == bsearch( @M[1], { $^v cmp 15 } );
ok 2  == bsearch( @M, { .head <= 29 <= .tail ?? Same !! .head cmp 29 } );
ok 3  == bsearch( @M[2], { $^v cmp 29 } );
ok -1 == bsearch( @M[2], { $^v cmp 29 }, -1);