"""Functions and classes related to the generation and traversal of the map.

"""
from . import Ifc, Region, Utl, Monster, g
from .data import Nodes, Species, Items
import sys, collections, operator

DIRS = ((0, -1), (1, 0), (0, 1), (-1, 0))
_NORTH, _EAST, _SOUTH, _WEST = DIRS
NORTH, EAST, SOUTH, WEST = range(4)
_DIRS = 'north east south west'.split()

class Grid(object):
    def __init__(self):
        self.grid = collections.defaultdict(lambda: None)
    
    def __getitem__(self, i):
        return self.grid[tuple(i)]
    def __setitem__(self, i, node):
        self.grid[tuple(i)] = node
    
    @property
    def link_integrity(self):
        for node in self.grid.values():
            if node is None: continue
            if node.north and node is not node.north.south:
                return node
            if node.south and node is not node.south.north:
                return node
            if node.east and node is not node.east.west:
                return node
            if node.west and node is not node.west.east:
                return node
    
    @property
    def max_sizes(self):
        return [max(x) + 1 for x in zip(*self.grid.keys())]
    @property
    def min_sizes(self):
        return map(min, zip(*self.grid.keys()))

def rotate( odir, steps ):
    return (odir + steps) % 4

def posop(l1, l2, op=operator.add):
    return map(op, l1, l2)

def distance( n1, n2 ):
    y1, x1 = n1.pos
    y2, x2 = n2.pos
    return ((x2 - x1)**2 + (y2 - y1)**2)**.5

def Dijkstra(start, end=None):
    d = {}
    p = {}
    q = Utl.priorityDictionary()
    q[start] = 0
    for v in q:
        d[v] = q[v]
        if v is end: break
        for w in [v.north, v.south, v.east, v.west]:
            if not w: continue
            vwLength = d[v] + 1
            if w in d:
                if vwLength < d[w]:
                    raise ValueError, "Dijkstra: found better path to already-final vertex"
            elif w not in q or vwLength < q.get(w, 0):
                q[w] = vwLength
                p[w] = v
    return d, p

class Mole(object):
    def __init__( self, startroom=None, *xparams ):
        self.startroom = startroom
        self.xinit( *xparams )
    def xinit( self, *params ): pass
    def tunnel( self ): pass

class TraversalMole(Mole):
    def tunnel(self):
        if self.startroom: 
            start = self.startroom
        else:
            start = self.grid[self.pos]
        self.lastnode = None
        self.traversed = []
        self.deadends = []
        phase = not start.trav
        stack = [(start, 0, '*')]
        self.deepest = 0
        while stack:
            self.deepest = max(self.deepest, len(stack))
            cnode, depth, direction = stack.pop()
            if self.maxdepth and depth >= self.maxdepth:
                continue
            self.traversed.append( cnode )
            if cnode.countexits() == 1 and not cnode.special_symbol and cnode.region == 0:
                self.deadends.append(cnode)
            cnode.trav = phase
            if cnode.north:
                if (self.anticurvature and direction in 'n*') or not self.anticurvature:
                    if cnode.north.trav != phase: stack.append(( cnode.north, depth + 1, 'n' ))
            if cnode.south:
                if (self.anticurvature and direction in 's*') or not self.anticurvature:
                    if cnode.south.trav != phase: stack.append(( cnode.south, depth + 1, 's' ))
            if cnode.east:
                if (self.anticurvature and direction in 'e*') or not self.anticurvature:
                    if cnode.east.trav != phase: stack.append(( cnode.east, depth + 1, 'e' ))
            if cnode.west:
                if (self.anticurvature and direction in 'w*') or not self.anticurvature:
                    if cnode.west.trav != phase: stack.append(( cnode.west, depth + 1, 'w' ))
    def xinit(self, maxdepth=0, anticurvature=False, grid={}, pos=(0, 0)):
        self.maxdepth = maxdepth
        self.anticurvature = anticurvature
        self.grid = grid
        self.pos = tuple(pos)
    def cleanup(self, state=False):
        for x in self.traversed:
            x.trav = state

