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 lgws 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 TODO: {
  84         local $TODO = 'backtrack';
  85         is_deeply(
  86                 $index->ranges(\@data, { context => 2 }),
  87                 # allowed to advance to 'kur', but provides no benefits over 'kuq'
  88                 [qw(-kup kuq-lgup lguq-)],
  89                 'minimal lookahead'
  90         );
  91 }
  92         is_deeply(
  93                 $index->ranges(\@data, { context => 3 }),
  94                 # shorten 'kuap' to 'ku' because lookbehind is 'kp...'
  95                 # 'lguq' matches 'lg', but may only backtrack to 'lgu'
  96                 [qw(-kt ku-lgt lgu-)],
  97                 'lookbehind'
  98         );
  99         is_deeply(
 100                 $index->ranges(\@data, { context => 4 }),
 101                 [qw(-kt ku-lf lg-)],
 102                 'maximal lookahead'
 103         );
 104         is_deeply(
 105                 $index->ranges(\@data, { context => 5 }),
 106                 # after forwarding 'kuap' to 'lc'
 107                 # disallow backtracking of 'lguq' to 'lc' to prevent qw[-k l-]
 108                 # so only lookahead (to 'lkq') remains
 109                 [qw(-k l-lj lk-)],
 110                 'lookbehind forbidden'
 111         );
 112         is_deeply(
 113                 $index->ranges(\@data, { context => 9 }),
 114                 # allow a single (10-9) entry (l-lf = lc) to remain
 115                 [qw(-k l-lf lg-)],
 116                 'lookbehind penalty'
 117         );
 118         is_deeply(
 119                 $index->ranges(\@data, { context => 10 }),
 120                 # allow the last page to go back upto 'lc', replacing the 2nd page
 121                 [qw(-k l-)],
 122                 'full overlap'
 123         );
 124 };
 125
 126 subtest 'distribution' => sub {
 127         plan tests => 2;
 128         my @data = qw(
 129                 gnihka gniub go gsearnrqns gtdvcxyt gw gwoufolwcvmtueyg gysgphci h habkdgifjfxoh
 130                 hbbvjf hbqleexnqts hccg hd hdoeqwdmgqwaoya hfbegicieuxz hfm hj hkoysmws hmylu
 131                 hnvtvpievbdlkrmb hs hvdvcqn hvn hyrybeur iaiaab ib ibavqyar idfniqvxpohbk idh
 132         );
 133         my $index = List::Index->new({ pagesize => 10 }) or return;
 134
 135         is_deeply(
 136                 $index->ranges(\@data, { context => 8 }),
 137                 [qw(-g h i-)],
 138                 'large context'
 139         );
 140         is_deeply(
 141                 $index->ranges(\@data, { context => 7 }),
 142                 # after 2nd page is enlarged by lookbehind to 'h', limit subsequent lookahead
 143                 # to prevent the page from getting too large (17 entries if forwarded to 'i')
 144                 [qw(-g h-hm hn-)],
 145                 'lookahead penalty'
 146         );
 147         # page #14 [gn-g] (8): gnihka gniub go gsearnrqns gtdvcxyt gwawkvmueovdjtfj gwoufolwcvmtueyg gysgphci
 148         # page #15 [h] (17): h habkdgifjfxoh hbbvjf hbqleexnqts hccgszftbaymfu hdaqzkow hdoeqwdmgqwaoya hfbegicieu hfmlpzzioqjbthz hj hkoysmws hmylu hnvtvpievbdlkrmb hsodfpkatk hvdvcqn hvn hyrybeurqtevjfmi
 149         # page #16 [i-ie] (5): i iaab ibiavqyar idfniqvxpohbk idh
 150 };
 151
 152 subtest 'modulo' => sub {
 153         plan tests => 2;
 154         my @data = qw( a b ccb   ccd  cce gf gg   gh  i j );
 155         my $index = List::Index->new({ pagesize => 4, context => 0 }) or return;
 156         # 10 entries at 4 per page requires 3 pages
 157         # so actual target page sizes should be 3,4,3 (not 4,4,2)
 158
 159         is_deeply(
 160                 $index->ranges(\@data),
 161                 [qw(-ccc ccd-gg gh-)],
 162                 'uniform page sizes'
 163         );
 164 { local $TODO = 'early lookbehind causing [c-gg]';
 165         is_deeply(
 166                 $index->ranges(\@data, { context => 1 }),
 167                 [qw(-b c-h i-)],
 168                 'context at new intervals'
 169         );
 170 }
 171 };
 172
 173 subtest 'context' => sub {
 174         plan tests => 4;
 175         my @data = qw( baa1 baa2  baa3 baaa  bbc cbc  daaa ea  eaaa zed );
 176         my $index = List::Index->new({ pagesize => 2 }) or return;
 177
 178         is_deeply(
 179                 $index->ranges(\@data, { context => 0 }),
 180                 [qw(-baa. baa.-bbb bbc-daa. daaa-eaa. eaaa-)],
 181                 'no context'
 182         );
 183         is_deeply(
 184                 $index->ranges(\@data, { context => undef }),
 185                 [qw(-a b c d e-)], #TODO
 186                 'default context'  # context should be 1
 187         );
 188         is_deeply(
 189                 $index->ranges(\@data, { context => 2 }),
 190                 # first item equals second due to large context
 191                 [qw(-a b-c d e-)],
 192                 'overlap'
 193         );
 194         is_deeply(
 195                 $index->ranges(\@data, { context => 0, length => 1 }),
 196                 [qw(-a b-c d e-)],
 197                 'single char'
 198         );
 199
 200         #pp(List::Index->new({pagesize => 2, context => 2, length => 1}))->ranges(\@data);
 201 };
 202