From a621cd10e5c167968a778cb6a1a4f319d4949a7a Mon Sep 17 00:00:00 2001
From: Mischa POSLAWSKY <perl@shiar.org>
Date: Tue, 10 Nov 2009 21:54:11 +0100
Subject: [PATCH] List::Index->ranges

---
 lib/List/Index.pm | 82 +++++++++++++++++++++++++++++++++++++++++++++++
 t/10-ranges.t     | 56 ++++++++++++++++++++++++++++++++
 2 files changed, 138 insertions(+)
 create mode 100644 lib/List/Index.pm
 create mode 100644 t/10-ranges.t

diff --git a/lib/List/Index.pm b/lib/List/Index.pm
new file mode 100644
index 0000000..513ce4f
--- /dev/null
+++ b/lib/List/Index.pm
@@ -0,0 +1,82 @@
+package List::Index;
+
+use 5.010;
+use strict;
+use warnings;
+
+our $VERSION = '1.00';
+
+sub new {
+	my ($class, $values) = @_;
+	bless [map { tr/{/./; $_ } sort map { s/[^a-z]/{/g; $_ } @$values], $class;
+}
+
+sub ranges {
+	my $self = shift;
+	my $options = shift || {};
+	my $pagesize = $options->{pagesize} || 50;
+	my $context  = $options->{context } // 1 + ($pagesize >> 4);
+	my $length   = $options->{length  } || 4;
+	my $pages    = $options->{pages   } || 1 + int $#$self / $pagesize;
+
+	$pagesize = @$self / $pages;
+	my $offset = 0;
+	my @links;
+	while ($offset < @$self) {
+		my $link = substr $self->[$offset], 0, $length;
+		if ($context) {
+			my $trim = 1;
+			my $before = $offset > $context ? $self->[$offset - $context] : '';
+			for my $match (split //, $before) {
+				scalar $link =~ /\G\Q$match/g or last;
+				$trim++;
+			}
+			substr($link, $trim) = '' unless $trim > length $link;
+		}
+
+		push @links, [$link];
+		$offset += $pagesize;
+	}
+
+	for my $i (0 .. $#links - 1) {
+		my ($link, $lastchar) = $links[$i + 1]->[0] =~ /(.*)(.)/;
+		$link .= $lastchar eq '.' ? 'z' : chr( ord($lastchar) - 1 )
+			unless $lastchar eq 'a';
+		$links[$i]->[1] = $link;
+	}
+	$links[-1]->[1] = '';
+
+	return \@links;
+}
+
+1;
+
+__END__
+
+=head1 NAME
+
+List::Index - Paginate alphabetic entries by finding minimal prefixes
+
+=head1 SYNOPSIS
+
+	use List::Index;
+	my $index = List::Index->new(\@values);
+	my @pages = $index->ranges({pagesize => 50});
+	printf '<a href="?start=%s&amp;end=%s">%1$s</a> ', @$_ for @pages;
+
+=head1 DESCRIPTION
+
+TODO
+
+=head1 SEE ALSO
+
+L<List::Maker|List::Maker> for complex ranges of numeric lists.
+
+=head1 AUTHOR
+
+Mischa POSLAWSKY <perl@shiar.org>
+
+=head1 LICENSE
+
+Copyright. All rights reserved.
+
diff --git a/t/10-ranges.t b/t/10-ranges.t
new file mode 100644
index 0000000..2b197e8
--- /dev/null
+++ b/t/10-ranges.t
@@ -0,0 +1,56 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use utf8;
+
+use Test::More tests => 16;
+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, [['a','']], 'single page');
+is_deeply($index->ranges({pages => 3}), [map { [split /-/, $_, 2] } qw(
+	a-h i-q r-
+)], 'given pages');
+is_deeply($index->ranges({pagesize => @uniform / 2.1}), [map { [split /-/, $_, 2] } qw(
+	a-h i-q r-
+)], 'equivalent pagesize');
+}
+
+{
+ok(my $index = List::Index->new(['aa'..'zz', 1..145]), 'non-alphabetic values (uniform)');
+is_deeply($index->ranges, [map { [split /-/, $_, 2] } qw(
+	a-bv bw-dr ds-fn fo-hk hl-jg jh-k l-m n-ov ow-qr qs-sn so-uk ul-wg wh-x
+	y-z .-.z ..-.z ..-..z ...-
+)], 'default ranges');
+is_deeply($index->ranges({pagesize => 300}), [map { [split /-/, $_, 2] } qw(
+	a-j k-u v-
+)], 'large pagesize');
+}
+
+{
+ok(my $index = List::Index->new([qw(
+	baaa baa1  baa2 baa3  bbc cbc  daaa ea  eaaa zed
+)]), 'variable length values');
+is_deeply($index->ranges({pagesize => 2, context => 0}), [
+	map { [split /-/, $_, 2] } qw(baaa-baaz baa.-bbb bbc-daa daaa-eaa eaaa-)
+], 'no context');
+is_deeply($index->ranges({pagesize => 2}), [
+	map { [split /-/, $_, 2] } qw(b-baaz baa.-ba bb-c d-ea eaa-)
+], 'default context');  # context should be 1
+is_deeply($index->ranges({pagesize => 2, context => 2}), [
+	map { [split /-/, $_, 2] } qw(b-a b-ba bb-c d-d e-)
+], 'overlap');  # first item equals second due to large context
+is_deeply($index->ranges({pagesize => 2, length => 1}), [
+	map { [split /-/, $_, 2] } qw(b-a b-a b-c d-d e-)
+], 'single char');
+
+#pp($index->ranges({pagesize => 2, context => 2, length => 1}));
+}
+
-- 
2.30.0