garwick_modified.cpp

这个课程项目完成了一个修改版的Garwick存储结构与查询设计。给定了一组数值

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;

int data[21]={1,1,1,3,3,3,3,2,2,3,3,3,3,2,2,2,1,2,2,2,2};
//int data[21]={1,1,1,3,3,3,3,2,2,3,3,3,3,2,2,2,1,3,3,3,2};
int Num_stack = 3;
int len_table = 21;
float Rho = 0.5;
int counter = 0;
int TotalUsed;
int SumOfIncreases;
int  *base, *newbase,*top, *oldtop, *increase, rem;
int table[23];
float *delta,*alloc;
void moving(int);
void reallocate(int);
int reallo;
int move;
int move_temp = 0;
float fraction(float a)
{
	return a - floor(a);
}

bool even(int a)
{
	if((a%2) == 0)
		return true;
	else
		return false;
}



void main()
{

	base = new int[Num_stack+1];
	newbase = new int[Num_stack+1];
	top = new int[Num_stack+1];	
	oldtop = new int[Num_stack+1];
	delta = new float[Num_stack+1];
	alloc = new float[Num_stack+1];

	base[1] = 0;
	top[1] = base[1];
	oldtop[1] = top[1];
	for(int i=2; i <= Num_stack; i=i+2)
	{
		base[i] = (len_table/Num_stack)*i;
        top[i] = base[i];
		oldtop[i]=top[i];

		base[i+1] = base[i];
        top[i+1] = base[i+1];
		oldtop[i+1]=top[i+1];
	}
	base[Num_stack+1] = len_table;
	top[Num_stack+1] =  len_table;
	oldtop[Num_stack+1] =  len_table;
	reallo = 0;
	move = 0;

	for(int i=1; i<= len_table; i++)
	{
		if(even(data[i-1]))
		{		
			top[data[i-1]]--;
			if(top[data[i-1]] >= top[data[i-1]-1])
			{
				table[top[data[i-1]]+1] = data[i-1];		
				//oldtop[data[i-1]] = top[data[i-1]];					
			}
			else
			{
				// reallocate the list to avoid the collision.
				int current_stack = 0;
				current_stack = data[i-1];
				reallocate(current_stack);
				reallo = reallo+1;
			}
		}
		else
		{
			top[data[i-1]]++;			
			if(top[data[i-1]] <= top[data[i-1]+1])
			{
				table[top[data[i-1]]] = data[i-1];					
				//oldtop[data[i-1]] = top[data[i-1]];			
			}
			else
			{
				// reallocate the list to avoid the collision.
				int current_stack = 0;
				current_stack = data[i-1];
				reallocate(current_stack);
				reallo = reallo+1;
			}
		}
		
	}
	
	cout<<"\n------------------------------------------------------"<<endl;
	//cout<<"the policy Rho is "<<Rho<<setw(5)<<"the growth is: "<<growth<<endl;
	cout<<"the total move: "<<move<<endl;
	cout<<"the total reallocate: "<<reallo<<endl;
	cout<<"------------------------------------------------------\n"<<endl;
	system("pause");
	// how to free the memory???
	//free(base[]);
	//free(newbase[]);
	//free(top[]);
	//free(oldtop[]);
	//free(increase[]);
}

void reallocate(int current_stack)
{
    counter = counter + 1;
	TotalUsed = 0;
	SumOfIncreases = 0;

	for(int j=1; j<= Num_stack; j++)
	{
		TotalUsed = TotalUsed + abs(top[j] - base[j]);
		SumOfIncreases = SumOfIncreases + abs(top[j] - oldtop[j]);			
	}
	rem = len_table - TotalUsed;
	if(rem < 0)
	{
		printf("REM < 0, the memory space is not enough");
		system("pause");
		//break;
	}
	else
	{
		for(int j=1; j<=Num_stack; j++)
		{
			alloc[j] = rem * ((1.0/Num_stack) *0.1 + float(abs(-top[j] + oldtop[j]))/SumOfIncreases*Rho*0.9 + float((abs(top[j] - base[j])))/TotalUsed*(1-Rho)*0.9);
		}
		
		newbase[1] = base[1];
		delta[1] = floor(alloc[1]);
		for(int k=2; k<= Num_stack;k = k+2)
		{
			float temp = 0;
			int j;
			for(j= 1; j<k; j++)
			{					
				temp = alloc[j] + temp;
			}
			delta[k] = floor(alloc[k]) + floor(fraction(temp) + fraction(alloc[k]));
			newbase[k] = newbase[k-1] + abs(top[k-1] - base[k-1]) + delta[k-1] + abs(base[k] - top[k]) + delta[k];	
			newbase[k+1] = newbase[k];
			delta[k+1] = floor(alloc[k+1]) + floor(fraction(temp+alloc[j]) + fraction(alloc[k+1]));
		}
		if(!even(Num_stack))
		{
			newbase[Num_stack+1] = len_table;
		}

		cout<<'\n'<<"-----------------------------------------------"<<endl;
		cout<<"This is number "<<counter<< " reallocation"<<endl;
		cout<<"Before moving stacks:"<<endl;
		for(int k=1; k<= len_table;k++)
		{
			cout<<table[k]<<" ";
		}
		moving(current_stack); // moving the stack data[i-1] for additional space;
						
		cout<<"\nAfter moving stacks:"<<endl;
		for(int k=1; k<= len_table;k++)
		{
			cout<<table[k]<<" ";
		}
		cout<<'\n'<<"There are "<<move - move_temp << " move"<<endl;
		cout<<'\n'<<"-----------------------------------------------"<<endl;	
		move_temp = move;
		system("pause");			
	}
}