class PathMole(Mole):
    def tunnel(self):
        import collections
        dirty = collections.deque(g.nodes)
        dirty_set = set(g.nodes)
        iterations, mdepth = 0, len(dirty)
        while dirty:
            cur = dirty.popleft()
            try:
                dirty_set.remove(cur)
            except KeyError:
                continue
            for n in [cur.north, cur.south, cur.east, cur.west]:
                if not n: continue
                dirtied = False
                if cur not in n.p_distance:
                    n.p_distance[cur] = 1
                    n.p_nodes[cur] = cur
                    dirtied = True
                for _n, d in cur.p_distance.items():
                    if _n not in n.p_distance or d + 1 < n.p_distance[_n]:
                        n.p_distance[_n] = d + 1
                        n.p_nodes[_n] = cur
                        dirtied = True
                if n in dirty_set:
                    if not dirtied: dirty_set.remove(n)
                elif dirtied: 
                    dirty.append(n)
                    dirty_set.add(n)
            iterations += 1
            mdepth = min(mdepth, len(dirty))
            if iterations % 20 == 0:
                sys.stdout.write('%-4d/%-4d %-6d' % (mdepth, len(dirty), iterations))
                sys.stdout.flush()
                sys.stdout.write('\x1b[16D')
        sys.stdout.write('%s iterations' % iterations)

class DisplayMole( Mole ):
    def tunnel( self ):
        start = self.startroom
        self.lastnode = None
        self.traversed = []
        phase = not start.trav
        stack = [(start, 0, '*', self.w / 2, self.h / 2)]
        self.deepest = 0
        ret = [[' '] * self.w for n in xrange(self.h)]
        while stack:
            self.deepest = max(self.deepest, len(stack))
            cnode, depth, direction, x, y = stack.pop()
            if self.maxdepth and depth >= self.maxdepth:
                continue
            self.traversed.append( cnode )
            if ret[y][x] == ' ':
                if g.player.here is cnode:
                    ret[y][x] = Ifc.color(Ifc.INVERSE) + cnode.unbiased_character() + Ifc.color()
                elif self.omni or cnode.visited:
                    ret[y][x] = Ifc.color(cnode.color) + cnode.character() + Ifc.color()
                else:
                    ret[y][x] = 'a'
            cnode.trav = phase
            cnode.seen = True
            if self.omni: cnode.visited = True
            if cnode.north:
                if ((self.anticurvature and direction in 'n*') or not self.anticurvature \
                or self.omni or cnode.north.seen) and y > 0 \
                and (cnode.north.region == self.region or cnode.north.bridge):
                    if cnode.north.trav != phase: stack.append((cnode.north, \
                    depth + (not cnode.north.visited), 'n', x, y - 1))
            if cnode.south:
                if ((self.anticurvature and direction in 's*') or not self.anticurvature \
                or self.omni or cnode.south.seen) and y < self.h - 1 \
                and (cnode.south.region == self.region or cnode.south.bridge):
                    if cnode.south.trav != phase: stack.append((cnode.south, \
                    depth + (not cnode.south.visited), 's', x, y + 1))
            if cnode.east:
                if ((self.anticurvature and direction in 'e*') or not self.anticurvature \
                or self.omni or cnode.east.seen) and x < self.w - 1 \
                and (cnode.east.region == self.region or cnode.east.bridge):
                    if cnode.east.trav != phase: stack.append((cnode.east, \
                    depth + (not cnode.east.visited), 'e', x + 1, y))
            if cnode.west:
                if ((self.anticurvature and direction in 'w*') or not self.anticurvature \
                or self.omni or cnode.west.seen) and x > 0 \
                and (cnode.west.region == self.region or cnode.west.bridge):
                    if cnode.west.trav != phase: stack.append((cnode.west, \
                    depth + (not cnode.west.visited), 'w', x - 1, y))
        return '\n'.join([''.join(x) for x in ret])
    def xinit(self, height, width, maxdepth=0, anticurvature=False, region=0, omniscient=False):
        self.maxdepth = maxdepth
        self.anticurvature = anticurvature
        self.w = width
        self.h = height
        self.region = region
        self.omni = omniscient
    def cleanup(self, state=False):
        for x in self.traversed:
            x.trav = state

