class GreedyGrouper(Grouper):
    """
    A grouper used to create a grouping of students according to their
    answers to a survey. This grouper uses a greedy algorithm to create
    groups.

    === Public Attributes ===
    group_size: the ideal number of students that should be in each group

    === Representation Invariants ===
    group_size > 1
    """

    group_size: int

    def make_grouping(self, course: Course, survey: Survey) -> Grouping:
        """
        Return a grouping for all students in <course>.

        Starting with a tuple of all students in <course> obtained by calling
        the <course>.get_students() method, create groups of students using the
        following algorithm:

        1. select the first student in the tuple that hasn't already been put
           into a group and put this student in a new group.
        2. select the student in the tuple that hasn't already been put into a
           group that, if added to the new group, would increase the group's
           score the most (or reduce it the least), add that student to the new
           group.
        3. repeat step 2 until there are N students in the new group where N is
           equal to self.group_size.
        4. repeat steps 1-3 until all students have been placed in a group.

        In step 2 above, use the <survey>.score_students method to determine
        the score of each group of students.

        The final group created may have fewer than N members if that is
        required to make sure all students in <course> are members of a group.
        """
        student_tuples = course.get_students()
        students = (list(student_tuples))
        master = Grouping()
        x = students[1]

        while not students != []:
            group_list = []
            if len(master) == 0:
                group_list.append(student_tuples[0])
            else:
                while len(group_list) <= self.group_size and not \
                        len(students) == 0:
                    for student in students:
                        if survey.score_students([student]) > \
                                survey.score_students([x]):
                            x = student
                        elif survey.score_students([student]) == \
                                survey.score_students([x]):
                            if student.id > x.id:
                                x = student
                    students.remove(x)
                    group_list.append(x)
                master.add_group(Group(group_list))
        return master


class WindowGrouper(Grouper):
    """
    A grouper used to create a grouping of students according to their
    answers to a survey. This grouper uses a window search algorithm to create
    groups.

    === Public Attributes ===
    group_size: the ideal number of students that should be in each group

    === Representation Invariants ===
    group_size > 1
    """

    group_size: int


    def make_grouping(self, course: Course, survey: Survey) -> Grouping:
        """
        Return a grouping for all students in <course>.

        Starting with a tuple of all students in <course> obtained by calling
        the <course>.get_students() method, create groups of students using the
        following algorithm:

        1. Get the windows of the list of students who have not already been
           put in a group.
        2. For each window in order, calculate the current window's score as
           well as the score of the next window in the list. If the current
           window's score is greater than or equal to the next window's score,
           make a group out of the students in current window and start again at
           step 1. If the current window is the last window, compare it to the
           first window instead.

        In step 2 above, use the <survey>.score_students to determine the score
        of each window (list of students).

        In step 1 and 2 above, use the windows function to get the windows of
        the list of students.

        If there are any remaining students who have not been put in a group
        after repeating steps 1 and 2 above, put the remaining students into a
        new group.
        """
        students = list(course.get_students())
        s = students.copy()
        master = Grouping()

        while s:
            window = windows(s, self.group_size)
            for i in range(len(window)):
                if i + 1 != len(window):
                    if survey.score_students(window[i]) > \
                            survey.score_students(window[i+1]):
                        x = []
                        for lst in window[i:i+2]:
                            for student in lst:
                                x.append(student)
                                s.remove(student)
                        master.add_group(Group(x))

                else:
                    if survey.score_students(window[i]) > \
                            survey.score_students(window[0]):
                        x = []
                        lst = window[i] + window[0]
                        for student in lst:
                            x.append(student)
                            s.remove(student)
                        master.add_group(Group(x))
        return master