#!/usr/bin/perl -wT

use strict;
use warnings;

# Generate a regex accepting any string but the string of concatenated numbers
# lower_bound to upper_bound (each inclusive).
sub generate_regex {
    my($lower_bound, $upper_bound, $mode) = @_;
    my $regex;

    # generate not_string
    my $not_string = "";
    for my $number ($lower_bound..$upper_bound) {
        $not_string .= "" . $number;
    }
    my $l = length $not_string;

    # mode 3 = lookahead
    if ($mode eq 3) {
        return "^(?!" . $not_string . "\$).*\$";
    }

    $regex .= "^(";

    # strings with length smaller than not_string
    # mode 1 == |.|..|...|…
    if ($mode eq 1) {
        for my $i (0..($l-1)) {
            $regex .= "." x $i;
            if ($i ne $l - 1) {
                $regex .= "|";
            }
        }
    # mode 2 == .?.?.?.?…
    } elsif ($mode eq 2) {
        $regex .= ".?" x ($l - 1);
    }

    $regex .= "|";

    # strings with length equal to not_string
    for my $index (0..($l-1)) {
        $regex .= "." x $index;
        $regex .= "[^" . substr($not_string, $index, 1) . "]";
        $regex .= "." x ($l - $index - 1);
        if ($index ne ($l - 1)) {
            $regex .= "|";
        }
    }

    $regex .= "|";

    # strings with length greater than not_string
    $regex .= "." x $l . ".+)\$";

    return $regex;
}

# Generate less than `(upper_bound - lower_bound)^2` input strings.
# Returns testsuite dict.
sub generate_input_strings {
    my($lower_bound, $upper_bound) = @_;
    my %testsuite;

    # generate not_string
    my $not_string = "";
    for my $number ($lower_bound..$upper_bound) {
        $not_string .= "" . $number;
    }

    # generate strings
    for my $begin ($lower_bound..$upper_bound) {
        for my $end (($begin + 1)..$upper_bound) {
            my $input_string = substr($not_string, $begin, $end - $begin);
            my $matches = ($input_string ne $not_string);
            $testsuite{$input_string} = $matches;
        }
    }

    return %testsuite;
}


sub run_test {
    my($regex, %testsuite) = @_;

    for my $input (keys %testsuite) {
        my $matches = !!($input =~ $regex);
        if ($matches ne !!$testsuite{$input}) {
            printf "FAIL for %s (should be %s)\n", $input, $matches;
        }
    }
}

sub main {
    my $low = 1;
    my $upp = 500;

    my $regex = generate_regex($low, $upp, 3);
    my %testsuite = generate_input_strings($low, $upp);

    printf "Generated regex of string length %d.\n", length $regex;
    printf "Generated %d input strings.\n", scalar keys %testsuite;

    print "Regex compilation not available.\n";

    my $begin = time;
    run_test($regex, %testsuite);
    my $end = time;

    print "It takes " . ($end - $begin) . " seconds to test all input strings.\n";
}

main();