#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int status;

typedef struct{
  char type;
  char num[5];
  int time;
}ElemType,*LElemType;

typedef struct{
 LElemType base;
 LElemType top;
 int stacksize;
} sqstack;     //存儲車場停車信息的棧


typedef struct QNode{
  ElemType data;
  struct QNode *next;
}QNode,*Queueptr;  

typedef struct{
 Queueptr front;
 Queueptr rear;
} LinkQueue;    //存儲便道停車信息的隊列

typedef struct LNode{
 char ch[5];
 struct LNode *next;
}LNode,*ListType;

typedef struct{
 ListType head,tail;
 int size;
} tagList;     //存儲場內車牌號的鏈表

//全局變量
sqstack garage,giveway;
LinkQueue waitway;
LElemType elem;
tagList L;
int n,i=1,j=1;

status InitStack(sqstack &s,int n);
status Push(sqstack &s,ElemType e);
status Pop(sqstack &s,ElemType &e);
status InitQueue(LinkQueue &Q);
status Gethead(LinkQueue s,ElemType &e);
status EnQueue(LinkQueue &Q,ElemType e);
status DeQueue(LinkQueue &Q,ElemType &e);
status DestroyQueue(LinkQueue &Q);
status InitList(tagList &L);
status MakeNode(ListType t,char &c);
status Insert(tagList &L,ListType t);
status judgenum(char num[]);
void printmessage();
void DeleteL(char num[]);
void count(LElemType q,char wh);
void Readmessage(char &c);
void Interpret(char c);

status InitStack(sqstack &s,int n)
{ s.base=(LElemType)malloc(n*sizeof(ElemType));
  if(!s.base) exit(OVERFLOW);
  s.top=s.base;
  s.stacksize=n;
  return OK;
}


status Push(sqstack &s,ElemType e)
{ *s.top=e;
   s.top++;
  return OK;
}

status Pop(sqstack &s,ElemType &e)
{if(s.top==s.base) return ERROR;
e=*--s.top;
return OK;
}

status InitQueue(LinkQueue &Q)
{ Q.front=Q.rear=(Queueptr)malloc(sizeof(QNode));
  if(!Q.front) exit(OVERFLOW);
  Q.front->next=NULL;
  return OK;
}

status DestroyQueue(LinkQueue &Q)
{ while(Q.front){
	Q.rear=Q.front->next;
	free(Q.front);
	Q.front=Q.rear;
}
return OK;
}


/*status Gethead( LinkQueue s,ElemType &e)
{ if(s.front==s.rear) return ERROR;
  e=s.front->data;
  return OK;
}*/

status EnQueue(LinkQueue &Q,ElemType e)
{ Queueptr p;
  Q.rear->data=e;
  p=(Queueptr)malloc(sizeof(QNode));
  if(!p) exit(OVERFLOW);
  p->next=NULL;
  Q.rear->next=p;
  Q.rear=p;
  return OK;
}

status DeQueue(LinkQueue &Q,ElemType &e)
{ if(Q.front==Q.rear) return ERROR;
  Queueptr p=Q.front;
  e=p->data;
  Q.front=p->next;
  if(Q.rear==p->next) Q.rear=Q.front;
  free(p);
  return OK;
}

status InitList(tagList &L)
{ L.head=new(LNode);
  L.tail=L.head;
  L.size=0;
  for(int i=0;i<5;i++)
	  L.head->ch[i]='0';
  return OK;
}

status MakeNode(ListType t,char c[])
{ for(int i=0;i<5;i++)
     t->ch[i]=c[i];
  t->next=NULL;
  return OK;
}

status Insert(tagList &L,ListType t)
{ L.tail->next=t;
  L.tail=t;
  L.tail->next=NULL;
  return OK;
}

status judgenum(char num[])
{ int i=0;
  ListType q=NULL;
  if(L.size>0) q=L.head->next;
  while(q)
  { if(strcmp(num,q->ch)) i=1;
    q=q->next;
  }
  return i;
}

