from __future__ import absolute_import
from __future__ import print_function
import unittest
import random
import itertools
import json

import sys
from six.moves import range

from .. import Tree, PhyloTree, TreeNode
from ..coretype.tree import TreeError
from ..parser.newick import NewickError
from .datasets import *

class Test_Coretype_Tree(unittest.TestCase):
    """ Tests tree basics. """
    def test_read_write_exceptions(self):

        def wrong_dist():
            t = Tree()
            t.dist = '1a'

        def wrong_support():
            t = Tree()
            t.support = '1a'

        def wrong_up():
            t = Tree()
            t.up = 'Something'

        def wrong_children():
            t = Tree()
            t.children = 'Something'

        self.assertRaises(TreeError, wrong_dist)
        self.assertRaises(TreeError, wrong_support)
        self.assertRaises(TreeError, wrong_up)
        self.assertRaises(TreeError, wrong_children)

    def test_add_remove_features(self):
        #The features concept will probably change in future versions. It is
        #very inefficient in larg trees.
        t = Tree()
        t.add_features(testf1=1, testf2="1", testf3=[1])
        t.add_feature('testf4', set([1]))
        self.assertEqual(t.testf1, 1)
        self.assertEqual(t.testf2, "1")
        self.assertEqual(t.testf3, [1])
        self.assertEqual(t.testf4, set([1]))

        t.del_feature('testf4')
        self.assertTrue('testf4' not in t.features)

    def test_tree_read_and_write(self):
        """ Tests newick support """
        # Read and write newick tree from file (and support for NHX
        # format): newick parser
        with open("/tmp/etetemptree.nw","w") as OUT:
            OUT.write(nw_full)

        t = Tree("/tmp/etetemptree.nw")
        t.write(outfile='/tmp/etewritetest.nw')
        self.assertEqual(nw_full, t.write(features=["flag","mood"]))
        self.assertEqual(nw_topo,  t.write(format=9))
        self.assertEqual(nw_dist, t.write(format=5))

        # Read and write newick tree from *string* (and support for NHX
        # format)
        t = Tree(nw_full)
        self.assertEqual(nw_full, t.write(features=["flag","mood"]))
        self.assertEqual(nw_topo, t.write(format=9))
        self.assertEqual( nw_dist, t.write(format=5))

        # Read complex newick
        t = Tree(nw2_full)
        self.assertEqual(nw2_full,  t.write())

        # Read wierd topologies
        t = Tree(nw_simple5)
        self.assertEqual(nw_simple5,  t.write(format=9))
        t = Tree(nw_simple6)
        self.assertEqual(nw_simple6,  t.write(format=9))

        #Read single node trees:
        self.assertEqual(Tree("hola;").write(format=9),  "hola;")
        self.assertEqual(Tree("(hola);").write(format=9),  "(hola);")

        #Test export root features
        t = Tree("(((A[&&NHX:name=A],B[&&NHX:name=B])[&&NHX:name=NoName],C[&&NHX:name=C])[&&NHX:name=I],(D[&&NHX:name=D],F[&&NHX:name=F])[&&NHX:name=J])[&&NHX:name=root];")
        #print t.get_ascii()
        self.assertEqual(t.write(format=9, features=["name"], format_root_node=True),
                         "(((A[&&NHX:name=A],B[&&NHX:name=B])[&&NHX:name=NoName],C[&&NHX:name=C])[&&NHX:name=I],(D[&&NHX:name=D],F[&&NHX:name=F])[&&NHX:name=J])[&&NHX:name=root];")

        #Test exporting ordered features
        t = Tree("((A,B),C);")
        expected_nw = "((A:1[&&NHX:dist=1.0:name=A:support=1.0],B:1[&&NHX:0=0:1=1:2=2:3=3:4=4:5=5:6=6:7=7:8=8:9=9:a=a:b=b:c=c:d=d:dist=1.0:e=e:f=f:g=g:h=h:i=i:j=j:k=k:l=l:m=m:n=n:name=B:o=o:p=p:q=q:r=r:s=s:support=1.0:t=t:u=u:v=v:w=w])1:1[&&NHX:dist=1.0:name=:support=1.0],C:1[&&NHX:dist=1.0:name=C:support=1.0]);"
        features = list("abcdefghijklmnopqrstuvw0123456789")
        random.shuffle(features)
        for letter in features:
            (t & "B").add_feature(letter, letter)
        self.assertEqual(expected_nw, t.write(features=[]))

        # Node instance repr
        self.assertTrue(Tree().__repr__().startswith('Tree node'))

    def test_concat_trees(self):
        t1 = Tree('((A, B), C);')
        t2 = Tree('((a, b), c);')
        concat_tree = t1 + t2
        concat_tree.sort_descendants()
        self.assertEqual(concat_tree.write(format=9), '(((A,B),C),((a,b),c));')
        t3 = PhyloTree('((a, b), c);')
        mixed_types = lambda: t1 + t3
        self.assertRaises(TreeError, mixed_types)


    def test_newick_formats(self):
        """ tests different newick subformats """
        from ..parser.newick import print_supported_formats, NW_FORMAT
        print_supported_formats()

        # Let's stress a bit
        for i in range(10):
            t = Tree()
            t.populate(4, random_branches=True)
            for f in NW_FORMAT:
                self.assertEqual(t.write(format=f), Tree(t.write(format=f),format=f).write(format=f))

        # Format 0 = ((H:1,(G:1,F:1)1:1)1:1,I:1)1:1;
        # Format 1 = ((H:1,(G:1,F:1):1):1,I:1):1;
        # Format 2 = ((H:1,(G:1,F:1)1:1)1:1,I:1)1:1;
        # Format 3 = ((H:1,(G:1,F:1)NoName:1)NoName:1,I:1)NoName:1;
        # Format 4 = ((H:1,(G:1,F:1)),I:1);
        # Format 5 = ((H:1,(G:1,F:1):1):1,I:1):1;
        # Format 6 = ((H,(G,F):1):1,I):1;
        # Format 7 = ((H:1,(G:1,F:1)NoName)NoName,I:1)NoName;
        # Format 8 = ((H,(G,F)NoName)NoName,I)NoName;
        # Format 9 = ((H,(G,F)),I);
        # Format 100 = ((,(,)),);

        t = Tree()
        t.populate(50, random_branches=True)
        t.sort_descendants()
        expected_distances = [round(x, 6) for x in [n.dist for n in t.traverse('postorder')]]
        expected_leaf_distances = [round(x, 6) for x in [n.dist for n in t]]
        expected_internal_distances = [round(x, 6) for x in [n.dist for n in t.traverse('postorder') if not n.is_leaf()]]
        expected_supports = [round(x, 6) for x in [n.support for n in t.traverse('postorder') if not n.is_leaf()]]
        expected_leaf_names = [n.name for n in t]

        # Check that all formats read names correctly
        for f in [0,1,2,3,5,6,7,8,9]:
            t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f)
            t2.sort_descendants()
            observed_names = [n.name for n in t]
            self.assertEqual(observed_names, expected_leaf_names)

        # Check that all formats reading distances, recover original distances
        for f in [0,1,2,3,5]:
            t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f)
            t2.sort_descendants()
            observed_distances = [round(x, 6) for x in [n.dist for n in t2.traverse('postorder')]]
            self.assertEqual(observed_distances, expected_distances)

        # formats reading only leaf distances
        for f in [4,7]:
            t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f)
            t2.sort_descendants()
            observed_distances = [round(x, 6) for x in [n.dist for n in t2]]
            self.assertEqual(observed_distances, expected_leaf_distances)

        # formats reading only leaf distances
        for f in [6]:
            t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f)
            t2.sort_descendants()
            observed_distances = [round(x, 6) for x in [n.dist for n in t2.traverse('postorder') if not n.is_leaf()]]
            self.assertEqual(observed_distances, expected_internal_distances)


        # Check that all formats reading supports, recover original distances
        #print t.get_ascii(attributes=["support"])
        for f in [0,2]:
            t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f)
            t2.sort_descendants()
            observed_supports = [round(x, 6) for x in [n.support for n in t2.traverse('postorder') if not n.is_leaf()]]
            self.assertEqual(observed_supports, expected_supports)


       # Check that formats reading supports, do not accept node names
        for f in [0,2]:
            # format 3 forces dumping internal node names, NoName in case is missing
            self.assertRaises(Exception, Tree, t.write(format=3), format=f)

       # Check that formats reading names, do not load supports
        for f in [1, 3]:
            # format 3 forces dumping internal node names, NoName in case is missing
            t2 = Tree(t.write(format=0), format=f)
            default_supports = set([n.support for n in t2.traverse()])
            self.assertEqual(set([1.0]), default_supports)


        # Check errors reading numbers
        error_nw1 = "((A:0.813705,(E:0.545591,D:0.411772)error:0.137245)1.000000:0.976306,C:0.074268);"
        for f in [0, 2]:
            self.assertRaises(NewickError, Tree, error_nw1, format=f)

        error_nw2 = "((A:0.813705,(E:0.545error,D:0.411772)1.0:0.137245)1.000000:0.976306,C:0.074268);"
        for f in [0, 1, 2]:
            self.assertRaises(NewickError, Tree, error_nw2, format=f)


        error_nw3 = "((A:0.813705,(E:0.545error,D:0.411772)1.0:0.137245)1.000000:0.976306,C:0.074268);"
        for f in [0, 1, 2]:
            self.assertRaises(NewickError, Tree, error_nw2, format=f)

        # Check errors derived from reading names with weird or illegal chars
        base_nw = "((NAME1:0.813705,(NAME2:0.545,NAME3:0.411772)NAME6:0.137245)NAME5:0.976306,NAME4:0.074268);"
        valid_names = ['[name]', '[name', '"name"', "'name'", "'name", 'name', '[]\'"&%$!*.']
        error_names = ['error)', '(error', "erro()r",  ":error", "error:", "err:or", ",error", "error,"]
        for ename in error_names:
            #print ename, base_nw.replace('NAME2', ename)
            self.assertRaises(NewickError, Tree, base_nw.replace('NAME2', ename), format=1)
            if not ename.startswith(','):
                #print ename, base_nw.replace('NAME6', ename)
                self.assertRaises(NewickError, Tree, base_nw.replace('NAME6', ename), format=1)

        for vname in valid_names:
            expected_names = set(['NAME1', vname, 'NAME3', 'NAME4'])
            #print set([n.name for n in Tree(base_nw.replace('NAME2', vname), format=1)])
            self.assertEqual(set([n.name for n in Tree(base_nw.replace('NAME2', vname), format=1)]),
                             expected_names)

        # invalid NHX format
        self.assertRaises(NewickError, Tree, "(((A, B), C)[&&NHX:nameI]);")
        # unsupported newick stream
        self.assertRaises(NewickError, Tree, [1,2,3])

    def test_quoted_names(self):
        complex_name = "((A:0.0001[&&NHX:hello=true],B:0.011)90:0.01[&&NHX:hello=true],(C:0.01, D:0.001)hello:0.01);"
        # A quoted tree within a tree
        nw1 = '(("A:0.1":1,"%s":2)"C:0.00":3,"D":4);' %complex_name
        #escaped quotes
        nw2 = '''(("A:\\"0.1\\"":1,"%s":2)"C:'0.00'":3,"D'sd''\'":4);''' %complex_name
        for nw in [nw1, nw2]:
            self.assertRaises(NewickError, Tree, newick=nw)
            self.assertRaises(NewickError, Tree, newick=nw, quoted_node_names=True, format=0)
            t = Tree(newick=nw, format=1, quoted_node_names=True)
            self.assertTrue(any(n for n in t if n.name == '%s'%complex_name))
            # test writing and reloading tree
            nw_back = t.write(quoted_node_names=True, format=1)
            t2 = Tree(newick=nw, format=1, quoted_node_names=True)
            nw_back2 = t2.write(quoted_node_names=True, format=1)
            self.assertEqual(nw, nw_back)
            self.assertEqual(nw, nw_back2)

    def test_custom_formatting_formats(self):
        """ test to change dist, name and support formatters """
        t = Tree('((A:1.111111, B:2.222222)C:3.33333, D:4.44444);', format=1)
        t.sort_descendants()

        check = [[0, '((TEST-A:1.1,TEST-B:2.2)SUP-1.0:3.3,TEST-D:4.4);'],
                 [1, '((TEST-A:1.1,TEST-B:2.2)TEST-C:3.3,TEST-D:4.4);'],
                 [2, '((TEST-A:1.1,TEST-B:2.2)SUP-1.0:3.3,TEST-D:4.4);'],
                 [3, '((TEST-A:1.1,TEST-B:2.2)TEST-C:3.3,TEST-D:4.4);'],
                 [4, '((TEST-A:1.1,TEST-B:2.2),TEST-D:4.4);'],
                 [5, '((TEST-A:1.1,TEST-B:2.2):3.3,TEST-D:4.4);'],
                 [6, '((TEST-A,TEST-B):3.3,TEST-D);'],
                 [7, '((TEST-A:1.1,TEST-B:2.2)TEST-C,TEST-D:4.4);'],
                 [8, '((TEST-A,TEST-B)TEST-C,TEST-D);'],
                 [9, '((TEST-A,TEST-B),TEST-D);']]

        for f, result in check:
            nw = t.write(format=f, dist_formatter="%0.1f", name_formatter="TEST-%s", support_formatter="SUP-%0.1f")
            self.assertEqual(nw, result)

    def test_tree_manipulation(self):
        """ tests operations which modify tree topology """
        nw_tree = "((Hola:1,Turtle:1.3)1:1,(A:0.3,B:2.4)1:0.43);"

        # Manipulate Topologies
        # Adding and removing nodes (add_child, remove_child,
        # add_sister, remove_sister). The resulting newick tree should
        # match the nw_tree defined before.
        t = Tree()

        remove_child_except = lambda: t.remove_child(t)
        add_sister_except = lambda: t.add_sister()
        self.assertRaises(TreeError, remove_child_except)
        self.assertRaises(TreeError, add_sister_except)


        c1 = t.add_child(dist=1, support=1)
        c2 = t.add_child(dist=0.43, support=1)
        n = TreeNode(name="Hola", dist=1, support=1)
        _n = c1.add_child(n)
        c3 = _n.add_sister(name="Turtle", dist="1.3")
        c4 = c2.add_child(name="A", dist="0.3")

        c5 = c2.add_child(name="todelete")
        _c5 = c2.remove_child(c5)

        c6 = c2.add_child(name="todelete")
        _c6 = c4.remove_sister()

        c7 = c2.add_child(name="B", dist=2.4)

        self.assertEqual(nw_tree, t.write())
        self.assertEqual(_c5, c5)
        self.assertEqual(_c6, c6)
        self.assertEqual(_n, n)

        # Delete,
        t = Tree("(((A, B), C)[&&NHX:name=I], (D, F)[&&NHX:name=J])[&&NHX:name=root];")
        D = t.search_nodes(name="D")[0]
        F = t.search_nodes(name="F")[0]
        J = t.search_nodes(name="J")[0]
        root = t.search_nodes(name="root")[0]
        J.delete()
        self.assertEqual(J.up, None)
        self.assertEqual(J in t, False)
        self.assertEqual(D.up, root)
        self.assertEqual(F.up, root)

        # Delete preventing non dicotomic
        t = Tree('((((A:1,B:1):1,C:1):1,D:1):1,E:1);')
        orig_dist = t.get_distance('A')
        C = t&('C')
        C.delete(preserve_branch_length=True)
        self.assertEqual(orig_dist, t.get_distance('A'))

        t = Tree('((((A:1,B:1):1,C:1):1,D:1):1,E:1);')
        orig_dist = t.get_distance('A')
        C = t&('C')
        C.delete(preserve_branch_length=False)
        self.assertEqual(orig_dist, t.get_distance('A')+1)

        t = Tree('((((A:1,B:1):1,C:1):1,D:1):1,E:1);')
        orig_dist = t.get_distance('A')
        C = t&('C')
        C.delete(prevent_nondicotomic=False)
        self.assertEqual(orig_dist, t.get_distance('A'))

        #detach
        t = Tree("(((A, B)[&&NHX:name=H], C)[&&NHX:name=I], (D, F)[&&NHX:name=J])[&&NHX:name=root];")
        D = t.search_nodes(name="D")[0]
        F = t.search_nodes(name="F")[0]
        J = t.search_nodes(name="J")[0]
        root = t.search_nodes(name="root")[0]
        J.detach()
        self.assertEqual(J.up, None)
        self.assertEqual(J in t, False)
        self.assertEqual(set([n.name for n in t.iter_descendants()]),set(["A","B","C","I","H"]))

        # sorting branches
        t1 = Tree('((A,B),(C,D,E,F), (G,H,I));')
        t1.ladderize()
        self.assertEqual(t1.get_leaf_names(), [_ for _ in 'ABGHICDEF'])
        t1.ladderize(direction=1)
        self.assertEqual(t1.get_leaf_names(), [_ for _ in 'FEDCIHGBA'])
        t1.sort_descendants()
        self.assertEqual(t1.get_leaf_names(), [_ for _ in 'ABCDEFGHI'])

        # prune
        t1 = Tree("(((A, B), C)[&&NHX:name=I], (D, F)[&&NHX:name=J])[&&NHX:name=root];")
        D1 = t1.search_nodes(name="D")[0]
        t1.prune(["A","C", D1])
        sys.stdout.flush()
        self.assertEqual(set([n.name for n in t1.iter_descendants()]),  set(["A","C","D","I"]))

        t1 = Tree("(((A, B), C)[&&NHX:name=I], (D, F)[&&NHX:name=J])[&&NHX:name=root];")
        D1 = t1.search_nodes(name="D")[0]
        t1.prune(["A","B"])
        self.assertEqual( t1.write(), "(A:1,B:1);")

        # test prune keeping internal nodes

        t1 = Tree('(((((A,B)C)D,E)F,G)H,(I,J)K)root;', format=1)
        #print t1.get_ascii()
        t1.prune(['A', 'B', 'F', 'H'])
        #print t1.get_ascii()
        self.assertEqual(set([n.name for n in t1.traverse()]),
                         set(['A', 'B', 'F', 'H', 'root']))

        t1 = Tree('(((((A,B)C)D,E)F,G)H,(I,J)K)root;', format=1)
        #print t1.get_ascii()
        t1.prune(['A', 'B'])
        #print t1.get_ascii()
        self.assertEqual(set([n.name for n in t1.traverse()]),
                         set(['A', 'B', 'root']))

        t1 = Tree('(((((A,B)C)D,E)F,G)H,(I,J)K)root;', format=1)
        #print t1.get_ascii()
        t1.prune(['A', 'B', 'C'])
        #print t1.get_ascii()
        self.assertEqual(set([n.name for n in t1.traverse()]),
                         set(['A', 'B', 'C', 'root']))

        t1 = Tree('(((((A,B)C)D,E)F,G)H,(I,J)K)root;', format=1)
        #print t1.get_ascii()
        t1.prune(['A', 'B', 'I'])
        #print t1.get_ascii()
        self.assertEqual(set([n.name for n in t1.traverse()]),
                         set(['A', 'B', 'C', 'I', 'root']))

    def test_pruninig(self):
        # test prune preserving distances
        for i in range(10):
            t = Tree()
            t.populate(40, random_branches=True)
            orig_nw = t.write()
            distances = {}
            for a in t.iter_leaves():
                for b in t.iter_leaves():
                    distances[(a,b)] = round(a.get_distance(b), 6)

            to_keep = set(random.sample(t.get_leaves(), 6))
            t.prune(to_keep, preserve_branch_length=True)
            for a,b in distances:
                if a in to_keep and b in to_keep:
                    self.assertEqual(distances[(a,b)], round(a.get_distance(b), 6))

        # Total number of nodes is correct (no single child nodes)
        for x in range(10):
            t_fuzzy = Tree("(((A,B)1, C)2,(D,E)3)root;", format=1)
            t_fuzzy.sort_descendants()
            orig_nw = t_fuzzy.write()
            ref_nodes = t_fuzzy.get_leaves()
            t_fuzzy.populate(10)
            (t_fuzzy&'1').populate(3)
            (t_fuzzy&'2').populate(5)
            (t_fuzzy&'3').populate(5)
            t_fuzzy.prune(ref_nodes)
            t_fuzzy.sort_descendants()
            self.assertEqual(orig_nw, t_fuzzy.write())
            self.assertEqual(len(t_fuzzy.get_descendants()), (len(ref_nodes)*2)-2 )

        # Total number of nodes is correct (no single child nodes)
        t = Tree()
        sample_size = 5
        t.populate(1000)
        sample = random.sample(t.get_leaves(), sample_size)
        t.prune(sample)
        self.assertEqual(len(t), sample_size)
        self.assertEqual(len(t.get_descendants()), (sample_size*2)-2 )

        # Test preserve branch dist when pruning
        t = Tree()
        t.populate(100, random_branches=True)
        orig_leaves = t.get_leaves()
        sample_size = 50
        sample= random.sample(t.get_leaves(), sample_size)
        matrix1 = ["%f" %t.get_distance(a, b) for (a,b) in itertools.product(sample, sample)]
        t.prune(sample, preserve_branch_length=True)
        matrix2 = ["%f" %t.get_distance(a, b) for (a,b)in itertools.product(sample, sample)]

        self.assertEqual(matrix1, matrix2)
        self.assertEqual(len(t.get_descendants()), (sample_size*2)-2 )

    def test_resolve_polytomies(self):
        # resolve polytomy
        t = Tree("((a,a,a,a), (b,b,b,(c,c,c)));")
        t.resolve_polytomy()
        t.ladderize()
        self.assertEqual(t.write(format=9), "((a,(a,(a,a))),(b,(b,(b,(c,(c,c))))));")

        t = Tree("((((a,a,a,a))), (b,b,b,(c,c,c)));")
        t.standardize()
        t.ladderize()
        self.assertEqual(t.write(format=9), "((a,(a,(a,a))),(b,(b,(b,(c,(c,c))))));")

    def test_common_ancestors(self):
        # getting nodes, get_childs, get_sisters, get_tree_root,
        # get_common_ancestor, get_nodes_by_name
        # get_descendants_by_name, is_leaf, is_root
        t = Tree("(((A,B)N1,C)N2[&&NHX:tag=common],D)[&&NHX:tag=root:name=root];", format=1)
        self.assertEqual(t.get_sisters(), [])

        A = t.search_nodes(name="A")[0]
        B = t.search_nodes(name="B")[0]
        C = t.search_nodes(name="C")[0]
        root = (t&"root")
        self.assertEqual("A", A.name)
        test_not_found = lambda: t&'noffound'
        self.assertRaises(TreeError, test_not_found)

        self.assertEqual("common", A.get_common_ancestor(C).tag)
        self.assertEqual("common", A.get_common_ancestor([C]).tag)
        self.assertEqual("common", t.get_common_ancestor(A, C).tag)
        self.assertEqual("common", A.get_common_ancestor(C, B).tag)
        self.assertEqual(root, t.get_common_ancestor([A, "D"]))

        self.assertEqual("root", A.get_tree_root().tag)
        self.assertEqual("root", B.get_tree_root().tag)
        self.assertEqual("root", C.get_tree_root().tag)

        common = A.get_common_ancestor(C)
        self.assertEqual("root", common.get_tree_root().tag)

        self.assertTrue(common.get_tree_root().is_root())
        self.assertTrue(not A.is_root())
        self.assertTrue(A.is_leaf())
        self.assertTrue(not A.get_tree_root().is_leaf())
        self.assertRaises(TreeError, A.get_common_ancestor, Tree())

        # Test multiple target nodes and get_path argument
        common, path = t.get_common_ancestor(['A', 'C'], get_path=True)
        N1 = t & "N1"
        N2 = t & "N2"
        expected_path = {A: set([A, root, N1, N2]), C: set([C, N2, root])}
        self.assertEqual(common, N2)
        self.assertEqual(path.keys(), expected_path.keys())
        for k in path.keys():
            self.assertEqual(list(sorted(path[k], key=lambda x: x.name)),
                             list(sorted(expected_path[k], key=lambda x: x.name)))

        # Test common ancestor function using self as single argument (issue #398)
        common = A.get_common_ancestor(A)
        self.assertEqual(common, A)
        common = C.get_common_ancestor("C")
        self.assertEqual(common, C)
        common, path = C.get_common_ancestor("C", get_path=True)
        self.assertEqual(common, C)
        self.assertDictEqual(path, {})

    def test_getters_iters(self):

        # Iter ancestors
        t = Tree("(((((a,b)A,c)B,d)C,e)D,f)root;", format=1)
        ancestor_names = [n.name for n in (t&"a").get_ancestors()]
        self.assertEqual(ancestor_names, ["A", "B", "C", "D", "root"])
        ancestor_names = [n.name for n in (t&"B").get_ancestors()]
        self.assertEqual(ancestor_names, ["C", "D", "root"])


        # Tree magic python features
        t = Tree(nw_dflt)
        self.assertEqual(len(t), 20)
        self.assertTrue("Ddi0002240" in t)
        self.assertTrue(t.children[0] in t)
        for a in t:
            self.assertTrue(a.name)

        # Populate
        t = Tree(nw_full)
        prev_size= len(t)
        t.populate(25)
        self.assertEqual(len(t), prev_size+25)
        for i in range(10):
            t = Tree()
            t.populate(100, reuse_names=False)
            # Checks that all names are actually unique
            self.assertEqual(len(set(t.get_leaf_names())), 100)

        # Adding and removing features
        t = Tree("(((A,B),C)[&&NHX:tag=common],D)[&&NHX:tag=root];")
        A = t.search_nodes(name="A")[0]

        # Check gettters and itters return the same
        t = Tree(nw2_full)
        self.assertEqual(t.get_leaf_names(), [name for name in  t.iter_leaf_names()])
        self.assertEqual(t.get_leaves(), [name for name in  t.iter_leaves()])
        self.assertEqual(t.get_descendants(), [n for n in  t.iter_descendants()])

        self.assertEqual(set([n for n in t.traverse("preorder")]), \
                             set([n for n in t.traverse("postorder")]))
        self.assertTrue(t in set([n for n in t.traverse("preorder")]))

        # Check order or visiting nodes

        t = Tree("((3,4)2,(6,7)5)1;", format=1)
        #t = Tree("(((A, B)C, (D, E)F)G, (H, (I, J)K)L)M;", format=1)
        #postorder = [c for c in "ABCDEFGHIJKLM"]
        #preorder =  [c for c in reversed(postorder)]
        #levelorder = [c for c in "MGLCFHKABDEIJ"]
        postorder = "3426751"
        preorder = "1234567"
        levelorder = "1253467"

        self.assertEqual(preorder,
                          ''.join([n.name for n in t.traverse("preorder")]))

        self.assertEqual(postorder,
                         ''.join([n.name for n in t.traverse("postorder")]))

        self.assertEqual(levelorder,
                         ''.join([n.name for n in t.traverse("levelorder")]))

        # Swap childs
        n = t.get_children()
        t.swap_children()
        n.reverse()
        self.assertEqual(n, t.get_children())


    def test_distances(self):
        # Distances: get_distance, get_farthest_node,
        # get_farthest_descendant, get_midpoint_outgroup
        t = Tree("(((A:0.1, B:0.01):0.001, C:0.0001):1.0[&&NHX:name=I], (D:0.00001):0.000001[&&NHX:name=J]):2.0[&&NHX:name=root];")
        A = t.search_nodes(name="A")[0]
        B = t.search_nodes(name="B")[0]
        C = t.search_nodes(name="C")[0]
        D = t.search_nodes(name="D")[0]
        I = t.search_nodes(name="I")[0]
        J = t.search_nodes(name="J")[0]
        root = t.search_nodes(name="root")[0]

        self.assertEqual(A.get_common_ancestor(I).name, "I")
        self.assertEqual(A.get_common_ancestor(D).name, "root")
        self.assertEqual(A.get_distance(I), 0.101)
        self.assertEqual(A.get_distance(B), 0.11)
        self.assertEqual(A.get_distance(A), 0)
        self.assertEqual(I.get_distance(I), 0)
        self.assertEqual(A.get_distance(root), root.get_distance(A))

        self.assertEqual(t.get_distance(A, root), root.get_distance(A))
        self.assertEqual(t.get_distance(root, A), A.get_distance(root))

        # Get_farthest_node, get_farthest_leaf
        self.assertEqual(root.get_farthest_leaf(), (A,1.101) )
        self.assertEqual(root.get_farthest_node(), (A,1.101) )
        self.assertEqual(A.get_farthest_leaf(), (A, 0.0))
        self.assertEqual(A.get_farthest_node(), (D, 1.101011))
        self.assertEqual(I.get_farthest_node(), (D, 1.000011))

        # Topology only distances
        t = Tree('(((A:0.5, B:1.0):1.0, C:5.0):1, (D:10.0, F:1.0):2.0):20;')

        self.assertEqual(t.get_closest_leaf(), (t&'A', 2.5))
        self.assertEqual(t.get_farthest_leaf(), (t&'D', 12.0))
        self.assertEqual(t.get_farthest_leaf(topology_only=True), (t&'A', 2.0))
        self.assertEqual(t.get_closest_leaf(topology_only=True), (t&'C', 1.0))
        self.assertEqual(t.get_distance(t), 0.0)
        self.assertEqual(t.get_distance(t, topology_only=True), 0.0)
        self.assertEqual(t.get_distance(t&'A', topology_only=True), 2.0)

        self.assertEqual((t&'F').get_farthest_node(topology_only=True), (t&'A', 3.0))
        self.assertEqual((t&'F').get_farthest_node(topology_only=False), (t&'D', 11.0))

    def test_rooting(self):
        # Test set_outgroup and get_midpoint_outgroup
        t = Tree(nw2_full)
        YGR028W = t.get_leaves_by_name("YGR028W")[0]
        YGR138C = t.get_leaves_by_name("YGR138C")[0]
        d1 = YGR138C.get_distance(YGR028W)
        nodes = t.get_descendants()
        t.set_outgroup(t.get_midpoint_outgroup())
        o1, o2 = t.children[0], t.children[1]
        nw_original = t.write()
        d2 = YGR138C.get_distance(YGR028W)
        self.assertEqual(d1, d2)
        # Randomizing outgroup test: Can we recover original state
        # after many manipulations?
        for i in range(10):
            for j in range(1000):
                n = random.sample(nodes, 1)[0]
                t.set_outgroup(n)
            t.set_outgroup(t.get_midpoint_outgroup())
            self.assertEqual(set([t.children[0], t.children[1]]), set([o1, o2]))
            ##  I need to sort branches first
            #self.assertEqual(t.write(), nw_original)
        d3 = YGR138C.get_distance(YGR028W)
        self.assertEqual(d1, d3)

        t = Tree('(A,B,(C,D)E)root;', format=1);
        t.sort_descendants()
        nw_unrooted = t.write()
        t.set_outgroup(t.get_common_ancestor('C', 'D'));
        t.unroot()
        t.sort_descendants()
        self.assertEqual(nw_unrooted, t.write())

        t = Tree('(A:10,B:1,(C:1,D:1)E:1)root;', format=1);
        t.set_outgroup(t.get_midpoint_outgroup())
        self.assertEqual(t.children[0].dist, 5.0)
        self.assertEqual(t.children[1].dist, 5.0)


    def test_unroot(self):
        t = Tree("(('a':0.5, 'b':0.5):0.5, ('c':0.2, 'd':0.2):0.8):1;" )
        t2 = Tree("(('a':0.5, 'b':0.5):0.5, ('c':0.2, 'd':0.2):0.8):1;" )
        t.unroot(mode="keep")
        with self.assertRaises(ValueError):
            t.unroot(mode="new")
        t2.unroot(mode="legacy")
        self.assertEqual("(('c':0.2,'d':0.2)1:1.3,'a':0.5,'b':0.5);", t.write())
        self.assertEqual("(('c':0.2,'d':0.2)1:0.8,'a':0.5,'b':0.5);", t2.write())

    def test_tree_navigation(self):
        t = Tree("(((A, B)H, C)I, (D, F)J)root;", format=1)
        postorder = [n.name for n in t.traverse("postorder")]
        preorder = [n.name for n in t.traverse("preorder")]
        levelorder = [n.name for n in t.traverse("levelorder")]

        self.assertEqual(postorder, ['A', 'B', 'H', 'C', 'I', 'D', 'F', 'J', 'root'])
        self.assertEqual(preorder, ['root', 'I', 'H', 'A', 'B', 'C', 'J', 'D', 'F'])
        self.assertEqual(levelorder, ['root', 'I', 'J', 'H', 'C', 'D', 'F', 'A', 'B'])
        ancestors = [n.name for n in (t&"B").get_ancestors()]
        self.assertEqual(ancestors, ["H", "I", "root"])
        self.assertEqual(t.get_ancestors(), [])

        # add something of is_leaf_fn etc...
        custom_test = lambda x: x.name in set("JCH")
        custom_leaves = t.get_leaves(is_leaf_fn=custom_test)
        self.assertEqual(set([n.name for n in custom_leaves]), set("JHC"))

        # Test cached content
        t = Tree()
        t.populate(20)

        cache_node = t.get_cached_content()
        cache_node_leaves_only_false = t.get_cached_content(leaves_only=False)
        self.assertEqual(cache_node[t], set(t.get_leaves()))
        self.assertEqual(cache_node_leaves_only_false[t], set(t.traverse()))

        cache_name = t.get_cached_content(store_attr="name")
        cache_name_leaves_only_false = t.get_cached_content(store_attr="name", leaves_only=False)
        self.assertEqual(cache_name[t], set(t.get_leaf_names()))
        self.assertEqual(cache_name_leaves_only_false[t], set([n.name for n in t.traverse()]))

        cache_many = t.get_cached_content(store_attr=["name", "dist", "support"])
        cache_many_lof = t.get_cached_content(store_attr=["name", "dist", "support"], leaves_only=False)
        self.assertEqual(cache_many[t], set([(leaf.name, leaf.dist, leaf.support) for leaf in t.get_leaves()]))
        self.assertEqual(cache_many_lof[t], set([(n.name, n.dist, n.support) for n in t.traverse()]))


        #self.assertEqual(cache_name_lof[t], [t.name])


    def test_rooting(self):
        """ Check branch support and distances after rooting """

        t = Tree("((((a,b)1,c)2,i)3,(e,d)4)5;", format=1)
        t.set_outgroup(t&"a")


        t = Tree("(((a,b)2,c)x)9;", format=1)
        t.set_outgroup(t&"a")

        # Test branch support and distances after rooting
        SIZE = 35
        t = Tree()
        t.populate(SIZE, reuse_names=False)
        t.unroot()
        for n in t.iter_descendants():
            if n is not t:
                n.support = random.random()
                n.dist = random.random()
        for n in t.children:
            n.support = 0.999
        t2 = t.copy()

        names = set(t.get_leaf_names())
        cluster_id2support = {}
        cluster_id2dist = {}
        for n in t.traverse():
            cluster_names = set(n.get_leaf_names())
            cluster_names2 = names - cluster_names
            cluster_id = '_'.join(sorted(cluster_names))
            cluster_id2 = '_'.join(sorted(cluster_names2))
            cluster_id2support[cluster_id] = n.support
            cluster_id2support[cluster_id2] = n.support

            cluster_id2dist[cluster_id] = n.dist
            cluster_id2dist[cluster_id2] = n.dist


        for i in range(100):
            outgroup = random.sample(t2.get_descendants(), 1)[0]
            t2.set_outgroup(outgroup)
            for n in t2.traverse():
                cluster_names = set(n.get_leaf_names())
                cluster_names2 = names - cluster_names
                cluster_id = '_'.join(sorted(cluster_names))
                cluster_id2 = '_'.join(sorted(cluster_names2))
                self.assertEqual(cluster_id2support.get(cluster_id, None), n.support)
                self.assertEqual(cluster_id2support.get(cluster_id2, None), n.support)
                if n.up and n.up.up:
                    self.assertEqual(cluster_id2dist.get(cluster_id, None), n.dist)

        # Test unrooting
        t = Tree()
        t.populate(20)
        t.unroot()

        # Printing and info
        text = t.get_ascii()

        Tree().describe()
        Tree('(a,b,c);').describe()
        Tree('(a,(b,c));').describe()


    def test_treeid(self):
        t = Tree()
        t.populate(50, random_branches=True)
        orig_id = t.get_topology_id()
        nodes = t.get_descendants()
        for i in range(20):
            for n in random.sample(nodes, 10):
                n.swap_children()
                self.assertEqual(t.get_topology_id(), orig_id)


    def test_ultrametric(self):

        # Convert tree to a ultrametric topology in which distance from
        # leaf to root is always 100. Two strategies are available:
        # balanced or fixed
        t =  Tree()
        t.populate(100, random_branches=True)
        t.convert_to_ultrametric(100, "balanced")
        self.assertEqual(set([round(t.get_distance(n), 6) for n in t]), set([100.0]))

        t =  Tree()
        t.populate(100, random_branches=True)
        t.convert_to_ultrametric(100, "fixed")
        self.assertEqual(set([round(t.get_distance(n), 6) for n in t]), set([100.0]))

        t =  Tree()
        t.populate(100, random_branches=True)
        t.convert_to_ultrametric(100, "balanced")
        self.assertEqual(set([round(t.get_distance(n), 6) for n in t]), set([100.0]))


    def test_expand_polytomies_rf(self):
        gtree = Tree('((a:1, (b:1, (c:1, d:1):1):1), (e:1, (f:1, g:1):1):1);')
        ref1 = Tree('((a:1, (b:1, c:1, d:1):1):1, (e:1, (f:1, g:1):1):1);')
        ref2 = Tree('((a:1, (b:1, c:1, d:1):1):1, (e:1, f:1, g:1):1);')
        for ref in [ref1, ref2]:
            #print gtree, ref
            gtree.robinson_foulds(ref, expand_polytomies=True)[0]


        gtree = Tree('((g, h), (a, (b, (c, (d,( e, f))))));')
        ref3 = Tree('((a, b, c, (d, e, f)), (g, h));')
        ref4 = Tree('((a, b, c, d, e, f), (g, h));')
        ref5 = Tree('((a, b, (c, d, (e, f))), (g, h));')

        for ref in [ref3, ref4, ref5]:
            #print gtree, ref
            gtree.robinson_foulds(ref, expand_polytomies=True, polytomy_size_limit=8)[0]


        gtree = Tree('((g, h), (a, b, (c, d, (e, f))));')
        ref6 = Tree('((a, b, (c, d, e, f)), (g, h));')
        ref7 = Tree('((a, (b, (c, d, e, f))), (g, h));')
        ref8 = Tree('((a, b, c, (d, e, f)), (g, h));')
        ref9 = Tree('((d, b, c, (a, e, f)), (g, h));')

        for ref in [ref6, ref7, ref8, ref9]:
            #print gtree, ref
            gtree.robinson_foulds(ref, expand_polytomies=True)[0]
            #print "REF GOOD", gtree.robinson_foulds(ref, expand_polytomies=True, polytomy_size_limit=8)[0]

        gtree = Tree('((g, h), ((a, b), (c, d), (e, f)));')
        ref10 = Tree('((g, h), ((a, c), ((b, d), (e, f))));')

        for ref in [ref10]:
            #print gtree, ref
            gtree.robinson_foulds(ref, expand_polytomies=True, polytomy_size_limit=8)[0]

    def test_tree_compare(self):
        def _astuple(d):
            keynames = ["norm_rf", "rf", "max_rf", "ref_edges_in_source", "source_edges_in_ref", "effective_tree_size", "source_subtrees", "treeko_dist"]
            # print
            # print "ref", len(d["ref_edges"])
            # print "src", len(d["source_edges"])
            # print "common", len(d["common_edges"]), d['common_edges']
            # print d["rf"], d["max_rf"]

            return tuple([d[v] for v in keynames])


        ref1 = Tree('((((A, B)0.91, (C, D))0.9, (E,F)0.96), (G, H));')
        ref2 = Tree('(((A, B)0.91, (C, D))0.9, (E,F)0.96);')
        s1 = Tree('(((A, B)0.9, (C, D))0.9, (E,F)0.9);')


        small = Tree("((A, B), C);")
        # RF unrooted in too small trees for rf, but with at least one internal node
        self.assertEqual(_astuple(small.compare(ref1, unrooted=True)),
                         ("NA", "NA", 0.0, 1.0, 1.0, 3, 1, "NA"))

        small = Tree("(A, B);")
        # RF unrooted in too small trees
        self.assertEqual(_astuple(small.compare(ref1, unrooted=True)),
                         ("NA", "NA", 0.0, "NA", "NA", 2, 1, "NA"))

        small = Tree("(A, B);")
        # RF unrooted in too small trees
        self.assertEqual(_astuple(small.compare(ref1, unrooted=False)),
                         ("NA", "NA", 0.0, "NA", "NA", 2, 1, "NA"))

        # identical trees, 8 rooted partitions in total (4 an 4), and 6 unrooted
        self.assertEqual(_astuple(s1.compare(ref1)),
                         (0.0, 0.0, 8, 1.0, 1.0, 6, 1, "NA"))

        self.assertEqual(_astuple(s1.compare(ref1, unrooted=True)),
                         (0.0, 0.0, 6, 1.0, 1.0, 6, 1, "NA"))

        # The same stats should be return discarding branches, as the topology
        # is still identical, but branches used should be different
        self.assertEqual(_astuple(s1.compare(ref1, min_support_source=0.99, min_support_ref=.99)),
                         (0.0, 0.0, 2, 1.0, 1.0, 6, 1, "NA"))

        self.assertEqual(_astuple(s1.compare(ref1, min_support_source=0.99, min_support_ref=.99, unrooted=True)),
                         (0.0, 0.0, 2, 1.0, 1.0, 6, 1, "NA"))


        self.assertEqual(_astuple(s1.compare(ref1, min_support_source=0.99)),
                         (0.0, 0.0, 5, 1/4., 1.0, 6, 1, "NA"))


        self.assertEqual(_astuple(s1.compare(ref1, min_support_source=0.99, unrooted=True)),
                         (0.0, 0.0, 4, 6/8., 1.0, 6, 1, "NA"))


        self.assertEqual(_astuple(s1.compare(ref1, min_support_ref=0.99)),
                         (0.0, 0.0, 5, 1.0, 1/4., 6, 1, "NA"))


        self.assertEqual(_astuple(s1.compare(ref1, min_support_ref=0.99, unrooted=True)),
                         (0.0, 0.0, 4, 1.0, 6/8., 6, 1, "NA"))


        # Three partitions different
        s2 = Tree('(((A, E)0.9, (C, D))0.98, (B,F)0.95);')
        self.assertEqual(_astuple(s2.compare(ref1)),
                         (6/8., 6, 8, 1/4., 1/4., 6, 1, "NA"))

        self.assertEqual(_astuple(s2.compare(ref1, unrooted=True)),
                         (4/6., 4, 6, 6/8., 6/8., 6, 1, "NA"))

        # lets discard one branch from source tree.  there are 4 valid edges in
        # ref, 3 in source there is only 2 edges in common, CD and root (which
        # should be discounted for % of found branches)
        self.assertEqual(_astuple(s2.compare(ref1, min_support_source=0.95)),
                         (5/7., 5, 7, 1/4., 1/3., 6, 1, "NA"))

        # similar in unrooted, but we don not need to discount root edges
        self.assertEqual(_astuple(s2.compare(ref1, min_support_source=0.95, unrooted=True)),
                         (3/5., 3, 5, 6/8., 6/7., 6, 1, "NA"))


        # totally different trees
        s3 = Tree('(((A, C)0.9, (E, D))0.98, (B,F)0.95);')
        self.assertEqual(_astuple(s3.compare(ref1)),
                         (1.0, 8, 8, 0.0, 0.0, 6, 1, "NA"))


    def test_tree_diff(self):
        # this is the result of 100 Ktreedist runs on random trees, using rooted
        # and unrooted topologies. ETE should provide the same RF result
        samples = [
        [28, True, '(((z,y),(x,(w,v))),(u,t),((s,r),((q,(p,o)),((n,(m,(l,(k,j)))),(i,(h,g))))));', '(((k,(j,(i,(h,g)))),z),(y,x),((w,v),((u,(t,(s,(r,q)))),(p,(o,(n,(m,l)))))));'],
        [28, False, '(((t,s),((r,(q,p)),(o,n))),(((m,(l,(k,j))),(i,(h,g))),(z,(y,(x,(w,(v,u)))))));', '((((k,(j,i)),((h,g),z)),((y,(x,w)),((v,(u,t)),(s,(r,(q,p)))))),((o,n),(m,l)));'],
        [18, True, '(((v,(u,(t,s))),((r,(q,(p,o))),((n,m),(l,k)))),(j,(i,(h,g))),(z,(y,(x,w))));', '(((z,(y,(x,w))),(v,(u,(t,s)))),((r,(q,p)),(o,(n,m))),((l,(k,(j,i))),(h,g)));'],
        [26, True, '(((l,k),(j,i)),((h,g),(z,(y,(x,w)))),((v,(u,(t,(s,(r,q))))),((p,o),(n,m))));', '(((p,o),((n,(m,l)),(k,j))),((i,(h,g)),(z,y)),((x,(w,v)),((u,(t,s)),(r,q))));'],
        [24, True, '(((o,(n,m)),(l,(k,(j,(i,(h,g)))))),(z,(y,x)),((w,v),((u,(t,(s,r))),(q,p))));', '(((t,(s,(r,(q,(p,o))))),(n,m)),((l,k),(j,(i,(h,g)))),((z,y),((x,w),(v,u))));'],
        [24, True, '(((y,(x,(w,v))),(u,t)),((s,(r,(q,(p,o)))),(n,m)),((l,k),((j,(i,(h,g))),z)));', '(((z,(y,(x,w))),(v,(u,t))),(s,(r,(q,(p,(o,(n,(m,(l,k)))))))),(j,(i,(h,g))));'],
        [28, False, '(((p,(o,(n,(m,l)))),((k,(j,i)),(h,g))),((z,y),((x,(w,(v,u))),(t,(s,(r,q))))));', '((((t,(s,r)),(q,p)),((o,n),(m,(l,(k,(j,i)))))),(((h,g),(z,(y,(x,w)))),(v,u)));'],
        [28, True, '((((i,(h,g)),z),(y,x)),((w,v),((u,(t,(s,r))),(q,p))),((o,n),(m,(l,(k,j)))));', '((((h,g),z),(y,x)),(w,(v,u)),((t,s),((r,(q,p)),((o,(n,m)),(l,(k,(j,i)))))));'],
        [28, True, '(((x,(w,(v,(u,(t,(s,(r,(q,(p,o))))))))),((n,(m,l)),(k,(j,i)))),(h,g),(z,y));', '(((u,t),(s,r)),((q,p),(o,(n,m))),(((l,(k,(j,i))),((h,g),(z,(y,x)))),(w,v)));'],
        [22, False, '(((x,(w,(v,u))),((t,(s,r)),(q,p))),((o,(n,(m,l))),((k,j),((i,(h,g)),(z,y)))));', '(((z,(y,(x,(w,(v,u))))),(t,(s,r))),((q,(p,(o,(n,m)))),((l,k),(j,(i,(h,g))))));'],
        [26, True, '((z,(y,(x,w))),(v,(u,(t,s))),((r,(q,(p,(o,(n,m))))),((l,k),(j,(i,(h,g))))));', '(((v,(u,t)),((s,r),((q,(p,o)),(n,(m,l))))),((k,j),((i,(h,g)),z)),(y,(x,w)));'],
        [34, False, '((((i,(h,g)),(z,(y,x))),(w,v)),((u,t),((s,r),((q,(p,(o,n))),(m,(l,(k,j)))))));', '(((p,(o,(n,(m,(l,k))))),((j,i),(h,g))),(z,(y,(x,(w,(v,(u,(t,(s,(r,q))))))))));'],
        [30, False, '(((i,(h,g)),(z,y)),((x,w),((v,(u,(t,(s,(r,q))))),(p,(o,(n,(m,(l,(k,j)))))))));', '((((l,k),(j,(i,(h,g)))),(z,(y,(x,w)))),((v,u),((t,s),((r,(q,p)),(o,(n,m))))));'],
        [26, False, '(((v,(u,t)),((s,(r,q)),((p,o),((n,m),((l,k),(j,i)))))),((h,g),(z,(y,(x,w)))));', '(((y,(x,(w,v))),(u,(t,s))),(((r,q),((p,o),(n,(m,(l,k))))),((j,i),((h,g),z))));'],
        [20, False, '(((u,(t,s)),(r,q)),(((p,o),((n,m),((l,k),((j,i),((h,g),z))))),(y,(x,(w,v)))));', '((((u,t),(s,r)),(((q,p),(o,(n,m))),(((l,k),(j,i)),((h,g),z)))),((y,x),(w,v)));'],
        [20, True, '(((y,x),(w,v)),((u,(t,s)),((r,q),(p,(o,(n,(m,(l,k))))))),((j,(i,(h,g))),z));', '(((r,q),((p,o),(n,(m,(l,(k,j)))))),((i,(h,g)),(z,(y,(x,(w,v))))),(u,(t,s)));'],
        [24, True, '((((k,(j,i)),(h,g)),((z,(y,(x,w))),((v,(u,t)),(s,r)))),(q,(p,(o,n))),(m,l));', '((((s,r),((q,p),(o,(n,m)))),((l,k),((j,i),((h,g),z)))),(y,x),(w,(v,(u,t))));'],
        [18, True, '((w,(v,(u,(t,s)))),(r,q),((p,(o,n)),((m,(l,k)),((j,(i,(h,g))),(z,(y,x))))));', '(((y,x),((w,v),(u,(t,s)))),((r,(q,(p,(o,n)))),(m,l)),((k,j),((i,(h,g)),z)));'],
        [26, True, '(((j,(i,(h,g))),(z,(y,(x,(w,(v,(u,t))))))),(s,r),((q,p),((o,(n,m)),(l,k))));', '(((s,(r,(q,(p,(o,(n,(m,l))))))),(k,j)),((i,(h,g)),(z,y)),((x,(w,v)),(u,t)));'],
        [30, True, '((((r,(q,(p,(o,n)))),((m,l),(k,(j,i)))),((h,g),z)),(y,(x,(w,v))),(u,(t,s)));', '(((u,t),(s,r)),((q,p),(o,(n,(m,(l,(k,j)))))),(((i,(h,g)),(z,(y,x))),(w,v)));'],
        [30, False, '((((m,(l,k)),(j,i)),(((h,g),(z,y)),(x,w))),((v,u),(t,(s,(r,(q,(p,(o,n))))))));', '(((u,t),((s,(r,q)),(p,(o,(n,(m,(l,k))))))),((j,(i,(h,g))),(z,(y,(x,(w,v))))));'],
        [22, False, '(((k,(j,i)),(h,g)),((z,(y,x)),((w,(v,(u,(t,(s,r))))),((q,(p,(o,n))),(m,l)))));', '(((w,(v,u)),((t,(s,r)),((q,p),((o,(n,(m,l))),((k,(j,i)),((h,g),z)))))),(y,x));'],
        [26, False, '(((x,(w,(v,(u,(t,s))))),(r,q)),((p,(o,(n,(m,l)))),((k,j),((i,(h,g)),(z,y)))));', '(((o,(n,m)),(l,(k,j))),(((i,(h,g)),(z,y)),((x,w),((v,u),((t,(s,r)),(q,p))))));'],
        [28, True, '(((x,(w,v)),(u,(t,s))),((r,(q,(p,(o,(n,m))))),(l,(k,(j,(i,(h,g)))))),(z,y));', '((((i,(h,g)),(z,(y,x))),((w,v),((u,t),(s,(r,(q,p)))))),(o,n),((m,l),(k,j)));'],
        [20, False, '((((m,l),(k,(j,(i,(h,g))))),(z,y)),((x,(w,(v,(u,(t,s))))),(r,(q,(p,(o,n))))));', '((((m,l),((k,(j,i)),(h,g))),(z,(y,(x,(w,v))))),((u,t),(s,(r,(q,(p,(o,n)))))));'],
        [26, True, '(((o,(n,(m,(l,k)))),(j,i)),((h,g),(z,y)),((x,(w,(v,(u,(t,s))))),(r,(q,p))));', '((((t,(s,(r,(q,(p,(o,n)))))),(m,(l,k))),((j,i),(h,g))),(z,(y,x)),(w,(v,u)));'],
        [22, False, '((((p,o),((n,m),((l,k),(j,i)))),((h,g),(z,y))),((x,(w,(v,u))),((t,s),(r,q))));', '((((v,(u,(t,s))),(r,q)),((p,o),((n,m),(l,k)))),(((j,i),(h,g)),(z,(y,(x,w)))));'],
        [28, False, '((((r,(q,(p,(o,n)))),(m,(l,k))),(((j,i),(h,g)),((z,y),(x,w)))),((v,u),(t,s)));', '((((k,j),((i,(h,g)),(z,y))),(x,w)),(((v,(u,t)),(s,r)),((q,p),((o,n),(m,l)))));'],
        [20, True, '((((q,(p,o)),(n,m)),((l,k),((j,i),(h,g)))),(z,(y,x)),((w,v),(u,(t,(s,r)))));', '((((l,(k,(j,i))),(h,g)),((z,y),(x,(w,v)))),(u,t),((s,(r,(q,(p,o)))),(n,m)));'],
        [28, False, '(((t,(s,r)),(q,(p,o))),(((n,(m,(l,k))),(j,(i,(h,g)))),((z,y),(x,(w,(v,u))))));', '(((w,(v,u)),(t,s)),(((r,(q,p)),(o,n)),(((m,l),((k,j),((i,(h,g)),z))),(y,x))));'],
        [24, True, '((((h,g),(z,y)),((x,(w,(v,u))),(t,(s,(r,q))))),(p,o),((n,m),((l,k),(j,i))));', '(((t,s),((r,(q,p)),((o,(n,(m,l))),((k,j),(i,(h,g)))))),(z,y),(x,(w,(v,u))));'],
        [20, True, '(((p,o),(n,(m,(l,(k,(j,i)))))),((h,g),z),((y,(x,w)),((v,u),(t,(s,(r,q))))));', '(((y,(x,w)),(v,(u,t))),((s,r),(q,p)),((o,(n,m)),((l,(k,(j,i))),((h,g),z))));'],
        [32, True, '((((s,(r,q)),((p,(o,n)),(m,(l,k)))),((j,(i,(h,g))),(z,y))),(x,w),(v,(u,t)));', '(((u,(t,(s,r))),((q,(p,o)),((n,(m,l)),(k,(j,i))))),((h,g),(z,(y,x))),(w,v));'],
        [26, True, '(((z,(y,x)),(w,(v,(u,t)))),(s,(r,(q,(p,(o,n))))),((m,l),(k,(j,(i,(h,g))))));', '(((u,t),((s,r),((q,p),((o,n),((m,(l,k)),((j,i),((h,g),z))))))),(y,x),(w,v));'],
        [10, True, '(((p,o),((n,m),((l,(k,(j,i))),((h,g),(z,y))))),(x,(w,(v,u))),((t,s),(r,q)));', '((((n,m),((l,(k,(j,i))),((h,g),(z,y)))),(x,w)),(v,(u,(t,(s,(r,q))))),(p,o));'],
        [30, True, '((((h,g),z),((y,x),((w,v),(u,t)))),(s,r),((q,p),((o,n),((m,l),(k,(j,i))))));', '((((v,(u,(t,(s,r)))),(q,(p,o))),((n,m),((l,k),(j,(i,(h,g)))))),(z,y),(x,w));'],
        [30, False, '(((q,(p,o)),((n,m),((l,(k,(j,(i,(h,g))))),(z,y)))),((x,(w,v)),(u,(t,(s,r)))));', '((((t,s),((r,q),((p,o),(n,m)))),((l,k),(j,i))),(((h,g),z),((y,(x,w)),(v,u))));'],
        [24, False, '(((p,o),(n,m)),(((l,(k,(j,i))),(h,g)),((z,y),((x,w),((v,u),(t,(s,(r,q))))))));', '((x,(w,v)),((u,(t,(s,(r,q)))),((p,(o,(n,(m,(l,(k,(j,(i,(h,g))))))))),(z,y))));'],
        [28, False, '(((z,y),((x,w),((v,u),(t,s)))),((r,(q,(p,(o,(n,m))))),((l,k),((j,i),(h,g)))));', '((((s,(r,q)),((p,o),((n,(m,l)),(k,(j,(i,(h,g))))))),(z,y)),((x,w),(v,(u,t))));'],
        [24, False, '((((o,n),((m,l),((k,(j,i)),(h,g)))),(z,(y,x))),((w,(v,(u,(t,(s,r))))),(q,p)));', '(((q,(p,(o,(n,m)))),((l,(k,j)),(i,(h,g)))),(z,(y,(x,(w,(v,(u,(t,(s,r)))))))));'],
        [22, True, '(((p,(o,(n,m))),((l,k),((j,i),((h,g),(z,y))))),(x,w),((v,u),((t,s),(r,q))));', '(((u,(t,(s,(r,(q,(p,(o,(n,m)))))))),((l,k),((j,i),((h,g),(z,(y,x)))))),w,v);'],
        [28, False, '((((r,q),((p,o),(n,(m,l)))),((k,(j,i)),(h,g))),((z,y),((x,(w,v)),(u,(t,s)))));', '(((h,g),z),((y,x),((w,v),((u,t),((s,(r,(q,(p,(o,(n,m)))))),(l,(k,(j,i))))))));'],
        [30, True, '((((h,g),z),((y,(x,(w,(v,u)))),((t,s),((r,(q,(p,o))),(n,m))))),(l,k),(j,i));', '((((o,n),((m,(l,(k,j))),((i,(h,g)),z))),(y,(x,(w,v)))),(u,(t,s)),(r,(q,p)));'],
        [30, True, '(((v,u),(t,(s,(r,(q,p))))),((o,(n,m)),((l,(k,j)),((i,(h,g)),z))),(y,(x,w)));', '((((m,(l,k)),((j,i),(h,g))),(z,y)),(x,w),((v,(u,(t,(s,(r,q))))),(p,(o,n))));'],
        [26, True, '(((q,p),((o,(n,(m,l))),(k,(j,i)))),((h,g),z),((y,x),((w,(v,(u,t))),(s,r))));', '((((j,(i,(h,g))),(z,(y,x))),((w,v),(u,t))),(s,(r,q)),((p,o),(n,(m,(l,k)))));'],
        [20, False, '((((o,(n,m)),((l,k),((j,i),((h,g),z)))),(y,x)),(((w,v),(u,t)),((s,r),(q,p))));', '((((j,i),((h,g),z)),((y,x),(w,(v,(u,(t,(s,r))))))),((q,p),((o,n),(m,(l,k)))));'],
        [30, False, '(((x,w),(v,(u,(t,(s,(r,(q,(p,(o,(n,m)))))))))),((l,k),((j,(i,(h,g))),(z,y))));', '(((m,l),((k,(j,(i,(h,g)))),z)),((y,(x,(w,(v,(u,t))))),((s,r),((q,p),(o,n)))));'],
        [32, True, '((((y,x),(w,v)),((u,(t,(s,r))),(q,(p,o)))),((n,m),(l,(k,j))),((i,(h,g)),z));', '(((m,l),(k,(j,i))),((h,g),z),((y,(x,w)),((v,u),((t,s),(r,(q,(p,(o,n))))))));'],
        [28, True, '(((v,u),((t,(s,(r,(q,p)))),((o,n),((m,l),(k,(j,(i,(h,g)))))))),(z,y),(x,w));', '((((n,m),((l,k),((j,i),((h,g),(z,(y,(x,(w,(v,u))))))))),(t,s)),(r,q),(p,o));'],
        [32, False, '(((r,(q,p)),(o,n)),(((m,(l,k)),(j,i)),(((h,g),(z,y)),((x,w),((v,u),(t,s))))));', '(((y,x),((w,v),(u,(t,(s,r))))),(((q,(p,(o,n))),(m,l)),((k,(j,(i,(h,g)))),z)));'],
        [20, True, '(((w,v),((u,(t,(s,r))),((q,p),((o,(n,(m,l))),((k,j),((i,(h,g)),z)))))),y,x);', '(((w,v),((u,t),(s,(r,q)))),((p,o),((n,(m,l)),(k,j))),((i,(h,g)),(z,(y,x))));'],
        [24, False, '(((x,(w,v)),((u,(t,s)),(r,q))),(((p,o),((n,(m,l)),(k,j))),((i,(h,g)),(z,y))));', '((((i,(h,g)),z),((y,x),(w,v))),((u,(t,s)),((r,(q,(p,(o,(n,m))))),(l,(k,j)))));'],
        [22, False, '((((k,(j,(i,(h,g)))),(z,(y,x))),((w,v),(u,t))),((s,(r,(q,(p,o)))),(n,(m,l))));', '(((w,v),(u,(t,(s,(r,(q,(p,o))))))),(((n,m),((l,(k,(j,i))),((h,g),z))),(y,x)));'],
        [28, True, '(((x,w),((v,u),((t,s),(r,(q,p))))),((o,n),(m,l)),((k,(j,i)),((h,g),(z,y))));', '((((p,o),(n,m)),((l,(k,(j,i))),((h,g),z))),(y,(x,(w,v))),((u,t),(s,(r,q))));'],
        [30, False, '(((q,p),((o,(n,(m,l))),((k,(j,(i,(h,g)))),z))),((y,x),((w,(v,u)),(t,(s,r)))));', '((((m,(l,k)),((j,(i,(h,g))),z)),(y,(x,w))),((v,(u,(t,(s,(r,q))))),(p,(o,n))));'],
        [30, False, '(((y,x),((w,(v,(u,(t,(s,r))))),(q,p))),((o,(n,(m,(l,(k,(j,i)))))),((h,g),z)));', '((((t,(s,(r,q))),((p,(o,(n,(m,l)))),((k,(j,i)),(h,g)))),(z,y)),((x,w),(v,u)));'],
        [20, False, '(((u,(t,s)),(r,(q,(p,(o,(n,(m,(l,(k,j))))))))),(((i,(h,g)),z),(y,(x,(w,v)))));', '(((o,n),(m,(l,(k,j)))),(((i,(h,g)),(z,y)),((x,(w,v)),((u,(t,(s,r))),(q,p)))));'],
        [26, False, '(((t,s),((r,(q,(p,(o,n)))),(m,(l,k)))),(((j,i),((h,g),z)),((y,(x,w)),(v,u))));', '(((r,(q,(p,o))),((n,(m,(l,k))),((j,i),(h,g)))),((z,(y,(x,(w,v)))),(u,(t,s))));'],
        [28, True, '((((r,q),((p,(o,(n,(m,l)))),((k,(j,i)),(h,g)))),(z,(y,(x,w)))),(v,u),(t,s));', '(((x,(w,(v,(u,(t,s))))),(r,(q,(p,o)))),(n,m),((l,k),((j,(i,(h,g))),(z,y))));'],
        [28, False, '(((t,s),((r,(q,p)),((o,n),(m,(l,(k,(j,i))))))),(((h,g),(z,y)),(x,(w,(v,u)))));', '((((h,g),(z,(y,(x,(w,v))))),(u,(t,(s,r)))),((q,(p,(o,(n,m)))),(l,(k,(j,i)))));'],
        [26, True, '((((q,(p,o)),((n,m),((l,(k,(j,i))),(h,g)))),(z,(y,x))),(w,v),(u,(t,(s,r))));', '(((y,x),(w,(v,u))),((t,(s,r)),((q,p),(o,n))),((m,(l,k)),((j,(i,(h,g))),z)));'],
        [28, False, '((((q,(p,(o,n))),((m,(l,k)),((j,(i,(h,g))),z))),(y,x)),((w,(v,(u,t))),(s,r)));', '(((z,(y,x)),(w,v)),(((u,t),((s,(r,(q,p))),((o,n),(m,l)))),((k,(j,i)),(h,g))));'],
        [22, True, '(((x,w),((v,(u,(t,s))),(r,q))),((p,(o,n)),((m,(l,k)),(j,(i,(h,g))))),(z,y));', '((((j,(i,(h,g))),(z,(y,x))),(w,(v,u))),((t,s),((r,q),(p,o))),((n,m),(l,k)));'],
        [26, False, '((((n,(m,l)),(k,j)),(((i,(h,g)),(z,y)),((x,w),((v,u),(t,s))))),((r,q),(p,o)));', '(((v,u),(t,s)),(((r,(q,(p,(o,n)))),((m,(l,k)),(j,i))),((h,g),(z,(y,(x,w))))));'],
        [32, False, '((((n,(m,(l,(k,j)))),((i,(h,g)),z)),(y,x)),((w,v),((u,(t,(s,r))),(q,(p,o)))));', '((((v,u),(t,(s,(r,(q,p))))),((o,(n,(m,(l,k)))),(j,(i,(h,g))))),((z,y),(x,w)));'],
        [20, False, '((((q,(p,(o,n))),(m,l)),((k,(j,(i,(h,g)))),z)),((y,(x,(w,(v,(u,t))))),(s,r)));', '(((w,(v,(u,t))),(s,r)),(((q,p),(o,n)),(((m,l),(k,(j,i))),((h,g),(z,(y,x))))));'],
        [20, True, '(((z,(y,(x,w))),(v,u)),((t,(s,r)),(q,(p,o))),((n,(m,l)),((k,(j,i)),(h,g))));', '((((q,(p,(o,n))),(m,l)),((k,j),(i,(h,g)))),(z,y),((x,w),((v,u),(t,(s,r)))));'],
        [34, False, '(((w,(v,(u,(t,(s,(r,q)))))),(p,o)),(((n,m),(l,(k,j))),((i,(h,g)),(z,(y,x)))));', '(((y,(x,(w,(v,u)))),(t,(s,r))),(((q,(p,(o,(n,(m,(l,k)))))),(j,i)),((h,g),z)));'],
        [26, False, '(((y,x),(w,(v,(u,t)))),(((s,r),((q,(p,o)),(n,(m,l)))),((k,(j,(i,(h,g)))),z)));', '(((s,(r,(q,(p,o)))),(n,m)),(((l,k),((j,i),((h,g),(z,(y,(x,w)))))),(v,(u,t))));'],
        [30, False, '(((v,(u,t)),((s,r),((q,p),((o,(n,(m,(l,k)))),(j,i))))),(((h,g),z),(y,(x,w))));', '(((y,(x,(w,v))),((u,(t,s)),(r,(q,(p,o))))),((n,(m,l)),((k,(j,i)),((h,g),z))));'],
        [26, False, '(((y,x),(w,v)),(((u,t),((s,(r,(q,p))),(o,n))),((m,(l,k)),((j,i),((h,g),z)))));', '((((s,(r,q)),((p,(o,n)),((m,l),(k,(j,i))))),((h,g),z)),((y,(x,w)),(v,(u,t))));'],
        [22, True, '(((w,v),(u,t)),((s,r),((q,p),((o,(n,m)),((l,k),((j,i),(h,g)))))),(z,(y,x)));', '(((z,y),(x,(w,(v,u)))),(t,(s,r)),((q,(p,o)),((n,m),((l,(k,(j,i))),(h,g)))));'],
        [28, False, '(((y,x),(w,(v,(u,t)))),(((s,(r,q)),((p,o),(n,(m,(l,k))))),((j,i),((h,g),z))));', '((((i,(h,g)),(z,(y,x))),((w,(v,u)),(t,s))),((r,q),((p,o),((n,m),(l,(k,j))))));'],
        [26, False, '(((v,(u,(t,s))),(r,(q,p))),(((o,n),((m,(l,(k,j))),((i,(h,g)),(z,y)))),(x,w)));', '(((q,p),((o,n),((m,l),((k,j),((i,(h,g)),z))))),(y,(x,(w,(v,(u,(t,(s,r))))))));'],
        [26, True, '(((t,(s,(r,q))),((p,o),((n,(m,l)),((k,j),((i,(h,g)),z))))),(y,x),(w,(v,u)));', '(((z,y),(x,w)),(v,u),((t,(s,r)),((q,(p,(o,(n,(m,l))))),((k,(j,i)),(h,g)))));'],
        [30, True, '(((w,(v,(u,(t,(s,r))))),(q,p)),((o,(n,m)),((l,k),(j,i))),(((h,g),z),(y,x)));', '((((p,o),(n,(m,(l,(k,(j,(i,(h,g)))))))),(z,(y,x))),(w,(v,u)),((t,s),(r,q)));'],
        [26, True, '((((i,(h,g)),(z,y)),(x,w)),((v,u),((t,(s,r)),(q,p))),((o,n),(m,(l,(k,j)))));', '(((l,k),((j,i),((h,g),(z,y)))),(x,w),((v,u),((t,s),((r,(q,(p,o))),(n,m)))));'],
        [26, False, '(((x,w),((v,(u,(t,s))),((r,(q,p)),((o,(n,(m,(l,k)))),((j,i),(h,g)))))),(z,y));', '(((p,(o,(n,m))),(l,k)),(((j,i),(h,g)),((z,y),((x,(w,v)),((u,t),(s,(r,q)))))));'],
        [24, True, '(((x,w),((v,(u,t)),(s,r))),((q,p),(o,(n,(m,(l,k))))),((j,i),((h,g),(z,y))));', '(((h,g),(z,y)),(x,(w,(v,u))),((t,(s,r)),(q,(p,(o,(n,(m,(l,(k,(j,i))))))))));'],
        [24, True, '(((y,x),(w,v)),((u,t),((s,r),((q,p),((o,n),(m,(l,k)))))),((j,(i,(h,g))),z));', '((((r,(q,p)),(o,(n,(m,(l,(k,(j,(i,(h,g))))))))),(z,y)),(x,(w,v)),(u,(t,s)));'],
        [28, False, '(((y,(x,(w,v))),((u,t),((s,(r,q)),((p,(o,n)),((m,l),(k,(j,i))))))),((h,g),z));', '(((v,u),(t,(s,(r,(q,(p,(o,n))))))),(((m,l),((k,j),((i,(h,g)),z))),(y,(x,w))));'],
        [26, True, '((((h,g),z),((y,x),((w,(v,u)),((t,(s,(r,q))),(p,(o,n)))))),(m,(l,k)),(j,i));', '((z,y),(x,(w,(v,(u,t)))),((s,r),((q,p),((o,n),((m,(l,k)),(j,(i,(h,g))))))));'],
        [24, True, '(((u,t),(s,r)),((q,p),((o,n),((m,(l,(k,(j,(i,(h,g)))))),z))),(y,(x,(w,v))));', '((((j,(i,(h,g))),z),(y,x)),(w,(v,(u,t))),((s,(r,(q,p))),((o,(n,m)),(l,k))));'],
        [30, True, '(((t,(s,r)),((q,p),((o,n),(m,(l,(k,j)))))),((i,(h,g)),z),((y,x),(w,(v,u))));', '((((w,(v,(u,t))),(s,(r,q))),((p,(o,(n,m))),(l,k))),((j,i),(h,g)),(z,(y,x)));'],
        [30, False, '((((x,(w,v)),(u,t)),((s,(r,q)),(p,o))),(((n,m),((l,k),((j,i),(h,g)))),(z,y)));', '((r,q),((p,(o,n)),((m,(l,(k,(j,i)))),((h,g),(z,(y,(x,(w,(v,(u,(t,s)))))))))));'],
        [28, True, '((((k,j),((i,(h,g)),(z,(y,x)))),(w,v)),(u,t),((s,(r,q)),(p,(o,(n,(m,l))))));', '(((z,y),(x,w)),(v,(u,(t,(s,(r,q))))),((p,o),((n,(m,(l,(k,(j,i))))),(h,g))));'],
        [18, True, '(((t,s),((r,(q,(p,o))),(n,m))),((l,(k,j)),((i,(h,g)),(z,y))),((x,w),(v,u)));', '((((l,k),(j,i)),(((h,g),(z,y)),(x,w))),((v,u),(t,s)),((r,q),((p,o),(n,m))));'],
        [26, True, '(((h,g),z),(y,(x,w)),((v,(u,(t,s))),((r,(q,p)),((o,(n,(m,l))),(k,(j,i))))));', '(((s,r),(q,p)),((o,n),(m,l)),(((k,j),((i,(h,g)),(z,(y,x)))),(w,(v,(u,t)))));'],
        [30, True, '(((x,w),((v,(u,(t,(s,(r,(q,(p,(o,n)))))))),((m,(l,k)),((j,i),(h,g))))),z,y);', '((((h,g),z),(y,x)),((w,v),((u,(t,s)),(r,q))),((p,(o,(n,(m,l)))),(k,(j,i))));'],
        [30, False, '(((v,(u,(t,(s,(r,q))))),((p,(o,(n,m))),((l,(k,(j,i))),(h,g)))),((z,y),(x,w)));', '(((v,u),((t,(s,(r,(q,(p,o))))),(n,(m,(l,(k,j)))))),((i,(h,g)),(z,(y,(x,w)))));'],
        [22, True, '(((z,y),((x,(w,v)),((u,(t,(s,r))),(q,(p,o))))),(n,m),((l,k),(j,(i,(h,g)))));', '(((r,q),(p,(o,(n,m)))),((l,(k,(j,(i,(h,g))))),(z,y)),((x,w),(v,(u,(t,s)))));'],
        [30, True, '(((x,w),((v,(u,(t,(s,r)))),(q,p))),((o,n),(m,l)),((k,j),((i,(h,g)),(z,y))));', '((((p,o),((n,(m,(l,k))),((j,i),(h,g)))),((z,y),(x,(w,v)))),(u,t),(s,(r,q)));'],
        [32, False, '(((r,(q,p)),(o,(n,m))),(((l,(k,(j,i))),(h,g)),((z,(y,(x,(w,(v,u))))),(t,s))));', '((((j,(i,(h,g))),(z,y)),(x,(w,(v,(u,t))))),(((s,r),(q,(p,o))),((n,m),(l,k))));'],
        [30, False, '((((q,p),((o,(n,(m,(l,k)))),((j,(i,(h,g))),(z,y)))),(x,w)),((v,u),(t,(s,r))));', '((((o,(n,m)),((l,(k,(j,i))),((h,g),z))),(y,x)),((w,v),((u,t),((s,r),(q,p)))));'],
        [28, False, '((((s,r),((q,(p,o)),(n,(m,l)))),((k,(j,i)),(h,g))),((z,(y,x)),(w,(v,(u,t)))));', '(((m,l),(k,j)),(((i,(h,g)),z),((y,x),((w,(v,(u,(t,(s,r))))),((q,p),(o,n))))));'],
        [20, True, '((((z,y),(x,(w,(v,u)))),((t,s),(r,q))),((p,o),(n,(m,l))),((k,(j,i)),(h,g)));', '(((j,i),(h,g)),(z,(y,x)),((w,(v,u)),((t,(s,(r,q))),((p,o),((n,m),(l,k))))));'],
        [20, False, '(((v,u),((t,s),(r,q))),(((p,o),(n,(m,l))),(((k,(j,i)),((h,g),z)),(y,(x,w)))));', '((((s,(r,q)),(p,o)),(((n,(m,l)),(k,(j,i))),((h,g),z))),((y,x),((w,v),(u,t))));'],
        [28, True, '((z,y),(x,w),((v,u),((t,(s,(r,q))),((p,(o,(n,m))),(l,(k,(j,(i,(h,g)))))))));', '((((r,q),((p,o),((n,m),((l,k),(j,i))))),((h,g),(z,(y,x)))),(w,v),(u,(t,s)));'],
        [24, False, '((((k,(j,(i,(h,g)))),(z,y)),(x,(w,v))),(((u,t),(s,(r,q))),((p,o),(n,(m,l)))));', '(((w,v),(u,(t,s))),(((r,(q,(p,o))),((n,m),(l,(k,(j,(i,(h,g))))))),(z,(y,x))));'],
        [24, True, '((((n,m),((l,(k,j)),(i,(h,g)))),(z,y)),(x,(w,v)),((u,(t,(s,(r,q)))),(p,o)));', '(((r,q),(p,o)),((n,(m,l)),((k,j),((i,(h,g)),z))),((y,x),(w,(v,(u,(t,s))))));']]

        # test RF exceptions
        t1 = Tree('(a,b,(c,d,e));')
        t2 = Tree('((a,b),(c,d,e));')
        # testing unrooted trees
        self.assertRaises(TreeError, t1.robinson_foulds, t2=t2)

        # expand polytomies and unrooted trees
        self.assertRaises(TreeError, t1.robinson_foulds, t2=t2,
                          unrooted_trees=True, expand_polytomies=True)

        # usisng expand_polytomies and correct_by_size at the same time
        self.assertRaises(TreeError, t1.robinson_foulds, t2=t1,
                          unrooted_trees=True, expand_polytomies=True,
                          correct_by_polytomy_size=True)

        # correct by size when polytomies in both sides
        self.assertRaises(TreeError, t1.robinson_foulds, t2=t1,
                          unrooted_trees=True, correct_by_polytomy_size=True)

        # polytomy larger than deafult limit
        self.assertRaises(TreeError, t2.robinson_foulds, t2=Tree('(a, (b,c,d,e,f,g,h));'),
                          expand_polytomies=True)

        # duplicated items
        t3 = Tree('(a, (b, (c, c)));')
        self.assertRaises(TreeError, t3.robinson_foulds, t2=t2)
        self.assertRaises(TreeError, t2.robinson_foulds, t2=t3)



        # test RF using a knonw set of results
        for RF, unrooted, nw1, nw2 in samples:
            t1 = Tree(nw1)
            t2 = Tree(nw2)
            rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted)
            real_max = (20*2) - 4 if not unrooted else (20*2) - 6

            self.assertEqual(len(names), 20)
            self.assertEqual(rf_max, real_max)
            self.assertEqual(rf, RF)

            comp = t1.compare(t2, unrooted=unrooted)
            self.assertEqual(20, comp['effective_tree_size'])
            self.assertEqual(rf_max, comp['max_rf'])
            self.assertEqual(RF, comp['rf'])
            # Let's insert some random nodes, that should be ignored
            for target in random.sample([n for n in t2.get_descendants() if not n.is_leaf()], 5):
                target.populate(5)
            comp = t1.compare(t2, unrooted=unrooted)
            self.assertEqual(20, comp['effective_tree_size'])
            self.assertEqual(rf_max, comp['max_rf'])
            self.assertEqual(RF, comp['rf'])

        # test treeko functionality
        t = PhyloTree('((((A,B),C), ((A,B),C)), (((A,B),C), ((A,B),C)));')
        ref = Tree('((A,B),C);')
        comp = t.compare(ref, has_duplications=True)
        #from pprint import pprint
        #pprint(comp)
        self.assertEqual(comp['effective_tree_size'], 3)
        self.assertEqual(comp['treeko_dist'], 0.0)
        self.assertEqual(comp['norm_rf'], 0.0)
        self.assertEqual(comp['rf'], 0.0)
        self.assertEqual(comp['max_rf'], 2)
        self.assertEqual(comp['source_subtrees'], 4)

        # test polytomy corrections

        ref2 = Tree("((a:1, (b:1, c:1, d:1):1):1, (e:1, f:1, g:1):1);")
        gtree = Tree("((a:1, (b:1, (c:1, d:1):1):1), (e:1, (f:1, g:1):1):1);")

        # Basic polytomy
        rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref2)
        self.assertEqual(rf, 2)
        rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref2, expand_polytomies=True)
        self.assertEqual(rf, 0)


        # nested polytomies
        gtree = Tree('((g, h), (a, (b, (c, (d,( e, f))))));')
        ref3 = Tree('((a, b, c, (d, e, f)), (g, h));')
        ref4 = Tree('((a, b, c, d, e, f), (g, h));')
        ref5 = Tree('((a, b, (c, d, (e, f))), (g, h));')

        rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref3)
        self.assertEqual(rf, 3)
        rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref3, expand_polytomies=True)
        self.assertEqual(rf, 0)

        rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref4)
        self.assertEqual(rf, 4)
        rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref4, expand_polytomies=True,
                                                                  polytomy_size_limit=6)
        self.assertEqual(rf, 0)

        rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref5)
        self.assertEqual(rf, 2)
        rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref5, expand_polytomies=True)
        self.assertEqual(rf, 0)

        # two side polytomies
        t1 = Tree("((a:1, (b:1, c:1, d:1):1):1, (e:1, f:1, g:1):1);")
        t2 = Tree("((a:1, (b:1, c:1, d:1):1), (e:1, (f:1, g:1):1):1);")
        rf, max_rf, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, expand_polytomies=True)
        self.assertEqual(rf, 0)


        # test auto pruned tree topology
        for RF, unrooted, nw1, nw2 in samples:
            # Add fake tips in the newick
            for x in "clanger":
                nw1 = nw1.replace(x, "(%s,%s1)" %(x, x) )
                nw2 = nw2.replace(x, "(%s,%s2)" %(x, x) )
            t1 = Tree(nw1)
            t2 = Tree(nw2)
            rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted)
            self.assertEqual(len(names), 20)
            real_max = (20*2) - 4 if not unrooted else (20*2) - 6
            self.assertEqual(rf_max, real_max)
            self.assertEqual(rf, RF)

        #print 'Testing RF with branch support thresholds...'
        # test discarding lowly supported branches
        for RF, unrooted, nw1, nw2 in samples:
            # Add fake internal nodes with low support
            for x in "jlnqr":
                nw1 = nw1.replace(x, "(%s,(%s1, %s11)0.6)" %(x, x, x) )
                nw2 = nw2.replace(x, "(%s,(%s1, %s11)0.5)" %(x, x, x) )
            t1 = Tree(nw1)
            t2 = Tree(nw2)
            rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted,
                                                                   min_support_t1 = 0.1, min_support_t2 = 0.1)
            self.assertEqual(len(names), 30)
            real_max = (30*2) - 4 if not unrooted else (30*2) - 6
            self.assertEqual(rf_max, real_max)
            self.assertEqual(rf, RF)

            rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted,
                                                                   min_support_t1 = 0.0, min_support_t2 = 0.51)
            self.assertEqual(len(names), 30)
            real_max = (30*2) - 4 - 5 if not unrooted else (30*2) - 6 -5 # -5 to discount low support branches
            self.assertEqual(rf_max, real_max)
            self.assertEqual(rf, RF)

            rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted,
                                                                   min_support_t1 = 0.61, min_support_t2 = 0.0)
            self.assertEqual(len(names), 30)
            real_max = (30*2) - 4 - 5 if not unrooted else (30*2) - 6 -5 # -5 to discount low support branches
            self.assertEqual(rf_max, real_max)
            self.assertEqual(rf, RF)


            rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted,
                                                                   min_support_t1 = 0.61, min_support_t2 = 0.51)
            self.assertEqual(len(names), 30)
            real_max = (30*2) - 4 - 10 if not unrooted else (30*2) - 6 -10 # -10 to discount low support branches
            self.assertEqual(rf_max, real_max)
            self.assertEqual(rf, RF)





    def test_monophyly(self):
        #print 'Testing monophyly checks...'
        t =  Tree("((((((a, e), i), o),h), u), ((f, g), j));")
        is_mono, monotype, extra  = t.check_monophyly(values=["a", "e", "i", "o", "u"], target_attr="name")
        self.assertEqual(is_mono, False)
        self.assertEqual(monotype, "polyphyletic")
        is_mono, monotype, extra= t.check_monophyly(values=["a", "e", "i", "o"], target_attr="name")
        self.assertEqual(is_mono, True)
        self.assertEqual(monotype, "monophyletic")
        is_mono, monotype, extra =  t.check_monophyly(values=["i", "o"], target_attr="name")
        self.assertEqual(is_mono, False)
        self.assertEqual(monotype, "paraphyletic")

        # Test examples
        #print 'Testing monophyly check with unrooted trees'
        t = PhyloTree('(aaa1, (aaa3, (aaa4, (bbb1, bbb2))));')
        is_mono, montype, extra = t.check_monophyly(values=set(['aaa']), target_attr='species', unrooted=True)
        self.assertEqual(is_mono, True)
        self.assertEqual(extra, set())

        t = PhyloTree('(aaa1, (bbb3, (aaa4, (bbb1, bbb2))));')
        is_mono, montype, extra = t.check_monophyly(values=set(['aaa']), target_attr='species', unrooted=True)
        self.assertEqual(is_mono, False)
        self.assertEqual(extra, set([t&'bbb3']))

        t = PhyloTree('(aaa1, (aaa3, (aaa4, (bbb1, bbb2))));')
        is_mono, montype, extra = t.check_monophyly(values=set(['bbb']), target_attr='species', unrooted=True)
        self.assertEqual(is_mono, True)
        self.assertEqual(extra, set())

        t = PhyloTree('(aaa1, (aaa3, (aaa4, (bbb1, ccc2))));')
        is_mono, montype, extra = t.check_monophyly(values=set(['bbb', 'ccc']), target_attr='species', unrooted=True)
        self.assertEqual(is_mono, True)
        self.assertEqual(extra, set())

        t = PhyloTree('(aaa1, (aaa3, (bbb4, (bbb1, bbb2))));')
        is_mono, montype, extra = t.check_monophyly(values=set(['bbb4', 'bbb2']), target_attr='name', unrooted=True)
        self.assertEqual(is_mono, False)
        self.assertEqual(extra, set([t&'bbb1']))

        t = PhyloTree('(aaa1, (aaa3, (bbb4, (bbb1, bbb2))));')
        is_mono, montype, extra = t.check_monophyly(values=set(['bbb1', 'bbb2']), target_attr='name', unrooted=True)
        self.assertEqual(is_mono, True)
        self.assertEqual(extra, set())

        t = PhyloTree('(aaa1, aaa3, (aaa4, (bbb1, bbb2)));')
        is_mono, montype, extra = t.check_monophyly(values=set(['aaa']), target_attr='species', unrooted=True)
        self.assertEqual(is_mono, True)
        self.assertEqual(extra, set())

        t = PhyloTree('(aaa1, bbb3, (aaa4, (bbb1, bbb2)));')
        is_mono, montype, extra = t.check_monophyly(values=set(['aaa']), target_attr='species', unrooted=True)
        self.assertEqual(is_mono, False)
        self.assertEqual(extra, set([t&'bbb3']))

        #print 'Check monophyly randomization test'
        t = PhyloTree()
        t.populate(100)
        ancestor = t.get_common_ancestor(['aaaaaaaaaa', 'aaaaaaaaab', 'aaaaaaaaac'])
        all_nodes = t.get_descendants()
        # I test every possible node as root for the tree. The content of ancestor
        # should allways be detected as monophyletic
        results = set()
        for x in all_nodes:
            mono, part, extra = t.check_monophyly(values=set(ancestor.get_leaf_names()), target_attr='name', unrooted=True)
            results.add(mono)
            t.set_outgroup(x)
        self.assertEqual(list(results), [True])

        #print 'Testing get_monophyly'
        t =  Tree("((((((4, e), i)M1, o),h), u), ((3, 4), (i, june))M2);", format=1)
        # we annotate the tree using external data
        colors = {"a":"red", "e":"green", "i":"yellow",
                  "o":"black", "u":"purple", "4":"green",
                  "3":"yellow", "1":"white", "5":"red",
                  "june":"yellow"}
        for leaf in t:
            leaf.add_features(color=colors.get(leaf.name, "none"))
        green_yellow_nodes = set([t&"M1", t&"M2"])
        mono_nodes = t.get_monophyletic(values=["green", "yellow"], target_attr="color")
        self.assertEqual(set(mono_nodes), green_yellow_nodes)


    def test_copy(self):
        t = Tree("((A, B)Internal_1:0.7, (C, D)Internal_2:0.5)root:1.3;", format=1)
        # we add a custom annotation to the node named A
        (t & "A").add_features(label="custom Value")
        # we add a complex feature to the A node, consisting of a list of lists
        (t & "A").add_features(complex=[[0,1], [2,3], [1,11], [1,0]])


        t_nw  = t.copy("newick")
        t_nwx = t.copy("newick-extended")
        t_pkl = t.copy("cpickle")
        (t & "A").testfn = lambda: "YES"
        t_deep = t.copy("deepcopy")

        self.assertEqual((t_nw & "root").name, "root")
        self.assertEqual((t_nwx & "A").label, "custom Value")
        self.assertEqual((t_pkl & "A").complex[0], [0,1])
        self.assertEqual((t_deep & "A").testfn(), "YES")


    def test_cophenetic_matrix(self):
        t = Tree(nw_full)
        dists, leaves = t.cophenetic_matrix()
        actualdists = [
            [0, 2.3662779999999994, 2.350554999999999, 2.7002369999999996, 3.527812, 3.305472, 2.424086, 2.424086,
             2.432288, 2.483421, 2.3355079999999995, 2.3355079999999995, 2.389350999999999, 2.3812519999999995,
             2.404005999999999, 2.3945459999999996, 2.4035289999999994, 2.3689599999999995, 2.4048339999999997,
             2.6487609999999995],
            [2.3662779999999994, 0, 0.079009, 1.122461, 2.38897, 2.16663, 0.47755000000000003, 0.47755000000000003,
             0.4857520000000001, 0.5368850000000001, 0.320202, 0.32020200000000004, 0.133729, 0.12563,
             0.14838400000000002, 0.230406, 0.168047, 0.113338, 0.16935199999999997, 0.633455],
            [2.350554999999999, 0.079009, 0, 1.106738, 2.373247, 2.150907, 0.461827, 0.461827, 0.47002900000000003,
             0.521162, 0.304479, 0.30447900000000006, 0.11800599999999999, 0.10990699999999998, 0.132661, 0.214683,
             0.152324, 0.09761499999999998, 0.153629, 0.617732],
            [2.7002369999999996, 1.122461, 1.106738, 0, 2.7229289999999997, 2.5005889999999997, 1.180269, 1.180269,
             1.188471, 1.239604, 1.091691, 1.091691, 1.145534, 1.137435, 1.160189, 1.1507290000000001, 1.159712,
             1.125143, 1.161017, 1.404944],
            [3.527812, 2.38897, 2.373247, 2.7229289999999997, 0, 2.6926, 2.446778, 2.446778, 2.45498, 2.506113,
             2.3581999999999996, 2.3581999999999996, 2.412043, 2.403944, 2.426698, 2.4172379999999998,
             2.4262209999999995, 2.391652, 2.427526, 2.6714529999999996],
            [3.305472, 2.16663, 2.150907, 2.5005889999999997, 2.6926, 0, 2.224438, 2.224438, 2.23264, 2.283773, 2.13586,
             2.13586, 2.189703, 2.181604, 2.204358, 2.194898, 2.2038809999999995, 2.169312, 2.205186, 2.449113],
            [2.424086, 0.47755000000000003, 0.461827, 1.180269, 2.446778, 2.224438, 0, 0.0, 0.01366,
             0.30963300000000005, 0.44678, 0.44677999999999995, 0.5006229999999999, 0.49252399999999996, 0.515278,
             0.505818, 0.5148010000000001, 0.480232, 0.5161060000000001, 0.7600329999999998],
            [2.424086, 0.47755000000000003, 0.461827, 1.180269, 2.446778, 2.224438, 0.0, 0, 0.01366,
             0.30963300000000005, 0.44678, 0.44677999999999995, 0.5006229999999999, 0.49252399999999996, 0.515278,
             0.505818, 0.5148010000000001, 0.480232, 0.5161060000000001, 0.7600329999999998],
            [2.432288, 0.4857520000000001, 0.47002900000000003, 1.188471, 2.45498, 2.23264, 0.01366, 0.01366, 0,
             0.317835, 0.45498200000000005, 0.454982, 0.508825, 0.500726, 0.5234800000000001, 0.51402, 0.523003,
             0.48843400000000003, 0.524308, 0.7682349999999999],
            [2.483421, 0.5368850000000001, 0.521162, 1.239604, 2.506113, 2.283773, 0.30963300000000005,
             0.30963300000000005, 0.317835, 0, 0.506115, 0.506115, 0.559958, 0.551859, 0.574613, 0.565153, 0.574136,
             0.539567, 0.5754410000000001, 0.8193679999999999],
            [2.3355079999999995, 0.320202, 0.304479, 1.091691, 2.3581999999999996, 2.13586, 0.44678, 0.44678,
             0.45498200000000005, 0.506115, 0, 0.0, 0.343275, 0.33517600000000003, 0.35793, 0.34847,
             0.35745299999999997, 0.322884, 0.35875799999999997, 0.531709],
            [2.3355079999999995, 0.32020200000000004, 0.30447900000000006, 1.091691, 2.3581999999999996, 2.13586,
             0.44677999999999995, 0.44677999999999995, 0.454982, 0.506115, 0.0, 0, 0.34327500000000005,
             0.33517600000000003, 0.35793, 0.34847, 0.357453, 0.32288400000000006, 0.358758, 0.531709],
            [2.389350999999999, 0.133729, 0.11800599999999999, 1.145534, 2.412043, 2.189703, 0.5006229999999999,
             0.5006229999999999, 0.508825, 0.559958, 0.343275, 0.34327500000000005, 0, 0.013558999999999998, 0.021967,
             0.25347900000000007, 0.19112, 0.031257, 0.192425, 0.656528],
            [2.3812519999999995, 0.12563, 0.10990699999999998, 1.137435, 2.403944, 2.181604, 0.49252399999999996,
             0.49252399999999996, 0.500726, 0.551859, 0.33517600000000003, 0.33517600000000003, 0.013558999999999998, 0,
             0.028214, 0.24538000000000004, 0.183021, 0.023157999999999998, 0.184326, 0.648429],
            [2.404005999999999, 0.14838400000000002, 0.132661, 1.160189, 2.426698, 2.204358, 0.515278, 0.515278,
             0.5234800000000001, 0.574613, 0.35793, 0.35793, 0.021967, 0.028214, 0, 0.26813400000000004,
             0.20577499999999999, 0.045912, 0.20708, 0.6711830000000001],
            [2.3945459999999996, 0.230406, 0.214683, 1.1507290000000001, 2.4172379999999998, 2.194898, 0.505818,
             0.505818, 0.51402, 0.565153, 0.34847, 0.34847, 0.25347900000000007, 0.24538000000000004,
             0.26813400000000004, 0, 0.267657, 0.233088, 0.268962, 0.661723],
            [2.4035289999999994, 0.168047, 0.152324, 1.159712, 2.4262209999999995, 2.2038809999999995,
             0.5148010000000001, 0.5148010000000001, 0.523003, 0.574136, 0.35745299999999997, 0.357453, 0.19112,
             0.183021, 0.20577499999999999, 0.267657, 0, 0.170729, 0.057269, 0.670706],
            [2.3689599999999995, 0.113338, 0.09761499999999998, 1.125143, 2.391652, 2.169312, 0.480232, 0.480232,
             0.48843400000000003, 0.539567, 0.322884, 0.32288400000000006, 0.031257, 0.023157999999999998, 0.045912,
             0.233088, 0.170729, 0, 0.17203399999999996, 0.636137],
            [2.4048339999999997, 0.16935199999999997, 0.153629, 1.161017, 2.427526, 2.205186, 0.5161060000000001,
             0.5161060000000001, 0.524308, 0.5754410000000001, 0.35875799999999997, 0.358758, 0.192425, 0.184326,
             0.20708, 0.268962, 0.057269, 0.17203399999999996, 0, 0.672011],
            [2.6487609999999995, 0.633455, 0.617732, 1.404944, 2.6714529999999996, 2.449113, 0.7600329999999998,
             0.7600329999999998, 0.7682349999999999, 0.8193679999999999, 0.531709, 0.531709, 0.656528, 0.648429,
             0.6711830000000001, 0.661723, 0.670706, 0.636137, 0.672011, 0]
        ]

        actualleaves = ['Aga0007658', 'Bta0018700', 'Cfa0016700', 'Cin0011239', 'Ddi0002240', 'Dme0014628',
                        'Dre0008390', 'Dre0008391', 'Dre0008392', 'Fru0004507', 'Gga0000981', 'Gga0000982',
                        'Hsa0000001', 'Hsa0010711', 'Hsa0010730', 'Mdo0014718', 'Mms0024821', 'Ptr0000001',
                        'Rno0030248', 'Xtr0044988']

        for i in range(len(actualdists)):
            for j in range(len(actualdists[i])):
                self.assertAlmostEqual(actualdists[i][j], dists[i][j], places=4)
        self.assertEqual(actualleaves, leaves)


    # def test_traversing_speed(self):
    #     return
    #     for x in xrange(10):
    #         t = Tree()
    #         t.populate(100000)

    #         leaves = t.get_leaves()
    #         sample = random.sample(leaves, 100)

    #         t1 = time.time()
    #         a = t.get_common_ancestor_OLD(sample)
    #         t2 = time.time() - t1
    #         print "OLD get common", t2

    #         t1 = time.time()
    #         b = t.get_common_ancestor(sample)
    #         t2 = time.time() - t1
    #         print "NEW get common", t2

    #         self.assertEqual(a, b)


    #         t1 = time.time()
    #         [n for n in t._iter_descendants_postorder_OLD()]
    #         t2 = time.time() - t1
    #         print "OLD postorder", t2

    #         t1 = time.time()
    #         [n for n in t._iter_descendants_postorder()]
    #         t2 = time.time() - t1
    #         print "NEW postorder", t2

if __name__ == '__main__':
    unittest.main()