#!/usr/bin/perl -w

# Version 3: Dated: 10/06/2004

my($BT,$i,$newE,$new_seq,$buffer_i,$seq_i);
my(@window,@buffer,@seq);

my $debug = 1 ,$step=1;

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

if ($debug) {print "Reading input file...";}
open IN , $ARGV[0] 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"; }
$seq_i = 0;

# Read in first BT+1 non-duplicate sequence numbers or whole sequence if lesser than BT+1
foreach (0..$BT)
{
    $new_seq = shift @seq;
    if (!($new_seq)) { last; }
    elsif (&exists_in_array($new_seq,@window) == -1)
    {
	push @window,$new_seq;
    }
}

if ($debug) {print "Start execution.\n";}
while(1)
{
    # Find minimum in current window to act as the next expected
    ($E) = &minimum(@window);
    if ($debug) {print "E = $E ";}

    # First packet in window as next S. It is deleted from the window.
    $S = shift @window;
    if ($debug) {print "S = $S\n";}

    if ($S == $E)
    {
	# Find minimum in window. If window is empty, there is no minimum.
	if ($#window >= 0) { ($min_win) = &minimum(@window);}
	else { undef $min_win; }

	while (1)
	{
	    if ($debug) {print "Buffer size = " ,$#buffer + 1,"\n";}

	    # If buffer is not empty
	    if ($#buffer >= 0)
	    {
		($min_buf,$pos) = &minimum(@buffer);

		# If window is empty or minimum in buffer < minimum in window, the packet in buffer can be freed.
		if (!defined($min_win) || ($min_buf < $min_win))
		{ 
		    splice @buffer , $pos , 1;
		}
		else { last; }
	    }
	    else { $E = $min_win; last; } # Need to change E to detect duplicates
	}
    }
    else
    {
	push @buffer,$S;		# if S != E, we need to keep it in RD buffer
    }

    if ($debug) {&print_windows;}

    $F[$#buffer + 1]++;		# Increment frequence of current buffer occupancy

    if ($new_seq = &get_new_seq)
    {
	push @window,$new_seq;		# Append a new non-duplicate packet at the end of window
    }

    if ($#window == -1)			# if there is nothing in window
    {
	foreach (0 .. $#buffer)
	{
	    $F[0]++;			# Just increment frequency of 0 for each packet in buffer
	}
	last;				# And BREAK main loop
    }
}

$sum = 0;
foreach $i(0 .. $#F)
{
    $sum += $F[$i];
}
if ($sum)
{
	foreach $i(0 .. $#F)
	{
	   $freq = $F[$i]/$sum;
    	   print "RBD[$i] $F[$i] $freq\n";
	}
}
else
{
	print "All zero frequency\n";
}


sub get_new_seq()
{
    my $new_seq;
    while (1)
    {
	$new_seq = shift @seq;
	if (!($new_seq)) { return $new_seq; }
	elsif ((exists_in_array($new_seq,@window,@buffer) == -1) &&  # packet does not alreay exist in window or buffer
	       ($new_seq > $E))      # packet seq is greater than or equal to current anticipated value
	{
	    return $new_seq;
	}
	else {print "Found duplicate (or ignored) $new_seq\n";}
    }
}

sub print_windows()
{
    print "\t\twindow = @window\n";
    print "\t\tbuffer = @buffer\n";
    print "\t\tbuffer size = ".($#buffer + 1)."\n";
}

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 minimum
{
    @arr = @_;
    if ($#arr < 0) { return (-1,-1); }
    $min = $arr[0];
    $pos = 0;
    foreach $i (1..$#arr)
    {
    	if ($arr[$i] < $min)
    	{
    	    $min = $arr[$i];
    	    $pos = $i;
    	}
    }
    return ($min,$pos);
}