#!/usr/bin/env perl

use strict;
use warnings;
use autodie;

use Tie::File;

my $subset_size = 4;
my $min_distance = 20;
my (%sample, @keep);

tie my @locations, 'Tie::File', './pm_1084445_locations.txt';

my $last_index = $#locations;
my @indexes = 0 .. $last_index;

for (0 .. $last_index) {
    my $rand_index = int rand @indexes;
    my ($chr, $pos) = (split ' ', $locations[$indexes[$rand_index]])[0, 1];

    if (is_new_location(\%sample, $min_distance, $chr, $pos)) {
        push @keep, $indexes[$rand_index];
        add_location(\%sample, $chr, $pos);
    }

    splice @indexes, $rand_index, 1;

    last if @keep == $subset_size;
}

if (@keep < $subset_size) {
    warn 'WARNING! Subset size [', scalar @keep,
            "] is less than the required size [$subset_size].\n";
}
else {
    print "$_\n" for @locations[sort { $a <=> $b } @keep];
}

untie @locations;


sub is_new_location {
    my ($sample, $min, $chr, $pos) = @_;

    return 1 unless $sample->{$chr};

    for (@{$sample->{$chr}}) {
        return 0 if abs($_ - $pos) < $min;
    }

    return 1;
}

sub add_location {
    my ($sample, $chr, $pos) = @_;

    my $index = 0;

    for (@{$sample->{$chr}}) {
        last if $_ > $pos;
        ++$index;
    }

    splice @{$sample->{$chr}}, $index, 0, $pos;

    return;
}