#!/usr/bin/perl
	#
	# LFD algorythm
	#
	
	#define constants
	
	#format of new traces
	$_Timestamp=0; 	$_Elapsed_Time=1;	$_HTTP_code=2;  
	$_Size=3; 		$_Method=4; 		$_URL=5;
	$_Exp_Date=6;	$_Next_Acc=7; 		$_Cacheable=8;

	$all_free = 16000000000;							#cache size
	$lfd_free = $all_free;								#lfd cache size
	$elapsed_time = 0;									#simulation time
	$path="";											#path to the working directory


   	#open log file
	$logname="rez_lfd.txt";
	open(LOG, "+<$path$logname") || die "$0: $path$logname will not open.";
	seek(LOG, 0,2);


	#process all files in directory with extension ".new"
	foreach $file (<$path*.new>) {
       	open(TRACES, "+<$file") || die "$file will not open.";
		print "\nOpened: ". $file. "\n";
		seek(TRACES, 0,2); $file_size = tell(TRACES); seek(TRACES, 0,0); 
		
		$pos = tell(TRACES);
		$prev_pos = tell(TRACES);
		$start_time = time();
		while(<TRACES>) { # takes data from $file
			$proc=tell(TRACES)/$file_size;
			print "\r$cur_time done: ".$proc." of 1     ";
			#if($proc>0.025){last;}
			@list = split(" ", $_);
			if($list[$_Cacheable]){
				&lfd;
			}
		}
		$end_time = time();
		close(TRACES);
		$elapsed_time += ($end_time-$start_time);
    }

	&std_stat;											#stat to screen
	&log_stat;											#stat to log file

	close(LOG);
	print "\nClosed: $path$logname\n";

## end ##


sub std_stat{
		print "Size = $all_free bytes, elapsed $elapsed_time seconds	atp refresh=$atp_refresh\n";
		if($lfd_access){print "LFD     : Acc = $lfd_access, Hits = $lfd_hits (".($lfd_hits/$lfd_access*100)."%), Miss = $lfd_miss \n".
							  "			 WAcc = $lfd_waccess, WHits = $lfd_whits (".($lfd_whits/$lfd_waccess*100)."%), WMiss = $lfd_wmiss \n";}
}
sub log_stat{
		print LOG "Size = $all_free, elapsed $elapsed_time seconds	atp refresh=$atp_refresh\n";
		if($lfd_access){print LOG "LFD     : Acc = $lfd_access, Hits = $lfd_hits (".($lfd_hits/$lfd_access*100)."%), Miss = $lfd_miss \n".
										"WAcc = $lfd_waccess, WHits = $lfd_whits (".($lfd_whits/$lfd_waccess*100)."%), WMiss = $lfd_wmiss \n";}
}
#############################################
# algorythms
#############################################

#########
# L F D #
#########

	sub lfd{
		my($i, $pom);
		if($all_free*0.1 < $list[$_Size]){			#if filesize > 10% of cache size => file is not cacheable
			$lfd_miss++;	$lfd_wmiss += $list[$_Size];
			$lfd_access++;	$lfd_waccess+=$list[$_Size];
			return 0;
		}elsif(defined $lfd_cache{$list[$_URL]}){
			#found in the cache
			$lfd_hits++;	$lfd_whits += $list[$_Size];
			
			#update entry for this moment $list[$_URL]
			$pom = $lfd_cache_access{$list[$_Timestamp]};							#lfd_cache_access holds list of URLs that will be accessed in $_Timestamp time

			substr( $pom, index($pom, $list[$_URL])-1, length($list[$_URL])+1)="";	#removes from the list of to_be_accessd
			if($pom){$lfd_cache_access{$list[$_Timestamp]} = $pom;}					#list is not empty
			else{delete($lfd_cache_access{$list[$_Timestamp]});}					#list is empty
			
			if($list[$_Next_Acc] eq "000000000" || $list[$_Next_Acc] eq ">>>>>>>>>"){
				delete($lfd_cache{$list[$_URL]});									#accessed never again
			}else{
				#updates list of to_be_accessd
				$lfd_cache_access{$list[$_Next_Acc]} = $pom." ".$list[$_URL];	
			}
		}else{
			#not found in the cache
			$lfd_miss++;		$lfd_wmiss += $list[$_Size];

			if($list[$_Next_Acc] eq "000000000" || $list[$_Next_Acc] eq ">>>>>>>>>"){
				#accessed never again
				$lfd_access++;	$lfd_waccess+=$list[$_Size];
				return 0;
			}	

			# if there is no free space in the cache...
			if($lfd_free < $list[$_Size]){@lfd_sort_acc = sort (keys(%lfd_cache_access));}
			while($lfd_free < $list[$_Size]){
				#...free some space
				$pom_time=pop(@lfd_sort_acc);									#time of the farest access
				$pom=(split(' ', $lfd_cache{$pom_time}))[0];					#url of  the farest access
				$lfd_free += $lfd_cache{$pom};
				delete($lfd_cache{$pom});
				substr( $pom, index($pom, $list[$_URL])-1, $list[$_URL])="";	#removes from the list of to_be_accessd
				if($pom){$lfd_cache_access{$pom_time} = $pom;}
				else{delete($lfd_cache_access{$pom_time});}
			}
			
			#now there is free space in cache
			$lfd_free -= $list[$_Size];											#reserve some space
			#add to the cache
			$lfd_cache{$list[$_URL]} = $list[$_Size];							#new last access time
			$lfd_cache_access{$list[$_Next_Acc]} = $lfd_cache_access{$list[$_Next_Acc]}." ".$list[$_URL];	
		}
		
		#update stats for all cases
		$lfd_access++;
		$lfd_waccess+=$list[$_Size];
	}