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

char MyMem[32];

int stTwo(int size)
{
  int k=0;
  while (pow(2,k)<size)
   k+=1;
   return k;
    }
    
void Raz(int st2,int beg)
{
int k, stbeg; 
stbeg=beg;     
while(MyMem[beg] != st2 )
{
               k=(int)pow(2,MyMem[beg])/2;
               MyMem[beg]=((int)MyMem[beg])-1;
               MyMem[beg+k] = ((int)MyMem[beg]);
               beg = stbeg; 
            
               }
}

void Sliyanie(int st2, int beg)
{ int k, stbeg;
  while(MyMem[beg] != st2)
  { 
               k=(int)pow(2,MyMem[beg]);
               MyMem[beg]=((int)MyMem[beg])+1;
               MyMem[beg+k] = 0;
               beg = stbeg; 
          
  }
}

void Bin(int sb,int st2)
{
   int k=0, g;     
    
   while( g != 1)
   
    
    { 
   
    
     if ((MyMem[k]>st2) && (MyMem[k+1] != 1))
     { Raz(st2,k); g=1; cout<<endl; break; }
      else 
      { 
           if((MyMem[k]<st2) && (MyMem[k+1] != 1))
            { 
            if ((MyMem[k] == MyMem [k+(int)pow(2,(int)MyMem[k])]) && (MyMem [k+1+(int)pow(2,(int)MyMem[k])] != 1 ))
             { Sliyanie(st2, k); g=1; cout<<endl; break; }
            }
      }     
      
      if (MyMem[k]>st2) k+=(int)pow(2,(int)MyMem[k]);
       else k+=sb;
       
     
     
     }       
      
     }


int ToAllocate(int sb, int st2)
{ int i=0, y=0;
    
    while(i < 32 )
      
      {  
      if (MyMem[i] == st2 && MyMem[i+1] != 1)
        { 
                  
                   MyMem[i+1]=1;
                   cout<<"Memory is allocated!"<<endl;
                   y=1;
                   break; 
        }
          i+=sb;
        
      }
      
  return y;  
}     

void BasAlg(int sb, int st2)
{ int i=0,j=0,key=0;
 
 while(key!=1)
 {
             j=ToAllocate(sb,st2);   
            
             
             if (j==1) 
             
                      key=1;
                      
             else 
             { cout<<endl;
               Bin(sb,st2);
             }
 }   
}

void DelMem(int sb, int st2)
{
 int i=0;
 
 while(i < 32)
 {
    if ((MyMem[i]==st2)&&(MyMem[i+1]==1))
    {
     MyMem[i+1]=0;
     cout<<"Blok is empty!"<<endl;
     break;                                    
    } 
    i+=sb;
 }
}

void info()
{ int i, k=0;
   for (i=0; i<32; i++)
    {
      if ((MyMem[i]>1)&&(MyMem[i+1]!=0))
       k+=(int)pow(2,(int)MyMem[i]);
    }
    
    cout<<"Free Memory: "<<32-k<<" Occupied Memory: "<<k<<endl;
         
}

int CheckedToAlloc(int sb,int st2)
{
    int k=0,i;     
    
 for(i=0; i<32; i+=sb)
      { if (( MyMem[i]==st2)&& (MyMem[i+1]!=1))
              return 1;
               }
   


   while( k < 32 )
   
    
    { 
   
    
     if ((MyMem[k]>st2) && (MyMem[k+1] != 1))
     {return 1; }
      else 
      { 
           if((MyMem[k]<st2) && (MyMem[k+1] != 1))
            { 
            if ((MyMem[k] == MyMem [k+(int)pow(2,(int)MyMem[k])]) && (MyMem [k+1+(int)pow(2,(int)MyMem[k])] != 1 ))
             { return 1; }
            }
      }     
      
      if (MyMem[k]>st2) k+=(int)pow(2,(int)MyMem[k]);
       else k+=sb;
       
     
     
     }       
    }
    
int CheckedToDel(int st2)
{
    int k=0;     
    
   while( k < 32 )
   
    
    { 
   
    
     if ((MyMem[k]==st2) && (MyMem[k+1] == 1))
     {return 1; }
      else k+=(int)pow(2,(int)MyMem[k]);
          
            
    }     
      
   
 }
    
    
int main()
{ 
  int size,st2,st,i=0,sb,checkA, checkD;
  char ch;
  st=stTwo(32);
  MyMem[0]=st;

  
    while (ch != 'x')
  
  {    cout<<endl;
       cout<<"********MENU*************"<<endl;
       cout<<"1. To allocate memory "<<endl;
       cout<<"2. To delete memory "<<endl; 
       cout<<"3. To display memory "<<endl;
       cout<<"4. To Exit "<<endl;
       cout<<"*************************"<<endl;
       cout<<endl;
       cin>>ch;
       
       switch(ch)
       {
         case '1':
              
         cout<<endl;
         cout<<"Enter size of blok!"<<endl;
         cin>>size;
         st2=stTwo(size);
         sb=(int)pow(2,st2);
         checkA=CheckedToAlloc(sb,st2);
         if (checkA==1)
          BasAlg(sb,st2);
         else cout<<"Memory allocation is impossible!"<<endl;
         break;
         
         case '2':
              
         cout<<"Enter size of blok to delete!"<<endl;
         cin>>size;
         st2=stTwo(size);
         sb=(int)pow(2,st2);
         checkD=CheckedToDel(st2);
         if (checkD==1) DelMem(sb,st2);   
         else cout<<"Memory removal is impossible!"<<endl;
         break;
         
        
              
         case '3':
              
          for(int i=0;i<32;i++)
                {
                  cout<<(int)MyMem[i]<<" ";
                }
                
          cout<<endl;
          info();
          break;
          
          case '4':
               cout<<"***Special thanks by Rock'n'Rolla***"<<endl;
               ch='x';
               cout<<"Press any key!"<<endl;
               getch();
               
          default: break;
                           
       }
        
        
  }
}