def _match_material(self, taskdoc):
        """
        Returns the material_id that has the same structure as this task as
         determined by the structure matcher. Returns None if no match.

        Args:
            taskdoc (dict): a JSON-like task document

        Returns:
            (int) matching material_id or None
        """
        formula = taskdoc["formula_reduced_abc"]

        if "parent_structure" in taskdoc:  # this is used to intentionally combine multiple data w/same formula but slightly different structure, e.g. from an ordering scheme
            t_struct = Structure.from_dict(taskdoc["parent_structure"]["structure"])
            q = {"formula_reduced_abc": formula, "parent_structure.spacegroup.number": taskdoc["parent_structure"]["spacegroup"]["number"]}
        else:
            sgnum = taskdoc["output"]["spacegroup"]["number"]
            t_struct = Structure.from_dict(taskdoc["output"]["structure"])
            q = {"formula_reduced_abc": formula, "sg_number": sgnum}

        for m in self._materials.find(q, {"parent_structure": 1, "structure": 1, "material_id": 1}):
            s_dict = m["parent_structure"]["structure"] if "parent_structure" in m else m["structure"]
            m_struct = Structure.from_dict(s_dict)
            sm = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5,
                                  primitive_cell=True, scale=True,
                                  attempt_supercell=False, allow_subset=False,
                                  comparator=ElementComparator())

            if sm.fit(m_struct, t_struct):
                return m["material_id"]

        return None

    def apply_transformation(self, structure):
        """
        Returns a copy of structure with lattice parameters
        and sites scaled to the same degree as the relaxed_structure.

        Arg:
            structure (Structure): A structurally similar structure in
                regards to crystal and site positions.
        """

        if self.species_map == None:
            match = StructureMatcher()
            s_map = \
                match.get_best_electronegativity_anonymous_mapping(self.unrelaxed_structure,
                                                                   structure)
        else:
            s_map = self.species_map

        params = list(structure.lattice.abc)
        params.extend(structure.lattice.angles)
        new_lattice = Lattice.from_parameters(*[p*self.params_percent_change[i] \
                                                for i, p in enumerate(params)])
        species, frac_coords = [], []
        for site in self.relaxed_structure:
            species.append(s_map[site.specie])
            frac_coords.append(site.frac_coords)

        return Structure(new_lattice, species, frac_coords)

    def structure_transform(self, original_structure, new_structure,
                            refine_rotation=True):
        """
        Transforms a tensor from one basis for an original structure
        into a new basis defined by a new structure.

        Args:
            original_structure (Structure): structure corresponding
                to the basis of the current tensor
            new_structure (Structure): structure corresponding to the
                desired basis
            refine_rotation (bool): whether to refine the rotations
                generated in get_ieee_rotation

        Returns:
            Tensor that has been transformed such that its basis
            corresponds to the new_structure's basis
        """
        sm = StructureMatcher()
        if not sm.fit(original_structure, new_structure):
            warnings.warn("original and new structures do not match!")
        trans_1 = self.get_ieee_rotation(original_structure, refine_rotation)
        trans_2 = self.get_ieee_rotation(new_structure, refine_rotation)
        # Get the ieee format tensor
        new = self.rotate(trans_1)
        # Reverse the ieee format rotation for the second structure
        new = new.rotate(np.transpose(trans_2))
        return new

    def add_if_belongs(self, cand_snl):

        # no need to compare if different formulas or spacegroups
        if cand_snl.snlgroup_key != self.canonical_snl.snlgroup_key:
            return False

        # no need to compare if one is ordered, the other disordered
        if not (cand_snl.structure.is_ordered == self.canonical_structure.is_ordered):
            return False

        # make sure the structure is not already in all_structures
        if cand_snl.snl_id in self.all_snl_ids:
            print 'WARNING: add_if_belongs() has detected that you are trying to add the same SNL id twice!'
            return False

        #try a structure fit to the canonical structure

        # use default Structure Matcher params from April 24, 2013, as suggested by Shyue
        # we are using the ElementComparator() because this is how we want to group results
        sm = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5, primitive_cell=True, scale=True, attempt_supercell=True, comparator=ElementComparator())

        if not sm.fit(cand_snl.structure, self.canonical_structure):
            return False

        # everything checks out, add to the group
        self.all_snl_ids.append(cand_snl.snl_id)
        self.updated_at = datetime.datetime.utcnow()

        return True

 def test_class(self):
     # Tests entire class as single working unit
     sm = StructureMatcher()
     # Test group_structures and find_indices
     out = sm.group_structures(self.struct_list)
     self.assertEqual(map(len, out), [4, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1])
     self.assertEqual(sum(map(len, out)), len(self.struct_list))

    def test_class(self):
        # Tests entire class as single working unit
        sm = StructureMatcher()
        # Test group_structures and find_indices
        out = sm.group_structures(self.struct_list)

        self.assertEqual(sm.find_indexes(self.struct_list, out), [0, 0, 0, 1, 2, 3, 4, 0, 5, 6, 7, 8, 8, 9, 9, 10])