void moving(int stackToAllocate)
{

	cout<<"\nthe newbase:"<<endl;
	for(int ik = 1; ik <= Num_stack; ik++)
	{
		cout<<"newbase["<<ik<<"]:"<<newbase[ik]<<endl;
	}

	for(int k=1; k<= Num_stack; k++)
	{

		if(!even(k))
		{

			if(newbase[k] < base[k])
			{
				int curr_pos;
				curr_pos = newbase[k]+1;
				int j;
				for(j=base[k]+1; j< top[k]; j++)
				{
					table[curr_pos] = table[j]; 
					table[j] = 0;
					curr_pos++;		
					move++;
				}
				if(top[k] < base[k+1])
				{
					table[curr_pos] = table[j]; 
					table[j] = 0;
					move++;

				}
					
				top[k] = top[k] - (base[k] - newbase[k]);
				base[k] = newbase[k];
				oldtop[k] = top[k];
			}
			else if(newbase[k] > base[k])
			{
				
				int curr_stack = k;
				while(curr_stack <= Num_stack)
				{
					if (newbase[curr_stack] < base[curr_stack])
						break;
					curr_stack++;
				}
				int stack = curr_stack-1;
				for(;stack>=k; stack--)
				{
					int stack_size;
					stack_size = -base[stack] + newbase[stack];
					if(!even(stack))
					{

						for(int j=top[stack]; j>base[stack]; j--)
						{
							table[j+stack_size] = table[j]; 
							table[j] = 0;
							move++;
						}								
					}
					else
					{
						for(int j=base[stack]; j>=top[stack]+1; j--)
						{
							table[j+stack_size] = table[j]; 
	     					table[j] = 0;
							move++;
						}
					}
					top[stack] = top[stack] + ( -base[stack] + newbase[stack]);
		        	base[stack] = newbase[stack];
					oldtop[stack] = top[stack];
				}			
			}
			else if(newbase[k] == base[k])
			{
				base[k] = newbase[k];			
				oldtop[k] = top[k];
				//move++;
			}	

		}
		else
		{
			if(newbase[k] < base[k])
			{
				int stack_size;
				stack_size = base[k] - newbase[k];
				for(int j=top[k]+1; j<=base[k]; j++)
				{
					table[j-stack_size] = table[j]; 
					table[j] = 0;
					move++;
				}				
					
				top[k] = top[k] - (base[k] - newbase[k]);
				base[k] = newbase[k];
				oldtop[k] = top[k];
			}
			else if(newbase[k] > base[k])
			{
				
				int curr_stack = k;
				while(curr_stack <= Num_stack)
				{
					if (newbase[curr_stack] < base[curr_stack])
						break;
					curr_stack++;
				}
				int stack = curr_stack-1;
				for(;stack>=k; stack--)
				{
					int stack_size;
					stack_size = -base[stack] + newbase[stack];
					if(!even(stack))
					{

						for(int j=top[stack]; j>base[stack]; j--)
						{
							table[j+stack_size] = table[j]; 
							table[j] = 0;
							move++;
						}								
					}
					else
					{
						int j;
						for( j=base[stack]; j>top[stack]+1; j--)
						{
							table[j+stack_size] = table[j]; 
	     					table[j] = 0;
							move++;
						}
						if(table[top[stack]+1] != table[top[stack]])
						{		
							table[j+stack_size] = table[j]; 
	     					table[j] = 0;
							move++;
						}

					}
					top[stack] = top[stack] + ( -base[stack] + newbase[stack]);
		        	base[stack] = newbase[stack];
					oldtop[stack] = top[stack];
				}			
			}
			else if(newbase[k] == base[k])
			{
				base[k] = newbase[k];			
				oldtop[k] = top[k];				
			}	
		}
	}
	if(even(stackToAllocate))
	{
		table[top[stackToAllocate]+1] = stackToAllocate;
		move++;
	}
	else
	{
		table[top[stackToAllocate]] = stackToAllocate;	
		move++;
	}

}