class Node:

    def __init__(self,n,a,p,x):
        self.name = n
        self.address = a
        self.phone = p
        self.next = x
    
    def get_name(self):
        return self.name

    def get_phone(self):
        return self.phone

    def get_address(self):
        return self.address

    def get_next(self):
        return self.next

    def set_name(self,n):
        self.name = n

    def set_phone(self,p):
        self.phone = p

    def set_address(self,a):
        self.address = a

    def set_next(self,n):
        self.next = n

    def __str__(self):
        return "("+self.name+","+self.phone+","+self.address+")"

#from Node import *
	
class ContactsLL:

	# sorted singly linked list of contacts with empty header node
    
    def __init__(self):
        self.head = Node("","","",None)
        self.size = 0
    
    def get_size(self):
        return self.size

    def find(self,name):
        p = self.head
        found = False
        while p.get_next() != None and not found:
            if p.get_next().get_name() >= name:
                found = True
            else:
                p = p.get_next()
        if found and p.get_next().get_name() == name:
            return (True,p)
        else:
            return (False,p)

    def insert(self,contact):
        (found,position) = self.find(contact[0])
        if found:
            return False
        else:
            p = Node(contact[0],contact[1],contact[2],position.get_next())
            position.set_next(p)
            self.size = self.size + 1
            return True

    def delete(self,name):
        (found,position) = self.find(name)
        if not found:
            return False
        else:
            position.set_next(position.get_next().get_next())
            self.size = self.size - 1
            return True

    def update(self,contact):
        (found,position) = self.find(contact[0])
        if not found:
            return False
        else:
            position.get_next().set_phone(contact[1])
            position.get_next().set_address(contact[2])
            return True

    def __str__(self):
        p = self.head
        result = "\n"
        while p.get_next() != None:
            result = result + str(p.get_next())+"\n"
            p = p.get_next()
        return result+"\n"

#from ContactsLL import *

def load_contacts(fname):
  contacts = ContactsLL()
  with open(fname) as f:
    for line in f.readlines():
      line = line.strip("\n")
      c = line.split(":") 
      contacts.insert((c[0],c[1],c[2]))
  return contacts

def main():
  contacts = load_contacts("contacts.dat")
  print()
  while True:
    s = input("i n:p:a, d n, f n, u n:p:a, p, s, q for quit: ").strip()
    if s[0] == 'i':
      contact = s[1:].strip().split(":")
      if contacts.insert(contact):
        print("\n",contact[0]," INSERTED\n")
      else:
        print("\n",contact[0]," IS ALREADY PRESENT\n")
    elif s[0] == 'd':
      name = s[1:].strip()
      if contacts.delete(name):
        print("\n",name," DELETED\n")
      else:
        print("\n",name," NOT FOUND\n")
    elif s[0] == 'f':
      name = s[1:].strip()
      (found,position) = contacts.find(name)
      if not found:
        print("\nNo entry for "+name+"\n") 
      else:
        print("\n",position.get_next(),"\n")
    elif s[0] == 'u':
      contact = s[1:].strip().split(":")
      if contacts.update(contact):
        print("\n",contact[0]," UPDATED\n")
      else:
        print("\n",contact[0]," NOT FOUND\n")
    elif s[0] == 'p':
      print(contacts)
    elif s[0] == 's':
      print("\nSize = ",contacts.get_size(),"\n")
    elif s[0] == 'q':
      break
    else:
      print("Invalid option")

main()

(James,123 Elm Street,555-1214)
(John,123 Oak Street,555-1213)
(Raj,123 Main Street,555-1212)
(Sally,123 Cherry Street,555-1215)



 (Raj,123 Main Street,555-1212)