from __future__ import annotations

from typing import List, Set, Tuple, Dict


class DepthChoiceGenerator:
    """
    Generates (nonrecursively) all of the combinations of a choose b, where a, b
    are nonnegative integers and a >= b.  The values of a and b are given in the
    constructor, and the sequence of choices is obtained by repeatedly calling
    the next() method.  When the sequence is finished, None is returned.

    A valid combination for the sequence of combinations for a choose b
    generated by this class is an array x[] of b integers i, 0 <= i < a, such
    that x[j] < x[j + 1] for each j from 0 to b - 1.

    Works by calling ChoiceGenerator with increasingly larger values of a.
    """

    def _initialize(self):
        self.diff = self.a - self.b
        self.choiceLocal: List[int] = []

        # Initialize the choice array with successive integers [0 1 2 ...].
        # Set the value at the last index one less than it would be in such
        # a series, ([0 1 2 ... b - 2]) so that on the first call to next()
        # the first combination ([0 1 2 ... b - 1]) is returned correctly.
        for i in range(self.b - 1):
            self.choiceLocal.append(i)
        if self.b > 0:
            self.choiceLocal.append(self.b - 2)

        self.choiceReturned: List[int] = [0 for i in range(self.b)]
        self.begun = False

    def __init__(self, a: int, depth: int):
        """
        Constructs a new choice generator for a choose b. Once this
        initialization has been performed, successive calls to next() will
        produce the series of combinations.  To begin a new series at any time,
        call this init method again with new values for a and b.

        Parameters
        ----------
        a: the number of objects being selected from.
        depth: the maximum number of objects selected.

        Returns
        -------
        DepthChoiceGenerator : DepthChoiceGenerator instance
        """

        if a < 0 or depth < -1:
            raise Exception("Illegal Argument!")

        self.a = a
        self.b = 0
        self.depth = depth

        self.effectiveDepth = depth
        if depth == -1:
            self.effectiveDepth = a
        if depth > a:
            self.effectiveDepth = a

        self._initialize()

    def _fill(self, index: int):
        """
        Fills the 'choice' array, from index 'index' to the end of the array,
        with successive integers starting with choice[index] + 1.

        Parameters
        ----------
        index: the index to begin this incrementing operation.

        Returns
        -------

        """
        self.choiceLocal[index] += 1

        for i in range(index + 1, self.b):
            self.choiceLocal[i] = self.choiceLocal[i - 1] + 1

    def next(self) -> List[int] | None:
        i = self.b

        # Scan from the right for the first index whose value is less than
        # its expected maximum (i + diff) and perform the fill() operation
        # at that index.
        while i > 0:
            i -= 1
            if self.choiceLocal[i] < i + self.diff:
                self._fill(i)
                self.begun = True
                for j in range(self.b):
                    self.choiceReturned[j] = self.choiceLocal[j]
                return self.choiceReturned

        if self.begun:
            self.b += 1

            if self.b > self.effectiveDepth:
                return None

            self._initialize()
            return self.next()
        else:
            self.begun = True
            for j in range(self.b):
                self.choiceReturned[j] = self.choiceLocal[j]
            return self.choiceReturned
