#!/usr/bin/perl -w

use strict;

my $longformat;
$longformat= 1, shift @ARGV if @ARGV && $ARGV[0] eq "-l";

if( @ARGV == 1 && $ARGV[0] =~ /^--?h(?:elp)?$/i ) {
    print <<EOF;
usage: mulrangegapsdups.pl <strings> ...
       listsomething | mulrangegapsdups.pl
Determine gaps and duplicates in strings (such as file names) supposed to
contain consecutive numbers.  If the strings contain multiple numbers, all
ranges must be contiguous (such as 1, 2_1, 2_2, 2_3, 3_4, 3_5, 3_6, 4, 5_3, 6).
Strings not containing any numbers will be ignored.  If no command-line
arguments are given, input is read from stdin and separated at white space.
EOF
    exit;
}


# Find gaps in sequence of numbers.
# -> Reference to array of numbers.  Need not be sorted.
#    Reference to array for storing gap intervals in format [ from, to ].
#    Reference to Hash for storing duplicates (key = number, value = duplicity)
# The last two references may be undef if the information is not of interest.
sub findgaps
{
    my ($nums, $gaps, $dups)= @_;
    
    if( @$nums < 2 ) {
        @$gaps= () if $gaps;
        %$dups= () if $dups;
        return;
    }
    my %nums;
    ++ $nums{$_} for @$nums;
    if( $gaps ) {
        my @sorted= sort { $a <=> $b } keys %nums;
        @$gaps= ();
        if( $#sorted != $sorted[-1] - $sorted[0] ) {
            my $next= $sorted[0];
            for (@sorted) {
                push @$gaps, [ $next, $_-1 ] if $_ > $next;
                $next= $_+1;
            }
        }
    }
    if( $dups ) {
        delete @nums{grep $nums{$_} < 2, keys %nums};
        %$dups= %nums;
    }
}


# Print out list of gaps and duplicates in a sequence.
# -> Prefix to print before each number
#    Reference to array containing gap intervals in format [ from, to ].
#    Reference to Hash containing duplicates (key = number, value = duplicity)
sub printgapsdups
{
    my ($prefix, $gaps, $dups)= @_;

    my %all= %$dups;
    @all{map $$_[0], @$gaps}= @$gaps;
    for (sort { $a <=> $b } keys %all) {
        print $prefix, $_;
        if( !ref $all{$_} ) {
            print ":  $all{$_} duplicates\n";
        }
        elsif( $all{$_}[1] == $_ ) {
            print ":  missing\n";
        }
        else {
            print " to $prefix$all{$_}[1]:  missing\n";
        }
    }
}


# Find and print gaps and duplicates recursively at and below one level.
# -> Prefix for printing sub-level indication
#    Reference to array of array references containing sets of numbers from
#    input strings
sub process_level
{
    my ($prefix, $list)= @_;
    my %subtrees;
    my @leaves;
    my @gaps;
    my %dups;

    for (@$list) {
        next unless @$_ > 0;
        if( @$_ > 1 ) {
            push @{$subtrees{$$_[0]}}, [ @$_[1..$#$_] ];
        }
        else {
            push @leaves, $$_[0];
        }
    }
    push @leaves, keys %subtrees;
    findgaps( \@leaves, \@gaps, \%dups );
    printgapsdups( $prefix, \@gaps, \%dups );
    for (sort { $a <=> $b } keys %subtrees) {
        process_level( "$prefix$_-", $subtrees{$_} );
    }
}


exit if @ARGV == 1;

my @nums;
if( @ARGV > 1 ) {
    @nums= @ARGV;
}
else {
    my $all= "";
    $all .= $_ while <>;
    @nums= split /\s+/, $all;
}

for (@nums) {
    $_= [ /\d+/g ];
}

# use Data::Dumper;
# print Dumper(\@nums);

process_level( "", \@nums );


