class Tag:
    def __init__(self, start_index, end_index, category):
        self.start_index = start_index
        self.end_index = end_index
        self.category = category

    def length(self):
        return self.end_index - self.start_index

    # if you want the tag to be hashable
    # def __hash__(self):
    #     return hash(f'{self.start_index}-{self.end_index}')

    def __eq__(self, tag):
        return (self.start_index == tag.start_index and self.end_index == tag.end_index)


class Disambiguator:
    disambiguate_tags_list = []

    def __init__(self, matrix_of_tags):
        self.matrix_of_tags = matrix_of_tags

    def disambiguate_tags(self):
        tag_dic = {}
        # iterate each user list
        for list in self.matrix_of_tags:
            # iterate through tags of each user creating a map of tags
            for tag in list:
                key = f'{tag.start_index}-{tag.end_index}'
                if key in tag_dic.keys():
                    tag_dic[key].append(tag)
                else:
                    tag_dic[key] = [tag]
        self.filter_should_desambiguate(tag_dic)
        return self.disambiguate_tags_list

    def filter_should_desambiguate(self, map_of_tags):
        # iterate through map of tags checking which tag should be checked
        for key in map_of_tags.keys():
            count_category = {}
            for tag in map_of_tags[key]:
                key = f'{tag.start_index}-{tag.end_index}'
                if key not in count_category:
                    count_category[key] = [tag.category]
                else:
                    count_category[key].append(tag.category)

            should_expert_check = True
            for tag in count_category.keys():
                for category in count_category[tag]:
                    # check if the category is the most voted
                    if count_category[tag].count(category) / len(count_category[tag]) > 0.5:
                        should_expert_check = False
                        break

            if should_expert_check:
                self.disambiguate_tags_list = [*self.disambiguate_tags_list, *map_of_tags[key]]


# Harry Potter and the philosopher stone is a book by JK Rowling from England
u1 = [
    Tag(0, 12, 'proper-name'),
    Tag(0, 38, 'title of book'),
    Tag(52, 62, 'proper-name'),
    Tag(68, 78, 'country')
]

u2 = [
    Tag(0, 38, 'movie'),
    Tag(52, 62, 'proper-name'),
    Tag(68, 78, 'city')
]

u3 = [
    Tag(0, 38, 'book'),
    Tag(52, 62, 'name'),
    Tag(68, 78, 'location')
]

# CASE 1
disambiguator = Disambiguator([u1, u2, u3])
tags_to_check = disambiguator.disambiguate_tags()
assert tags_to_check == [Tag(0, 38, 'title of book'),
                         Tag(0, 38, 'movie'),
                         Tag(0, 38, 'book'),
                         Tag(68, 78, 'country'),
                         Tag(68, 78, 'city'),
                         Tag(68, 78, 'location')]

#CASE 2
u2[0] = Tag(0, 38, 'book')
disambiguator = Disambiguator([u1, u2, u3])
tags_to_check = disambiguator.disambiguate_tags()
assert tags_to_check == [Tag(68, 78, 'country'),
                         Tag(68, 78, 'city'),
                         Tag(68, 78, 'location')]

# CASE 3
u2[2] = Tag(68, 78, "country")
disambiguator = Disambiguator([u1, u2, u3])
tags_to_check = disambiguator.disambiguate_tags()
assert tags_to_check == []

"""
I did not considered overlapping tags. For example, "Harry Potter and the philosopher stone" and "Harry Potter", since
I thought Harry Potter could be one tag and the whole name of the book could be another.

I considered that tags are equal if they have start index and end index equal. So the verification needs to be done by
checking the category.
"""
