#!/usr/bin/perl
	#
	# ATP algorythms
	#
	
	#define constants
	$all_free = 16000000000;		#cache size
	$atp_free = $all_free;	#atp cache size
	$atp_apt{"00000000000"}="00000000000";	#initialize access pattern table
	@t_val = (900,1800, 3600, 5400, 7200, 	#time constants for apt
	10800, 14400, 21600, 43200, 86400, 172800,3000000); 
	$atp_refresh=900;
	$atp_last_pred = 0;	#time of last prediction
	$elapsed_time = 0;	#simulation time

   	#open log file
	open(LOG, "+<rezultati_atp.txt") || die "$0: rezultati.txt will not open.";
	seek(LOG, 0,2);
	#load atp_apt
	&loadaa(\%atp_apt, "atp_atp_table.txt");
		foreach $key (keys %atp_apt) {
			print $key." ".$atp_apt{$key}."\n";
		}


	#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     ";
			#if((tell(TRACES)/$file_size)>0.25){last;}
			@list = split(" ", $_);
			if($list[13]){
				&atp;
				#&atpmin;
			}
		}
		$end_time = time();
		close(TRACES);
		$elapsed_time += ($end_time-$start_time);
    }
	print "\nClosed: ". $s."\n";
	&std_stat;
	&log_stat;
	if($atp_access){&storeaa(\%atp_apt, "+<atp_atp_table.txt");}
	if($atp_access){&storeaa(\%atp_apt, ">>atp_atp_table_all.txt");}
	if($atp_access){&storeaa(\%atp_apt_cnt, ">>atp_atp_table_all.txt");}

## end ##

sub std_stat{
		print "Size = $all_free bytes, elapsed $elapsed_time seconds	atp refresh=$atp_refresh\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)."%), WMiss = $atp_wmiss \n";}
}
sub log_stat{
		print LOG "Size = $all_free, elapsed $elapsed_time seconds	atp refresh=$atp_refresh\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)."%), WMiss = $atp_wmiss \n";}
}
#############################################
# algorythms
#############################################

#########
# 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];
			for($i=$klass=0; $i<11; $i++){	#estimate position in the table
				if($d <= $t_val[$i]) {$klass = $i;last;}
			}
			if($i==11){$klass--;}
			$ota = $$key->[3];	#objects time access
			if(defined ($atp_apt{$ota})){
				$ta=$atp_apt{$ota};
			}else{
				$ta = "00000000000";				#global time access from access patern table
			}
			substr($ta, $klass, 1) = "1";
			$atp_apt{$ota}=$ta;						#update table
			$atp_apt_cnt{$t_val[$klass]}++;			#update table counter
			substr($ota, $klass, 1) = "1";
			$$key->[3] = $ota;			#update object's state
			$$key->[0] = $list[0]; $$key->[1] = $list[5]; $$key->[2] = $list[7]; 
		}else{
			#not found in the cache
			$atp_miss++;
			$atp_wmiss += $list[5];
			
			$max_delay = -1;
			if($atp_last_pred+$atp_refresh<=$list[0] && $atp_free < $list[5]){
				undef @atp_sorted_keys;
				@urlkeys = values %atp_key_cache;
				print "\nscheduling";
				for($keycount=0; $keycount<scalar(@urlkeys); $keycount++){
				    $urlkey = $urlkeys[$keycount];
					$d = $list[0] - $$urlkey->[0];

					for($klass=0; $klass<11; $klass++){	#estimate position in the table
						if($d <= $t_val[$klass]) {last;}
					}
					if($klass==11){$i=11;}
					else{$i = index($atp_apt{$$urlkey->[3]}, "1", $klass);}	#first '1' right from $klass position
					if($i<0){$i=$klass;}
					#mozda bi trebalo klasifikovati vreme do sledeceg pristupa
					#a ne kao do sad stanje!
					push @{$klasses{$i}}, $urlkey;
				}
				$atp_last_pred = $list[0];
				
				print "\nsorting".scalar(@urlkeys);
				for($klass=0; $klass<=11; $klass++){	#estimate position in the table
					if(defined $klasses{$klass}) {
						$a=$klasses{$klass};
						push(@atp_sorted_keys, @$a);
					}
				}
				print "\nt=$list[0] atp_free=$atp_free atp_sorted_keys=".scalar @atp_sorted_keys." fadded=$fadded fdeleted=$fdeleted; realdeleted=$frealdeleted\n";
				undef %klasses;
			}

			# if there is no free space in the cache...
			while($atp_free < $list[5]){
				#...free some space
				$key = pop (@atp_sorted_keys);
				$atp_free += $$key->[1];
				delete($atp_key_cache{$$key->[2]});		#delete entry in the cache
				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], "00000000000"];	#new entry
			$key = $atp_key_cache{$list[7]};
			$fadded++;

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


