<repo_name>sarthak77/Undo-Logging<file_sep>/20171091_1.py
import sys

def readinput(file):
    """
    Returns contents of disk and transactions
    """

    Disk,Tran=[{},{}]
    
    with open(file,'r') as f:

        #read first line
        fl=f.readline()
        fl=fl.strip().split()

        for i in range(0,len(fl),2):
            Disk[fl[i]]=fl[i+1]

        # print(Disk)

        #read transactions
        flag=0
        tr=0
        for line in f:
            line=line.strip().split()
            if(len(line)==0):
                flag=1
            else:
                if(flag):
                    Tran[line[0]]=[]
                    tr=line[0]
                    flag=0
                else:
                    Tran[tr].append(line)

        # for x in Tran:
        #     print (x)
        #     for y in Tran[x]:
        #         print(y)

    return [Disk,Tran]



def str_to_list(tr,v):
    """
    Convert string to list
    """

    if(v=="r"):
        tr=tr[5:]
        tr=tr[:-1]
        tr=tr.split(",")
        return tr

    if(v=="w"):
        tr=tr[6:]
        tr=tr[:-1]
        tr=tr.split(",")
        return tr

    if(v=="o"):
        tr=tr[7:]
        tr=tr[:-1]
        tr=tr.split(",")
        return tr



def evalexp(e,var):
    """
    Check which op to perform
    """
    
    if(len(e[2].split('+'))==2):
        var[e[0]]=evalexp2(e[2],'+',var)
    
    if(len(e[2].split('-'))==2):
        var[e[0]]=evalexp2(e[2],'-',var)    
    
    if(len(e[2].split('/'))==2):
        var[e[0]]=evalexp2(e[2],'/',var)

    if(len(e[2].split('*'))==2):
        var[e[0]]=evalexp2(e[2],'*',var)

    return var



def evalexp2(e,v,var):
    """
    perform op in memory
    """

    e=e.split(v)
    a=int(var[e[0]])
    b=int(e[1])
    s=str(a)+v+str(b)
    return int(eval(s))        



def processaction(tr,var,D,M,x):
    """
    Perform individual action
    """

    cp=tr#for op
    tr=tr[0]#for r,w,o

    if(tr[0:4]=="READ"):
        #split
        tr=str_to_list(tr,"r")

        #bring to memory if not there
        if(tr[0] not in M):
            M[tr[0]]=D[tr[0]]
        
        #set val in var
        var[tr[1]]=M[tr[0]]


    elif(tr[0:5]=="WRITE"):
        #split
        tr=str_to_list(tr,"w")
        
        #add to log
        s="<"+x+", "+str(tr[0])+", "+str(M[tr[0]])+">"
        
        #change in memory
        M[tr[0]]=var[tr[1]]
        
        #printlog
        printlog(D,M,s)


    elif(tr[0:6]=="OUTPUT"):
        #split
        tr=str_to_list(tr,"o")

        #update in disk
        D[tr[0]]=M[tr[0]]
    

    else:
        var=evalexp(cp,var)


    return var,D,M



def runtr(D,T,M,X,start,var):
    """
    Run all transactions for X steps
    """

    #check if any trans can occur
    flag=False
    for x in T:
        if(len(T[x])>start):
            flag=True
            break
    
    #break if not
    if(flag==False):
        return flag,D,M,var

    #loop over all transactions
    for x in T:
        for y in range(start,min(start+X,len(T[x])),1):

            t=T[x][y]

            #check if tr starts
            if(y==0):
                s="<START "+x+">"
                printlog(D,M,s)
        
            #run transaction
            var,D,M=processaction(t,var,D,M,x)

            #check if tr ends
            if(y==len(T[x])-1):
                s="<COMMIT "+x+">"
                printlog(D,M,s)

    return flag,D,M,var



def printlog(D,M,s):
    """
    Print memory and log status in the given format
    """

    #print log
    print(s)

    #sort M and D
    Mt=sorted(M.keys())
    Dt=sorted(D.keys())

    #print M
    i=0
    for x in Mt:
        i+=1
        if(i==len(Mt)):
            print(x,M[x],end='')
        else:
            print(x,M[x],end=' ')
    print("")

    #print D
    i=0
    for x in Dt:
        i+=1
        if(i==len(Dt)):
            print(x,D[x],end='')
        else:
            print(x,D[x],end=' ')
    print("")



def processtr(D,T,X):
    """
    Run transactions in RR fashion
    """

    X=int(X)
    M={}
    start=0
    var={}

    #run until all transactions are over
    while(1):
        flag,D,M,var=runtr(D,T,M,X,start,var)
        if(flag==False):
            break
        else:
            start+=X



if __name__=="__main__":

    F=sys.argv[1]
    X=sys.argv[2]
    # print(F,X)
    Disk,Transactions=readinput(F)
    processtr(Disk,Transactions,X)<file_sep>/20171091.sh
