# Copyright (c) 2013 Edward Langley
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
# Redistributions of source code must retain the above copyright notice,
# this list of conditions and the following disclaimer.
#
# Redistributions in binary form must reproduce the above copyright
# notice, this list of conditions and the following disclaimer in the
# documentation and/or other materials provided with the distribution.
#
# Neither the name of the project's author nor the names of its
# contributors may be used to endorse or promote products derived from
# this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
# HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
# TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

from __future__ import division
import collections
import random
import numpy

#				5			  #
#							  #
#				|			  #
#				V			  #
#							  #
#			 3 4 6		  #
#			 7 5 5		  #
#			 1 9 5		  #
#							  #
#				|			  #
#				V			  #
#							  #
#	1 4 2  3 6 4  5 7 6 #
#	5 3 3  2 4 5  3 9 5 #
#	3 3 3  4 3 5  7 5 6 #
#							  #
#	5 9 7  . . .  . . . #
#	6 8 5  . . .  . . . #
#	9 7 7  . . .  . . . #
#							  #
#	1 1 1  . . .  . . . #
#	1 1 1  . . .  . . . #
#	1 1 1  . . .  . . . #
PGM_template = """\
P2
%(width)d %(height)d
%(maxval)d
%(data)s
"""

class MapData(collections.MutableMapping):
	def __init__(self, data, base=9):
		self.data = data
		self.base = base
		self.below = [[None for __ in range(base)] for ___ in range(base)]

	@classmethod
	def rand_new(cls, mean, base=9):
		data = numpy.random.normal(mean, max(mean/4,1), (base,base)).astype(int)
		return cls(data,base)

	def get_cell(self, x,y, depth=1):
		cur = self
		if depth > 1:
			below = self.get_below(x,y)
			depth -= 1
			while depth > 1:
				below = below.get_below(0,0)
				depth -= 1
			cur = below
		return cur.data[y,x]

	def get_below(self, x,y):
		below = self.below[y][x]
		if below is None:
			mean = self.get_cell(x,y)
			below = self.below[y][x] = self.rand_new(mean,self.base)
		return below

	def get_all_below(self):
		for y, lis in enumerate(self.below):
			for x, val in enumerate(lis):
				if val is not None: continue
				self.get_below(x,y)
		return numpy.concatenate([numpy.concatenate([x.data for x in l],1) for l in self.below])

	def get_rect_below(self, x,y, w,h):
		tw = w/self.base
		tw = int(numpy.ceil(tw))
		th = h/self.base
		th = int(numpy.ceil(th))
		out = []
		for ny  in range(y,min(len(self.data),y+th)):
			out.append([])
			for nx in range(x,min(len(self.data[0]),x+tw)):
				out[-1].append(self.get_below(nx,ny))

		return numpy.concatenate([numpy.concatenate([x.data for x in l],1) for l in out])[:h,:w]

	def __getitem__(self, key):
		return self.data.__getitem__(key)
	def __delitem__(self, key):
		self.data.__setitem__(key, 0.0)
	def __len__(self):
		return len(self.data)
	def __setitem__(self, key, value):
		self.data.__setitem__(key, value)
	def __iter__(self):
		return iter(self.data)


class Map(object):
	def __init__(self, data, depth, base=9):
		self.data = data
		self.depth = depth
		self.base = base

	@classmethod
	def rand_new(cls, depth,base=9):
		data = MapData.rand_new(numpy.random.randint(0,10),base)
		return cls(data,depth)

	def get_level(self, level):
		cur = self.data
		for idx in range(1, level):
			cur = cur.get_below(0,0)
		return cur.get_rect_below(0,0, self.base**level, self.base**level)

	def to_pgm(self,level):
		level = self.data[level].copy()
		level -= min(l.min() for l in self.data)
		maxval = level.max()
		width = len(level)
		height = len(level[0])
		data = '\n'.join(' '.join(str(c) for c in row) for row in level)
		return PGM_template % dict(width=width,height=height,maxval=maxval,data=data)