# Copyright (C) 2009 by Eric Talevich (eric.talevich@gmail.com)
# This code is part of the Biopython distribution and governed by its
# license. Please see the LICENSE file that should have been included
# as part of this package.

"""Unit tests for the Bio.Phylo module."""

import os
import tempfile
import unittest
from io import StringIO

from Bio import Phylo
from Bio.Phylo import PhyloXML

# Example Newick and Nexus files
EX_NEWICK = "Nexus/int_node_labels.nwk"
EX_NEWICK2 = "Nexus/test.new"
EX_NEXUS = "Nexus/test_Nexus_input.nex"
EX_NEXUS2 = "Nexus/bats.nex"
EX_NEWICK_BOM = "Nexus/ByteOrderMarkFile.nwk"

# Example PhyloXML files
EX_APAF = "PhyloXML/apaf.xml"
EX_BCL2 = "PhyloXML/bcl_2.xml"
EX_DIST = "PhyloXML/distribution.xml"
EX_PHYLO = "PhyloXML/phyloxml_examples.xml"


class IOTests(unittest.TestCase):
    """Tests for parsing and writing the supported formats."""

    def test_newick_read_single1(self):
        """Read first Newick file with one tree."""
        tree = Phylo.read(EX_NEWICK, "newick")
        self.assertEqual(len(tree.get_terminals()), 28)

    def test_newick_read_single2(self):
        """Read second Newick file with one tree."""
        tree = Phylo.read(EX_NEWICK2, "newick")
        self.assertEqual(len(tree.get_terminals()), 33)
        self.assertEqual(tree.find_any("Homo sapiens").comment, "modern human")
        self.assertEqual(
            tree.find_any("Equus caballus").comment,
            "wild horse; also 'Equus ferus caballus'",
        )
        self.assertEqual(tree.root.confidence, 80)
        tree = Phylo.read(EX_NEWICK2, "newick", comments_are_confidence=True)
        self.assertEqual(tree.root.confidence, 100)

    def test_newick_read_single3(self):
        """Read Nexus file with one tree."""
        tree = Phylo.read(EX_NEXUS2, "nexus")
        self.assertEqual(len(tree.get_terminals()), 658)

    def test_unicode_exception(self):
        """Read a Newick file with a unicode byte order mark (BOM)."""
        with open(EX_NEWICK_BOM, encoding="utf-8") as handle:
            tree = Phylo.read(handle, "newick")
        self.assertEqual(len(tree.get_terminals()), 3)

    def test_newick_read_multiple(self):
        """Parse a Nexus file with multiple trees."""
        trees = list(Phylo.parse(EX_NEXUS, "nexus"))
        self.assertEqual(len(trees), 3)
        for tree in trees:
            self.assertEqual(len(tree.get_terminals()), 9)

    def test_newick_write(self):
        """Parse a Nexus file with multiple trees."""
        # Tree with internal node labels
        mem_file = StringIO()
        tree = Phylo.read(StringIO("(A,B,(C,D)E)F;"), "newick")
        Phylo.write(tree, mem_file, "newick")
        mem_file.seek(0)
        tree2 = Phylo.read(mem_file, "newick")
        # Sanity check
        self.assertEqual(tree2.count_terminals(), 4)
        # Check internal node labels were retained
        internal_names = {c.name for c in tree2.get_nonterminals() if c is not None}
        self.assertEqual(internal_names, {"E", "F"})

    def test_newick_read_scinot(self):
        """Parse Newick branch lengths in scientific notation."""
        tree = Phylo.read(StringIO("(foo:1e-1,bar:0.1)"), "newick")
        clade_a = tree.clade[0]
        self.assertEqual(clade_a.name, "foo")
        self.assertAlmostEqual(clade_a.branch_length, 0.1)

    def test_phylo_read_extra(self):
        """Additional tests to check correct parsing."""
        tree = Phylo.read(StringIO("(A:1, B:-2, (C:3, D:4):-2)"), "newick")
        self.assertEqual(tree.distance("A"), 1)
        self.assertEqual(tree.distance("B"), -2)
        self.assertEqual(tree.distance("C"), 1)
        self.assertEqual(tree.distance("D"), 2)

        tree = Phylo.read(StringIO("((A:1, B:-2):-5, (C:3, D:4):-2)"), "newick")
        self.assertEqual(tree.distance("A"), -4)
        self.assertEqual(tree.distance("B"), -7)
        self.assertEqual(tree.distance("C"), 1)
        self.assertEqual(tree.distance("D"), 2)

        tree = Phylo.read(StringIO("((:1, B:-2):-5, (C:3, D:4):-2)"), "newick")
        distances = {-4.0: 1, -7.0: 1, 1: 1, 2: 1}
        for x in tree.get_terminals():
            entry = int(tree.distance(x))
            distances[entry] -= distances[entry]
            self.assertEqual(distances[entry], 0)

        tree = Phylo.read(StringIO("((:\n1\n,\n B:-2):-5, (C:3, D:4):-2);"), "newick")
        distances = {-4.0: 1, -7.0: 1, 1: 1, 2: 1}
        for x in tree.get_terminals():
            entry = int(tree.distance(x))
            distances[entry] -= distances[entry]
            self.assertEqual(distances[entry], 0)

    def test_format_branch_length(self):
        """Custom format string for Newick branch length serialization."""
        tree = Phylo.read(StringIO("A:0.1;"), "newick")
        mem_file = StringIO()
        Phylo.write(tree, mem_file, "newick", format_branch_length="%.0e")
        value = mem_file.getvalue().strip()
        self.assertTrue(value.startswith("A:"))
        self.assertTrue(value.endswith(";"))
        self.assertEqual(value[2:-1], "%.0e" % 0.1)

    def test_newick_writer_preserves_small_branch_lengths(self):
        """Small nonzero branch lengths should not be rounded to zero."""
        tree = Phylo.read(StringIO("(A:0.000001,B:0.000002);"), "newick")

        mem_file = StringIO()
        Phylo.write(tree, mem_file, "newick")

        newick = mem_file.getvalue()
        self.assertNotIn(":0.00000", newick)
        self.assertIn(":1e-06", newick)
        self.assertIn(":2e-06", newick)

    def test_convert(self):
        """Convert a tree between all supported formats."""
        mem_file_1 = StringIO()
        mem_file_2 = StringIO()
        mem_file_3 = StringIO()
        Phylo.convert(EX_NEWICK, "newick", mem_file_1, "nexus")
        mem_file_1.seek(0)
        Phylo.convert(mem_file_1, "nexus", mem_file_2, "phyloxml")
        mem_file_2.seek(0)
        Phylo.convert(mem_file_2, "phyloxml", mem_file_3, "newick")
        mem_file_3.seek(0)
        tree = Phylo.read(mem_file_3, "newick")
        self.assertEqual(len(tree.get_terminals()), 28)

    def test_convert_phyloxml_binary(self):
        """Try writing phyloxml to a binary handle; fail on Py3."""
        trees = Phylo.parse("PhyloXML/phyloxml_examples.xml", "phyloxml")
        with tempfile.NamedTemporaryFile(mode="wb") as out_handle:
            self.assertRaises(TypeError, Phylo.write, trees, out_handle, "phyloxml")

    def test_convert_phyloxml_text(self):
        """Write phyloxml to a text handle."""
        trees = Phylo.parse("PhyloXML/phyloxml_examples.xml", "phyloxml")
        with tempfile.NamedTemporaryFile(mode="w") as out_handle:
            count = Phylo.write(trees, out_handle, "phyloxml")
        self.assertEqual(14, count)

    def test_convert_phyloxml_filename(self):
        """Write phyloxml to a given filename."""
        trees = Phylo.parse("PhyloXML/phyloxml_examples.xml", "phyloxml")
        out_handle = tempfile.NamedTemporaryFile(mode="w", delete=False)
        out_handle.close()
        tmp_filename = out_handle.name
        try:
            count = Phylo.write(trees, tmp_filename, "phyloxml")
        finally:
            os.remove(tmp_filename)
        self.assertEqual(14, count)

    def test_convert_phyloxml_to_newick_branch_length_only(self):
        """Write phyloxml with bootstrap values to newick format using branch_length_only=True"""
        trees = Phylo.parse(EX_APAF, "phyloxml")
        out_handle = tempfile.NamedTemporaryFile(mode="w", delete=False)
        out_handle.close()
        tmp_filename = out_handle.name
        try:
            Phylo.write(trees, tmp_filename, "newick", branch_length_only=True)
        finally:
            os.remove(tmp_filename)

    def test_int_labels(self):
        """Read newick formatted tree with numeric labels."""
        tree = Phylo.read(
            StringIO("(((0:0.1,1:0.1)0.99:0.1,2:0.1)0.98:0.0);"), "newick"
        )
        self.assertEqual({leaf.name for leaf in tree.get_terminals()}, {"0", "1", "2"})

    def test_newick_escaped_quote_parse(self):
        """Parse a newick tree with an escaped quote in a label."""
        newick_str = "('Node''Name':0.00000)Root:0.00000;"
        tree = Phylo.read(StringIO(newick_str), "newick")
        self.assertEqual(tree.get_terminals()[0].name, "Node'Name")

    def test_newick_escaped_quote_write(self):
        """Write a newick tree with an escaped quote in a label."""
        tree = Phylo.BaseTree.Tree(root=Phylo.BaseTree.Clade(name="Root"))
        clade_with_quote = Phylo.BaseTree.Clade(name="Node'Name")
        tree.root.clades.append(clade_with_quote)
        mem_file = StringIO()
        Phylo.write(tree, mem_file, "newick")
        mem_file.seek(0)
        self.assertEqual(mem_file.read(), "('Node''Name':0)Root:0;\n")