###############
# A T P M I N #
###############
	
	sub atpmin{
		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];
			for($i=$klass=0; $i<11; $i++){	#estimate position in the table
				if($d <= $t_val[$i]) {$klass = $i;last;}
			}
			if($i==11){$klass--;}
			$ota = $$key->[3];	#objects time access
			if(defined ($atp_apt{$ota})){
				$ta=$atp_apt{$ota};
			}else{
				$ta = "00000000000";				#global time access from access patern table
			}
																				#if(length($ta)!=11){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
			$atp_apt_cnt{$t_val[$klass]}++;			#update table counter
			substr($ota, $klass, 1) = "1";
			$$key->[3] = $ota;			#update object's state
			#$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];
			
			$max_delay = -1;
			if($atp_last_pred+$atp_refresh<=$list[0] && $atp_free < $list[5]){
				undef @atp_sorted_keys;
				@urlkeys = values %atp_key_cache;
				print "\nscheduling";
				for($keycount=0; $keycount<scalar(@urlkeys); $keycount++){
				    $urlkey = $urlkeys[$keycount];
					$d = $list[0] - $$urlkey->[0];

					for($klass=0; $klass<11; $klass++){	#estimate position in the table
						if($d <= $t_val[$klass]) {last;}
					}
					if($klass==11){$i=11;}
					else{$i = index($atp_apt{$$urlkey->[3]}, "1", $klass);}	#first '1' right from $klass position
					if($i<0){$i=$klass;}
					#mozda bi trebalo klasifikovati vreme do sledeceg pristupa
					#$d=$t_val[$i]-$d;
					#for($klass=0; $klass<11; $klass++){	#estimate position in the table
					#	if($d <= $t_val[$klass]) {last;}
					#}
					#a ne kao do sad stanje!
					
					#push @{$klasses{$klass}}, $urlkey;	#klasifikuje vreme do sledeceg pristupa
					push @{$klasses{$i}}, $urlkey;	#klasifikuje stanje
				}
				$atp_last_pred = $list[0];
				
				print "\nsorting".scalar(@urlkeys);
				for($klass=0; $klass<=11; $klass++){	#estimate position in the table
					if(defined $klasses{$klass}) {
						$a=$klasses{$klass};
						unshift(@atp_sorted_keys, @$a);
					}
				}

				print "\nt=$list[0] atp_free=$atp_free atp_sorted_keys=".scalar @atp_sorted_keys." fadded=$fadded fdeleted=$fdeleted; realdeleted=$frealdeleted\n";
				undef %klasses;
			}


			# if there is no free space in the cache...
			for($i=0, $scalsize=2*$list[5]; $atp_free < $list[5]; $i++, $i%=(scalar @atp_sorted_keys)){
				if($i==0){$scalsize/=2;}
				#...free some space
				$key = $atp_sorted_keys[$i];
				$size = $$key->[1];
				if($size>=$scalsize){
					$atp_free += $size;
					#delete entry in the cache
					delete($atp_key_cache{$$key->[2]});
					$fdeleted++;	if(!defined($atp_key_cache{$$key->[2]})){$frealdeleted++};
					undef $$key; undef $key; undef $size;
					splice(@atp_sorted_keys, $i, 1);
				}
			}


			#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], "00000000000"];	#new entry
			$key = $atp_key_cache{$list[7]};
			$fadded++;

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

############################################
#subroutine for dumping asoc array to file #
############################################

sub storeaa($$){
	my $a=shift(@_), $f=shift(@_), $key;

	open(DMP, "$f") || die "$0: will not open.";
	
		foreach $key (keys %$a) {
			print DMP $key." ".$$a{$key}."\n";
		}

	close DMP;
}

sub loadaa($$){
	my $a=shift(@_), $f=shift(@_), $key;

	open(DMP, "<$f") || die "$0: will not open.";
	
		while(<DMP>) { # takes data from $file
			@list = split(" ", $_);
			$$a{$list[0]}=$list[1];
		}

	close DMP;
}