#!/bin/bash

if [ "$#" -eq 2 ]
then
	python3 20171091_1.py $1 $2 > 20171091_1.txt

elif [ "$#" -eq 1 ]
then
	python3 20171091_2.py $1 > 20171091_2.txt

else
    echo "Input format for 1st case: bash <input file name> <X>"
    echo "Input format for 2nd case: bash <input file name>"
fi
<file_sep>/20171091_2.py
import sys

def readinput(file):
    """
    Returns contents of disk and transactions
    """

    Disk,Tran=[{},[]]
    
    with open(file,'r') as f:

        #read first line
        fl=f.readline()
        fl=fl.strip().split()

        for i in range(0,len(fl),2):
            Disk[fl[i]]=fl[i+1]

        # print(Disk)

        fl=f.readline()
        #read transactions
        for line in f:
            line=line.strip()
            line=line[1:-1]
            line=line.split()
            Tran.append(line)

        # for i in Tran:
        #     print(i)

    return [Disk,Tran]



def preprocess(T):
    """
    Convert T in a format easy to work
    """

    arr=["START","COMMIT","END"]

    for i in range(len(T)):
        tr=T[i]

        #update logs(remove ',')
        if(tr[0] not in arr):
            s=""
            s=s.join(tr)
            s=s.split(',')
            T[i]=s

        #start ckpts
        if(tr[1]=="CKPT"):

            #remove ()
            tr[2]=tr[2][1:]
            tr[-1]=tr[-1][:-1]

            #remove ','
            for j in range(2,len(tr),1):
                if(tr[j][-1]==","):
                    tr[j]=tr[j][:-1]

            T[i]=tr

    return T



def find_commit(T):
    """
    Return list of committed transactions
    """

    CT=[]
    for i in T:
        if(i[0]=="COMMIT"):
            CT.append(i[1])

    return CT



def remove_commit(T,CT):
    """
    Return updated transaction list after removing committed transactions
    """

    arr=["START","COMMIT","END","CKPT"]
    T_upd=[]
    for i in T:
        
        #start
        if(i[0]==arr[0]) and (i[1] not in CT) and(i[1] not in arr):
            T_upd.append(i)
        
        #update
        if(i[0] not in arr) and (i[0] not in CT):
            T_upd.append(i)

        #commit
        if(i[0]==arr[1]) and (i[1] not in CT):
            T_upd.append(i)
        
        #ckpt
        if(i[1]==arr[3]):
            temp=[]
            temp.append(i[0])
            temp.append(i[1])
            for j in range(2,len(i),1):
                if(i[j] not in CT):
                    temp.append(i[j])

            T_upd.append(temp)
                    
    return T_upd



def findckpt(T):
    """
    Return latest ckpt index
    """

    start=len(T)
    end=len(T)
    for i in range(len(T)):
        log=T[i]
        if(log[1]=="CKPT"):
            start=i
        if(log[0]=="END"):
            end=i
    
    start=len(T)-1-start
    end=len(T)-1-end

    return [start,end]



def get_end_index(T,start):
    """
    Return index till where we have to do recovery
    """

    last=start

    #find incomplete transactions
    incomplete=[]
    for i in range(2,len(T[start]),1):
        incomplete.append(T[start][i])


    for i in incomplete:
        for j in range(start,len(T),1):
            x=T[j]
            if(x[0]=="START" and x[1]==i):
                last=max(last,j)
                
    return last



def log_recovery(D,T):
    """
    Return recovered values in disk
    """

    #preprocessing
    T=preprocess(T)
    CT=find_commit(T)
    T=remove_commit(T,CT)
    start,end=findckpt(T)

    #reverse the list
    T.reverse()
    
    #initialise variables
    arr=["START","COMMIT","END"]
    last=len(T)

    #CASE-1 no start and no end
    if(start==-1 and end==-1):
        last=len(T)

    #CASE-2 no start but end (not possible)

    #CASE-3 start and no end
    elif(start!=-1 and end==-1):
        last=get_end_index(T,start)

    #CASE-3 start and end
    elif(start!=-1 and end!=-1):
        if(end<start):
            last=start
        else:
            last=get_end_index(T,start)

    #do recovery
    for i in range(last):
        tr=T[i]
        if(tr[0] not in arr):
            D[tr[1]]=tr[2]

    return D



def printdisk(D):
    """
    Print content of disk in the given format
    """

    Dt=sorted(D.keys())
    i=0
    for x in Dt:
        i+=1
        if(i==len(Dt)):
            print(x,D[x],end='')
        else:
            print(x,D[x],end=' ')
    print("")



if __name__=="__main__":

    F=sys.argv[1]
    # print(F,X)
    Disk,Transactions=readinput(F)
    Disk=log_recovery(Disk,Transactions)
    printdisk(Disk)<file_sep>/README.md
# Undo-Logging
Implementaion of undo logging and recovery
