X-Git-Url: http://git.shiar.net/perl/list-index.git/blobdiff_plain/0f46a9fa54c9ecca0f0c3180b51f7c3079d048a8..HEAD:/t/10-ranges.t

diff --git a/t/10-ranges.t b/t/10-ranges.t
index aa87a87..9befbb6 100644
--- a/t/10-ranges.t
+++ b/t/10-ranges.t
@@ -2,49 +2,213 @@
 use strict;
 use warnings;
 
-use Test::More tests => 16;
+use Test::More tests => 10;
 use Test::NoWarnings;
 use Data::Dump 'pp';
 
 BEGIN { use_ok('List::Index'); }
 ok(eval { List::Index->VERSION(1) }, 'version 1.00 compatibility');
 
-{
-my @uniform = 'a'..'z';
-ok(my $index = List::Index->new(\@uniform), 'object (single-char values)');
-is_deeply(\@uniform, ['a'..'z'], 'original data unaltered');
-is_deeply($index->ranges, ['-'], 'single page');
-is_deeply($index->ranges({pages => 3}), [qw(-h i-q r-)], 'given pages');
-is_deeply($index->ranges({pagesize => @uniform / 2.1}), [qw(
-	-h i-q r-
-)], 'equivalent pagesize');
-}
-
-{
-ok(my $index = List::Index->new(['aa'..'zz', 1..193]), 'non-alphabetic values (uniform)');
-is_deeply($index->ranges, [qw(
-	-. .
-	a-b c-dr ds-fn fo-hk hl-jg jh-k l-m n-o p-qr qs-sn so-uk ul-wg wh-x y-
-)], 'default ranges');
-is_deeply($index->ranges({pagesize => 300}), [qw(-c d-o p-)], 'large pagesize');
-}
-
-{
-ok(my $index = List::Index->new([qw(
-	baa1 baa2  baa3 baaa  bbc cbc  daaa ea  eaaa zed
-)]), 'variable length values');
-is_deeply($index->ranges({pagesize => 2, context => 0}), [
-	qw(-baa. baa.-bbb bbc-daa. daaa-eaa. eaaa-)
-], 'no context');
-is_deeply($index->ranges({pagesize => 2}), [
-	qw(-a b c d-ea. eaa-)
-], 'default context');  # context should be 1
-is_deeply($index->ranges({pagesize => 2, context => 2}), [
-	qw(-a b-c d e-)
-], 'overlap');  # first item equals second due to large context
-is_deeply($index->ranges({pagesize => 2, length => 1}), [
-	qw(-a b-c d e-)
-], 'single char');
-
-#pp($index->ranges({pagesize => 2, context => 2, length => 1}));
-}
+eval { Test::More->VERSION(0.93) } or eval q{
+	diag "Install Test::More v0.93 to run subtests\n";
+	sub subtest {
+		SKIP: { skip 'subtest', 1; }
+	}
+};
+
+subtest('single-char alphabet' => sub {
+	plan tests => 5;
+	my @data = ('a'..'z');
+
+	is_deeply(List::Index->new->ranges(\@data), ['-'], 'single page');
+	is_deeply(\@data, ['a'..'z'], 'original data unaltered');
+	is_deeply(
+		List::Index->new({ pages => 3 })->ranges(\@data),
+		[qw(-i j-q r-)],
+		'given pages'
+	);
+	is_deeply(
+		List::Index->new({ pagesize => @data / 2.1 })->ranges(\@data),
+		[qw(-i j-q r-)],
+		'equivalent pagesize'
+	);
+	is_deeply(
+		List::Index->new({ pages => 500 })->ranges(\@data),
+		['-a', 'b'..'y', 'z-'],
+		'max pages'
+	);
+});
+
+subtest('uniform alphanumeric' => sub {
+	plan tests => 2;
+	my @data = ('aa'..'zz', 1..202);
+	my $index = List::Index->new or return;
+
+	is_deeply(
+		$index->ranges(\@data),
+		[qw(
+			-.. ..-...
+			...-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-
+		)],
+		'default ranges'
+	);
+	is_deeply(
+		$index->ranges(\@data, { pagesize => 300 }),
+		[qw(-c d-n o-)],
+		'large pagesize'
+	);
+});
+
+subtest('context' => sub {
+	plan tests => 9;
+	my @data = qw(
+		kkeg kl km kmlu knsy    koxb kpeo kuaa kuab kuac
+		kuapa kuq kur kux kzb   lc lg lgu lgua lguc
+		lguq lgur lgus lgx lka  lkq lks lln llq llx
+	);
+	my $index = List::Index->new({ pagesize => 10 }) or return;
+
+	is_deeply(
+		$index->ranges(\@data, { context => 0, length => 5 }),
+		# ranges should match offsets exactly
+		[qw(-kuap. kuapa-lgup lguq-)],
+		'no context'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 0 }),
+		# default length limits to 4 chars
+		[qw(-kuao kuap-lgup lguq-)],
+		'default length'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 1 }),
+		# lookbehinds aren't shorter (kuac<kuap, lguc<lguq)
+		# 'kuap' can advance to 'kuq'
+		[qw(-kup kuq-lgup lguq-)],
+		'lookahead'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 2 }),
+		# allowed to advance to 'kur', but provides no benefits over 'kuq'
+		[qw(-kup kuq-lgup lguq-)],
+		'minimal lookahead'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 3 }),
+		# shorten 'kuap' to 'ku' because lookbehind is 'kp...'
+		# 'lguq' matches 'lg', but may only backtrack to 'lgu'
+		[qw(-kt ku-lgt lgu-)],
+		'lookbehind'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 4 }),
+		[qw(-kt ku-lf lg-)],
+		'maximal lookahead'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 5 }),
+		# after forwarding 'kuap' to 'lc'
+		# disallow backtracking of 'lguq' to 'lc' to prevent qw[-k l-]
+		# so only lookahead (to 'lkq') remains
+		[qw(-k l-lj lk-)],
+		'lookbehind forbidden'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 9 }),
+		# allow a single (10-9) entry (l-lf = lc) to remain
+		[qw(-k l-lf lg-)],
+		'lookbehind penalty'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 10 }),
+		# allow the last page to go back upto 'lc', replacing the 2nd page
+		[qw(-k l-)],
+		'full overlap'
+	);
+});
+
+subtest('distribution' => sub {
+	plan tests => 2;
+	my @data = qw(
+		gnihka gniub go gsearnrqns gtdvcxyt gw gwoufolwcvmtueyg gysgphci h habkdgifjfxoh
+		hbbvjf hbqleexnqts hccg hd hdoeqwdmgqwaoya hfbegicieuxz hfm hj hkoysmws hmylu
+		hnvtvpievbdlkrmb hs hvdvcqn hvn hyrybeur iaiaab ib ibavqyar idfniqvxpohbk idh
+	);
+	my $index = List::Index->new({ pagesize => 10 }) or return;
+
+	is_deeply(
+		$index->ranges(\@data, { context => 7 }),
+		[qw(-g h i-)],
+		'large context'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 6 }),
+		# after 2nd page is enlarged by lookbehind to 'h', limit subsequent lookahead
+		# to prevent the page from getting too large (17 entries if forwarded to 'i')
+		[qw(-g h-hm hn-)],
+		'lookahead penalty'
+	);
+	# page #14 [gn-g] (8): gnihka gniub go gsearnrqns gtdvcxyt gwawkvmueovdjtfj gwoufolwcvmtueyg gysgphci
+	# page #15 [h] (17): h habkdgifjfxoh hbbvjf hbqleexnqts hccgszftbaymfu hdaqzkow hdoeqwdmgqwaoya hfbegicieu hfmlpzzioqjbthz hj hkoysmws hmylu hnvtvpievbdlkrmb hsodfpkatk hvdvcqn hvn hyrybeurqtevjfmi
+	# page #16 [i-ie] (5): i iaab ibiavqyar idfniqvxpohbk idh
+});
+
+subtest('modulo' => sub {
+	plan tests => 2;
+	my @data = qw( a b ccb   ccd  cce gf ggg   ggh  i j );
+	my $index = List::Index->new({ pagesize => 4, context => 0 }) or return;
+	# 10 entries at 4 per page requires 3 pages
+	# so actual target page sizes should be 3,4,3 (not 4,4,2)
+
+	is_deeply(
+		$index->ranges(\@data),
+		[qw(-ccc ccd-ggg ggh-)],
+		'uniform page sizes'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 1 }),
+		[qw(-b c-gf gg-)],
+		'context at new intervals'
+	);
+});
+
+subtest('corner cases' => sub {
+	plan tests => 1;
+
+	is_deeply(
+		List::Index->new->ranges(['foo','bar']),
+		['-'],
+		'2 rows 1 page'
+	);
+});
+
+subtest('context' => sub {
+	plan tests => 4;
+	my @data = qw( baa1 baa2  baa3 baaa  bbc cbc  daaa ea  eaaa zed );
+	my $index = List::Index->new({ pagesize => 2 }) or return;
+
+	is_deeply(
+		$index->ranges(\@data, { context => 0 }),
+		[qw(-baa. baa.-bbb bbc-daa. daaa-eaa. eaaa-)],
+		'no context'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => undef }),
+		[qw(-baa. baa.-b c d e-)],
+		'default context'  # context should be 1
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 2 }),
+		# first item equals second due to large context
+		[qw(-ba bb-b c d e-)],
+		'overlap'
+	);
+	is_deeply(
+		$index->ranges(\@data, { context => 0, length => 1 }),
+		[qw(-a b-c d e-)],
+		'single char'
+	);
+
+	#pp(List::Index->new({pagesize => 2, context => 2, length => 1}))->ranges(\@data);
+});
+