from time import clock
import sys
import random

class CreateNode(object):  

  def __init__(this,Num): 

    this.Num = Num     
    this.Left  = None
    this.Right  = None
    this.Top  = None
    this.Down  = None      

class NodeOperation(object): 

  def __init__(this): 
    
    this.First=CreateNode(-1)   ## -1 as - infinity
    this.Last= CreateNode(1000) ## 1000 as + infinity
    this.First.Right=this.Last
    this.Last.Left=this.First    
    this.Headpoint=[this.First]      
      
  def InsertStage(this):    
    
    this.First=CreateNode(-1)
    this.Last= CreateNode(1000)
    this.First.Right=this.Last
    this.Last.Left=this.First
    
    this.First.Down=this.Headpoint[len(this.Headpoint)-1]
    this.Headpoint[len(this.Headpoint)-1].Top=this.First
    this.Last.Down=this.Headpoint[len(this.Headpoint)-1].Right
    this.Headpoint[len(this.Headpoint)-1].Right.Top=this.Last          
    this.Headpoint.append(this.First)
    

  def SearchNumposition(this,num):
       
    ## start from len-1 stage for searching
    
    this.positionpoint=[this.Headpoint[len(this.Headpoint)-1]]
        
    i=len(this.Headpoint)-1
    while(i != 0):

      this.previous=this.positionpoint[len(this.positionpoint)-1].Down
      this.next1=this.positionpoint[len(this.positionpoint)-1].Down.Right      
      
      while(num not in range(this.previous.Num,this.next1.Num)):  ## search in only one stage
        
        if( num == this.previous.Num or num==this.next1.Num ):
          print "\n Number is already present !!! ",num,"\n"
##          break          
          return 0
        else:        
          this.previous=this.next1
          this.next1=this.next1.Right
        
      this.positionpoint.append(this.previous)
          
      i-=1
  


  def InsertNode(this,num):
     
      for i in range(len(this.positionpoint)-1,0,-1):
        this.First=CreateNode(num)
        this.First.Right=this.positionpoint[i].Right
        this.positionpoint[i].Right=this.First
        this.First.Left=this.positionpoint[i]
        this.First.Right.Left=this.First

        if(i !=len(this.positionpoint)-1):
          this.First.Down=this.positionpoint[i+1].Right
          this.positionpoint[i+1].Right.Top=this.First


  def countstage(this)  :
    print len(this.Headpoint)       

  
  def DeleteNode(this):
      
      for i in range(len(this.delpositionpoint)-1,-1,-1):

##        print "deleted number",this.delpositionpoint[i].Num
        if(this.delpositionpoint[i].Right != None):
          this.delpositionpoint[i].Left.Right= this.delpositionpoint[i].Right
          this.delpositionpoint[i].Right.Left=this.delpositionpoint[i].Left
          this.delpositionpoint[i].Top=None
          this.delpositionpoint[i].Down=None
        else:
          break
        
  def SearchNumposition_Del(this,num):
         
      ## start from len-1 stage for searching
      this.delpositionpoint=[]
      this.positionpoint=[this.Headpoint[len(this.Headpoint)-1]]
      
      i=len(this.Headpoint)-1
      while(i != 0):

        this.previous=this.positionpoint[len(this.positionpoint)-1].Down
        this.next1=this.positionpoint[len(this.positionpoint)-1].Down.Right      
        
        while(num not in range(this.previous.Num,this.next1.Num)):  ## search in only one stage
          
          if( num == this.previous.Num or num==this.next1.Num ):
##            print "\n deletion Number is already present !!! ",this.previous.Num, num,this.next1.Num , i,"\n"
            if num == this.previous.Num:              
              this.delpositionpoint.append(this.previous)
            else:              
              this.delpositionpoint.append(this.next1)
              
            break          
            
          else:        
            this.previous=this.next1
            this.next1=this.next1.Right
        this.positionpoint.append(this.previous)
        
            
        i-=1





def Skip_List():

     try:
          
          InFile=open('in21_1.txt','r')          
          OutFile=open('out_11_sec21_1.txt','w')
          start=clock()    
          
          Anum=InFile.readline().split(",")
          Adelnum=InFile.readline().split(",")          
          
## START
          
          OprationObj=NodeOperation()

          ## Insert Node into Skiplist
          for i in range(0,len(Anum)):
            
            if(OprationObj.SearchNumposition(int(Anum[i])) !=0):
                  noofHead=0

                  while(random.randint(0,1) !=1):
                      noofHead+=1              
                      OprationObj.InsertStage()                  

                  if noofHead==0:  ##when start=0                    
                    OprationObj.InsertStage()
                    
                  OprationObj.SearchNumposition(int(Anum[i]))
                  OprationObj.InsertNode(int(Anum[i]))          

          ## To Delete the Node From Skiplist
          for i in range(0,len(Adelnum)):            
            OprationObj.SearchNumposition_Del(int(Adelnum[i]))
            OprationObj.DeleteNode()            

## END
           

          OutFile.write("Total Excution Time : "+str(clock()-start))

          memUsed = sys.getsizeof(InFile) + sys.getsizeof(OutFile)+ sys.getsizeof(start)+ sys.getsizeof(Anum)+ sys.getsizeof(Adelnum)+sys.getsizeof(OprationObj)
          OutFile.write("\nMemory used : "+str(memUsed)+" Bytes")

          InFile.close()
          OutFile.close()
          
          print "Check Your Output File : out_11_sec21_1.txt is Generated"

     except ValueError:

          print "Check Your Output File Cant Not Generated",ValueError
          InFile.close()
          OutFile.close()



Skip_List()