#!/usr/bin/perl
	#
	# LRU & LRU min algorithms
	#
	
	#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
	$lru_free = $all_free;								#lru cache size
	$lrumin_free = $all_free;							#lru cache size
	$elapsed_time = 0;									#simulation time
	$path="";											#path to the working directory

   	#open log file
	$logname="rez_lru.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]){
				&lru;
				#&lrumin;
			}
		}
		$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($lru_access){print	"LRU     : Acc = $lru_access, Hits = $lru_hits (".($lru_hits/$lru_access*100)."%), Miss = $lru_miss \n".
								"		   WAcc = $lru_waccess, Hits = $lru_whits (".($lru_whits/$lru_waccess*100)."%), WMiss = $lru_wmiss \n";}
		if($lrumin_access){print	"LRUMIN     : Acc = $lrumin_access, Hits = $lrumin_hits (".($lrumin_hits/$lrumin_access*100)."%), Miss = $lrumin_miss \n".
								"		   WAcc = $lrumin_waccess, Hits = $lrumin_whits (".($lrumin_whits/$lrumin_waccess*100)."%), WMiss = $lrumin_wmiss \n";}
}
sub log_stat{
		print LOG "Size = $all_free, elapsed $elapsed_time seconds	atp refresh=$atp_refresh\n";
		if($lru_access){print LOG "LRU     : Acc = $lru_access, Hits = $lru_hits (".($lru_hits/$lru_access*100)."%), Miss = $lru_miss \n".
										"WAcc = $lru_waccess, Hits = $lru_whits (".($lru_whits/$lru_waccess*100)."%), WMiss = $lru_wmiss \n";}
		if($lrumin_access){print LOG	"LRUMIN     : Acc = $lrumin_access, Hits = $lrumin_hits (".($lrumin_hits/$lrumin_access*100)."%), Miss = $lrumin_miss \n".
								"		   WAcc = $lrumin_waccess, Hits = $lrumin_whits (".($lrumin_whits/$lrumin_waccess*100)."%), WMiss = $lrumin_wmiss \n";}
}
#############################################
# algorythms
#############################################


#########
# L R U #
#########
	
	sub lru{
		my($i);
		if($all_free*0.1 < $list[$_Size]){
			$lru_miss++;		$lru_wmiss += $list[$_Size];
			$lru_access++;		$lru_waccess+=$list[$_Size];
			return 0;
		}elsif(defined $lru_cache{$list[$_URL]}){
			#found in the cache
			$lru_hits++;		$lru_whits += $list[$_Size];

			for($i=0; $sorted_access[$i] ne $list[$_URL]; $i++){}			#$sorted_access holds accesses by turn
			splice(@sorted_access, $i, 1);									#remove from list (and addto the tail later)
		}else{
			#not found in the cache
			$lru_miss++;
			$lru_wmiss += $list[$_Size];
			
			# if there is no free space in the cache...
			while($lru_free < $list[$_Size]){
				#...free some space

				$lru_free += $lru_size_cache{$sorted_access[0]};			#$lru_size_cache holds sizes for each URL
				delete($lru_cache{$sorted_access[0]});						#remove from list of URLs in cache
				delete($lru_size_cache{$sorted_access[0]});					#remove from list of sizes in cache
				shift(@sorted_access);										#remove from list of URLs by access
			}
			
			#now there is free space in cache
			#reserve some space
			$lru_free -= $list[$_Size];
		}
		
		#update cache for all cases
		#add to the tail of the list
		push(@sorted_access, $list[$_URL]);									#add last accessed to the tail of list
		$lru_cache{$list[$_URL]} = $list[$_Timestamp];						#new last access time
		$lru_size_cache{$list[$_URL]} = $list[$_Size];						#new size
		$lru_access++;
		$lru_waccess+=$list[$_Size];
	}

###############
# L R U M I N #
###############
	
	sub lrumin{
		my($i, $size);
		if($all_free*0.1 < $list[$_Size]){
			$lrumin_miss++;		$lrumin_wmiss += $list[$_Size];
			$lrumin_access++;	$lrumin_waccess+=$list[$_Size];
			return 0;
		}elsif(defined $lrumin_cache{$list[$_URL]}){
			#found in the cache
			$lrumin_hits++;
			$lrumin_whits += $list[$_Size];
			for($i=0; $sorted_access[$i] ne $list[$_URL]; $i++){}			#$sorted_access holds accesses by turn
			splice(@sorted_access, $i, 1);									#remove from list (and addto the tail later)
		}else{
			#not found in the cache
			$lrumin_miss++;
			$lrumin_wmiss += $list[$_Size];
			
			# if there is no free space in the cache...
			for($i=0, $scalsize=2*$list[$_Size]; $lrumin_free < $list[$_Size]; $i++, $i%=(scalar @sorted_access)){
				if($i==0){$scalsize/=2;}
				#...free some space
				$size = $lrumin_size_cache{$sorted_access[$i]};				#$lrumin_size_cache holds sizes for each URL
				if($size>=$scalsize){										#old file size should be > n.f.s or > 0,5 n.f.s....
					$lrumin_free += $size;
					delete($lrumin_cache{$sorted_access[$i]});				#remove from list of URLs in cache
					delete($lrumin_size_cache{$sorted_access[$i]});			#remove from list of sizes in cache
					splice(@sorted_access, $i, 1);							#remove from list of URLs by access
				}
			}
			
			#now there is free space in cache
			#reserve some space
			$lrumin_free -= $list[$_Size];
		}
		
		#update cache for all cases
		#add to the tail of the list
		push(@sorted_access, $list[$_URL]);									#add last accessed to the tail of list
		$lrumin_cache{$list[$_URL]} = $list[$_Timestamp];					#new last access time
		$lrumin_size_cache{$list[$_URL]} = $list[$_Size];					#new size
		$lrumin_access++;
		$lrumin_waccess+=$list[$_Size];
	}