#!/usr/bin/python3
"""Tiny regular expressions.
"""
from collections import namedtuple

def test():
    rea = Lit("a")              # Literally “a”
    assert rea.matches("a")
    assert not rea.matches("b")
    assert not rea.matches("aa")
    assert Lit("b").matches("b")

    bs = Star(Lit("b"))         # Kleene closure, "*" in standard regexps
    assert bs.matches("b")
    assert not bs.matches("a")
    assert bs.matches("bbb")
    assert not bs.matches("bbba")
    assert bs.matches("")

    bsas = Cat(Star(Lit("b")), Star(Lit("a"))) # Catenation
    assert bsas.matches("b")
    assert bsas.matches("bb")
    assert bsas.matches("bbaa")

    # (a|b)*
    abs = Star(Alt(Lit("a"), Lit("b")))
    assert abs.matches("a")
    assert abs.matches("ba")
    assert not abs.matches("c")
    assert abs.matches("abbaba")
    assert not abs.matches("abbaga")

class Regexp:
    def matches(self, s):
        return self.run(s) == ""

class Lit(Regexp, namedtuple("Lit", "contents")):
    def run(self, s):
        if not s.startswith(self.contents):
            return None
        return s[len(self.contents):]

class Star(Regexp, namedtuple("Star", "contents")):
    def run(self, s):
        if s == "":
            return ""
        result = self.contents.run(s)
        if result is None:
            return None
        continuation = self.run(result)
        if continuation is None:
            return result
        return continuation

class Cat(Regexp, namedtuple("Cat", ("a", "b"))):
    def run(self, s):
        result = self.a.run(s)
        if result is None:
            return None
        return self.b.run(result)

class Alt(Regexp, namedtuple("Alt", ("a", "b"))):
    def run(self, s):
        result = self.a.run(s)
        if result is not None:
            return result
        return self.b.run(s)

def search(re, s):
    for i in range(len(s)+1):
        result = re.run(s[i:])
        if result is not None:
            return i, len(s) - len(result)
    return None

if __name__ == '__main__':
    test()