t/10-ranges.t

   1 #!/usr/bin/env perl
   2 use strict;
   3 use warnings;
   4
   5 use Test::More tests => 9;
   6 use Test::NoWarnings;
   7 use Data::Dump 'pp';
   8
   9 BEGIN { use_ok('List::Index'); }
  10 ok(eval { List::Index->VERSION(1) }, 'version 1.00 compatibility');
  11
  12 subtest 'single-char alphabet' => sub {
  13         plan tests => 5;
  14         my @data = ('a'..'z');
  15
  16         is_deeply(List::Index->new->ranges(\@data), ['-'], 'single page');
  17         is_deeply(\@data, ['a'..'z'], 'original data unaltered');
  18         is_deeply(
  19                 List::Index->new({ pages => 3 })->ranges(\@data),
  20                 [qw(-i j-q r-)],
  21                 'given pages'
  22         );
  23         is_deeply(
  24                 List::Index->new({ pagesize => @data / 2.1 })->ranges(\@data),
  25                 [qw(-i j-q r-)],
  26                 'equivalent pagesize'
  27         );
  28         is_deeply(
  29                 List::Index->new({ pages => 500 })->ranges(\@data),
  30                 ['-a', 'b'..'y', 'z-'],
  31                 'max pages'
  32         );
  33 };
  34
  35 subtest 'uniform alphanumeric' => sub {
  36         plan tests => 2;
  37         my @data = ('aa'..'zz', 1..202);
  38         my $index = List::Index->new or return;
  39
  40         is_deeply(
  41                 $index->ranges(\@data),
  42                 [qw(
  43                         -.. ..-...
  44                         ...-bp bq-dm dn-fi fj-hf hg-i j-k l-m n-os ot-qp qq-sm sn-uj uk-wf wg-x y-
  45                 )],
  46                 'default ranges'
  47         );
  48         is_deeply(
  49                 $index->ranges(\@data, { pagesize => 300 }),
  50                 [qw(-c d-n o-)],
  51                 'large pagesize'
  52         );
  53 };
  54
  55 subtest 'context' => sub {
  56         plan tests => 9;
  57         my @data = qw(
  58                 kkeg kl km kmlu knsy    koxb kpeo kuaa kuab kuac
  59                 kuapa kuq kur kux kzb   lc lg lgu lgua lguc
  60                 lguq lgur lgus lgx lka  lkq lks lln llq llx
  61         );
  62         my $index = List::Index->new({ pagesize => 10 }) or return;
  63
  64         is_deeply(
  65                 $index->ranges(\@data, { context => 0, length => 5 }),
  66                 # ranges should match offsets exactly
  67                 [qw(-kuap. kuapa-lgup lguq-)],
  68                 'no context'
  69         );
  70         is_deeply(
  71                 $index->ranges(\@data, { context => 0 }),
  72                 # default length limits to 4 chars
  73                 [qw(-kuao kuap-lgup lguq-)],
  74                 'default length'
  75         );
  76         is_deeply(
  77                 $index->ranges(\@data, { context => 1 }),
  78                 # lookbehinds aren't shorter (kuac<kuap, lguc<lguq)
  79                 # 'kuap' can advance to 'kuq'
  80                 [qw(-kup kuq-lgup lguq-)],
  81                 'lookahead'
  82         );
  83         is_deeply(
  84                 $index->ranges(\@data, { context => 2 }),
  85                 # allowed to advance to 'kur', but provides no benefits over 'kuq'
  86                 [qw(-kup kuq-lgup lguq-)],
  87                 'minimal lookahead'
  88         );
  89         is_deeply(
  90                 $index->ranges(\@data, { context => 3 }),
  91                 # shorten 'kuap' to 'ku' because lookbehind is 'kp...'
  92                 # 'lguq' matches 'lg', but may only backtrack to 'lgu'
  93                 [qw(-kt ku-lgt lgu-)],
  94                 'lookbehind'
  95         );
  96         is_deeply(
  97                 $index->ranges(\@data, { context => 4 }),
  98                 [qw(-kt ku-lf lg-)],
  99                 'maximal lookahead'
 100         );
 101         is_deeply(
 102                 $index->ranges(\@data, { context => 5 }),
 103                 # after forwarding 'kuap' to 'lc'
 104                 # disallow backtracking of 'lguq' to 'lc' to prevent qw[-k l-]
 105                 # so only lookahead (to 'lkq') remains
 106                 [qw(-k l-lj lk-)],
 107                 'lookbehind forbidden'
 108         );
 109         is_deeply(
 110                 $index->ranges(\@data, { context => 9 }),
 111                 # allow a single (10-9) entry (l-lf = lc) to remain
 112                 [qw(-k l-lf lg-)],
 113                 'lookbehind penalty'
 114         );
 115         is_deeply(
 116                 $index->ranges(\@data, { context => 10 }),
 117                 # allow the last page to go back upto 'lc', replacing the 2nd page
 118                 [qw(-k l-)],
 119                 'full overlap'
 120         );
 121 };
 122
 123 subtest 'distribution' => sub {
 124         plan tests => 2;
 125         my @data = qw(
 126                 gnihka gniub go gsearnrqns gtdvcxyt gw gwoufolwcvmtueyg gysgphci h habkdgifjfxoh
 127                 hbbvjf hbqleexnqts hccg hd hdoeqwdmgqwaoya hfbegicieuxz hfm hj hkoysmws hmylu
 128                 hnvtvpievbdlkrmb hs hvdvcqn hvn hyrybeur iaiaab ib ibavqyar idfniqvxpohbk idh
 129         );
 130         my $index = List::Index->new({ pagesize => 10 }) or return;
 131
 132         is_deeply(
 133                 $index->ranges(\@data, { context => 7 }),
 134                 [qw(-g h i-)],
 135                 'large context'
 136         );
 137         is_deeply(
 138                 $index->ranges(\@data, { context => 6 }),
 139                 # after 2nd page is enlarged by lookbehind to 'h', limit subsequent lookahead
 140                 # to prevent the page from getting too large (17 entries if forwarded to 'i')
 141                 [qw(-g h-hm hn-)],
 142                 'lookahead penalty'
 143         );
 144         # page #14 [gn-g] (8): gnihka gniub go gsearnrqns gtdvcxyt gwawkvmueovdjtfj gwoufolwcvmtueyg gysgphci
 145         # page #15 [h] (17): h habkdgifjfxoh hbbvjf hbqleexnqts hccgszftbaymfu hdaqzkow hdoeqwdmgqwaoya hfbegicieu hfmlpzzioqjbthz hj hkoysmws hmylu hnvtvpievbdlkrmb hsodfpkatk hvdvcqn hvn hyrybeurqtevjfmi
 146         # page #16 [i-ie] (5): i iaab ibiavqyar idfniqvxpohbk idh
 147 };
 148
 149 subtest 'modulo' => sub {
 150         plan tests => 2;
 151         my @data = qw( a b ccb   ccd  cce gf ggg   ggh  i j );
 152         my $index = List::Index->new({ pagesize => 4, context => 0 }) or return;
 153         # 10 entries at 4 per page requires 3 pages
 154         # so actual target page sizes should be 3,4,3 (not 4,4,2)
 155
 156         is_deeply(
 157                 $index->ranges(\@data),
 158                 [qw(-ccc ccd-ggg ggh-)],
 159                 'uniform page sizes'
 160         );
 161         is_deeply(
 162                 $index->ranges(\@data, { context => 1 }),
 163                 [qw(-b c-gf gg-)],
 164                 'context at new intervals'
 165         );
 166 };
 167
 168 subtest 'context' => sub {
 169         plan tests => 4;
 170         my @data = qw( baa1 baa2  baa3 baaa  bbc cbc  daaa ea  eaaa zed );
 171         my $index = List::Index->new({ pagesize => 2 }) or return;
 172
 173         is_deeply(
 174                 $index->ranges(\@data, { context => 0 }),
 175                 [qw(-baa. baa.-bbb bbc-daa. daaa-eaa. eaaa-)],
 176                 'no context'
 177         );
 178         is_deeply(
 179                 $index->ranges(\@data, { context => undef }),
 180                 [qw(-baa. baa.-b c d e-)],
 181                 'default context'  # context should be 1
 182         );
 183         is_deeply(
 184                 $index->ranges(\@data, { context => 2 }),
 185                 # first item equals second due to large context
 186                 [qw(-ba bb-b c d e-)],
 187                 'overlap'
 188         );
 189         is_deeply(
 190                 $index->ranges(\@data, { context => 0, length => 1 }),
 191                 [qw(-a b-c d e-)],
 192                 'single char'
 193         );
 194
 195         #pp(List::Index->new({pagesize => 2, context => 2, length => 1}))->ranges(\@data);
 196 };
 197