def IDENT(current, G,):
    global varName1
    t = tree('IDENT')
    if current.name == "REFERENCE":
        current = next(G)
        current.pattern = "ref-" + current.pattern
    if current.name != 'ID':
        raise ParserError("Syntax Error: Error when parsing IDENT: " \
                          + current.line)
    tmp = tree('ID')
    tmp.val = current.pattern
    t.append(tmp)
    g = ""
    try:
        g = dict_[current.pattern][0]
    except:
        pass
    gt = typeOfVar
    try:
        gt = dict_[current.pattern][1]
    except:
        pass
    dict_[current.pattern] = (g, gt) #add symbol to symbol table, will use different values later.
    varScopeDict[scope_variate] = {current.pattern:(g, gt)}
    return t, next(G)

def STATEMENT(current, G):
	t = tree("STATEMENT")
	s = {}
	if current.name == "ID":
		current, child, s1 = ASSIGNMENT(current, G) #make sure ASSIGNMENT is returning next(G)
		t.children.append(child)
		s.update(s1)
		return current, t, s #current should be a ;

	elif current.name == "READ":
		t.children.append(tree("READ"))
		current = next(G)
		if not current.name == "LPAREN":
			raise ParserError("READ token is not followed by a (" + getTokenLineInfo(current))
		current, child, s1 = ID_LIST(next(G), G) #should be returning a )
		t.children.append(child) #child should be the ID_LIST tree
		s.update(s1)
		if not current.name == "RPAREN":
			raise ParserError("Missing closing ) in READ statement" + getTokenLineInfo(current))
		return next(G), t, s  #next(G) should be a ;

	elif current.name == "WRITE":
		t.children.append(tree("WRITE"))
		current = next(G)
		if not current.name == "LPAREN":
			raise ParserError("WRITE token is not followed by a (" + getTokenLineInfo(current))
		current, child, s1 = EXPR_LIST(next(G), G) #should be returning a )
		t.children.append(child)
		s.update(s1)
		if not current.name == "RPAREN":
			raise ParserError("Missing closing ) in WRITE statement" + getTokenLineInfo(current))
		return next(G), t, s  #next(G) should be a ;

	else:
		raise ParserError("Inappproriate token to start a statement" + getTokenLineInfo(current))

def init_plat_tree():

    # Create /api end point as root node
    r_api = tree("api", data = get_node_api())

    # Add /api/spb to represent side plane board
    r_spb = tree("spb", data = get_node_spb())
    r_api.addChild(r_spb)

    # Add servers /api/server[1-max]
    num = pal_get_num_slots()
    for i in range(1, num+1):
        r_server = populate_server_node(i)
        if r_server:
            r_api.addChild(r_server)

    # TODO: Need to add /api/nic to represent NIC Mezz Card

    # Add /api/spb/fruid end point
    r_temp = tree("fruid", data = get_node_fruid("spb"))
    r_spb.addChild(r_temp)

    # /api/spb/bmc end point
    r_temp = tree("bmc", data = get_node_bmc())
    r_spb.addChild(r_temp)

    # /api/spb/sensors end point
    r_temp = tree("sensors", data = get_node_sensors("spb"))
    r_spb.addChild(r_temp)

    return r_api

def rearrange_tree(t):
	'''Take a tree, and rearrange either a tree or a child. Return the rearranged tree.'''
	if t.size() == 3:
		return do_rearrange(t)
	lsize = t.left.size()
	rsize = t.right.size()
	if lsize < 3 and rsize < 3:
		return do_rearrange(t)
	elif lsize < 3:
		rand = random.randrange(rsize - 1)
		if rand == 0:
			return do_rearrange(t)
		else:
			return tree.tree(children=(t.left, rearrange_tree(t.right)))
	elif rsize < 3:
		rand = random.randrange(lsize - 1)
		if rand == 0:
			return do_rearrange(t)
		else:
			return tree.tree(children=(rearrange_tree(t.left), t.right))
	else:
		rand = random.randrange(lsize + rsize - 3)
		if rand == 0:
			return do_rearrange(t)
		elif rand < lsize - 1:
			return tree.tree(children=(rearrange_tree(t.left), t.right))
		else:
			return tree.tree(children=(t.left, rearrange_tree(t.right)))

