t/10-ranges.t

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