# Exercise 3B
# Maintaining a contacts list.
# Each contact is a (name, phone-number) pair.
# The contacts are ordered by name.
#
# Author: David Watt.

def initialise (contacts):
    "Remove all entries from contacts."
    del contacts[:]

def add (contacts, name, number):
    "Add an entry (name, number) to contacts, \
     replacing any existing entry (name, ???)."
    entry = (name, number)
    l = len(contacts)
    for i in range(0, l):
        (cname, cnum) = contacts[i]
        if cname > name:
            contacts[i:i] = [entry]
            return
        elif cname == name:
            contacts[i] = entry
            return
    contacts[l:l] = [entry]

def lookup (contacts, name):
    "Return the number corresponding to name in contacts, \
     or '????' if there is no such name."
    p = fast_search(contacts, name)
    if p >= 0:
        (cname, cnum) = contacts[p]
        return cnum
    else:
        return '????'

def remove (contacts, name):
    "Remove the entry corresponding to name in contacts, \
     or do nothing if there is no such name."
    p = fast_search(contacts, name)
    if p >= 0:
        del contacts[p]

def tabulate (contacts):
    "Tabulate the names and numbers in contacts."
    if contacts == []:
        print 'Contacts list is empty'
    else:
        print 'Name', '\t', 'Number'
        for contact in contacts:
            (cname, cnum) = contact
            print cname, '\t', cnum

def slow_search (contacts, name):
    "Return the position of the entry (name, ????) in contacts, \
     or -1 if there is no such name."
    for i in range(0, len(contacts)):
        (cname, cnum) = contacts[i]
        if cname == name:
            return i
        elif cname > name:
            return -1
    return -1

def fast_search (contacts, name):
    "Return the position of the entry (name, ????) in contacts, \
     or -1 if there is no such name."
    l = 0
    r = len(contacts)
    while l < r:
        # Invariant: the target entry is in contacts[l:r].
        m = (l + r) // 2
        (cname, cnum) = contacts[m]
        if cname == name:
            return m
        elif cname > name:
            r = m
        else:
            l = m+1
    return -1