def FUNCTIONLST(current, G):
    global scope_variate
    t1 = tree("FUNCLIST")
    while(True):
        t = tree("FUNCTION")
        if current.name != "FUNCTION":
            break
        type = next(G)
        funcReturn = tree(type.name)
        funcReturn.val = type.pattern
        t.append(funcReturn)
        name = next(G)
        funcName = tree(name.name)
        funcName.val = name.pattern
        t.append(funcName)
        funcDict[name.pattern] = type.name
        scope_variate = name.pattern
        current = next(G)
        if current.name == "LPAREN":
            holder = False
            current = next(G)
            while(True):
                if current.name == "RPAREN":
                    break
                if current.name == "COMMA":
                    current = next(G)
                t1, current, holder = STATEMENT(current, G)
                t.append(t1)
        current = next(G)
        tt, current = PROGRAM(current, G)
        t.append(tt)
        t1.append(t)
    return t1, current

def TERM2(current, G):
    t = tree("TERM2")
    s = {}
    # assumes sign returns useful current
    current, child, s1 = SIGN(current, G)
    t.children.append(child)
    s.update(s1)
    current, child, s1 = FACT2(current, G)
    t.children.append(child)
    s.update(s1)
    while current.name == "TIMES" or current.name == "DIVIDE" or current.name == "MODULO":
        if current.name == "TIMES":
            t.children.append(tree("TIMES"))
        elif current.name == "DIVIDE":
            t.children.append(tree("DIVIDE"))
        else:  # current.name == "MODULO"
            t.children.append(tree("MODULO"))
        current, child, s1 = SIGN(next(G), G)
        t.children.append(child)
        s.update(s1)
        # Assumes FACT2 returns useful current
        current, child, s1 = FACT2(current, G)
        t.children.append(child)
        s.update(s1)
    return current, t, s

def IDENT(current, G):
	t = tree("IDENT")
	s = {current.pattern: None}
	if not current.name == "ID":
		raise ParserError("Invalid identifier" + getTokenLineInfo(current))
	t.children.append(tree("ID"))
	return next(G), t, s

def branchnbound_search(cm):
	'''Do an exhaustive search on all possible trees in the char matrix using
	branch-and-bound methods.'''
	global best_length
	taxa = cm.taxon_set()
	outgroup = cm.get_outgroup()
	taxa.remove(outgroup)
	outgroup_tree = tree.tree(id=outgroup)

	trees = all_trees_rec_bb(taxa, cm, outgroup_tree)

	best_tree = None
	ntrees = 0
	for a_tree in trees:
		ntrees += 1
		real_tree = tree.tree(children=(outgroup_tree, a_tree))
		tree_len = real_tree.length(cm)
		if best_length == None or tree_len < best_length:
			best_tree = [real_tree]
			best_length = tree_len
		elif tree_len == best_length:
			best_tree.append(real_tree)

	print "Total trees examined: %d" % ntrees
	print "Length of best tree(s): %d" % best_length	
	print "Number of best tree(s): %d" % len(best_tree)

	return best_tree

def main():
    MUSIC_FORMATS = ['mp3', 'flac', 'waw', 'm4a']
    yes = set(['yes','y', 'ye', ''])
    no = set(['no','n'])

    args = unparse_arguments(MUSIC_FORMATS)

    empty_dirs = find_folders_not_containing(args.path, MUSIC_FORMATS)
    for folder in empty_dirs:
        if args.tree:
            tree.tree(folder, '  ', True)
        else:
            print(folder)

    if empty_dirs:
        print("Do you want to delete listed directories? [yes/no]")
        choice = input().lower()

        if (choice in yes):
            print("Deleting dirs")
            delete_dirs(empty_dirs)
        else:
            print("You have canceled this action")
    else:
        print("Your music library is already clean")

def ARITH_OP(current, G):
	# process the ARITHOP here when building tree before returning the next (G)
	if current.name == "PLUS":
		return next(G), tree("PLUS")
	if current.name == "MINUS":
		return next(G), tree("MINUS")
	else: #this should never happen because only way to get to this function is if current is an arith op
		raise ParserError("Invalid ARITH_OP" + getTokenLineInfo(current))

def do_rearrange(t):
	'''Perform a rearrangement on a tree'''
	if t.left.is_terminal:
		child1, child2 = t.right, t.left
	elif t.right.is_terminal:
		child1, child2 = t.left, t.right
	else:
		child1, child2 = t.children()

	gchild1, gchild2 = child1.children()
	return tree.tree(children=(gchild1, tree.tree(children=(gchild2, child2))))

def getData(f,words):
    data = open(f,'r')
    lines = data.readlines()
    examples = []
    for i in lines:
        i=i.strip()
        if(len(i) > 0):
            i=i.split('\t')
            if len(i) >= 2:
                e = (tree(i[0]), tree(i[1]))
                examples.append(e)
    return examples

