#!/usr/bin/perl
	#
	# All algorythms
	#
	
	#define constants
	$all_free = 16000000000;		#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
	$lrumin_free = $all_free;	#lru cache size
	$yeh_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
	$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.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]){
				#&infinite;
				&lru;
				#&atp;
				#&atpmin;
				#&fifo;
				#&lfd;
				#&lrumin;
				#&yeh;
			}
		}
		$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");}
	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($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)."%), WMiss = $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)."%), WMiss = $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";}
		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";}
		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($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)."%), WMiss = $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)."%), WMiss = $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";}
		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";}
		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
#############################################

##########################
# 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=$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
			#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+$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);
																					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], "00000000000"];	#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];
	}


###############
# L R U M I N #
###############
	
	sub lrumin{
		my($i, $size);
		if($all_free*0.1 < $list[5]){
			$lrumin_miss++;
			$lrumin_wmiss += $list[5];
			$lrumin_access++;
			$lrumin_waccess+=$list[5];
			return 0;
		}elsif(defined $lrumin_cache{$list[7]}){
			#found in the cache
			$lrumin_hits++;
			$lrumin_whits += $list[5];
			for($i=0; $sorted_access[$i] ne $list[7]; $i++){}
			splice(@sorted_access, $i, 1);	
		}else{
			#not found in the cache
			$lrumin_miss++;
			$lrumin_wmiss += $list[5];
			
			# if there is no free space in the cache...
			for($i=0, $scalsize=2*$list[5]; $lrumin_free < $list[5]; $i++, $i%=(scalar @sorted_access)){
				if($i==0){$scalsize/=2;}
				#...free some space
				$size = $lrumin_size_cache{$sorted_access[$i]};
				if($size>=$scalsize){
					$lrumin_free += $size;
					delete($lrumin_cache{$sorted_access[$i]});
					delete($lrumin_size_cache{$sorted_access[$i]});
					splice(@sorted_access, $i, 1);
				}
			}
			
			#now there is free space in cache
			#reserve some space
			$lrumin_free -= $list[5];
		}
		
		#update cache for all cases
		#add to the tail of the list
		push(@sorted_access, $list[7]);
		$lrumin_cache{$list[7]} = $list[0];	#new last access time
		$lrumin_size_cache{$list[7]} = $list[5];	#new size
		$lrumin_access++;
		$lrumin_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];
			#print "d = $d   $$key->[2] ";
			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
			#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+$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];
	}

#########
# 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];
			#print "d = $d   $$key->[2] ";
			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);
																					if(!defined($key)){print "\n".scalar(@yeh_sorted_keys)."	yeh_free=$yeh_free key=$key d=$d"; }
																					#print "\n".scalar(@$pom)."	yeh_free=$yeh_free	url=$$key->[2]	size=\n";
				$yeh_free += $$key->[1];
				#delete entry in the cache
																					if(!defined($yeh_key_cache{$$key->[2]})){print "\a\n".scalar(@$pom)."d=$d key=$key url=$$key->[2]"};
																					$fdeleted++;				
				delete($yeh_key_cache{$$key->[2]});
																					if(!defined($yeh_key_cache{$$key->[2]})){$frealdeleted++};
				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;
}