def _perform_grouping(args):
    (entries_json, hosts_json, ltol, stol, angle_tol,
     primitive_cell, scale, comparator, groups) = args

    entries = json.loads(entries_json, cls=MontyDecoder)
    hosts = json.loads(hosts_json, cls=MontyDecoder)
    unmatched = list(zip(entries, hosts))
    while len(unmatched) > 0:
        ref_host = unmatched[0][1]
        logger.info(
            "Reference tid = {}, formula = {}".format(unmatched[0][0].entry_id,
                                                      ref_host.formula)
        )
        ref_formula = ref_host.composition.reduced_formula
        logger.info("Reference host = {}".format(ref_formula))
        matches = [unmatched[0]]
        for i in range(1, len(unmatched)):
            test_host = unmatched[i][1]
            logger.info("Testing tid = {}, formula = {}"
                        .format(unmatched[i][0].entry_id, test_host.formula))
            test_formula = test_host.composition.reduced_formula
            logger.info("Test host = {}".format(test_formula))
            m = StructureMatcher(ltol=ltol, stol=stol, angle_tol=angle_tol,
                                 primitive_cell=primitive_cell, scale=scale,
                                 comparator=comparator)
            if m.fit(ref_host, test_host):
                logger.info("Fit found")
                matches.append(unmatched[i])
        groups.append(json.dumps([m[0] for m in matches], cls=MontyEncoder))
        unmatched = list(filter(lambda x: x not in matches, unmatched))
        logger.info("{} unmatched remaining".format(len(unmatched)))

    def test_get_supercell_size(self):
        l = Lattice.cubic(1)
        l2 = Lattice.cubic(0.9)
        s1 = Structure(l, ['Mg', 'Cu', 'Ag', 'Cu', 'Ag'], [[0] * 3] * 5)
        s2 = Structure(l2, ['Cu', 'Cu', 'Ag'], [[0] * 3] * 3)

        sm = StructureMatcher(supercell_size='volume')
        self.assertEqual(sm._get_supercell_size(s1, s2),
                         (1, True))
        self.assertEqual(sm._get_supercell_size(s2, s1),
                         (1, True))

        sm = StructureMatcher(supercell_size='num_sites')
        self.assertEqual(sm._get_supercell_size(s1, s2),
                         (2, False))
        self.assertEqual(sm._get_supercell_size(s2, s1),
                         (2, True))

        sm = StructureMatcher(supercell_size='Ag')
        self.assertEqual(sm._get_supercell_size(s1, s2),
                         (2, False))
        self.assertEqual(sm._get_supercell_size(s2, s1),
                         (2, True))

        sm = StructureMatcher(supercell_size='wfieoh')
        self.assertRaises(ValueError, sm._get_supercell_size, s1, s2)

    def test_subset(self):
        sm = StructureMatcher(
            ltol=0.2,
            stol=0.3,
            angle_tol=5,
            primitive_cell=False,
            scale=True,
            attempt_supercell=False,
            allow_subset=True,
        )
        l = Lattice.orthorhombic(10, 20, 30)
        s1 = Structure(l, ["Si", "Si", "Ag"], [[0, 0, 0.1], [0, 0, 0.2], [0.7, 0.4, 0.5]])
        s2 = Structure(l, ["Si", "Ag"], [[0, 0.1, 0], [-0.7, 0.5, 0.4]])
        result = sm.get_s2_like_s1(s1, s2)

        self.assertEqual(len(find_in_coord_list_pbc(result.frac_coords, [0, 0, 0.1])), 1)
        self.assertEqual(len(find_in_coord_list_pbc(result.frac_coords, [0.7, 0.4, 0.5])), 1)

        # test with fewer species in s2
        s1 = Structure(l, ["Si", "Ag", "Si"], [[0, 0, 0.1], [0, 0, 0.2], [0.7, 0.4, 0.5]])
        s2 = Structure(l, ["Si", "Si"], [[0, 0.1, 0], [-0.7, 0.5, 0.4]])
        result = sm.get_s2_like_s1(s1, s2)
        mindists = np.min(s1.lattice.get_all_distances(s1.frac_coords, result.frac_coords), axis=0)
        self.assertLess(np.max(mindists), 1e-6)

        self.assertEqual(len(find_in_coord_list_pbc(result.frac_coords, [0, 0, 0.1])), 1)
        self.assertEqual(len(find_in_coord_list_pbc(result.frac_coords, [0.7, 0.4, 0.5])), 1)

        # test with not enough sites in s1
        # test with fewer species in s2
        s1 = Structure(l, ["Si", "Ag", "Cl"], [[0, 0, 0.1], [0, 0, 0.2], [0.7, 0.4, 0.5]])
        s2 = Structure(l, ["Si", "Si"], [[0, 0.1, 0], [-0.7, 0.5, 0.4]])
        self.assertEqual(sm.get_s2_like_s1(s1, s2), None)

    def test_ordered_primitive_to_disordered_supercell(self):
        sm_atoms = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5,
                                    primitive_cell=False, scale=True,
                                    attempt_supercell=True,
                                    allow_subset=True,
                                    supercell_size = 'num_atoms',
                                    comparator=OrderDisorderElementComparator())
        sm_sites = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5,
                                    primitive_cell=False, scale=True,
                                    attempt_supercell=True,
                                    allow_subset=True,
                                    supercell_size = 'num_sites',
                                    comparator=OrderDisorderElementComparator())
        lp = Lattice.orthorhombic(10, 20, 30)
        pcoords = [[0,   0,   0],
                   [0.5, 0.5, 0.5]]
        ls = Lattice.orthorhombic(20,20,30)
        scoords = [[0,    0,   0],
                   [0.5,  0,   0],
                   [0.25, 0.5, 0.5],
                   [0.75, 0.5, 0.5]]
        s1 = Structure(lp, ['Na', 'Cl'], pcoords)
        s2 = Structure(ls, [{'Na':0.5}, {'Na':0.5}, {'Cl':0.5}, {'Cl':0.5}], scoords)

        self.assertTrue(sm_sites.fit(s1, s2))
        self.assertFalse(sm_atoms.fit(s1, s2))

    def test_disordered_primitive_to_ordered_supercell(self):
        sm_atoms = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5,
                                    primitive_cell=False, scale=True,
                                    attempt_supercell=True,
                                    allow_subset=True,
                                    supercell_size = 'num_atoms',
                                    comparator=OrderDisorderElementComparator())
        sm_sites = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5,
                                    primitive_cell=False, scale=True,
                                    attempt_supercell=True,
                                    allow_subset=True,
                                    supercell_size = 'num_sites',
                                    comparator=OrderDisorderElementComparator())
        lp = Lattice.orthorhombic(10, 20, 30)
        pcoords = [[0,   0,   0],
                   [0.5, 0.5, 0.5]]
        ls = Lattice.orthorhombic(20,20,30)
        scoords = [[0,    0,   0],
                   [0.75, 0.5, 0.5]]
        prim = Structure(lp, [{'Na':0.5}, {'Cl':0.5}], pcoords)
        supercell = Structure(ls, ['Na', 'Cl'], scoords)
        supercell.make_supercell([[-1,1,0],[0,1,1],[1,0,0]])

        self.assertFalse(sm_sites.fit(prim, supercell))
        self.assertTrue(sm_atoms.fit(prim, supercell))

        self.assertRaises(ValueError, sm_atoms.get_s2_like_s1, prim, supercell)
        self.assertEqual(len(sm_atoms.get_s2_like_s1(supercell, prim)), 4)

    def test_previous_reconstructions(self):

        # Test to see if we generated all reconstruction
        # types correctly and nothing changes

        m = StructureMatcher()
        for n in self.rec_archive.keys():
            if "base_reconstruction" in self.rec_archive[n].keys():
                arch = self.rec_archive[
                    self.rec_archive[n]["base_reconstruction"]]
                sg = arch["spacegroup"]["symbol"]
            else:
                sg = self.rec_archive[n]["spacegroup"]["symbol"]
            if sg == "Fm-3m":
                rec = ReconstructionGenerator(self.Ni, 20, 20, n)
                el = self.Ni[0].species_string
            elif sg == "Im-3m":
                rec = ReconstructionGenerator(self.Fe, 20, 20, n)
                el = self.Fe[0].species_string
            elif sg == "Fd-3m":
                rec = ReconstructionGenerator(self.Si, 20, 20, n)
                el = self.Si[0].species_string

            slabs = rec.build_slabs()
            s = Structure.from_file(get_path(os.path.join("reconstructions",
                                                          el + "_" + n + ".cif")))
            self.assertTrue(any(
                [len(m.group_structures([s, slab])) == 1 for slab in slabs]))

    def test_no_scaling(self):
        sm = StructureMatcher(ltol=0.1, stol=0.1, angle_tol=2,
                              scale=False, comparator=ElementComparator())
        self.assertTrue(sm.fit(self.struct_list[0], self.struct_list[1]))

        self.assertTrue(sm.get_rms_dist(self.struct_list[0],
                                        self.struct_list[1])[0] < 0.0008)

    def _match_material(self, doc):
        """
        Returns the material_id that has the same structure as this doc as
         determined by the structure matcher. Returns None if no match.

        Args:
            doc: a JSON-like document

        Returns:
            (int) matching material_id or None
        """
        formula = doc["formula_reduced_abc"]
        sgnum = doc["spacegroup"]["number"]

        for m in self._materials.find({"formula_reduced_abc": formula, "sg_number": sgnum},
                                      {"structure": 1, "material_id": 1}):

            m_struct = Structure.from_dict(m["structure"])
            t_struct = Structure.from_dict(doc["structure"])

            sm = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5,
                                  primitive_cell=True, scale=True,
                                  attempt_supercell=False, allow_subset=False,
                                  comparator=ElementComparator())

            if sm.fit(m_struct, t_struct):
                return m["material_id"]

        return None

    def test_get_supercell_matrix(self):
        sm = StructureMatcher(ltol=0.1, stol=0.3, angle_tol=2,
                              primitive_cell=False, scale=True,
                              attempt_supercell=True)

        l = Lattice.orthorhombic(1, 2, 3)

        s1 = Structure(l, ['Si', 'Si', 'Ag'],
                       [[0,0,0.1],[0,0,0.2],[.7,.4,.5]])
        s1.make_supercell([2,1,1])
        s2 = Structure(l, ['Si', 'Si', 'Ag'],
                       [[0,0.1,0],[0,0.1,-0.95],[-.7,.5,.375]])
        result = sm.get_supercell_matrix(s1, s2)
        self.assertTrue((result == [[-2,0,0],[0,1,0],[0,0,1]]).all())

        s1 = Structure(l, ['Si', 'Si', 'Ag'],
                       [[0,0,0.1],[0,0,0.2],[.7,.4,.5]])
        s1.make_supercell([[1, -1, 0],[0, 0, -1],[0, 1, 0]])

        s2 = Structure(l, ['Si', 'Si', 'Ag'],
                       [[0,0.1,0],[0,0.1,-0.95],[-.7,.5,.375]])
        result = sm.get_supercell_matrix(s1, s2)
        self.assertTrue((result == [[-1,-1,0],[0,0,-1],[0,1,0]]).all())

        #test when the supercell is a subset
        sm = StructureMatcher(ltol=0.1, stol=0.3, angle_tol=2,
                              primitive_cell=False, scale=True,
                              attempt_supercell=True, allow_subset=True)
        del s1[0]
        result = sm.get_supercell_matrix(s1, s2)
        self.assertTrue((result == [[-1,-1,0],[0,0,-1],[0,1,0]]).all())

 def test_as_dict_and_from_dict(self):
     sm = StructureMatcher(ltol=0.1, stol=0.2, angle_tol=2,
                           primitive_cell=False, scale=False,
                           comparator=FrameworkComparator())
     d = sm.as_dict()
     sm2 = StructureMatcher.from_dict(d)
     self.assertEqual(sm2.as_dict(), d)

 def test_primitive(self):
     """Test primitive cell reduction"""
     sm = StructureMatcher(primitive_cell=True)
     mod = SupercellMaker(self.struct_list[1],
                          scaling_matrix=[[2, 0, 0], [0, 3, 0], [0, 0, 1]])
     super_cell = mod.modified_structure
     self.assertTrue(sm.fit(self.struct_list[0], super_cell))

    def test_electronegativity(self):
        sm = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5)

        s1 = read_structure(os.path.join(test_dir, "Na2Fe2PAsO4S4.cif"))
        s2 = read_structure(os.path.join(test_dir, "Na2Fe2PNO4Se4.cif"))
        self.assertAlmostEqual(sm.fit_with_electronegativity(s1, s2),
                               {Composition('S'): Composition('Se'), Composition('As'): Composition('N')})