def trees_adding_bb(t, taxon, cm, og):
	'''Yield all the trees that can be obtained from adding taxon to the tree t'''
	new_tree = tree.tree(children=(t, tree.tree(id=taxon)))
	if best_length == None or tree.tree(children=(og, new_tree)).length(cm) < best_length:
		yield new_tree

	if not t.is_terminal:
		l, r = t.left, t.right
		for a_tree in r.all_trees_left(trees_adding_bb(l, taxon, cm, og)):
			yield a_tree
		for a_tree in l.all_trees_right(trees_adding_bb(r, taxon, cm, og)):
			yield a_tree

def PROGRAM(current, G):
    t = tree("PROGRAM")
    if current.name == "BEGIN":
        t1 = tree("BEGIN")
        t.append(t1)
        t2, current = STATEMENT_LIST(next(G), G)
        t.append(t2)
        if current.name == "END":
            t.append(tree("END"))
            return t, next(G)
        raise ParserError("Syntax Error: No 'end' at line: " + current.line)
    raise ParserError("Syntax Error: No 'begin' at line: " + current.line)

def TYPE(current, G):
    t = tree("TYPE")
    s = {}
    if current.name == "INT":
        t.children.append(tree("INT"))
        return next(G), t, s, "INT"
    elif current.name == "BOOL":
        t.children.append(tree("BOOL"))
        return next(G), t, s, "BOOL"
    elif current.name == "STRING":
        t.children.append(tree("STRING"))
        return next(G), t, s, "STRING"

def R(current, G):
    t = tree("R")
    if(current.name == 'GREATEREQUAL') | (current.name == 'LESSEQUAL') |\
      (current.name == 'EQUAL') | (current.name == 'LESSTHAN') | \
      (current.name == 'GREATERTHAN') | (current.name == 'NOTEQUAL'):
        t.append(tree(current.name))
        current = next(G)
        t2, current = EXP2(current, G)
        t.append(t2)
        return t, current
    else:
        return t, current

def PRIMARY(current, G):
    global counter
    t = tree('PRIMARY')
    if current.pattern in funcDict.keys():
        tmp = tree("FUNCCALL")
        tmp.val = current.pattern
        paren = next(G)
        current = next(G)
        if current.name == "RPAREN":
            pass
        else:
            t1, current = ID_LIST(current, G)
            if current.name != "RPAREN":
                raise ParserError("not matching parens")
            tmp.append(t1)
            t.append(tmp)
        return t, next(G)
    if current.name == 'INTLIT':
        tmp = tree('INTLIT')
        tmp.val = current.pattern
        tuple1 = ("False", typeOfVar)
        dict_[varName1] = tuple1 #do we need this?
        t.append(tmp)
        return t, next(G)
    if current.name == 'BOOLLIT':
        tmp = tree('BOOLLIT')
        tmp.val = current.pattern
        tuple1 = ("False", typeOfVar)
        dict_[varName1] = tuple1 #do we need this?
        t.append(tmp)
        return t, next(G)
    if current.name == 'LPAREN':
        t1, current = EXPRESSION(next(G), G)
        if current.name != 'RPAREN':
            raise ParserError("Syntax Error: Expected rparen is missing: " \
                              + current.line)
        t.append(t1)
        return t, next(G)
    if current.name == "STRING": #unsure
        tstrlit = tree("STRING")
        tstrlit.val = current.pattern
        t.append(tstrlit)
        # valOfVar = current.pattern
        tuple1 = (current.pattern, "STRING")
        tname = "lit%i" % counter
        strDict[tname] = tuple1
        counter = counter + 1
        ct = next(G)
        return t, ct
    t2, current = IDENT(current, G)
    t.append(t2)
    return t, current

def TERM1(current, G):
    t = tree("TERM1")
    t1, current = FACT1(current, G)
    t.append(t1)

    while True:
        if (current.name == 'AND'): #May have to add ARITHOP in future
            t.append(tree(current.name))
            current = next(G)
            t2, current = FACT1(current, G)
            t.append(t2)
        if (current.name != 'AND'):
            return t, current

def TERM1(current, G):
    t = tree("TERM1")
    s = {}
    current, child, s1 = FACT1(current, G)
    t.children.append(child)
    s.update(s1)
    while current.name == "AND":
        t.children.append(tree("AND"))
        current = next(G)  # move to token after "and"
        current, child, s1 = FACT1(current, G)
        t.children.append(child)
        s.update(s1)
    return current, t, s  # current should be in {),;}

def FACT3(current, G):
    t = tree("FACT3")
    t1, current = PRIMARY(current, G)
    t.append(t1)

    while True:
        if (current.name == 'REMAINDER'): #May have to add ARITHOP in future
            t.append(tree(current.name))
            current = next(G)
            t2, current = PRIMARY(current, G)
            t.append(t2)
        if (current.name != 'REMAINDER'):
            return t, current