class CacheGroup:
    def __init__(self, generator_list, relator_list):
        # here is the construction of the class Group. Each Group must have
        # a list of generators and a list of relators. Unlike the other classes
        # I didn't design methods to add generators or relators after the initial
        # construction of the class. As the name specifies, this version of Group
        # uses iterable functions (generators) to yield a value. This frees up
        # space as an entire list need not be created if the first values suffices.
        # The generators must all be Letters and the relators Words.
        self._generator_list = []
        self._relator_list = []
        self._relator_len_list = []

        # this feels like putting training wheels on a 747 but maybe that's what
        # 747s need. after all, crashing a 747 is worse than crashing a bike
        self._paranoid = True

        for entry in generator_list:
            if not isinstance(entry, Letter):
                raise Exception("noooo")
            self._generator_list.append(entry)
            if entry.return_inv_letter() not in self._generator_list:
                self._generator_list.append(entry.return_inv_letter())

        for entry in relator_list:
            if not isinstance(entry, Word):
                raise Exception("...i don't know what to say anymore")
            for i in range(entry.return_word_len()):
                if entry.return_word_letter(i) not in self._generator_list:
                    raise Exception("i'm not working with relators that "
                                    "don't send to my generators, sorry pal")
            self._relator_list.append(entry)

        for entry in self._relator_list:
            if entry.return_inv_word() not in self._relator_list:
                self._relator_list.append(entry.return_inv_word())
            if entry.check_identity():
                if entry.return_reverse() not in self._relator_list:
                    self._relator_list.append(entry.return_reverse())

        # Down here, I'm going to add the Cache and Trie stuff. it is going to call
        # a cache and store it here locally.
        self._cache = Cache([])

    def yield_coset_old(self, a_word, max_length):
        # this function creates a generator that will spit out the next item
        # which is equivalent to the inputted word. It accomplishes this by
        # inserting the relators in every possible position in the Word, and
        # yields that word. Once it goes through all positions and relators,
        # it goes through the previously yielded Words and runs on them.
        # it stores them in a list local to the function. It was the only way
        # to prevent duplicates from coming up
        if self._paranoid:
            if not isinstance(a_word, Word):
                raise Exception("I'm gonna lose it. words only")
            if not isinstance(max_length, int):
                raise Exception("we're working with math and you can't tell "
                                "me an integer to work with?")

        def _insert_relators(a_str, a_rule):
            # as the variable names suggest, this only takes strings as inputs.
            # Because this requires cutting up and gluing together objects, it's
            # easier to work with mutable objects than the Words or Letters
            for i in range(len(a_str)):
                if i == 0:
                    new_str = a_rule + a_str
                    yield new_str
                else:
                    head_a_str = a_str[:i]
                    tail_a_str = a_str[i:]
                    new_str = head_a_str + a_rule + tail_a_str
                    yield new_str
            new_str = a_str + a_rule
            yield new_str

        def _iterate_with_words(product_list, word_rule_list, list_to_expand,
                                fresh_list, max_length_here):
            # this takes the "fresh" list (list_to_expand) so to speak and only
            # runs the iteration over them. it does this so as to make sure that
            # only the new words generated by the last iteration are run. the
            # product list is added to every time but it is almost unnecessary
            # except in its role to check from duplicates. Max length was also
            # added here so as to ensure that the words being yielded are of the
            # right length rather than changing whether the function continues to run
            # based on the output each time.
            fresh_list.clear()
            for one_word in list_to_expand:
                for a_rule in word_rule_list:
                    if not one_word.return_word_len() + a_rule.return_word_len() > max_length_here:
                        a_str = one_word.return_word_str()
                        a_rule_str = a_rule.return_word_str()
                        for new_string in _insert_relators(a_str, a_rule_str):
                            new_word = Word([])
                            new_word.add_str(new_string)
                            if new_word not in product_list:
                                if new_word not in fresh_list:
                                    if new_word.return_word_len() <= max_length_here:
                                        fresh_list.append(new_word)
                                        yield new_word

            product_list.extend(fresh_list)
            list_to_expand.clear()
            list_to_expand.extend(fresh_list)

        # this takes the coset of the word and adds itself as well as the
        # list for expansion and expands it. then whenever the expansion
        # list has entries to expand, the program will run and the iterable
        # will continue to run

        coset_list = [a_word]
        expand_me = [a_word]
        yield a_word

        while expand_me:
            newly_added = []
            coset_producer = _iterate_with_words(coset_list, self._relator_list,
                                                 expand_me, newly_added, max_length)
            for member in coset_producer:
                yield member

    def yield_coset_of_len(self, a_word, max_len):
        # this calls the yield coset method but only outputs them if the length is equal to
        # the length specified. so if I wanted only the members with length 3 it will output
        # only them
        total_coset = self.yield_coset_old(a_word, max_len)
        for member in total_coset:
            if member.return_word_len() == max_len:
                yield member

    def yield_coset_cache(self, a_word, max_length):
        # new version of yield coset. This takes the yield coset that we used before
        # and also makes use of the cache class that was built. This allows us to only
        # yield a coset once and then the rest of the time it just searches lists
        # stored in the class of Group itself.
        if self._paranoid:
            if not isinstance(a_word, Word):
                raise Exception("I'm gonna lose it. words only")
            if not isinstance(max_length, int):
                raise Exception("we're working with math and you can't tell "
                                "me an integer to work with?")

        def _insert_relators(a_str, a_rule):
            # as the variable names suggest, this only takes strings as inputs.
            # Because this requires cutting up and gluing together objects, it's
            # easier to work with mutable objects than the Words or Letters
            for i in range(len(a_str)):
                if i == 0:
                    new_str = a_rule + a_str
                    yield new_str
                else:
                    head_a_str = a_str[:i]
                    tail_a_str = a_str[i:]
                    new_str = head_a_str + a_rule + tail_a_str
                    yield new_str
            new_str = a_str + a_rule
            yield new_str

        def _iterate_with_words(product_list, word_rule_list, list_to_expand,
                                recently_added_list, the_max_length, product_trie):
            # this takes the "fresh" list (list_to_expand) so to speak and only
            # runs the iteration over them. it does this so as to make sure that
            # only the new words generated by the last iteration are run. the
            # product list is added to every time but it is almost unnecessary
            # except in its role to check from duplicates. Max length was also
            # added here so as to ensure that the words being yielded are of the
            # right length rather than changing whether the function continues to run
            # based on the output each time.
            recently_added_list.clear()
            for another_word in list_to_expand:
                for a_rule in word_rule_list:
                    if not another_word.return_word_len() + a_rule.return_word_len() > the_max_length:
                        a_str = another_word.return_word_str()
                        a_rule_str = a_rule.return_word_str()
                        for new_string in _insert_relators(a_str, a_rule_str):
                            new_word = Word([])
                            new_word.add_str(new_string)
                            if not product_trie.search_trie(new_word):
                                if new_word not in recently_added_list:
                                    if new_word.return_word_len() <= the_max_length:
                                        product_trie.add_word(new_word)
                                        recently_added_list.append(new_word)
                                        yield new_word

            product_list.extend(recently_added_list)
            list_to_expand.clear()
            list_to_expand.extend(recently_added_list)

        if not self._cache.check_key(a_word):
            self._cache.create_coset(a_word)

        if self._cache.check_complete(a_word):
            a_word_coset = self._cache.get_coset_list(a_word)
            for entry in a_word_coset:
                yield entry
        else:
            coset_list = [a_word]
            expand_me = [a_word]
            self._cache.add_to_coset(a_word, a_word)
            yield a_word

            word_trie = WordTrie()
            while expand_me:
                newly_added_list = []
                coset_producer = _iterate_with_words(coset_list, self._relator_list,
                                                     expand_me, newly_added_list, max_length, word_trie)
                for member in coset_producer:
                    # more cache stuff here
                    self._cache.add_to_coset(a_word, member)
                    yield member
            self._cache.mark_coset_complete(a_word)

    def yield_non_reduced_words(self, max_len):
        # the purpose of this method is to create a iterable that will hand the
        # program the members of the set of the non reduced words on the generators
        # one at a time. This saves the space of having to generate the entire list
        # similarly to how the yield coset was aimed at not creating and saving the entire
        # list of Words

        def _add_generators(letter_list, product_list, new_list):
            # this takes the generators, and the list of Words which are already non-reduced
            # members, and adds the generators to the members of that list, yielding them
            # one at a time.
            new_product_list = []
            for letter in letter_list:
                for old_word in new_list:
                    non_reduced_word = Word([])
                    non_reduced_word.add_word(old_word)
                    non_reduced_word.add_letter(letter)
                    if non_reduced_word not in product_list:
                        if non_reduced_word not in new_product_list:
                            new_product_list.append(non_reduced_word)
                            yield non_reduced_word
            product_list.extend(new_product_list)
            new_list.clear()
            new_list.extend(new_product_list)

        # this then takes an empty list and runs the _add_generators. So the first iteration
        # will return the generators, and the next will return their combinations, and so on

        identity = Word([])
        non_reduced_word_list = [identity]
        fresh_list = [identity]
        for i in range(max_len):
            nrw_iterable = _add_generators(self._generator_list, non_reduced_word_list, fresh_list)
            for j in nrw_iterable:
                yield j

    def test_equals(self, word1, word2, num):
        # this takes two Words and tests if they are equals. it does so by combining a Word
        # (word1 in this case) with the second Word's inverse. The logic of this being that
        # if A = B then A*B^-1 = I where I is the identity. However, some words require more
        # than just that, so we create a iterator for the coset of this new word and test each
        # entry against a Word yielded from the normal closure of the relators. We obtain this
        # normal closure of the relators by creating a coset for the identity.
        # also i set num like that for fun, and it'll help with figuring out how long the words
        # have to be to get them to properly reduce

        if self._paranoid:
            if not isinstance(word1, Word):
                raise Exception("only words; the first one is not one")
            if not isinstance(word2, Word):
                raise Exception("still only working with words")
            if not isinstance(num, int):
                raise Exception("see earlier comment about not knowing integers")

        word1_word2inv = Word([])
        word1_word2inv.add_word(word1)
        word1_word2inv.add_word(word2.return_inv_word())
        # print(word1.return_word_str() + " == " + word2.return_word_str() + "?")
        identity = Word([])

        coset_w1w2inv = self.yield_coset_old(word1_word2inv, num)

        for w1w2inv_equiv in coset_w1w2inv:
            w1w2inv_length = w1w2inv_equiv.return_word_len()
            # ncor is normal closure of the relators, with the length of the equivalent to w1w2inv
            # being tested against the ncor being the maximum length
            ncor = self.yield_coset_of_len(identity, w1w2inv_length)
            for trivial_word in ncor:
                if w1w2inv_equiv == trivial_word:
                    # print("equal")
                    return True

            # print("still here and working")
        # print("not equal")
        return False

    def yield_elems_of_quotient(self, len_of_non_reduced, num_of_test_equals):
        # this method yields from the group each element of the quotient. it does so
        # by creating an iterable which yields the next member of the set of non reduced
        # Words on the Free group and tests if they are equal to members of the elements
        # of the quotient. if they aren't they then are yielded forward.
        identity = Word([])
        elem_of_quotient = [identity]

        freegroup_nonreduced = self.yield_non_reduced_words(len_of_non_reduced)

        for a_word in freegroup_nonreduced:
            # print("I'm " + a_word.return_word_str())
            admitted = True

            for existing_elem in elem_of_quotient:
                # print("I'm being tested against " + existing_elem.return_word_str())
                if self.test_equals_old(a_word, existing_elem, num_of_test_equals):
                    # print("didn't make it \n")
                    admitted = False
                    break

            if admitted:
                # print("made it \n")
                elem_of_quotient.append(a_word)
                yield a_word

    def test_equals_cache(self, word1, word2, max_len):
        # this is a new version of test equals that makes use of the changes made to
        # yield coset that can be seen in yield_coset_cache. The purpose of this new
        # test equals is to cut down on the time required to process the test equals
        if self._paranoid:
            if not isinstance(word1, Word):
                raise Exception("you figure it out i'm tired of saying it")
            if not isinstance(word2, Word):
                raise Exception("no")

        if not self._cache.check_key(word1):
            self._cache.create_coset(word1)
        if not self._cache.check_key(word2):
            self._cache.create_coset(word2)

        # print(word1.return_word_str() + " == " + word2.return_word_str() + "?")
        if self._cache.check_complete(word1):
            ans = False
            for word2_equivalent in self.yield_coset_cache(word2, max_len):
                word1_trie_coset = self._cache.get_coset_trie(word1)
                if word1_trie_coset.search_trie(word2_equivalent):
                    ans = True
                    if self._cache.check_complete(word2):
                        return ans
            # print(str(ans))
            return ans
        elif self._cache.check_complete(word2):
            ans = False
            for word1_equivalent in self.yield_coset_cache(word1, max_len):
                word2_trie_coset = self._cache.get_coset_trie(word2)
                if word2_trie_coset.search_trie(word1_equivalent):
                    ans = True
            # print(str(ans))
            return ans
        else:
            # this part is inefficient but i wasn't sure how else to do it
            for x in self.yield_coset_cache(word1, max_len):
                processing = True
            for y in self.yield_coset_cache(word2, max_len):
                processing = True
            for x in self.yield_coset_cache(word1, max_len):
                for y in self.yield_coset_cache(word2, max_len):
                    if x == y:
                        # print("yea")
                        return True
            # print("nah")
            return False

    def yield_elems_of_quot_cache(self, len_of_non_reduced, num_of_test_equals):
        # this method yields from the group each element of the quotient. it does so
        # by creating an iterable which yields the next member of the set of non reduced
        # Words on the Free group and tests if they are equal to members of the elements
        # of the quotient. if they aren't they then are yielded forward.

        # overall_start_time = time.time()
        identity = Word([])
        elem_of_quotient = [identity]

        freegroup_nonreduced = self.yield_non_reduced_words(len_of_non_reduced)

        for a_word in freegroup_nonreduced:
            # print("\nI'm " + a_word.return_word_str())
            admitted = True
            # start_time = time.time()
            for existing_elem in elem_of_quotient:
                # print("I'm being tested against " + existing_elem.return_word_str())
                if self.test_equals_cache(a_word, existing_elem, num_of_test_equals):
                    # print("didn't make it")
                    # print("this took %s seconds \n" % (round(time.time() - start_time, 3)))
                    admitted = False
                    break

            if admitted:
                # print("made it")
                elem_of_quotient.append(a_word)
                # print("this took %s seconds" % (round(time.time() - start_time, 3)))
                yield a_word

        # print("Overall time: %s seconds" % (round(time.time() - overall_start_time, 3)))
        # print("There are " + str(len(elem_of_quotient)) + " entries")

    def list_generators(self):
        # this returns all of the generators in a list. This is done so that when the
        # Letters need to be added in graph form, it doesn't assume which letters to append.
        a_list = []
        for entry in self._generator_list:
            a_list.append(entry)
        return a_list

    def list_non_inv_generators(self):
        a_list = []
        for entry in self._generator_list:
            if not entry.check_capital():
                a_list.append(entry)

        return a_list