#!/usr/bin/perl
	#
	# Sample connection oriented server using Perl
	#
	
	#define constants
	$all_free = 400000000;		#cache size
	$lru_free = $all_free;	#lru cache size
	$atp_free = $all_free;	#atp cache size
	$fifo_free = $all_free;	#atp cache size
	$lfd_free = $all_free;	#atp cache size
	$atp_apt{"0000000000"}="0000000000";	#initialize access pattern table
	@t_val = (1800, 3600, 7200, 21600, 	#time constants for apt
	43200, 86400, 172800, 432000, 1296000, 2592000); 
	reverse @t_val;
	$atp_last_pred = 0;	#time of last prediction
	$atp_last_sort = 0;	#time of last sort
	$elapsed_time = 0;	#simulation time

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

	#process all files in directory with extension ".new"
	foreach $file (<*.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
			print "\rdone: ".(tell(TRACES)/$file_size)." of 1     ";
			@list = split(" ", $_);
			if(@list[13]){
				#&infinite;
				#&lru;
				&atp;
				#&fifo;
				#&lfd;
			}
		}
		$end_time = time();
		close(TRACES);
		$elapsed_time += ($end_time-$start_time);
    }
	print "\nClosed: ". $s."\n";

		print "Size = $all_free bytes, elapsed $elapsed_time seconds\n";
		if($infinite_access){print "Infinite: Acc = $infinite_access, Hits = $infinite_hits (".($infinite_hits/$infinite_access*100)."%), Miss = $infinite_miss \n".
												"WAcc = $infinite_waccess, WHits = $infinite_whits (".($infinite_whits/$infinite_waccess*100)."%), WMiss = $infinite_wmiss \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)."%), Miss = $lru_wmiss \n";}
		if($atp_access){print "ATP     : Acc = $atp_access, Hits = $atp_hits (".($atp_hits/$atp_access*100)."%), Miss = $atp_miss \n".
										"WAcc = $atp_waccess, Hits = $atp_whits (".($atp_whits/$atp_waccess*100)."%), Miss = $atp_wmiss \n";}
		if($fifo_access){print "FIFO     : Acc = $fifo_access, Hits = $fifo_hits (".($fifo_hits/$fifo_access*100)."%), Miss = $fifo_miss \n".
										"WAcc = $fifo_waccess, WHits = $fifo_whits (".($fifo_whits/$fifo_waccess*100)."%), WMiss = $fifo_wmiss \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";}
		print LOG "Size = $all_free, elapsed $elapsed_time seconds\n";
		if($infinite_access){print LOG "Infinite: Acc = $infinite_access, Hits = $infinite_hits (".($infinite_hits/$infinite_access*100)."%), Miss = $infinite_miss \n".
												"WAcc = $infinite_waccess, WHits = $infinite_whits (".($infinite_whits/$infinite_waccess*100)."%), WMiss = $infinite_wmiss \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)."%), Miss = $lru_wmiss \n";}
		if($atp_access){print LOG "ATP     : Acc = $atp_access, Hits = $atp_hits (".($atp_hits/$atp_access*100)."%), Miss = $atp_miss \n".
										"WAcc = $atp_waccess, Hits = $atp_whits (".($atp_whits/$atp_waccess*100)."%), Miss = $atp_wmiss \n";}
		if($fifo_access){print LOG "FIFO     : Acc = $fifo_access, Hits = $fifo_hits (".($fifo_hits/$fifo_access*100)."%), Miss = $fifo_miss \n".
										"WAcc = $fifo_waccess, WHits = $fifo_whits (".($fifo_whits/$fifo_waccess*100)."%), WMiss = $fifo_wmiss \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
#############################################

##########################
# infinite storage space #
##########################
	sub infinite{
		if(defined $infinite_cache{@list[7]}){
			$infinite_hits++;
			$infinite_whits += @list[5];
		}else{
			$infinite_miss++;
			$infinite_wmiss += @list[5];
		}
		$infinite_cache{@list[7]} = 1;
		$infinite_access++;
		$infinite_waccess+=@list[5];
	}

#########
# L R U #
#########
	
	sub lru{
		local($i);
		if($all_free*0.1 < @list[5]){
			$lru_miss++;
			$lru_wmiss += @list[5];
			$lru_access++;
			$lru_waccess+=@list[5];
			return 0;
		}elsif(defined $lru_cache{@list[7]}){
			#found in the cache
			$lru_hits++;
			$lru_whits += @list[5];
			#@sorted_access = sort {$lru_cache{$a} <=> $lru_cache{$b}} keys %lru_cache;
			for($i=0; @sorted_access[$i] ne @list[7]; $i++){}
			#if(1){
				splice(@sorted_access, $i, 1);	
			#}
		}else{
			#not found in the cache
			$lru_miss++;
			$lru_wmiss += @list[5];
			
			# if there is no free space in the cache...
			while($lru_free < @list[5]){
				#...free some space
				#print "lru ima: ".$lru_free." treba: ". @list[5]."\n";
				#$pom1 = $lru_cache{@sorted_access[0]};
				#$pom2 = $lru_size_cache{@sorted_access[0]};
				$lru_free += $lru_size_cache{@sorted_access[0]};
				delete($lru_cache{@sorted_access[0]});
				delete($lru_size_cache{@sorted_access[0]});
				#print "lru no space => remove: ".$pom1." ". $pom2."\n";
				#$lru_free += $pom2;
				shift(@sorted_access);
			}
			
			#now there is free space in cache
			#reserve some space
			$lru_free -= @list[5];
		}
		
		#update cache for all cases
		#add to the tail of the list
		push(@sorted_access, @list[7]);
		$lru_cache{@list[7]} = @list[0];	#new last access time
		$lru_size_cache{@list[7]} = @list[5];	#new size
		$lru_access++;
		$lru_waccess+=@list[5];
	}

#########
# A T P #
#########
	
	sub atp{
		local($i, $d, $klass, $key, $pom);
		if($all_free*0.1 < $list[5]){
			$atp_miss++;	$atp_wmiss += $list[5];
			$atp_access++;	$atp_waccess+=$list[5];
			return 0;
		}
		if(defined $atp_key_cache{$list[7]}){
			#found in the cache
			$key = $atp_key_cache{$list[7]};
			$atp_hits++;
			$atp_whits += $list[5];
			$d = $list[0] - $$key->[0];
			#print "d = $d   $$key->[2] ";
			for($i=0; $i<10; $i++){	#estimate position in the table
				if($d <= $t_val[$i]) {$klass = $i;last;}
			}
			if($i==10){$klass--;}
			$ota = $$key->[3];	#objects time access
			if(!defined ($atp_apt{$ota})){
				$ta=$ota;
			}else{
				$ta = $atp_apt{$ota};				#global time access from access patern table
			}
			if(length($ta)!=10){print "\n\a klass=$klass ta=$ta ota=$ota arp=$atp_apt{$ota}\n";}
			substr($ta, $klass, 1) = "1";
			$atp_apt{$ota}=$ta;			#update table
			$$key->[3] = $ta;			#update object's state
			#print "ta = $ta    ";
			$klass = index($ta, "1", 0);
			$$key->[0] = $list[0]; $$key->[1] = $list[5]; $$key->[2] = $list[7]; 
		}else{
			#not found in the cache
			$atp_miss++;
			$atp_wmiss += $list[5];
			
			#print "atp ima: ".$atp_free." treba: ". @list[5]."\n";
			$max_delay = -1;
			if($atp_last_pred+1800<=$list[0] && $atp_free < $list[5]){
				undef @atp_sorted_delays;
				undef @atp_sorted_keys;
				undef @urlkeys;
				undef %atp_delay_keys;
				@urlkeys = values %atp_key_cache;
				print "\nscheduling";
				for($keycount=0; $keycount<scalar(@urlkeys); $keycount++){
				    $urlkey = $urlkeys[$keycount];
					$d = @list[0] - $$urlkey->[0];

					for($i=0; $i<10; $i++){	#estimate position in the table
						if($d <= $t_val[$i]) {$klass = $i;last;}
					}
					$i = index($atp_apt{$$urlkey->[3]}, "1", $klass);	#first '1' right from $klass position
					if($i>=0 && $i<10){	#delay could be found in table
						$d = $t_val[$i];	#estimated delay
					}elsif($i<0){print "\ni<0\n"}

					push(@atp_sorted_delays, $d);
					$atp_delay_keys{$urlkey}=$d;
				}
				$atp_last_pred = $list[0];
				
				print "\nsorting".scalar(@urlkeys);
				@atp_sorted_delays = sort @atp_sorted_delays;
				print "\narangeing".scalar(@urlkeys);
				while($d=pop(@atp_sorted_delays)){
					for($urlkey=pop(@urlkeys);
						$atp_delay_keys{$urlkey}!=$d;
						$urlkey=pop(@urlkeys)){
						unshift(@urlkeys, $urlkey);
					}
					unshift(@atp_sorted_keys, $urlkey);
				}

				print "\nt=$list[0] atp_delay_keys=".scalar @atp_delay_keys." urlkeys=".scalar @urlkeys." fadded=$fadded fdeleted=$fdeleted; pomdeleted=$pomdeleted realdeleted=$frealdeleted\n";
				undef @atp_sorted_delays;
				undef @urlkeys;
				undef %atp_delay_keys;
			}


			# if there is no free space in the cache...
			while($atp_free < $list[5]){
				#...free some space

				$key = pop (@atp_sorted_keys);
																					if(!defined($key)){print "\n".scalar(@$pom)."	atp_free=$atp_free key=$key d=$d"; }
																					#print "\n".scalar(@$pom)."	atp_free=$atp_free	url=$$key->[2]	size=\n";
				$atp_free += $$key->[1];
				#delete entry in the cache
																					if(!defined($atp_key_cache{$$key->[2]})){print "\a\n".scalar(@$pom)."d=$d key=$key url=$$key->[2]"};
																					$fdeleted++;				
				delete($atp_key_cache{$$key->[2]});
																					if(!defined($atp_key_cache{$$key->[2]})){$frealdeleted++};
				undef $$key;
				undef $key;
			}
			undef $pom;
			#now there is free space in cache
			#reserve some space
			$atp_free -= $list[5];
			$atp_key_cache{$list[7]} = \[$list[0], $list[5], $list[7], "0000000000"];	#new entry
			$key = $atp_key_cache{$list[7]};
			$fadded++;

		}
		
		#update cache for all cases
		$atp_access++;
		$atp_waccess+=$list[5];
	}

###########
# F I F O #
###########

	sub fifo{
		local($i);
		if($all_free*0.1 < @list[5]){
			$fifo_miss++;
			$fifo_wmiss += @list[5];
			$fifo_access++;
			$fifo_waccess+=@list[5];
			return 0;
		}elsif(defined $fifo_cache{@list[7]}){
			#found in the cache
			$fifo_hits++;
			$fifo_whits += @list[5];
		}else{
			#not found in the cache
			$fifo_miss++;
			$fifo_wmiss += @list[5];
			
			# if there is no free space in the cache...
			while($fifo_free < @list[5]){
				#...free some space
				$fifo_free += $fifo_cache{@fifo_sorted_access[0]};
				delete($fifo_cache{@fifo_sorted_access[0]});
				shift(@fifo_sorted_access);
			}
			
			#now there is free space in cache
			$fifo_free -= @list[5];	#reserve some space
			push(@fifo_sorted_access, @list[7]);	#add to the tail of the list
		}
		
		#update cache for all cases
		$fifo_cache{@list[7]} = @list[5];	#new last access time
		$fifo_access++;
		$fifo_waccess+=@list[5];
	}

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

	sub lfd{
		my($i, $pom);
		if($all_free*0.1 < @list[5]){
			$lfd_miss++;	$lfd_wmiss += @list[5];
			$lfd_access++;	$lfd_waccess+=@list[5];
			return 0;
		}elsif(defined $lfd_cache{@list[7]}){
			#found in the cache
			$lfd_hits++;
			$lfd_whits += @list[5];
			
			#update entry for this moment
			$pom = $lfd_cache_access{@list[0]};
			substr( $pom, index($pom, @list[7])-1, lenght(@list[7])+1)="";	#removes from the list of to_be_accessd
			if($pom){$lfd_cache_access{@list[0]} = $pom;}
			else{delete($lfd_cache_access{@list[0]});}
			
			if(@list[12] eq "000000000" || @list[12] eq ">>>>>>>>>"){
				delete($lfd_cache{@list[7]});	#accessed never again
			}else{
				#updates list of to_be_accessd
				$lfd_cache_access{@list[12]} = $pom." ".@list[7];	
			}
		}else{
			#not found in the cache
			$lfd_miss++;
			$lfd_wmiss += @list[5];
			if(@list[12] eq "000000000" || @list[12] eq ">>>>>>>>>"){
				$lfd_access++;	$lfd_waccess+=@list[5];
				return 0;
			}	#accessed never again

			# if there is no free space in the cache...
			if($lfd_free < @list[5]){@lfd_sort_acc = sort (keys(%lfd_cache_access));}
			while($lfd_free < @list[5]){
				#print"\a";
				#...free some space
				$pom_time=pop(@lfd_sort_acc);	#time of farest access
				$pom=(split(' ', lfd_cache{$pom_time}))[0];		#url of  farest access
				$lfd_free += $lfd_cache{$pom};
				delete($lfd_cache{$pom});
				substr( $pom, index($pom, @list[7])-1, @list[7])="";	#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[5];	#reserve some space
			#add to cache
			$lfd_cache{@list[7]} = @list[5];	#new last access time
			$lfd_cache_access{@list[12]} = $lfd_cache_access{@list[12]}." ".@list[7];	
		}
		
		#update stats for all cases
		$lfd_access++;
		$lfd_waccess+=@list[5];
	}