class TreeNode:

  def __init__(self, left, symbols, weight, right):
    self._left = left
    self._symbols = symbols
    self._weight = weight
    self._right = right

  def __str__(self):
    if self._left == None and self._right == None:
      return "TreeNode(None,"+str(self._symbols)+","+str(self._weight)+",None)"
    elif self._left == None:
      return "TreeNode(None,"+str(self._symbols)+","+str(self._weight)+","+str(self._right)+")"
    elif self._right == None:
      return "TreeNode("+str(self._left)+","+str(self._symbols)+","+str(self._weight)+",None)"
    else:
      return "TreeNode("+str(self._left)+","+str(self._symbols)+","+str(self._weight)+","+str(self._right)+")"

# takes a list of character frequencies (c,n) sorted in increasing order
# of frequency and returns a list of initial tree objects
def construct_initial_trees(sorted_frequencies):
	if len(sorted_frequencies) == 0:
		return []
	else:
		t = TreeNode(None,{sorted_frequencies[0][0]},
			               sorted_frequencies[0][1],None)
		return [t] + construct_initial_trees(sorted_frequencies[1:])

answer = construct_initial_trees([['A',4],['B',10]])
for t in answer:
    print(t)

TreeNode(None,{'A'},4,None)
TreeNode(None,{'B'},10,None)

# takes as input two Huffman trees and returns a single tree
# with a root and the two trees as sub-trees
def combine(t1,t2):
	return TreeNode(t1,t1._symbols.union(t2._symbols),t1._weight+t2._weight,t2)

t = combine(TreeNode(None,{'A'},4,None),TreeNode(None,{'B'},10,None))
print(t)

TreeNode(TreeNode(None,{'A'},4,None),{'B', 'A'},14,TreeNode(None,{'B'},10,None))

# takes as input a new tree t and a list of sorted trees and
# returns a sorted list of trees after inserting t into tlist.
def insertHT(t,tlist):
        if tlist == []:
                return [t]
        if t._weight <= tlist[0]._weight:
                return [t] + tlist
        return [tlist[0]] + insertHT(t,tlist[1:])

t = TreeNode(TreeNode(None,{'A'},4,None),
             {'B', 'A'},100,
             TreeNode(None,{'B'},10,None))
tlist = [TreeNode(None,{'A'},4,None), TreeNode(None,{'B'},20,None)] 
new_tlist = insertHT(t,tlist)
for t in new_tlist:
    print(t)

TreeNode(None,{'A'},4,None)
TreeNode(None,{'B'},20,None)
TreeNode(TreeNode(None,{'A'},4,None),{'B', 'A'},100,TreeNode(None,{'B'},10,None))

# takes as input a list of sorted trees, tlist, and returns a Huffman tree
# generated from tlist
def construct_huffman_tree(tlist):
	if len(tlist) == 1:
		return tlist[0]
	return construct_huffman_tree(insertHT(combine(tlist[0],tlist[1]),tlist[2:]))

print({1:10})

{1: 10}

def squareList(xs):
    result = []
    for x in xs:
        result.append(x*x)
    return result

def sumList(xs):
    result = 0
    for x in xs:
        result = result + x
    return result