diff options
author | Andinus <andinus@nand.sh> | 2021-01-19 21:53:16 +0530 |
---|---|---|
committer | Andinus <andinus@nand.sh> | 2021-01-19 21:53:16 +0530 |
commit | a5c540608c469a2797262facb766e175b932f0e2 (patch) | |
tree | 1e0eb79678d66f5ba657c63003592029757aefe7 /lib/RangeSearch.rakumod | |
parent | 5bb0f224483fbc1d57fd1c5a2f4a22dd7263ecd6 (diff) | |
download | octans-a5c540608c469a2797262facb766e175b932f0e2.tar.gz |
Re-structure for CPAN upload, include a dictionary file v0.1.0
bin/octans calls lib/Octans/CLI.rakumod which has the MAIN subroutine.
Diffstat (limited to 'lib/RangeSearch.rakumod')
-rw-r--r-- | lib/RangeSearch.rakumod | 70 |
1 files changed, 0 insertions, 70 deletions
diff --git a/lib/RangeSearch.rakumod b/lib/RangeSearch.rakumod deleted file mode 100644 index 16e43c1..0000000 --- a/lib/RangeSearch.rakumod +++ /dev/null @@ -1,70 +0,0 @@ -unit module RangeSearch; - -# range-starts-with returns a subset of given @dict list that start -# with $str. It should be faster than: -# -# @dict.grep: *.starts-with($str) -# -# @dict should be a sorted list of words. It performs binary lookup on -# the list. -sub range-starts-with ( - @dict, Str $str --> List -) is export { - # $lower, $upper hold the lower and upper index of the range - # respectively. - my Int ($lower, $upper); - - # Lookup the whole dictionary. - my Int ($start, $end) = (0, @dict.end); - - # Loop until we end up on the lower index of range. - while $start < $end { - # Divide the list into 2 parts. - my Int $mid = ($start + $end) div 2; - - # Check if $mid word is le (less than or equal to) $str. If - # true then discard the bottom end of the list, if not then - # discard the top end. - if $str le @dict[$mid].substr(0, $str.chars).lc { - $end = $mid; - } else { - $start = $mid + 1; - } - } - - # Found the lower index. - $lower = $start; - - # Set $end to the end of list but keep $start at the lower index. - $end = @dict.end; - - # Loop until we end up on the upper index of range. - while $start < $end { - # Divide the list into 2 parts. Adds 1 because we have to find - # the upper index in this part. `div' performs Interger - # division, output is floor'ed. - my Int $mid = (($start + $end) div 2) + 1; - - # Check if $mid word is lt (less than) $str. If true then - # discard the bottom end of the list, if not then discard the - # top end. - if $str lt @dict[$mid].substr(0, $str.chars).lc { - $end = $mid - 1; - } else { - $start = $mid; - } - } - - # Found the upper index. - $upper = $end; - - with @dict[$lower..$upper] -> @list { - # Maybe the word doesn't exist in the list, in that case there - # will be a single element in @list. We return an empty list - # unless that single element starts with $str. - if @list.elems == 1 { - return () unless @list[0].starts-with($str); - } - return @list; - } -} |