class DiggingMole( Mole ):
    def xinit(self, grid, params, pos=(0, 0), life=32, dir=2, endnode=None):
        self.grid = grid
        self.pos = tuple(pos)
        self.life = life
        self.dir = dir
        self.endnode = endnode
        self.params = params
    def tunnel(self):
        p = self.params
        w, h = p['map_width'], p['map_height']
        hold = rooms = i = 0
        setlink = False
        count = p['switchlen']
        freq = p['corrchance']
        nodes = []
        while rooms < self.life:
            i += 1
            oldnode = self.grid[self.pos]
            self.pos = posop(self.pos, DIRS[self.dir])
            x, y = self.pos
            hold = 2
            if x == 0:
                self.dir = 1
            elif y == 0:
                self.dir = 2
            elif x == w - 1:
                self.dir = 3
            elif y == h - 1:
                self.dir = 0
            else:
                hold = 0
            hold -= 1
            if hold <= 0:
                newnode = self.grid[self.pos]
                setlink = False
                if not newnode:
                    rooms += 1
                    if rooms == self.life and self.endnode: 
                        newnode = self.endnode
                        newnode.x, newnode.y = newnode.pos = self.pos
                    elif Utl.rn(1000) < p['special_chance']:
                        newnode = Utl.rn_seq(Nodes.non_unique_special_nodes)(self.pos)
                    else: 
                        newnode = Nodes.PlainNode(self.pos)
                        newnode.tunnel = Utl.rn(1000) < p['tunnel_chance']
                        if Utl.rn(1000) < p['item_chance']:
                            newnode.add(Utl.rn_seq(Items.all_items).make())
                        if Utl.rn(1000) < p['monster_chance']:
                            newnode.add(Monster.good_mon(self.life * p['difficulty_slope'] + p['initial_difficulty']).make())
                    self.grid[self.pos] = newnode
                    nodes.append(newnode)
                    setlink = True
                else:
                    if newnode.countexits() < 2 or Utl.rn(p['gridchance']) == 0:
                        setlink = True
                if setlink:
                    if self.dir == 0:
                        if oldnode: oldnode.north = newnode
                        newnode.south = oldnode
                    elif self.dir == 1:
                        if oldnode: oldnode.east = newnode
                        newnode.west = oldnode
                    elif self.dir == 2:
                        if oldnode: oldnode.south = newnode
                        newnode.north = oldnode
                    elif self.dir == 3:
                        if oldnode: oldnode.west = newnode
                        newnode.east = oldnode
                count -= 1
                if count <= 0:
                    count = p['switchlen']
                    freq = (p['randchance'] + p['corrchance']) - freq
                if g.rng.randint(0, freq) == 0:
                    self.dir = g.rng.randint(0, 3)
        return (nodes, i)

def genmap():
    grid = Grid()
    _w = _h = g.config['mole_life'] + g.config['mole_vlife']
    center = Nodes.BoilerRoom()
    grid[_w, _h] = center
    life = lambda: g.config['mole_life'] + Utl.rn(-g.config['mole_vlife'])
    
    en_config = g.config.copy()
    en_config.update(g.config['entrance_config'])
    en = Nodes.Entrance()
    m = DiggingMole(center, grid, en_config, (_w, _h), life(), NORTH, en)
    nodes, steps = m.tunnel()
    
    lab = Nodes.PlainNode()
    m = DiggingMole(center, grid, g.config, (_w, _h), life(), SOUTH, lab)
    nodes, steps = m.tunnel()
    
    hall = Nodes.ChampionHall()
    m = DiggingMole(center, grid, g.config, (_w, _h), life(), EAST, hall)
    nodes, steps = m.tunnel()
    
    tower = Nodes.ProgrammerTower()
    m = DiggingMole(center, grid, g.config, (_w, _h), life(), WEST, tower)
    nodes, steps = m.tunnel()
    
    g.grid = grid
    
    gen = Utl.gen_shuffle(g.nodes)
    while lab.countexits() == 4:
        lab = gen.next()
    lab = Region.RegionBridge(src=lab)
    lab.bridge_region = 1
    grid[lab.pos] = lab
    from .regions.ZeiusRegion import ZeiusRegion
    Region.gen_region(lab, 1, ZeiusRegion)
    g.regions.append(('ZeiusRegion', lab))
    
    m = TraversalMole(None, 0, False, grid, (_w, _h + 1))
    m.tunnel()
    g.deadends = m.deadends
    m.cleanup()
    
    return en

