# Linked List insertion

class Link:
    empty = ()

    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is self.empty:
            return "Link({})".format(repr(self.first))
        else:
            return "Link({}, {})".format(repr(self.first), repr(self.rest))

def insert_sorted(L, v):
    """Return the result of inserting V at the appropriate point into
    list L, which is in ascending order.  Nondestructive.
    >>> P = Link(1, Link(15, Link(17)))
    >>> Q = insert_sorted(P, 16)
    >>> P
    Link(1, Link(15, Link(17)))
    >>> Q
    Link(1, Link(15, Link(16, Link(17))))
    """

    if L is Link.empty:
        return Link(v)
    elif L.first > v:
        return Link(v, L)

    result = last = Link(L.first)
    curr = L.rest
    
    while curr is not Link.empty and curr.first <= v:
        next = Link(curr.first)
        last.rest = next
        curr = curr.rest
        last = next

    last.rest = Link(v, curr)
    return result

# Prefix Codes

class BinTree:
    empty = ()

    def __init__(self, label, left=empty, right=empty):
        self.label = label
        self.left = left
        self.right = right

    def __repr__(self):
        if self.left == self.empty and self.right == self.empty:
            return 'BinTree({})'.format(repr(self.label))
        left = 'BinTree.empty' if self.left == self.empty else repr(self.left)
        right = 'BinTree.empty' if self.right == self.empty else repr(self.right)
        return 'BinTree({}, {}, {})'.format(repr(self.label), left, right)

    def is_leaf(self):
        return self.left == self.right == BinTree.empty

# Sample decoding tree from lecture.

CODED_ALPHABET = {
    "A": "1110",
    "B": "101100",
    "C": "01000",
    "D": "11111",
    "E": "011",
    "F": "00110",
    "G": "111100",
    "H": "0101",
    "I": "1100",
    "J": "001011001",
    "K": "0010111",
    "L": "10111",
    "M": "00111",
    "N": "1010",   
    "O": "1101",   
    "P": "101101", 
    "Q": "001011010",
    "R": "1000",   
    "S": "1001",   
    "T": "000",    
    "U": "01001",  
    "V": "001010", 
    "W": "111101", 
    "X": "001011011",
    "Y": "00100",  
    "Z": "001011000",
}

def make_encoding_tree(coding_map):
    """An encoding tree that implements CODING_MAP, a dictionary mapping
    characters to strings of 0s and 1s with the prefix property"""
    def add(c, code):
        """Add C to result with encoding CODE."""
        T = result
        for v in code:
            if v == '0':
                if T.left is BinTree.empty:
                    T.left = BinTree(None, BinTree.empty, BinTree.empty)
                T = T.left
            else:
                if T.right is BinTree.empty:
                    T.right = BinTree(None, BinTree.empty, BinTree.empty)
                T = T.right
        T.label = c

    result = BinTree(None, BinTree.empty, BinTree.empty)
    for c, code in coding_map.items():
        add(c, code)
    return result

ENCODING = make_encoding_tree(CODED_ALPHABET)

def decode(msg, encoding):
    """Decode MSG according ENCODING.
    MSG is a string of '0' and '1' characters.
    ENCODING is a prefix tree where leaf nodes contain the
    characters encoded by the path to that leaf.
    >>> decode(encode("THE CAT IN THE HAT", CODED_ALPHABET), ENCODING)
    'THEXCATXINXTHEXHAT'
    """
    result = ""
    k = 0
    def decode1():
        """Decode and return character starting at MSG[k], incrementing
        k to the bit after that character's representation."""
        nonlocal k
        T = encoding
        while T.label is None: # or while not T.is_leaf()
            if msg[k] == '0':
                T = T.left
            else:
                T = T.right
            k += 1
        return T.label

    while k < len(msg):
        result += decode1()
    return result

def encode(msg, coding_map, default="X"):
    """Encode MSG using CODING_MAP, a dictionary mapping characters to
    strings of 0's and 1's.  Any unrecognized characters are replaced by
    DEFAULT, which must be in CODING_MAP."""
    d = coding_map[default]
    return ''.join(map(lambda x: coding_map.get(x, d), msg))