void DeleteL(char num[])
{ ListType q=L.head->next,R=L.head;
  while(q)
  { if(!strcmp(q->ch,num))
  { R->next=q->next;
    if(q==L.tail) L.tail=R;
	delete(q);
	q=R->next;
	L.size--;
  }
  else {R=R->next;q=q->next;}
  }
}

void count(ElemType q,char wh) 
{ cout<<endl;
  cout<<"車    型:  ";
  if(q.type=='p')
  {cout<<"客車                 ";
   cout<<"收費標準:  ";
   if(wh=='g')  cout<<"0.15";
      else cout<<"0.075";
   cout<<"  元/分鐘        "<<endl;
  }
     else if(q.type=='t')
	 { cout<<"卡車                  ";
	   cout<<"收費標準:  ";
	   if(wh=='g')  cout<<"0.3";
           else cout<<"0.15";
	   cout<<"  元/分鐘        "<<endl;
	 }
	   else { cout<<"小汽車                ";
	          cout<<"收費標準:  ";
		   	  if(wh=='g')  cout<<"0.1";
                  else cout<<"0.05";
			  cout<<"  元/分鐘        "<<endl;
	   }
  
  cout<<"停車時間:  "<<elem->time-q.time<<"   分鐘           ";
  cout<<"   收費金額:  ";
  if(wh=='g')
  {  if(q.type=='p')
		   cout<<0.15*(elem->time-q.time)<<"  元";
         else if(q.type=='t')
              cout<<0.30*(elem->time-q.time)<<"  元";
             else cout<<0.1*(elem->time-q.time)<<"  元";
		 
  }
  else { if(q.type=='p')
		   cout<<0.075*(elem->time-q.time)<<"  元";
         else if(q.type=='t')
              cout<<0.15*(elem->time-q.time)<<"  元";
             else cout<<0.05*(elem->time-q.time)<<"  元";
  }
  cout<<endl;
  cout<<"-----------------------------------------------------------------------------"<<endl;
}


int main()
{ 
  char c='E';
  elem=new(ElemType);
  elem->time=0;
  printmessage();
  InitList(L);
  cout<<"請輸入車場總車位數:";
  cin>>n;
  InitStack(garage,n);
  InitQueue(waitway);
  do{
	  Readmessage(c);
	  Interpret(c);
  }while(c!='E');
  return 0;
}

void printmessage()
{
 printf("\n");
 printf("*******************************停車場管理操作程序*******************************\n");
 printf("設計者:ＴＩＬＬ      專業:軟件工程      學號:20052110010829    日期:26/12/2006\n");				   ;
 printf("--------------------------------------------------------------------------------\n");
 printf("程序功能:\n");
 printf("請用戶按提示信息輸入!\n");
 printf("--------------------------------------------------------------------------------");
}

void Readmessage(char &c)
{ 
  char h;
  char num[5];
  int time=0;
again1:;
  cout<<"\n請輸入車輛的情況,'A'代表進站,'D'代表出站,'E'代表結束:";
  cin>>c;
  if(c!='A'&&c!='D'&&c!='E')
  { cout<<"輸入不正確,請按要求重新輸入!"<<endl;goto again1;}
  if(c=='D') {cout<<endl;goto again3;}
  if(c=='E') goto end;
  cout<<endl;
again2:; 
  cout<<"請輸入該車的類型,'p'代表客車,'t'代表卡車,'c'代表小汽車:";
  cin>>h;
  if(h!='p'&&h!='t'&&h!='c')
  { cout<<"輸入不正確,請按要求重新輸入!"<<endl;goto again2;}
  elem->type=h;
  cout<<endl;
again3:;
   cout<<"請輸入該車的車牌:";
   cin>>num;
   if(c!='D')
   {if(judgenum(num)) {cout<<"該車牌已存在!請重新輸入!"<<endl;goto again3;}
     else { ListType s;
            s=new(LNode);
		    MakeNode(s,num);
		    Insert(L,s);
	 }
   }
  strcpy(elem->num,num);
  cout<<endl;
again4:;
  if(c=='A') cout<<"請輸入該車進車場時間:";
      else cout<<"請輸入該車出車場的時間:";
  cin>>time;
  if(time<=elem->time)
  { cout<<"時間必須遞增!請重新輸入!"<<endl;
    goto again4;
  }
  elem->time=time;
  cout<<endl;
end:;
}

