_s2_options = {
    "a": (
        (["a", "t", "i", "o", "n", "a", "l"], ["a", "t", "e"]),
        (["t", "i", "o", "n", "a", "l"], ["t", "i", "o", "n"]),
    ),
    "c": (
        (["e", "n", "c", "i"], ["e", "n", "c", "e"]),
        (["a", "n", "c", "i"], ["a", "n", "c", "e"]),
    ),
    "e": ((["i", "z", "e", "r"], ["i", "z", "e"]),),
    "l": (
        (["b", "l", "i"], ["b", "l", "e"]),
        (["a", "l", "l", "i"], ["a", "l"]),
        (["e", "n", "t", "l", "i"], ["e", "n", "t"]),
        (["e", "l", "i"], ["e"]),
        (["o", "u", "s", "l", "i"], ["o", "u", "s"]),
    ),
    "o": (
        (["i", "z", "a", "t", "i", "o", "n"], ["i", "z", "e"]),
        (["a", "t", "i", "o", "n"], ["a", "t", "e"]),
        (["a", "t", "o", "r"], ["a", "t", "e"]),
    ),
    "s": (
        (["a", "l", "i", "s", "m"], ["a", "l"]),
        (["i", "v", "e", "n", "e", "s", "s"], ["i", "v", "e"]),
        (["f", "u", "l", "n", "e", "s", "s"], ["f", "u", "l"]),
        (["o", "u", "s", "n", "e", "s", "s"], ["o", "u", "s"]),
    ),
    "t": (
        (["a", "l", "i", "t", "i"], ["a", "l"]),
        (["i", "v", "i", "t", "i"], ["i", "v", "e"]),
        (["b", "i", "l", "i", "t", "i"], ["b", "l", "e"]),
    ),
    "g": ((["l", "o", "g", "i"], ["l", "o", "g"]),),
}


_s3_options = {
    "e": (
        (["i", "c", "a", "t", "e"], ["i", "c"]),
        (["a", "t", "i", "v", "e"], []),
        (["a", "l", "i", "z", "e"], ["a", "l"]),
    ),
    "i": ((["i", "c", "i", "t", "i"], ["i", "c"]),),
    "l": ((["i", "c", "a", "l"], ["i", "c"]), (["f", "u", "l"], [])),
    "s": ((["n", "e", "s", "s"], []),),
}

_s4_endings = {
    "a": (["a", "l"],),
    "c": (["a", "n", "c", "e"], ["e", "n", "c", "e"]),
    "e": (["e", "r"],),
    "i": (["i", "c"],),
    "l": (["a", "b", "l", "e"], ["i", "b", "l", "e"]),
    "n": (
        ["a", "n", "t"],
        ["e", "m", "e", "n", "t"],
        ["m", "e", "n", "t"],
        ["e", "n", "t"],
    ),
    # handle 'o' separately
    "s": (["i", "s", "m"],),
    "t": (["a", "t", "e"], ["i", "t", "i"]),
    "u": (["o", "u", "s"],),
    "v": (["i", "v", "e"],),
    "z": (["i", "z", "e"],),
}


class Stemmer(object):
    def __init__(self, b):
        self.b = list(b)
        self.k = len(b) - 1
        self.j = 0

    def cons(self, i):
        """ True iff b[i] is a consonant """
        if self.b[i] in "aeiou":
            return False
        elif self.b[i] == "y":
            return True if i == 0 else not self.cons(i - 1)
        return True

    def m(self):
        n = i = 0
        while True:
            if i > self.j:
                return n
            if not self.cons(i):
                break
            i += 1
        i += 1
        while True:
            while True:
                if i > self.j:
                    return n
                if self.cons(i):
                    break
                i += 1

            i += 1
            n += 1

            while True:
                if i > self.j:
                    return n
                if not self.cons(i):
                    break
                i += 1
            i += 1

    def vowel_in_stem(self):
        """ True iff 0...j contains vowel """
        for i in range(0, self.j + 1):
            if not self.cons(i):
                return True
        return False

    def doublec(self, j):
        """ True iff j, j-1 contains double consonant """
        if j < 1 or self.b[j] != self.b[j - 1]:
            return False
        return self.cons(j)

    def cvc(self, i):
        """ True iff i-2,i-1,i is consonant-vowel consonant
        and if second c isn't w,x, or y.
        used to restore e at end of short words like cave, love, hope, crime
        """
        if (
            i < 2
            or not self.cons(i)
            or self.cons(i - 1)
            or not self.cons(i - 2)
            or self.b[i] in "wxy"
        ):
            return False
        return True

    def ends(self, s):
        length = len(s)
        """ True iff 0...k ends with string s """
        res = self.b[self.k - length + 1 : self.k + 1] == s
        if res:
            self.j = self.k - length
        return res

    def setto(self, s):
        """ set j+1...k to string s, readjusting k """
        length = len(s)
        self.b[self.j + 1 : self.j + 1 + length] = s
        self.k = self.j + length

    def r(self, s):
        if self.m() > 0:
            self.setto(s)

    def step1ab(self):
        if self.b[self.k] == "s":
            if self.ends(["s", "s", "e", "s"]):
                self.k -= 2
            elif self.ends(["i", "e", "s"]):
                self.setto(["i"])
            elif self.b[self.k - 1] != "s":
                self.k -= 1
        if self.ends(["e", "e", "d"]):
            if self.m() > 0:
                self.k -= 1
        elif (
            self.ends(["e", "d"]) or self.ends(["i", "n", "g"])
        ) and self.vowel_in_stem():
            self.k = self.j
            if self.ends(["a", "t"]):
                self.setto(["a", "t", "e"])
            elif self.ends(["b", "l"]):
                self.setto(["b", "l", "e"])
            elif self.ends(["i", "z"]):
                self.setto(["i", "z", "e"])
            elif self.doublec(self.k):
                self.k -= 1
                if self.b[self.k] in "lsz":
                    self.k += 1
            elif self.m() == 1 and self.cvc(self.k):
                self.setto(["e"])

    def step1c(self):
        """ turn terminal y into i if there's a vowel in stem """
        if self.ends(["y"]) and self.vowel_in_stem():
            self.b[self.k] = "i"

    def step2and3(self):
        for end, repl in _s2_options.get(self.b[self.k - 1], []):
            if self.ends(end):
                self.r(repl)
                break

        for end, repl in _s3_options.get(self.b[self.k], []):
            if self.ends(end):
                self.r(repl)
                break

    def step4(self):
        ch = self.b[self.k - 1]

        if ch == "o":
            if not (
                (self.ends(["i", "o", "n"]) and self.b[self.j] in "st")
                or self.ends(["o", "u"])
            ):
                return
        else:
            endings = _s4_endings.get(ch, [])
            for end in endings:
                if self.ends(end):
                    break
            else:
                return

        if self.m() > 1:
            self.k = self.j

    def step5(self):
        self.j = self.k
        if self.b[self.k] == "e":
            a = self.m()
            if a > 1 or a == 1 and not self.cvc(self.k - 1):
                self.k -= 1
        if self.b[self.k] == "l" and self.doublec(self.k) and self.m() > 1:
            self.k -= 1

    def result(self):
        return "".join(self.b[: self.k + 1])

    def stem(self):
        if self.k > 1:
            self.step1ab()
            self.step1c()
            self.step2and3()
            self.step4()
            self.step5()
        return self.result()