#!/usr/bin/perl -w
#################################################################################
#
# RD Perl Script provides RD from a file containing sequence numbers
#
# Usage:
# RD.pl input_file DT_value [-debug]
#
# 1. The input file must contain sequence numbers
# 2. If DT value is not provided then the deafult value is 10
#
#################################################################################

my($DT,$pl);
my(@seq,@window,@buffer);
my(%FLE);

my $debug=0;

sub get_new_seq()
{
   my $new_seq = shift @seq;
   return $new_seq;
}

sub exists_in_array()           # Utility subroutine: returns index of an element if it exists in the array given else -1
{
   my ($key,@in) = @_;
   my $i = 0;
   if ($key && ($#in >= 0))
   {
       foreach $k(@in)
       {
           return $i if ($key == $k);
           $i++;
       }
   }
   return -1;
}


sub min_in_array()
{
   my $arr_r = shift , $min=-1;
   my @arr = @$arr_r;
   if ($#arr > 0)
   {
      $min = $arr[0];
      foreach (@arr)
      {
          $min = $_ if ($_ < $min);
      }
   }
   return($min);
}

sub print_windows()
{
   print "\t\twindow = @window\n";
}

if ($#ARGV == 2) { $DT = $ARGV[1]; $file = $ARGV[0]; if ($ARGV[2] eq "-debug") { $debug = 1; }}
elsif ($#ARGV == 1) { $DT = $ARGV[1]; $file = $ARGV[0];}
elsif ($#ARGV == 0) { $DT = 10; $file = $ARGV[0]; }
else { print "Format:$0 input-file [DT value] [-debug]\n"; exit;}

if ($debug) { print "Reading input file...";}
open IN , $file or die "Error:Could not open input file";       # Open input file with sequence numbers
while (<IN>) { chomp; push @seq,$_; }
close IN;
if ($debug) { print "Read ".($#seq+1)." sequence numbers\n"; }

$pl = 1;

# Read in first DT+1 non-duplicate sequence numbers or whole sequence if lesser than DT+1
foreach (0..$DT)
{
   do {$new_seq = &get_new_seq; }
   while ($new_seq &&
          ((&exists_in_array($new_seq,@buffer) != -1) ||
           (&exists_in_array($new_seq,@window) != -1) ||
           ($new_seq < $pl)));
   if ($new_seq) { push @window,$new_seq; } else { last; }
}

if ($#window == -1) {print "No sequence numbers to process\n";exit;}

while(1)
{
   $pl_source = 0;
   if ($debug)
   {
       if ($debug) { print "Currently:\n";
       print "\tPl = $pl\n\twindow=@window\n\tbuffer=@buffer\n"; }
   }
   $pl_position = &exists_in_array($pl,@window);
   if ($pl_position == -1) {$pl_position = &exists_in_array($pl,@buffer); $pl_source = 1;}

   if ($pl_position != -1)
   {
       $reordering = $pl - $window[0];
       if ($debug) {print "Found reordering = $reordering for $window[0]\n";}
       if (abs($reordering) <= $DT)
       {
          $FLE{$reordering}++;
          if ($pl_source == 1)
          {
             if ($debug) { print "Pl = $pl found in buffer\n"; }
             splice @buffer,$pl_position,1;
          }
          if ($reordering < 0) { push @buffer , $window[0]; }
          $pl++;
       }
       else { if ($debug) {print "Reordering more than DT, ignoring the packet...\n";}}
       shift @window;
       do {$new_seq = &get_new_seq; }
       while ($new_seq &&
              ((&exists_in_array($new_seq,@buffer) != -1) ||
               (&exists_in_array($new_seq,@window) != -1) ||
               ($new_seq < $pl)));
       if ($new_seq) {push @window,$new_seq;}
       last if ($#window < 0);
   }
   else
   {
       $m = &min_in_array(\@window);
       if ($pl < $m) {$pl = $m;} else {$pl++;}
   }
}

if ($debug) { print "\n\nFinal RD\n";
print "DT = $DT\n"; }

$sum = 0;
foreach $i(keys(%FLE))
{
   $sum += $FLE{$i};
}
if ($sum)
{
   foreach (sort {$a <=> $b} keys(%FLE))
   {
       $freq = $FLE{$_}/$sum;
       print "RD[$_] $FLE{$_} $freq\n";
   }
}
else
{
       print "All zero frequency\n";
}