#!/usr/bin/perl
	#
	# All algorythms
	#
	
	#define constants
	$all_free = 16000000000;		#cache size
	$yeh_free = $all_free;	#atp cache size
	@t_val = (900,1800, 3600, 5400, 7200, 	#time constants for apt
	10800, 14400, 21600, 43200, 86400, 172800,3000000); 
	$yeh_apt{"00000000000"}=0;	#initialize access pattern table
	$yeh_last_sort = 0;	#time of last sort
	$yeh_refresh=60;
	$yeh_last_pred = 0;	#time of last prediction
	$yeh_last_sort = 0;	#time of last sort
	$elapsed_time = 0;	#simulation time

   	#open log file
	open(LOG, "+<rezultati_yeh.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     ";
			#if((tell(TRACES)/$file_size)>0.25){last;}
			@list = split(" ", $_);
			if($list[13]){
				&yeh;
			}
		}
		$end_time = time();
		close(TRACES);
		$elapsed_time += ($end_time-$start_time);
    }
	print "\nClosed: ". $s."\n";
	&std_stat;
	&log_stat;
	if($yeh_access){&storeaa(\%yeh_apt, ">>yeh_atp_table_all.txt");}
	if($yeh_access){&storeaa(\%yeh_apt_cnt, ">>yeh_atp_table_all.txt");}

## end ##

sub std_stat{
		print "Size = $all_free bytes, elapsed $elapsed_time seconds	atp refresh=$atp_refresh\n";
		if($yeh_access){print	"YEH     : Acc = $yeh_access, Hits = $yeh_hits (".($yeh_hits/$yeh_access*100)."%), Miss = $yeh_miss \n".
								"		   WAcc = $yeh_waccess, Hits = $yeh_whits (".($yeh_whits/$yeh_waccess*100)."%), WMiss = $yeh_wmiss \n";}
}
sub log_stat{
		print LOG "Size = $all_free, elapsed $elapsed_time seconds	atp refresh=$atp_refresh\n";
		if($yeh_access){print LOG	"YEH     : Acc = $yeh_access, Hits = $yeh_hits (".($yeh_hits/$yeh_access*100)."%), Miss = $yeh_miss \n".
								"		   WAcc = $yeh_waccess, Hits = $yeh_whits (".($yeh_whits/$yeh_waccess*100)."%), WMiss = $yeh_wmiss \n";}
}
#############################################
# algorythms
#############################################

#########
# Y E H #
#########
	
	sub yeh{
		local($i, $d, $klass, $key, $pom);
		if($all_free*0.1 < $list[5]){
			$yeh_miss++;	$yeh_wmiss += $list[5];
			$yeh_access++;	$yeh_waccess+=$list[5];
			return 0;
		}
		if(defined $yeh_key_cache{$list[7]}){
			#found in the cache
			$key = $yeh_key_cache{$list[7]};
			$yeh_hits++;
			$yeh_whits += $list[5];
			$d = $list[0] - $$key->[0];
			for($i=$klass=0; $i<$#t_val; $i++){	#estimate position in the table
				if($d <= $t_val[$i]) {$klass = $i;last;}
			}
			if($i==$#t_val){$klass=$#t_val-1;}
			$ota = $$key->[3];	#objects time access
			if(defined ($yeh_apt{$ota})){
				$ta=$yeh_apt{$ota};
			}else{
				$ta = 0;				#global time access from access patern table
			}
																				#if(length($ota)!=$#t_val){print "\n\a klass=$klass ta=$ta ota=$ota arp=$yeh_apt{$ota}\n";}
			$ta = ($t_val[$klass]+$ta)/2;	#check average, now last
			$yeh_apt{$ota}=$ta;			#update table
			$yeh_apt_cnt{$ota}++;			#update table counter
			$ota="$klass".$ota;	$ota=substr($ota, 0, 4);
			$$key->[3] = $ota;			#update object's state
			print "ta = $ta    ota=$ota         klass=$klass        ";
			$$key->[0] = $list[0]; $$key->[1] = $list[5]; $$key->[2] = $list[7]; 
		}else{
			#not found in the cache
			$yeh_miss++;
			$yeh_wmiss += $list[5];
			
			#print "yeh ima: ".$yeh_free." treba: ". $list[5]."\n";
			if($yeh_last_pred+$yeh_refresh<=$list[0] && $yeh_free < $list[5]){
				undef @yeh_sorted_keys;
				@urlkeys = values %yeh_key_cache;
				print "\nscheduling ".scalar(@urlkeys);
				for($keycount=0; $keycount<scalar(@urlkeys); $keycount++){
				    $urlkey = $urlkeys[$keycount];
					if(!defined $urlkey){print "\nundefined";}
					$d = $yeh_apt{$$urlkey->[3]}-($list[0]-$$urlkey->[0]);
					if($d<0){$d+=$yeh_apt{$$urlkey->[3]}}
					for($klass=0; $klass<$#t_val; $klass++){	#estimate position in the table
						if($d <= $t_val[$klass]) {last;}
					}
					#if($klass==$#t_val){$i=$#t_val;}
					#else{$i = index($yeh_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{$klass}}, $urlkey;
				}
				$yeh_last_pred = $list[0];
				
				print "\nsorting ".scalar(@urlkeys);
				for($klass=0; $klass<=$#t_val; $klass++){	#estimate position in the table
					if(defined $klasses{$klass}) {
						$a=$klasses{$klass};
						if(defined @$a){push(@yeh_sorted_keys, @$a);}
					}
				}
				print "\nt=$list[0] yeh_free=$yeh_free yeh_sorted_keys=".scalar @yeh_sorted_keys." fadded=$fadded fdeleted=$fdeleted; realdeleted=$frealdeleted\n";
				undef %klasses;
			}


			# if there is no free space in the cache...
			while($yeh_free < $list[5]){
				#...free some space
				$key = pop (@yeh_sorted_keys);
				$yeh_free += $$key->[1];
				delete($yeh_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
			$yeh_free -= $list[5];
			$yeh_key_cache{$list[7]} = \[$list[0], $list[5], $list[7], "0"x$#t_val];	#new entry
			$key = $yeh_key_cache{$list[7]};
			$fadded++;

		}
		
		#update cache for all cases
		$yeh_access++;
		$yeh_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;
}