def compare_structures(options):
    """Inspired to a similar function in pmg_structure."""
    paths = options.paths
    if len(paths) < 2:
        print("You need more than one structure to compare!")
        return 1

    try:
        structures = [abilab.Structure.from_file(p) for p in paths]
    except Exception as ex:
        print("Error reading structures from files. Are they in the right format?")
        print(str(ex))
        return 1

    from pymatgen.analysis.structure_matcher import StructureMatcher, ElementComparator
    compareby = "species" if options.anonymous else "element"
    m = StructureMatcher() if compareby == "species" else StructureMatcher(comparator=ElementComparator())
    print("Grouping %s structures by `%s` with `anonymous: %s`" % (len(structures), compareby, options.anonymous))

    for i, grp in enumerate(m.group_structures(structures, anonymous=options.anonymous)):
        print("Group {}: ".format(i))
        for s in grp:
            spg_symbol, international_number = s.get_space_group_info()
            print("\t- {} ({}), vol: {:.2f} A^3, {} ({})".format(
                  paths[structures.index(s)], s.formula, s.volume, spg_symbol, international_number))
        print()

    if options.verbose:
        pprint(m.as_dict())

    def test_get_mapping(self):
        sm = StructureMatcher(ltol=0.2, stol=0.3, angle_tol=5,
                              primitive_cell=False, scale=True,
                              attempt_supercell=False,
                              allow_subset = True)
        l = Lattice.orthorhombic(1, 2, 3)
        s1 = Structure(l, ['Ag', 'Si', 'Si'],
                       [[.7,.4,.5],[0,0,0.1],[0,0,0.2]])
        s1.make_supercell([2,1,1])
        s2 = Structure(l, ['Si', 'Si', 'Ag'],
                       [[0,0.1,-0.95],[0,0.1,0],[-.7,.5,.375]])

        shuffle = [2,0,1,3,5,4]
        s1 = Structure.from_sites([s1[i] for i in shuffle])
        #test the mapping
        s2.make_supercell([2,1,1])
        #equal sizes
        for i, x in enumerate(sm.get_mapping(s1, s2)):
            self.assertEqual(s1[x].species_and_occu,
                             s2[i].species_and_occu)

        del s1[0]
        #s1 is subset of s2
        for i, x in enumerate(sm.get_mapping(s2, s1)):
            self.assertEqual(s1[i].species_and_occu,
                             s2[x].species_and_occu)
        #s2 is smaller than s1
        del s2[0]
        del s2[1]
        self.assertRaises(ValueError, sm.get_mapping, s2, s1)