'''Hilbert curve'''

from itertools import (chain, islice)



def hilbertCurve(n):
    '''An SVG string representing a
       Hilbert curve of degree n.
    '''
    w = 1024
    return svgFromPoints(w)(
        hilbertPoints(w)(
            hilbertTree(n)
        )
    )



def hilbertTree(n):
    '''Nth application of a rule to a seedling tree.'''

    
    rule = {
        'a': ['d', 'a', 'a', 'b'],
        'b': ['c', 'b', 'b', 'a'],
        'c': ['b', 'c', 'c', 'd'],
        'd': ['a', 'd', 'd', 'c']
    }

    
    def go(tree):
        c = tree['root']
        xs = tree['nest']
        return Node(c)(
            map(go, xs) if xs else map(
                flip(Node)([]),
                rule[c]
            )
        )
    seed = Node('a')([])
    return list(islice(
        iterate(go)(seed), n
    ))[-1] if 0 < n else seed



def hilbertPoints(w):
    '''Serialization of a tree to a list of points
       bounded by a square of side w.
    '''

    
    vectors = {
        'a': [(-1, 1), (-1, -1), (1, -1), (1, 1)],
        'b': [(1, -1), (-1, -1), (-1, 1), (1, 1)],
        'c': [(1, -1), (1, 1), (-1, 1), (-1, -1)],
        'd': [(-1, 1), (1, 1), (1, -1), (-1, -1)]
    }

    
    def points(d):
        '''Size -> Centre of a Hilbert subtree -> All subtree points
        '''
        def go(xy, tree):
            r = d 

            def deltas(v):
                return (
                    xy[0] + (r * v[0]),
                    xy[1] + (r * v[1])
                )
            centres = map(deltas, vectors[tree['root']])
            return chain.from_iterable(
                map(points(r), centres, tree['nest'])
            ) if tree['nest'] else centres
        return go

    d = w 
    return lambda tree: list(points(d)((d, d), tree))



def svgFromPoints(w):
    '''Width of square canvas -> Point list -> SVG string'''

    def go(xys):
        def points(xy):
            return str(xy[0]) + ' ' + str(xy[1])
        xs = ' '.join(map(points, xys))
        return '\n'.join(
            ['<svg xmlns=',
             f'width= height= viewBox=>',
             f'<path d= ',
             'stroke-width= stroke= fill=/>',
             '</svg>'
             ]
        )
    return go



def main():
    '''Testing generation of the SVG for a Hilbert curve'''
    print(
        hilbertCurve(6)
    )





def Node(v):
    '''Contructor for a Tree node which connects a
       value of some kind to a list of zero or
       more child trees.'''
    return lambda xs: {'type': 'Node', 'root': v, 'nest': xs}



def flip(f):
    '''The (curried or uncurried) function f with its
       arguments reversed.
    '''
    return lambda a: lambda b: f(b)(a)



def iterate(f):
    '''An infinite list of repeated
       applications of f to x.
    '''
    def go(x):
        v = x
        while True:
            yield v
            v = f(v)
    return go



if __name__ == '__main__':
    main()