use v6;
unit class Search::Dict:ver<0.2>:auth<github:zengargoyle>;



head

Search::Dict - a fast binary search of dictionary like files


my &lookup = search-dict('/usr/share/dict/words');


given lookup('existing-word') -> $w {
  +$w;  # seek offset in dict
  ?$w;  # True
  ~$w;  # 'existing-word'
}
given lookup('non-existing-word') -> $w {
  +$w;  # seek offset after where non-existing-word would be
  ?$w;  # False
  ~$w;  # word after where non-existing-word would be
  # or
  $w.match.defined # False  - after last word in dict
}


Search::Dict is a fast binary search of dictionary like files (e.g. F</usr/share/dict/words>).  A dictionary file is one where:



my class R {
  has Str $.match handles <Str>;
  has Bool $.found handles <Bool>;
  has Int $.pos handles <Numeric Int>;
  method gist { qq:to[END].chomp;
    (:found($.found) :pos($.pos) :match($.match))
    END
  }
}

sub search-dict( $filename, :$block-size = 128 ) is export {
  my $fh = $filename.IO.open;
  my $size = $filename.IO.s // do { .seek(0,SeekFromEnd); my $s = .tell; .seek(0,SeekFromBeginning); $s }($fh);
  my $min = 0;
  my $max = Int($size / $block-size);  # XXX: blksize?

  sub look($fh, $key, $min is copy, $max is copy) {
    while $max - $min > 1 {
      state $mid;
      $mid = Int(($max + $min) / 2);
      $fh.seek: $mid * $block-size, SeekFromBeginning;
      $fh.get if $mid;
      given $fh.get {
        when !*.defined { last }
        when * lt $key { $min = $mid }
        default { $max = $mid }
      }
    }
    $fh.seek: $min * $block-size, SeekFromBeginning;
    $fh.get if $min;

    my Bool $found = False;
    my Int $pos;
    my Str $match;

    loop {
      $pos = $fh.tell;
      given $fh.get {
        when !.defined { return R.new( :$found,      :$pos, :match(Str) ) }
        when $key      { return R.new( :found(True), :$pos, :match($_) ) }
        when * gt $key { return R.new( :$found,      :$pos, :match($_) ) }
      }
    }
    fail "can not happen!";
  }

  return sub (Str $string) {
    look($fh, $string, $min, $max)
  }
}




This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.


root

README

React

=begin React :component<HeaderCol> :id<menu> 
=para L<Documentation|/doc/introduction>
=para L<Modules| /mods>
=para L<Examples| file:../examples/index.podlite>
=para L<Download |file:../download/index.podlite>
=para L<About|file:../about/index.podlite>
=para 🔍 K<⌘K>/K<ctrl-K>
=end React


=begin React :component<HeaderCol> :id<footer>  
=begin nested :!nested
=item1 B<Language>
    =item2 L<Get started|file:../getting-started/getting-started.podlite>
    =item2 L<Why Raku?|/doc/language/faq#Why-should-I-learn-Raku-What's-so-great-about-it>
    =item2 L<Try Raku|https://glot.io/new/raku>
    =item2 L<Raku cheat sheet|https://github.com/Raku/mu/blob/master/docs/Perl6/Cheatsheet/cheatsheet.txt>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<Raku on Exercism|https://exercism.org/tracks/raku>
    =item2 L<Wikipedia|https://en.wikipedia.org/wiki/Raku_(programming_language)>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=begin nested :!nested

=item1 B<L<Documentation|/doc>>
    =item2 L<Getting started, Migration guides from other languages, & Tutorials | file:../doc/introduction.podlite>
    =item2 L<Language References|file:../doc/reference.podlite>
    =item2 L<Type Reference| file:../doc/types.podlite>
    =item2 L<Miscellaneous| file:../doc/miscellaneous.podlite>
    =item2 L<FAQs (Frequently Asked Questions)|/doc/language/faq>
    =item2 L<Community|/doc/language/community>
    =item2 L<The list of all documents|file:../doc/index.podlite>

=item1 B<Resources>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>

=end nested
=begin nested :!nested

=item1 B<Resoures>
    =item2 L<Download | file:../download/index.podlite>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=item1 B<Learning>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Wikibook |https://en.wikibooks.org/wiki/Raku_Programming>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>
    =item2 L<Learn Raku in Y minutes|https://learnxinyminutes.com/docs/raku/>
    =item2 L<Golfing |https://github.com/AlexDaniel/raku-golf-cheatsheet>
=end nested
=begin nested :!nested

=item1 B<Explore>
    =item2 L<Raku Blog Aggregator|https://planet.raku.org/>
    =item2 L<Rakudo Weekly|https://rakudoweekly.blog/>
    =item2 L<The Weekly Challenge |https://perlweeklychallenge.org/>
    =item2 L<Raku Advent Calendar|https://raku-advent.blog/>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=end React


=begin React :component<CookieConsent> :id<CookieConsent> :buttonCaption("Got it!")
=para
This website uses cookies for analytics.
=end React


Dict

NAME

SYNOPSIS

DESCRIPTION

AUTHOR

COPYRIGHT AND LICENSE