#ile: BST_Cipher.py

#  Description: BST Cipher

#  Student Name: Sungho Park

#  Student UT EID: sp44443

#  Partner's Name: Ohyoon Kwon

#  Partner's UT EID: ok2364

#  Course Name: CS 313E

#  Unique Number: 51345

#  Date Created: NOV/12/2018

#  Date Last Modified: NOV/12/2018


class Node(object):
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

class Tree (object):
    # the init() function creates the binary search tree with the
    #  encryption string. If the encryption string contains any
    #  character other than the characters 'a' through 'z' or the
    #  space character drop that character.
    def __init__ (self, encrypt_str):
        self.root = None
        self.extract(encrypt_str)

  # the insert() function adds a node containing a character in
  # the binary search tree. If the character already exists, it
  # does not add that character. There are no duplicate characters
  # in the binary search tree.
    def insert(self, ch):
        new_node = Node(ch)
        asc = ord(ch)
        if (self.root == None):
            self.root = new_node
        else:
            current = self.root
            parent = self.root
            while (current != None):
                parent = current
                if (asc < ord(current.data)):
                    current = current.lchild
                else:
                    current = current.rchild

            if (asc < ord(parent.data)):
                parent.lchild = new_node
            elif (asc == ord(parent.data)):
                pass
            else:
                parent.rchild = new_node


    # the search() function will search for a character in the binary
    #  search tree and return a string containing a series of lefts
    #  (<) and rights (>) needed to reach that character. It will
    #  return a blank string if the character does not exist in the tree.
    #  It will return * if the character is the root of the tree.

    def search (self, ch):
        current = self.root
        string = ""
        if ord(ch) == ord(self.root.data):
            string += "*"
        if current == None:
            return ""
        for i in range(len(ch)):
            while (current != None) and (ord(current.data) != ord(ch)):
                if ord(ch) < ord(current.data):
                    string += "<"
                    current = current.lchild
                else:
                    string += ">"
                    current = current.rchild
        return string

    # the traverse() function will take string composed of a series of
    # lefts (<) and rights (>) and return the corresponding
    # character in the binary search tree. It will return an empty string
    # if the input parameter does not lead to a valid character in the tree.
    def traverse (self, st):
        current = self.root
        string = ""
        if st == "":
            return string
        if current == None:
            return string
        for i in st:
            if i == ">":
                current = current.rchild
            elif i == "<":
                current = current.lchild
            elif i == "*":
                string += current.data
                return string
        return current.data


    # the encrypt() function will take a string as input parameter, convert
    # it to lower case, and return the encrypted string. It will ignore
    # all digits, punctuation marks, and special characters.
    def encrypt (self, st):
        st = st.lower()
        string = ""
        count = 0

        for i in st:
            a = self.search(i)
            string += a
            count += 1
            if (count < len(st)):
                string += "!"
        return string


    # the decrypt() function will take a string as input parameter, and
    # return the decrypted string.
    def decrypt (self, st):
        string1 = ""
        string2 = ""

        for i in st:
            if i == "!":
                string2 += self.traverse(string1)
                string1 = ""
            else:
                string1 += i
        string2 += self.traverse(string1)
        return string2

    #extracting received string and sending each character to the insert function
    def extract(self, str):
        templist = []
        str = str.lower()
        for i in str:
            if i.isalpha() or i == " ":
                if i not in templist:
                    templist.append(i)
        for i in templist:
            self.insert(i)

def main():
    str = input("Enter the encryption key: ")
    newstr = ''
    for ch in str:
        if (ch == " " or ch.isalpha()):
            newstr = newstr + ch

    tree1 = Tree(newstr)
    print()
    inp1 = input("Enter string to be encrypted: ")
    newstr1 = ''
    for ch in inp1:
        if (ch == " " or ch.isalpha()):
            newstr1 = newstr1 + ch
    print("Encrypted String:", tree1.encrypt(newstr1))
    print()
    inp2 = input("Enter string to be decrypted: ")
    print("Decrypted String:", tree1.decrypt(inp2))
    print()

main()