void Interpret(char c)
{ if(c=='A')
{if(garage.top-garage.base<garage.stacksize)
   { Push(garage,*elem);
     cout<<"請停在車場第 "<< i<<" 號車位!"<<endl;
     i++;
   }
  else{ EnQueue(waitway,*elem);
        cout<<"請停在便道!"<<endl;
        j++;
  }
}
      else if(c=='D')
	  { int k=1;
	    LElemType s,g;
        ElemType e;
		Queueptr q;
		char wh='g';
		s=garage.base;
		while(strcmp(s->num,elem->num)&&k<i)
		{ s++;k++;}
		if(k>=i)
		{ q=waitway.front;
		  k=1;
		  while(strcmp(s->num,elem->num)&&k<j)
		  { q++;k++;}
		  if(k<j) wh='w';
		    else wh='n';
		}
		//計算停車費
		if(wh=='g') 
		{ cout<<"-----------------------------------該車在車場內--------------------------------"<<endl;
		  count(*s,wh);
		}
		   else if(wh=='w') 
		   { cout<<"-----------------------------------該車在便道內---------------------------------"<<endl;
		      count(q->data,wh);
		   }
		        else { cout<<"該車沒在停車場內!"<<endl;goto end;}
       //讓路情況
		if(wh=='g')     //從車場開走
		{ i--;
		  DeleteL(s->num);
		  if(++s!=garage.top)
		  { 
		    giveway.base=s;
		    giveway.top=garage.top;
		    giveway.stacksize=giveway.top-giveway.base;
		    cout<<"為該車讓路，須從入口退出車場的車輛順序:"<<endl;
		    g=giveway.top; 
			while(g!=giveway.base)
			{ g--;
			  cout<<"   "<<g->num;
		 	}
			cout<<endl;
		    
		  }
		      else cout<<"不必讓路,該車可直接從車場開走!"<<endl;
		  s--;
          g=giveway.base; 
		  while(g!=giveway.top)
			{*s=*g;s++;g++;}
		  garage.top--;
		  
		  if(waitway.front!=waitway.rear) //便道上的車輛數目不為零
			{  if(DeQueue(waitway,e))
		          Push(garage,e);
		       cout<<"######請便道內車牌為 "<<e.num<<" 的車進車場,停在第"<<i<<"號車位!######"<<endl;
			   j--;
			   i++;
			}
		}
		
		else if(wh=='w')        //從便道上開走
		{ j--;
		  DeleteL(s->num);
		  if(q!=waitway.front)
		  {
		   LinkQueue Q;
		   InitQueue(Q);
		   Queueptr p=waitway.front;
		   do{ EnQueue(Q,p->data);  //copy它前面的車輛情況
		      p=p->next;
		   }while(p->next!=q);
		   p=waitway.front;
		   Queueptr M=q->next;            
		   do{ p->data=M->data;
		       p=p->next;
			   M=M->next;
		   }while(M);
           cout<<"便道上為該車讓路的車輛順序:";
		   Queueptr N=Q.front;
		   do{ cout<<"  "<<N->data.num; 
			   p->data=N->data;
		       p=p->next;
               N=N->next;
		   }while(N!=Q.rear);
		   DestroyQueue(Q);
		   delete(waitway.rear);
		   waitway.rear=p;
		  }
		}
		else cout<<"不必讓路,該車可直接從便道開走!"<<endl;
	  }
end:;
}