def genregions():
    for e, r in enumerate(g.config['regions']):
        start = g.deadend()
        start = Region.RegionBridge(src=start)
        start.bridge_region = e + 2
        g.grid[start.pos] = start
        reg_module = __import__('th.regions.' + r, fromlist=[None])
        Region.gen_region(start, e + 2, getattr(reg_module, r))
        g.regions.append((r, start))

def shownodes(_grid, l, h):
    x_ = map(lambda x: x.pos[0], l)
    y_ = map(lambda x: x.pos[1], l)
    l_, h_ = l[:], h[:]
    if l:
        x1, x2 = min(x_), max(x_)
        y1, y2 = min(y_), max(y_)
    else:
        x1, y1 = msize(_grid)
        x2, y2 = size(_grid)
    try:
        sys.stdout.write('\033(0')
        for y in xrange(y1, y2 + 1):
            for x in xrange(x1, x2 + 1):
                s = ' '
                n = _grid[(x, y)]
                if n and (n in l_ or not l):
                    s = n.character()
                    if l_: l_.remove(n)
                    if n in h_:
                        s = Ifc.color(Ifc.BRIGHT_MAGENTA) + s + Ifc.color()
                        h_.remove(n)
                sys.stdout.write(s)
            print
    finally:
        sys.stdout.write('\033(B')

def showseen(_grid):
    x1, y1 = _grid.min_sizes
    x2, y2 = _grid.max_sizes
    w, h = x2 - x1, y2 - y1
    try:
        sys.stdout.write('\033(0')
        sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'l' + 'q' * w + 'k' + Ifc.color())
        print
        for y in xrange(y1, y2):
            sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'x' + Ifc.color())
            for x in xrange(x1, x2):
                s = ' '
                n = _grid[(x, y)]
                if n:
                    if g.player.here is n: 
                        s = Ifc.color(Ifc.INVERSE) + n.unbiased_character() + Ifc.color()
                    elif g.player.here.region == n.bridge_region and n.bridge and n.visited:
                        s = Ifc.color(Ifc.INVERSE) + n.character() + Ifc.color()
                    elif n.visited: s = Ifc.color(n.color) + n.character() + Ifc.color()
                    elif n.seen: s = 'a'
                sys.stdout.write(s)
            sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'x' + Ifc.color())
            print
        sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'm' + 'q' * w + 'j' + Ifc.color())
        print
    finally:
        sys.stdout.write('\033(B')

def showall(_grid):
    x1, y1 = _grid.min_sizes
    x2, y2 = _grid.max_sizes
    w, h = x2 - x1, y2 - y1
    try:
        sys.stdout.write('\033(0')
        sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'l' + 'q' * w + 'k' + Ifc.color())
        print
        for y in xrange(y1, y2):
            sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'x' + Ifc.color())
            for x in xrange(x1, x2):
                s = ' '
                n = _grid[(x, y)]
                if n:
                    if g.player.here is n: 
                        s = Ifc.color(Ifc.INVERSE) + n.unbiased_character() + Ifc.color()
                    elif g.player.here.region == n.bridge_region and n.bridge and n.visited:
                        s = Ifc.color(Ifc.INVERSE) + n.character() + Ifc.color()
                    else: 
                        s = n.character() + Ifc.color()
                        if n.mons: s = Ifc.color(Ifc.INVERSE) + s
                sys.stdout.write(s)
            sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'x' + Ifc.color())
            print
        sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'm' + 'q' * w + 'j' + Ifc.color())
        print
    finally:
        sys.stdout.write('\033(B')

def show_map(height=6, width=10, maxdepth=5, anticurve=True, omni=False, border=False):
    m = DisplayMole(g.player.here, height, width, maxdepth, anticurve, g.player.here.region, omni)
    try:
        sys.stdout.write('\033(0')
        if border: 
            sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'l' + 'q' * width + 'k\n' + Ifc.color())
        cache = m.tunnel().split('\n')
        for l in cache:
            if border: 
                sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'x' + Ifc.color())
            sys.stdout.write(l)
            if border: 
                sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'x' + Ifc.color())
            print
        if border: 
            sys.stdout.write(Ifc.color(Ifc.BRIGHT_RED) + 'm' + 'q' * width + 'j' + Ifc.color())
    finally:
        sys.stdout.write('\033(B')
    m.cleanup()
    print