class TreeTests(unittest.TestCase):
    """Tests for methods on BaseTree.Tree objects."""

    def test_randomized(self):
        """Tree.randomized: generate a new randomized tree."""
        for N in (2, 5, 20):
            tree = Phylo.BaseTree.Tree.randomized(N)
            self.assertEqual(tree.count_terminals(), N)
            self.assertEqual(tree.total_branch_length(), (N - 1) * 2)
            tree = Phylo.BaseTree.Tree.randomized(N, branch_length=2.0)
            self.assertEqual(tree.total_branch_length(), (N - 1) * 4)
        tree = Phylo.BaseTree.Tree.randomized(5, branch_stdev=0.5)
        self.assertEqual(tree.count_terminals(), 5)

    def test_root_with_outgroup(self):
        """Tree.root_with_outgroup: reroot at a given clade."""
        # On a large realistic tree, at a deep internal node
        tree = Phylo.read(EX_APAF, "phyloxml")
        orig_num_tips = len(tree.get_terminals())
        orig_tree_len = tree.total_branch_length()
        tree.root_with_outgroup("19_NEMVE", "20_NEMVE")
        self.assertEqual(orig_num_tips, len(tree.get_terminals()))
        self.assertAlmostEqual(orig_tree_len, tree.total_branch_length())
        # Now, at an external node
        tree.root_with_outgroup("1_BRAFL")
        self.assertEqual(orig_num_tips, len(tree.get_terminals()))
        self.assertAlmostEqual(orig_tree_len, tree.total_branch_length())
        # Specifying outgroup branch length mustn't change the total tree size
        tree.root_with_outgroup("2_BRAFL", outgroup_branch_length=0.5)
        self.assertEqual(orig_num_tips, len(tree.get_terminals()))
        self.assertAlmostEqual(orig_tree_len, tree.total_branch_length())
        tree.root_with_outgroup("36_BRAFL", "37_BRAFL", outgroup_branch_length=0.5)
        self.assertEqual(orig_num_tips, len(tree.get_terminals()))
        self.assertAlmostEqual(orig_tree_len, tree.total_branch_length())
        # On small contrived trees, testing edge cases
        for small_nwk in (
            "(A,B,(C,D));",
            "((E,F),((G,H)),(I,J));",
            "((Q,R),(S,T),(U,V));",
            "(X,Y);",
        ):
            tree = Phylo.read(StringIO(small_nwk), "newick")
            orig_tree_len = tree.total_branch_length()
            for node in list(tree.find_clades()):
                tree.root_with_outgroup(node)
                self.assertAlmostEqual(orig_tree_len, tree.total_branch_length())

    def test_root_at_midpoint(self):
        """Tree.root_at_midpoint: reroot at the tree's midpoint."""
        for treefname, fmt in [
            (EX_APAF, "phyloxml"),
            (EX_BCL2, "phyloxml"),
            (EX_NEWICK, "newick"),
        ]:
            tree = Phylo.read(treefname, fmt)
            orig_tree_len = tree.total_branch_length()
            # Total branch length does not change
            tree.root_at_midpoint()
            self.assertAlmostEqual(orig_tree_len, tree.total_branch_length())
            # Root is bifurcating
            self.assertEqual(len(tree.root.clades), 2)
            # Deepest tips under each child of the root are equally deep
            deep_dist_0 = max(tree.clade[0].depths().values())
            deep_dist_1 = max(tree.clade[1].depths().values())
            self.assertAlmostEqual(deep_dist_0, deep_dist_1)

    # Magic method
    def test_str(self):
        """Tree.__str__: pretty-print to a string.

        NB: The exact line counts are liable to change if the object
        constructors change.
        """
        for source, count in zip((EX_APAF, EX_BCL2, EX_DIST), (386, 747, 15)):
            tree = Phylo.read(source, "phyloxml")
            output = str(tree)
            self.assertEqual(len(output.splitlines()), count)


