clear;
N=100;
M=100;
Q_size=1000;
S_size=30;
P_num=30;
for i=1:N
    x(i)=rand(1)*M;
    y(i)=rand(1)*M;
end
x(1)=M*0.95;y(1)=M*0.95;
%plot(x,y,'o',x(1),y(1),'p');
for i=1:N
    str=num2str(i);
%    text(x(i)-2,y(i)-2,str);
end
neighbour=zeros(N,N*0.2);
for i=1:N
    n(i)=1;
   for j=1:N
      if (x(i)-x(j))^2+(y(i)-y(j))^2<M^2*0.04 & i~=j
          neighbour(i,n(i))=j;
          n(i)=n(i)+1;
      end
   end
end
parent=ones(100,1);
for i=1:N
    k=i;
    for j=1:n(i)-1
        temp=neighbour(i,j);
        if ((x(temp)-M*0.95)^2+(y(temp)-M*0.95)^2<(x(k)-M*0.95)^2+(y(k)-M*0.95)^2 )
            k=temp;
        end
    end
if k~=i
    parent(i)=k;
end
  parent(1)=1;
  cordinate_x(1)=x(i);cordinate_x(2)=x(k);cordinate_y(1)=y(i);cordinate_y(2)=y(k);
%  line(cordinate_x,cordinate_y);
end
child=zeros(N,N*0.2);
for i=1:N
    c(i)=1;
   for j=1:N
        if  parent(j)==i
            child(i,c(i))=j;
            c(i)=c(i)+1;
        end
   end
end
for i=1:N
    if c(parent(i))~=0
       b(i)=c(parent(i))-1;
    end
   for j=1:b(i)
       brother(i,j)=child(parent(i),j);
   end
end
for i=1:N
   h(i)=1;
   for j=1:n(i)-1
      for k=1:n(neighbour(i,j))-1
         if i~=neighbour(i,j)
             hop(i,h(i))=neighbour(neighbour(i,j),k);
             h(i)=h(i)+1;
         end
      end
   end
end
t=zeros(N,1);
f=zeros(N,1);
u=1;v=1;
t(u)=1;f(u)=1;
k=1;d=1;
visited=zeros(N+1,1);visited(1)=1;
max_t=1;max_f=1;
p=1;q=1;i=1;
while k<N & d<20*N
    if  child(u,v)~=0 
        if visited(child(u,v))==0 
           u=child(u,v);
           p=1;q=1;i=1;
           while i~=n(u)
                i=1;
                while i<n(u)
                    if   p==t(neighbour(u,i))
                         p=p+1;
                         break;
                    end
                    i=i+1;
                end
           end
%       i=1;
%       while i~=n(u)
%          i=1;
%          while i<n(u)
%             if  q==f(neighbour(u,i)) 
%                q=q+1; 
%                break;
%             end
%             i=i+1;
%          end
%       end
           i=1;
           while i~=h(u)
                 i=1;
                 while i<h(u)
                      if q==f(hop(u,i))
                         q=q+1; 
                         break;
                      end
                      i=i+1;
                 end
            end
%    if u==1
%        q=1;
%    else
%      while i~=b(u) 
%        i=1;
%        while i<b(u)
%            if   q==f(brother(u,i))| q==f(parent(u))| q==f(parent(parent(u)))
%               q=q+1;
%               break;
%            end
%            i=i+1;
%        end
%      end
%    end
          t(u)=p;f(u)=q;
          if t(u)>max_t
          max_t=t(u);
          end
          if f(u)>max_f
             max_f=f(u);
          end
          visited(u)=1; 
          k=k+1;
%      text(x(u)+2,y(u)+2,num2str(t(u)));
%      text(x(u)-2,y(u)-2,num2str(f(u)));
          v=1;
       end
   end
      if child(u,v)==0
         u=parent(u);
         v=1;
      else if visited(child(u,v))==1 
           v=v+1;
          end
      end
   d=d+1;
end
%max_t
%max_f
s=zeros(S_size,1);
a=zeros(N,1);
for i=1:S_size
    s(i)=ceil(N*rand(1));
    while a(s(i))==1
        s(i)=ceil(N*rand(1));
    end
    a(s(i))=1;
end
inc=1;
for Q_size=100:100:1000
    total_pack(inc)=0;
    total_rpack(inc)=0;
r=zeros(S_size,P_num);
pack=zeros(S_size,1);
rpack=zeros(S_size,1);
rec_front=ones(N,P_num);
rec_rear=ones(N,P_num);
front=ones(N,1);
rear=ones(N,1);
posi=zeros(S_size,P_num);
flag=zeros(S_size,P_num);
wait=zeros(S_size,P_num);
drop=zeros(S_size,P_num);
error=0;
for i=1:P_num*20
    for l=1:N
        v(l,i)=0;
        rec_front(l,i)=front(l);
        rec_rear(l,i)=rear(l);
    end
    for k=1:S_size
        if i<P_num
           pack(k)=pack(k)+1;
           r(k,pack(k))=s(k);
           posi(k,pack(k))=rear(s(k));  
           rear(s(k))=rear(s(k))+1; 
        end
        for j=1:max_t
               for m=1:pack(k)
                   if flag(k,m)==0
                      if r(k,m)==1
                         rpack(k)=rpack(k)+1;
                         flag(k,m)=1;
                         else if r(k,m)~=0
                               loc=r(k,m);
                               if  t(loc)==j & posi(k,m)==front(loc) & v(loc,i)==0
                                   front(loc)=front(loc)+1;
                                   v(loc,i)=1;
                                   next=parent(loc);                      
                                   if  next==1 
                                       break;
                                       else if  rear(next)-front(next)<Q_size  
                                                posi(k,m)=rear(next);
                                                ear(next)=rear(next)+1;
                                                r(k,m)=next;
                                           else
                                                 r(k,m)=0;
                                    drop(k,m)=1;
                                    break;
                                end
                               end
                          end
                       end
                   end
                end
            end
    end
end
for k=1:S_size
    total_pack(inc)=total_pack(inc)+pack(k);
    total_rpack(inc)=total_rpack(inc)+rpack(k);
end
inc=inc+1;
end
k=100:100:1000;
plot(k,total_pack,k,total_rpack);
%k=1:S_size;
%rpack;
%plot(k,pack,k,rpack);
%axis([0,S_size,990,1010]);