class MixinTests(unittest.TestCase):
    """Tests for TreeMixin methods."""

    def setUp(self):
        self.phylogenies = list(Phylo.parse(EX_PHYLO, "phyloxml"))

    # Traversal methods

    def test_find_elements(self):
        """TreeMixin: find_elements() method."""
        # From the docstring example
        tree = self.phylogenies[5]
        matches = list(tree.find_elements(PhyloXML.Taxonomy, code="OCTVU"))
        self.assertEqual(len(matches), 1)
        self.assertIsInstance(matches[0], PhyloXML.Taxonomy)
        self.assertEqual(matches[0].code, "OCTVU")
        self.assertEqual(matches[0].scientific_name, "Octopus vulgaris")
        # Iteration and regexps
        tree = self.phylogenies[10]
        for point, alt in zip(
            tree.find_elements(geodetic_datum=r"WGS\d{2}"), (472, 10, 452)
        ):
            self.assertIsInstance(point, PhyloXML.Point)
            self.assertEqual(point.geodetic_datum, "WGS84")
            self.assertAlmostEqual(point.alt, alt)
        # class filter
        tree = self.phylogenies[4]
        events = list(tree.find_elements(PhyloXML.Events))
        self.assertEqual(len(events), 2)
        self.assertEqual(events[0].speciations, 1)
        self.assertEqual(events[1].duplications, 1)
        # string filter & find_any
        tree = self.phylogenies[3]
        taxonomy = tree.find_any("B. subtilis")
        self.assertEqual(taxonomy.scientific_name, "B. subtilis")
        # integer filter
        tree = Phylo.read(EX_APAF, "phyloxml")
        domains = list(tree.find_elements(start=5))
        self.assertEqual(len(domains), 8)
        for dom in domains:
            self.assertEqual(dom.start, 5)
            self.assertEqual(dom.value, "CARD")

    def test_find_clades(self):
        """TreeMixin: find_clades() method."""
        # boolean filter
        for clade, name in zip(
            self.phylogenies[10].find_clades(name=True), list("ABCD")
        ):
            self.assertIsInstance(clade, PhyloXML.Clade)
            self.assertEqual(clade.name, name)
        # finding deeper attributes
        octo = list(self.phylogenies[5].find_clades(code="OCTVU"))
        self.assertEqual(len(octo), 1)
        self.assertIsInstance(octo[0], PhyloXML.Clade)
        self.assertEqual(octo[0].taxonomies[0].code, "OCTVU")
        # string filter
        dee = next(self.phylogenies[10].find_clades("D"))
        self.assertEqual(dee.name, "D")

    def test_find_terminal(self):
        """TreeMixin: find_elements() with terminal argument."""
        for tree, total, extern, intern in zip(
            self.phylogenies,
            (6, 6, 7, 18, 21, 27, 7, 9, 9, 19, 15, 9, 6),
            (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3),
            (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3),
        ):
            self.assertEqual(len(list(tree.find_elements())), total)
            self.assertEqual(len(list(tree.find_elements(terminal=True))), extern)
            self.assertEqual(len(list(tree.find_elements(terminal=False))), intern)

    def test_get_path(self):
        """TreeMixin: get_path() method."""
        path = self.phylogenies[1].get_path("B")
        self.assertEqual(len(path), 2)
        self.assertAlmostEqual(path[0].branch_length, 0.06)
        self.assertAlmostEqual(path[1].branch_length, 0.23)
        self.assertEqual(path[1].name, "B")

    def test_trace(self):
        """TreeMixin: trace() method."""
        tree = self.phylogenies[1]
        path = tree.trace("A", "C")
        self.assertEqual(len(path), 3)
        self.assertAlmostEqual(path[0].branch_length, 0.06)
        self.assertAlmostEqual(path[2].branch_length, 0.4)
        self.assertEqual(path[2].name, "C")

    def test_missing_target_trace(self):
        """TreeMixin: trace() method with missing target."""
        tree = self.phylogenies[1]
        with self.assertRaises(ValueError) as cm:
            tree.trace("Aaa", "C")
        self.assertEqual(str(cm.exception), "target 'Aaa' is not in this tree")

    # Information methods

    def test_common_ancestor(self):
        """TreeMixin: common_ancestor() method."""
        tree = self.phylogenies[1]
        lca = tree.common_ancestor("A", "B")
        self.assertEqual(lca, tree.clade[0])
        lca = tree.common_ancestor("A", "C")
        self.assertEqual(lca, tree.clade)
        tree = self.phylogenies[10]
        lca = tree.common_ancestor("A", "B", "C")
        self.assertEqual(lca, tree.clade[0])

    def test_depths(self):
        """TreeMixin: depths() method."""
        tree = self.phylogenies[1]
        depths = tree.depths()
        self.assertEqual(len(depths), 5)
        for found, expect in zip(
            sorted(depths.values()), [0, 0.060, 0.162, 0.290, 0.400]
        ):
            self.assertAlmostEqual(found, expect)

    def test_distance(self):
        """TreeMixin: distance() method."""
        t = self.phylogenies[1]
        self.assertAlmostEqual(t.distance("A"), 0.162)
        self.assertAlmostEqual(t.distance("B"), 0.29)
        self.assertAlmostEqual(t.distance("C"), 0.4)
        self.assertAlmostEqual(t.distance("A", "B"), 0.332)
        self.assertAlmostEqual(t.distance("A", "C"), 0.562)
        self.assertAlmostEqual(t.distance("B", "C"), 0.69)

    def test_is_bifurcating(self):
        """TreeMixin: is_bifurcating() method."""
        for tree, is_b in zip(
            self.phylogenies, (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1)
        ):
            self.assertEqual(tree.is_bifurcating(), is_b)

    def test_is_monophyletic(self):
        """TreeMixin: is_monophyletic() method."""
        tree = self.phylogenies[10]
        abcd = tree.get_terminals()
        abc = tree.clade[0].get_terminals()
        ab = abc[:2]
        d = tree.clade[1].get_terminals()
        self.assertEqual(tree.is_monophyletic(abcd), tree.root)
        self.assertEqual(tree.is_monophyletic(abc), tree.clade[0])
        self.assertFalse(tree.is_monophyletic(ab))
        self.assertEqual(tree.is_monophyletic(d), tree.clade[1])
        # Alternate argument form
        self.assertEqual(tree.is_monophyletic(*abcd), tree.root)

    def test_total_branch_length(self):
        """TreeMixin: total_branch_length() method."""
        tree = self.phylogenies[1]
        self.assertAlmostEqual(tree.total_branch_length(), 0.792)
        self.assertAlmostEqual(tree.clade[0].total_branch_length(), 0.392)

    # Tree manipulation methods

    def test_collapse(self):
        """TreeMixin: collapse() method."""
        tree = self.phylogenies[1]
        parent = tree.collapse(tree.clade[0])
        self.assertEqual(len(parent), 3)
        for clade, name, blength in zip(parent, ("C", "A", "B"), (0.4, 0.162, 0.29)):
            self.assertEqual(clade.name, name)
            self.assertAlmostEqual(clade.branch_length, blength)

    def test_collapse_all(self):
        """TreeMixin: collapse_all() method."""
        tree = Phylo.read(EX_APAF, "phyloxml")
        d1 = tree.depths()
        tree.collapse_all()
        d2 = tree.depths()
        # Total branch lengths should not change
        for clade in d2:
            self.assertAlmostEqual(d1[clade], d2[clade])
        # No internal nodes should remain except the root
        self.assertEqual(len(tree.get_terminals()), len(tree.clade))
        self.assertEqual(len(list(tree.find_clades(terminal=False))), 1)
        # Again, with a target specification
        tree = Phylo.read(EX_APAF, "phyloxml")
        d1 = tree.depths()
        internal_node_ct = len(tree.get_nonterminals())
        tree.collapse_all(lambda c: c.branch_length < 0.1)  # noqa: E731
        d2 = tree.depths()
        # Should have collapsed 7 internal nodes
        self.assertEqual(len(tree.get_nonterminals()), internal_node_ct - 7)
        for clade in d2:
            self.assertAlmostEqual(d1[clade], d2[clade])

    def test_collapse_without_branch_lengths(self):
        tree = Phylo.read(StringIO("(((A,B),C),D);"), "newick")
        tree.collapse_all()
        self.assertEqual(len(tree.get_terminals()), 4)
        self.assertEqual(len(tree.get_nonterminals()), 1)

    def test_ladderize(self):
        """TreeMixin: ladderize() method."""

        def ordered_names(tree):
            return [n.name for n in tree.get_terminals()]

        tree = self.phylogenies[10]
        self.assertEqual(ordered_names(tree), list("ABCD"))
        tree.ladderize()
        self.assertEqual(ordered_names(tree), list("DABC"))
        tree.ladderize(reverse=True)
        self.assertEqual(ordered_names(tree), list("ABCD"))

    def test_prune(self):
        """TreeMixin: prune() method."""
        tree = self.phylogenies[10]
        # Taxon in a trifurcation -- no collapse afterward
        parent = tree.prune(name="B")
        self.assertEqual(len(parent.clades), 2)
        self.assertEqual(parent.clades[0].name, "A")
        self.assertEqual(parent.clades[1].name, "C")
        self.assertEqual(len(tree.get_terminals()), 3)
        self.assertEqual(len(tree.get_nonterminals()), 2)
        # Taxon in a bifurcation -- collapse
        tree = self.phylogenies[0]
        parent = tree.prune(name="A")
        self.assertEqual(len(parent.clades), 2)
        for clade, name, blen in zip(parent, "BC", (0.29, 0.4)):
            self.assertTrue(clade.is_terminal())
            self.assertEqual(clade.name, name)
            self.assertAlmostEqual(clade.branch_length, blen)
        self.assertEqual(len(tree.get_terminals()), 2)
        self.assertEqual(len(tree.get_nonterminals()), 1)
        # Taxon just below the root -- don't screw up
        tree = self.phylogenies[1]
        parent = tree.prune(name="C")
        self.assertEqual(parent, tree.root)
        self.assertEqual(tree.root.branch_length, 0.06)
        self.assertEqual(len(parent.clades), 2)
        for clade, name, blen in zip(parent, "AB", (0.102, 0.23)):
            self.assertTrue(clade.is_terminal())
            self.assertEqual(clade.name, name)
            self.assertAlmostEqual(clade.branch_length, blen)
        self.assertEqual(len(tree.get_terminals()), 2)
        self.assertEqual(len(tree.get_nonterminals()), 1)
        # Taxon just below root
        tree = self.phylogenies[13]
        parent = tree.prune(name="C")
        self.assertEqual(tree.root.branch_length, 0.1)

    def test_split(self):
        """TreeMixin: split() method."""
        tree = self.phylogenies[0]
        C = tree.clade[1]
        C.split()
        self.assertEqual(len(C), 2)
        self.assertEqual(len(tree.get_terminals()), 4)
        self.assertEqual(len(tree.get_nonterminals()), 3)
        C[0].split(3, 0.5)
        self.assertEqual(len(tree.get_terminals()), 6)
        self.assertEqual(len(tree.get_nonterminals()), 4)
        for clade, name, blen in zip(C[0], ("C00", "C01", "C02"), (0.5, 0.5, 0.5)):
            self.assertTrue(clade.is_terminal())
            self.assertEqual(clade.name, name)
            self.assertEqual(clade.branch_length, blen)

    def test_resolve_polytomies(self):
        """TreeMixin: resolve_polytomies() method."""
        poly_tree_str = "(A:2,(B:1,C:2,D:4,(E:3,(F:2,G:3,H:1):2):1):5);\n"
        #                         ^   ^             ^   polytomies
        # Each polytomy resolves to a balanced hierarchy of zero-length
        # bifurcations, preserving the child order left to right.
        resolved_tree_str = (
            "(A:2,((B:1,C:2):0,(D:4,(E:3,(F:2,(G:3,H:1):0):2):1):0):5);\n"
        )
        poly_tree = Phylo.read(StringIO(poly_tree_str), "newick")
        resolved_tree = Phylo.read(StringIO(resolved_tree_str), "newick")
        self.assertFalse(poly_tree.is_bifurcating())
        poly_tree.resolve_polytomies(shuffle=False, recursive=True)
        self.assertTrue(poly_tree.is_bifurcating())
        self.assertEqual(poly_tree.format("newick"), resolved_tree.format("newick"))

    def test_resolve_polytomies_wide(self):
        """TreeMixin: resolve_polytomies() on a star wider than the recursion limit."""
        # A star tree, as produced by e.g. FastTree on unresolvable data.
        # 1500 children exceeds Python's default recursion limit of 1000;
        # a chain-per-child resolution either dies while building (the
        # original recursive implementation) or leaves a tree too deep for
        # the library's recursive traversals to validate or serialise.
        # The balanced resolution keeps the tree ~log2(n) deep, so the
        # ordinary machinery must work on the result.
        size = 1500
        star = "(" + ",".join("t%d:1" % i for i in range(size)) + ");"
        tree = Phylo.read(StringIO(star), "newick")
        tree.resolve_polytomies()
        self.assertTrue(tree.is_bifurcating())
        for clade in tree.find_clades():
            self.assertLessEqual(len(clade.clades), 2)
        # Serialisation round trip, preserving leaf count and order
        reread = Phylo.read(StringIO(tree.format("newick")), "newick")
        self.assertEqual(
            [leaf.name for leaf in reread.get_terminals()],
            ["t%d" % i for i in range(size)],
        )


# ---------------------------------------------------------

if __name__ == "__main__":
    runner = unittest.TextTestRunner(verbosity=2)
    unittest.main(testRunner=runner)
