enhanced_grid.py

## @package enhanced_grid 
## @brief Contains 2D and 3D Grid containers that supports extended slicing syntax.
## 
# These classes are provided for rapid prototyping, the methods defined on them might be slow.
# @code
# grid1 = Grid3D(10, 10, 10, 0)
# grid2 = Grid3D(10, 10, 10, 1)
# grid1[0, 0, 0] = grid2[0, 0, 0]
# grid1[0, 0, 2:6:2] = grid2[0, 0, 4:5]
# grid1[0, 0, ...] = grid2[0, 0, ...]
# grid1[0, ..., 0] = grid2[..., 0, 0]
# grid1[..., ..., ...] = grid2[..., ...., ....]
# @endcode
#
# Slicing does not copy elements - an auxiliary window container is created that delegates 
# further operations to the underlying container.
# Note that assignments to slices from the same object might not behave as espected. 
# Parallel assignment also does not always work as expected.
# For example:
#@code
# grid[..., 0], grid[..., 1] = grid[..., 1], grid[..., 0]
#@endcode
# does not correctly swop two rows, but the following does:
#@code
# grid[..., 0], grid[..., 1] = grid[..., 1].clone(), grid[..., 0].clone()
#@endcode
#Strictly speaking, it is necessary only to clone the one object,
#but it is hard to remember which, so it is better to clone both (?).
# 
#@todo Implement a way to use copy containers instead of window containers

from __future__ import division
from random import randint
from math import floor
from math import ceil
from array import array

##@brief A class that works just like a queue or a stack, except
## that a randomly selected element is returned. 
##
# This class is useful for implementing algorithms that gather 
# elements, and need to process them randomly. Something along the 
# lines of:
# 
# @code
# while not rqueue.empty():
#   #generates 3 new elements to process
#   for i in range(3): 
#     rqueue.push(process(rqueue.pop())) 
# @endcode
class RandomQueue:
	## Constructs a new empty RandomQueue
	def __init__(self):		
		## The internal list to store objects.
		self.array = []

	##Returns True if this RandomQueue is empty.	
	def empty(self):
		return len(self.array) <= 0

	## Push a new element into the RandomQueue.
	def push(self, x):
		self.array.append(x)

	## @brief Pops a randomly selected element from the queue. 
	##
	# All elements can be selected equiprobably
	def pop(self):
		n = len(self.array)

		if n <= 0:
			raise IndexError('Cannot pop from emty container!')
		elif n == 1:
			return self.array.pop()
		else:
			i = randint(0, n - 1)
			j = n - 1
			self.array[i], self.array[j] = 	self.array[j], self.array[i]

		return self.array.pop()

## @brief Class that represents a 2D array. 
##
# The following convenient syntax is supported:
# @code
# p = 2, 3 # a coordinate in the grid
# grid[p] = 5
# print grid[p] 
# print grid[2, 3] 
# @endcode
#

def signum(x):
	if x > 0:
		return 1
	elif x < 0:
		return -1
	else:
		return 0

## Truncates a point to integer coordinates.
def int_point_2d(p):
	x, y = p
	return int(x), int(y)

## Truncates a point to integer coordinates.
def int_point_3d(p):
	x, y, z = p
	return int(x), int(y), int(z)

# Every point in the sample set is represented with 
# a 1 in th grid; all other points are represented with 0.
# The returned grid is usefull for producing image data.
def points_to_grid(points, dimensions):
	grid = Grid2D(dimensions, 0)

	for point in points:
		grid[int_point_2d(point)] = 1

	return grid

## Converts a list of points to a 3D grid. 

# Every point in the sample set is represented with 
# a 1 in th grid; all other points are represented with 0.
# The returned grid is usefull for producing image data.
def points_to_grid_3d(points, dimensions):
	grid = Grid3D(dimensions, 0)

	for point in points:
		grid[int_point_3d(point)] = 1

	return grid

def make_grid_1d(width, initial_item=None):
	grid = [initial_item] * width

	return grid

## @brief Makes 2 list of lists.
def make_grid_2d(width, height, initial_item=None):
	grid = [None] * width

	for i in range(width):
		grid[i] = [None] * height

		for j in range(height):
			grid[i][j] = initial_item

	return grid

## @brief Makes 2 list of lists.
def make_grid_3d(width, height, depth, initial_item):
	grid = [None] * width

	for i in range(width):
		grid[i] = [None] * height

		for j in range(height):
			grid[i][j] = [None] * depth

			for k in range(depth):
				grid[i][j][k] = initial_item

	return grid

## @brief Returns an range that can be used to iterate over 
## the slice of the container.
#
# The following snippets are equivalent
#@code
# s = slice(3, 18, 3)
# for i in srange(s):
#	print list[i]
#@endcode
#
#@code
# for item in list[s]:
#	print item
#@endcode
def srange(s, length):
	if s == Ellipsis:
		return range(length)
	else:
		b, e, s = s.indices(length)
		return range(b, e, s)

## @brief Returns true if s is a slice or an Ellipsis.
def is_slice(s):
	return type(s) is slice or s == Ellipsis

## @brief Returns the number of elements this slice will return, provided the provided 
## primary is large enough.
def slice_len(s, length):
	if s == Ellipsis:
		return length

	b, e, s, = s.indices(length)

	tmp = int(ceil((e - b) / s))

	if tmp < 0:
		return 0
	else:
		return min(tmp, length)

	if s.stop > s.start and s.step > 0:
		return (s.stop - s.start) // s.step
	elif s.stop < s.start and s.step < 0:
		return (s.start - s.stop) // -s.step
	else:
		return 0

## @brief Returns a slice that is equivalent to the two slices combined.
##
# The following snippets are equivalent:
#@code
# list[s1][s2]
#@endcode

#@code
# list[slice_mul(s1, s2)]
#@endcode
def slice_mul(slice1, slice2, length):
	if type(slice2) is int:
		if type(slice1) is type(Ellipsis):
			return slice2
		b1, e1, s1 = slice1.indices(length)
		s2 = slice2
		if s2 < 0:
			s2 += length
		if s2 < 0:
			s2 = 0		
		return b1 + s2*s1
	elif type(slice2) is slice:
		if type(slice1) is type(Ellipsis):
			return slice2
		else:
			b1, e1, s1 = slice1.indices(length)
			b2, e2, s2 = slice2.indices(length)			
			b = b1 + b2*s1
			s = s1*s2
			e = min(b1 + e2*s1, e1)

			if e < 0 and s < 0:
				return slice(b, None, s)
			else:
				return slice(b, e,  s)



			b = slice1.start + slice2.start*slice1.step
			s = slice1.step*slice2.step
			return slice(b, min(slice1.start + slice2.stop*slice1.step, slice1.stop), s)
	elif slice2 == Ellipsis:
		return slice1

## @brief Completes this slice for a given length.
##
# The resulting slice will give the same elements for a container of the given length, but
# none of the start, stop, or step attributes will be None. If s is the Ellipses, then 
# the slice (0, length, 1) is returned.
# @deprecated
def complete_slice(s, length):
	return s

## @brief Sub-classes of this container can be used directly.
##
## A principle container will do assignment on a 1D point.
## Assignment of larger chunks is delegated to the AuxilaryContainer
## with the right dimensions.
##
## The enherritance is merely for documentation purposes.
class PrincipleContainer:
	pass

## @brief Sub-classes of this container is used as windows by a
##PrincipleContainer, and should not be used directly!
##
## An AuxiliaryContainer will do assignment a chunk with the same 
## dimensionality as itself, otherwise it delegates it to the underlying
## principle container, which will, in turn, construct the correct 
## AuxiliaryContainer to perform the assignment, or perform it if it is 
## a 1D point.
##
## The enherritance is merely for documentation purposes.
class AuxiliaryContainer:
	pass

##Abstract super class of all grid-like containers.
##These containers are static, that is, once they are created, 
##their dimensions cannot change.
#
# Children of this class must implement
# the attribute __clonetype__, which must 
# hold a callable type that can be constructed
# for clones.
# 
# Children must also implement the iterators
# cell_iter() and index_iter().
class Container:
	##
	##
	# @param dim
	#		The dimensions of this grid
	def __init__(self, dims):
		self.dims = dims

		count = 1

		for dim in dims:
			count *= dim

		self.count = count

	##Test whether two containers have the same dimensions
	##and the same items at equal indices.
	def __eq__(self, other):
		if other == None:
			return False
		if self.dims != other.dims:
			return False

		for cell1, cell2 in zip(self.cell_iter(), other.cell_iter()):
			if cell1 != cell2:
				return False
		return True

	##Equivalent to @code not (self == other) @endcode .
	def __ne__(self, other):
		return not (self == other)

	## Returns the length (1D) or width (nD) of this container.
	#
	# The length of a container is defined such that the length behaves as it would
	# for a list of lists.
	def __len__(self):
		return self.dims[0]

	## @brief Returns the minimum and maximum elements
	## of this grid as a tuple. 
	##
	#This method assumes the grid is filled.
	def min_max(self):		
		cell_iter = self.cell_iter()		
		min = max = cell_iter.next()

		for cell in cell_iter:
			if cell > max:
				max = cell
			elif cell < min:
				min = cell
		return min, max

	def copy_from(self, other):
		for index in self.index_iter():
			self[index] = other[index]

	##Makes a shallow copy of this container.
	#
	#This method constructs an instance of
	#this instance's __clonetype__. In general,
	#if this class is an AuxiliaryContainer,
	#the clone will be a PrincipleContainer
	#of the same dimension.
	def clone(self):
		new_grid = self.__clonetype__(self.dims)		
		new_grid.copy_from(self)

		return new_grid

## Class that implements __str__ and __iter__.
class Container1D (Container):
	def __init__(self, length):
		Container.__init__(self, (length,))
		self.length = length
		self.__clonetype__ = Grid1D

	def __str__(self):    
		#slow...
		glst = []

		for i in range(self.length):
			glst.append(self[i])

		return glst.__repr__()

	def __iter__(self):
		for i in range(self.length):
			yield self[i]
		raise StopIteration

	## @brief Returns the same iterator as __iter__.
	#
	# Provided so that all containers have consistent cell_iter methods.
	def cell_iter(self):
		return self.__iter__()

	## @brief Returns an iterator that iterates over a subgrid of this grid.
	##
	# The iteratir will iterate over all cells x, y in the grid	
	# such that 
	#@code
	# x0 <= x < x1
	# y0 <= y < y1
	#@endcode
	# The iterator does not iterate outside the grid.	
	def window_iter(self, x1, x0):
		for i in range(max(0, x0), min(x1, self.length)):
			yield self[i]
		raise StopIteration

	## @brief Returns an iterator that iterates over a subgrid of this grid.
	##
	# The iteratir will iterate over all cells x, y in the grid	
	# such that 
	#@code
	# x0 <= x < x1
	# y0 <= y < y1
	#@endcode
	# The iterator wraps over the grid. For example, if x is one unit too high 
	# (it is outside the grid to the right), the iterator will return first 
	# cell in that row.
	def wrapped_window_iter(self, x1, x0):
		for i in range(x0, x1):
			yield self[i % self.length]
		raise StopIteration

	## @brief Returns an iterator that iterates over all cells in the square
	## surrounding the given point. 
	##
	#The square is 2*n + 1 units.
	def square_iter(self, x, n):
		return self.window_iter(x - n, x + n + 1)

	def wrapped_square_iter(self, x, n):
		return self.wrapped_window_iter(x - n, x + n + 1)

	## @brief Returns an iterator that iterates over the indeces of this 
	## container.
	##
	# If grid is a 2 by 2 grid, then:
	# @code
	# for p in index_iter(grid):
	# 	print p
	# @endcode
	# will produce 
	# @code
	# 0, 0
	# 0, 1
	# 1, 0
	# 1, 1
	# @endcode
	# This iterator is useful for assigning elements of grids:
	# @code
	# for p in index_iter(grid):
	# 	grid[p] = random()
	# @endcode
	def index_iter(self):
		for i in range(self.length):
			yield i
		raise StopIteration

## Class that implements __str__ and __iter__.
class Container2D (Container):
	def __init__(self, width, height):
		Container.__init__(self, (width, height))
		self.width = width
		self.height = height
		self.__clonetype__ = Grid2D

	def __str__(self):    
		#slow...
		glst = []

		for i in range(self.width):
			gcol = []

			for j in range(self.height):
				gcol.append(self[i, j])

			glst.append(gcol)

		return glst.__repr__()	

	## @brief Returns an iterator that iterates over columns.
	##
	# This iterator is provided so that a Grid2D better emulates a list of 
	# lists, as in the following example:
	#@code
	# 	for col in grid:
	#		for item in col:
	#			process(item)
	#@endcode
	# Use of this iterator is discouraged - it is slow
	def __iter__(self):
		for i in range(self.width):
			yield self[i, ...]
		raise StopIteration

	## @brief Returns an iterator that iterates over all cells in the grid.
	##
	# This allows you to write:
	#@code
	# for cell in cell_iter(grid):
	#   process(cell)
	#@endcode
	def cell_iter(self):
		for i in range(self.width):
			for j in range(self.height):
				yield self[i, j]
		raise StopIteration

	## @brief Returns an iterator that iterates over a subgrid of this grid.
	##
	# The iterator will iterate over all cells x, y in the grid	
	# such that 
	#@code
	# x0 <= x < x1
	# y0 <= y < y1
	#@endcode
	#	
	def window_index_iter(self, p0, p1):
		x0, y0 = p0
		x1, y1 = p1    
		for i in range(max(0, x0), min(x1, self.width)):
			for j in range(max(0, y0), min(y1, self.height)):
				yield (i, j)
		raise StopIteration
	## @brief Returns an iterator that iterates over a subgrid of this grid.
	##
	# The iterator will iterate over all cells x, y in the grid	
	# such that 
	#@code
	# x0 <= x < x1
	# y0 <= y < y1
	#@endcode
	#	
	# The iterator wraps over the grid. For example, if x is one unit too high 
	# (it is outside the grid to the right), the iterator will return the index of the 
	# first cell in that row.
	def wrapped_window_index_iter(self, p0, p1):
		x0, y0 = p0
		x1, y1 = p1    
		for i in range(x0, x1):
			for j in range(y0, y1):
				yield (i % self.width, j % self.height)
		raise StopIteration

	## @brief Returns an iterator that iterates over a subgrid of this grid.
	##
	# The iterator will iterate over all cells x, y in the grid	
	# such that 
	#@code
	# x0 <= x < x1
	# y0 <= y < y1
	#@endcode	
	def window_iter(self, p0, p1):
		x0, y0 = p0
		x1, y1 = p1
		for i in range(max(0, x0), min(x1, self.width)):
			for j in range(max(0, y0), min(y1, self.height)):
				yield self[i, j]
		raise StopIteration	

	## @brief Returns an iterator that iterates over a subgrid of this grid.
	##
	# The iterator will iterate over all cells x, y in the grid	
	# such that 
	#@code
	# x0 <= x < x1
	# y0 <= y < y1
	#@endcode
	#	
	# The iterator wraps over the grid. For example, if x is one unit too high 
	# (it is outside the grid to the right), the iterator will return first 
	# cell in that row.
	def wrapped_window_iter(self, p0, p1):
		x0, y0 = p0
		x1, y1 = p1
		for i in range(x0, x1):
			for j in range(y0, y1):
				yield self[i % self.width, j % self.height]
		raise StopIteration	

	## @brief Returns an iterator that iterates over all cells in the square
	## surrounding the given point. 
	##
	#The square is 2*n + 1 units.
	def square_index_iter(self, p, n):
		x, y = p
		return self.window_index_iter((x - n, y - n), (x + n + 1, y + n +1))
	
	## @brief Returns an iterator that iterates over all cells in the square
	## surrounding the given point. 
	##
	#The square is 2*n + 1 units.
	# The iterator wraps over the grid. For example, if x is one unit too high 
	# (it is outside the grid to the right), the iterator will return first 
	# cell in that row.
	def wrapped_square_index_iter(self, p, n):
		x, y = p
		return self.wrapped_window_index_iter((x - n, y - n), (x + n + 1, y + n +1))


	## @brief Returns an iterator that iterates over all cells in the square
	## surrounding the given point. 
	##
	#The square is 2*n + 1 units.
	def square_iter(self, p, n):
		x, y = p
		return self.window_iter((x - n, y - n), (x + n + 1, y + n +1))

	## @brief Returns an iterator that iterates over all cells in the square
	## surrounding the given point. 
	##
	#The square is 2*n + 1 units.
	# The iterator wraps over the grid. For example, if x is one unit too high 
	# (it is outside the grid to the right), the iterator will return first 
	# cell in that row.
	def wrapped_square_iter(self, p, n):
		x, y = p
		return self.wrapped_window_iter((x - n, y - n), (x + n + 1, y + n +1))

	## @brief Returns an iterator that iterates over the indeces of this 
	## grid as tuples.
	##
	# If grid is a 2 by 2 grid, then:
	# @code
	# for p in index_iter(grid):
	# 	print p
	# @endcode
	# will produce 
	# @code
	# 0, 0
	# 0, 1
	# 1, 0
	# 1, 1
	# @endcode
	# This iterator is useful for assigning elements of grids:
	# @code
	# for p in index_iter(grid):
	# 	grid[p] = random()
	# @endcode
	def index_iter(self):
		for i in range(self.width):
			for j in range(self.height):
				yield i, j
		raise StopIteration

## Class that implements __str__ and __iter__.
class Container3D (Container):
	def __init__(self, width, height, depth):
		Container.__init__(self, (width, height, depth))
		self.width = width
		self.height = height
		self.depth = depth

		self.__clonetype__ = Grid3D

	def __str__(self):    
		#slow...
		glst = []

		for i in range(self.width):
			gcol = []
			for j in range(self.height):
				gslice = []

				for k in range(self.depth):
					gslice.append(self[i, j, k])

				gcol.append(gslice)
			glst.append(gcol)

		return glst.__repr__()

	def __iter__(self):
		for i in range(self.width):
			yield self[i, ..., ...]
		raise StopIteration

	## Returns an iterator that iterates over all cells in the grid
	def cell_iter(self):
		for i in range(self.width):
			for j in range(self.height):
				for k in range(self.depth):
					yield self[i, j, k]
		raise StopIteration

	## @brief Returns an iterator that iterates over the indeces of this 
	## grid as tuples.
	##
	# If grid is a 2 by 2 grid, then:
	# @code
	# for p in index_iter(grid):
	# 	print p
	# @endcode
	# will produce 
	# @code
	# 0, 0
	# 0, 1
	# 1, 0
	# 1, 1
	# @endcode
	# This iterator is useful for assigning elements of grids:
	# @code
	# for p in index_iter(grid):
	# 	grid[p] = random()
	# @endcode
	def index_iter(self):
		for i in range(self.width):
			for j in range(self.height):
				for k in range (self.depth):
					yield i, j, k
		raise StopIteration	

	## @brief Returns an iterator that iterates over a subgrid of this grid.
	##
	# The iterator will iterate over all cells x, y, z in the grid
	# such that 
	#@code
	# x0 <= x < x1
	# y0 <= y < y1
	# z0 <= z < z1
	#@endcode
	#
	def window_iter(self, p0, p1):
		x0, y0, z0 = p0
		x1, y1, z1 = p1

		for i in range(max(0, x0), min(x1, self.width)):
			for j in range(max(0, y0), min(y1, self.height)):
				for k in range(max(0, z0), min(z1, self.depth)):
					yield self[i, j, k]
		raise StopIteration

	## @brief Returns an iterator that iterates over a subgrid of this grid.
	##
	# The iterator will iterate over all cells x, y, z in the grid
	# such that 
	#@code
	# x0 <= x < x1
	# y0 <= y < y1
	# z0 <= z < z1
	#@endcode
	#wrapping around the edges as necessary.
	
	def wrapped_window_iter(self, p0, p1):
		x0, y0, z0 = p0
		x1, y1, z1 = p1

		for i in range(x0, x1):
			for j in range(y0, y1):
				for k in range(z0, z1):
					yield self[i % self.width, j % self.height, k % self.depth]
		raise StopIteration
	## @brief Returns an iterator that iterates over all cells in the square
	##	surrounding the given point. 
	##
	#The cube is 2*n + 1 units.
	def square_iter(self, p, n):
		x, y, z = p
		return self.window_iter(
			(x - n, y - n, z - n), 
			(x + n + 1, y + n +1, z + n +1))
	## @brief Returns an iterator that iterates over all cells in the square
	##	surrounding the given point, wrapping around as necessary.
	##
	#The cube is 2*n + 1 units.
	def wrapped_square_iter(self, p, n):
		x, y, z = p
		return self.wrapped_window_iter(
			(x - n, y - n, z - n), 
			(x + n + 1, y + n +1, z + n +1))

class GridWindow1D (Container1D, AuxiliaryContainer): #Constant y
	def __init__(self, grid, col_slice):
		self.grid = grid
		self.x = complete_slice(col_slice, grid.width)		
		Container1D.__init__(self, slice_len(self.x), grid.width)

	def __getitem__(self, x):
		new_x = slice_mul(self.x, x, self.grid.width)

		return self.grid[new_x]		

	def __setitem__(self, x, item):
		new_x = slice_mul(self.x, x, self.grid.width)

		if type(x) is int:
			self.grid[new_x] = item
		else: #slice!
			for i, item_i in zip(srange(new_x, self.grid.width), item):
				self.grid[i] = item_i

## Class that represent a 2D grid, with enhanced slicing notation.
class Grid1D (Container1D, PrincipleContainer):
	def __init__(self, dims, initial_item = None):
		(width,) = dims
		Container1D.__init__(self, width)
		self.grid = make_grid_1d(width, initial_item)
		self.width = width
	## @brief Returns an iterator that iterates over all cells in the grid.
	##
	# This allows you to write:
	#@code
	# for cell in cell_iter(grid):
	#   process(cell)
	#@endcode
	def cell_iter(self):
		for i in range(self.width):
			yield self.grid[i]
		raise StopIteration

	def __getitem__(self, x):
		if isinstance(x, int):
			return self.grid[x]
		elif is_slice(x):
			GridWindow1D(self, x)
		raise TypeError

	def __setitem__(self, x, item):		
		if type(x) is int:			
			self.grid[x] = item
		elif is_slice(x):
			g = GridWindow1D(self, x)
			g[...] = item
		else:
			raise TypeError

class GridRow2D (Container1D, AuxiliaryContainer): #Constant y
	def __init__(self, grid, col_slice, row):
		self.grid = grid
		self.x = complete_slice(col_slice, grid.width)
		self.y = row

		Container1D.__init__(self, slice_len(self.x, grid.width))

	def __getitem__(self, x):
		new_x = slice_mul(self.x, x, self.grid.width)

		return self.grid[new_x, self.y]		

	def __setitem__(self, x, item):
		new_x = slice_mul(self.x, x, self.grid.width)

		if type(x) is int:
			self.grid[new_x] = item
		else: #slice!
			for i, item_i in zip(srange(new_x, self.grid.width), item):
				self.grid[i, self.y] = item_i

class GridCol2D (Container1D, AuxiliaryContainer): #Constant x
	def __init__(self, grid, col, row_slice):
		self.grid = grid
		self.x = col
		self.y = complete_slice(row_slice, grid.height)

		Container1D.__init__(self, slice_len(self.y, grid.height))

	def __getitem__(self,  y):
		new_y = slice_mul(self.y, y, self.grid.height)

		return self.grid[self.x, new_y]

	def __setitem__(self, y, item):
		new_y = slice_mul(self.y, y, self.grid.height)

		if type(y) is int:			
			self.grid[self.x, new_y] = item
		else: #slice!
			for i, item_i in zip(srange(new_y, self.grid.height), item):
				self.grid[self.x, i] = item_i

class GridWindow2D (Container2D):
	def __init__(self, grid, x, y):
		self.grid = grid
		self.x = complete_slice(x, grid.width)
		self.y = complete_slice(y, grid.height)

		Container2D.__init__(self, slice_len(self.x, grid.width), slice_len(self.y, grid.height))

	def __getitem__(self, p):
		if isinstance(p, int):
			return self[p, ...]			
		x, y = p			

		new_x = slice_mul(self.x, x, self.grid.width)
		new_y = slice_mul(self.y, y, self.grid.height)
		return self.grid[new_x, new_y]

	def __setitem__(self, p, item):
		if isinstance(p, int):
			self[p, ...] = item
		x, y = p
		new_x = slice_mul(self.x, x, self.grid.width)
		new_y = slice_mul(self.y, y, self.grid.height)

		if type(x) is int or type(y) is int:
			#delegate!			
			self.grid[new_x, new_y] = item
		else: #slice!
			for i, item_i in zip(srange(new_x, self.grid.width), item):
				for j, item_j in zip(srange(new_y, self.grid.height), item_i):
					self.grid[i, j] = item_j

	def __repr__(self):    
		#slow...
		glst = []

		for i in range(slice_len(self.x, self.grid.width)):
			gcol = []
			for j in range(slice_len(self.y, self.grid.height)):
				gcol.append(self[i, j])
			glst.append(gcol)

		return glst.__repr__()			

## Class that represent a 2D grid, with enhanced slicing notation.
class Grid2D (Container2D, PrincipleContainer):

	def __init__(self, dims, initial_item = None):
		(width, height) = dims
		Container2D.__init__(self, width, height)
		self.grid = make_grid_2d(width, height, initial_item)
	## @brief Returns an iterator that iterates over all cells in the grid.
	##
	# This allows you to write:
	#@code
	# for cell in cell_iter(grid):
	#   process(cell)
	#@endcode
	def cell_iter(self):
		for i in range(self.width):
			for j in range(self.height):
				yield self.grid[i][j]
		raise StopIteration

	def __getitem__(self, p):
		if isinstance(p, int):
			return self[p, ...]
		x, y = p
		if isinstance(x, int):
			if isinstance(y, int):
				return self.grid[x][y]
			elif is_slice(y):
				return GridCol2D(self, x, y)
		elif is_slice(x):
			if isinstance(y, int):
				return GridRow2D(self, x, y)
			elif is_slice(y):
				return GridWindow2D(self, x, y)

		raise TypeError

	def __setitem__(self, p, item):		
		x, y = p
		if type(x) is int:
			if type(y) is int:
				self.grid[x][y] = item
			elif is_slice(y):
				g = GridCol2D(self, x, y)
				g[...] = item
		elif is_slice(x):
			if type(y) is int:
				g = GridRow2D(self, x, y)
				g[...] = item
			elif is_slice(y):
				g = GridWindow2D(self, x, y)
				g[..., ...] = item
		else:
			raise TypeError

class GridBar3D (Container1D, AuxiliaryContainer): #constant x, y
	def __init__(self, grid, x, y, z):
		self.grid = grid
		self.x = x
		self.y = y
		self.z = complete_slice(z, grid.depth)

		Container1D.__init__(self, slice_len(self.z, grid.depth))

	def __getitem__(self,  z):
		new_z = slice_mul(self.z, z, self.grid.depth)		
		return self.grid[self.x, self.y, new_z]

	def __setitem__(self, z, item):
		new_z = slice_mul(self.z, z, self.grid.depth)

		if type(z) is int:
			self.grid[new_z] = item
		else: #slice!
			for i, item_i in zip(srange(new_z, self.grid.depth), item):
				self.grid[self.x, self.y, i] = item_i	

class GridCol3D (Container1D, AuxiliaryContainer): #constant x, z
	def __init__(self, grid, x, y, z):
		self.grid = grid
		self.x = x
		self.y = complete_slice(y, grid.height)
		self.z = z

		Container1D.__init__(self, slice_len(self.y, grid.height))

	def __getitem__(self,  y):
		new_y = slice_mul(self.y, y, self.grid.height)		
		return self.grid[self.x, new_y, self.z]
	def __setitem__(self, y, item):
		new_y = slice_mul(self.y, y, self.grid.height)

		if type(y) is int:
			self.grid[new_y] = item
		else: #slice!
			for i, item_i in zip(srange(new_y, self.grid.height), item):
				self.grid[self.x, i, self.z] = item_i	

class GridRow3D (Container1D, AuxiliaryContainer): #constant y, z
	def __init__(self, grid, x, y, z):
		self.grid = grid
		self.x = complete_slice(x, grid.width)
		self.y = y
		self.z = z

		Container1D.__init__(self, slice_len(self.x, grid.width))
	def __getitem__(self,  x):
		new_x = slice_mul(self.x, x, self.grid.width)		
		return self.grid[new_x, self.y, self.z]
	def __setitem__(self, x, item):
		new_x = slice_mul(self.x, x, self.grid.width)

		if type(x) is int:
			self.grid[new_x] = item
		else: #slice!
			for i, item_i in zip(srange(new_x, self.grid.width), item):
				self.grid[i, self.y, self.y] = item_i

class GridSliceXY (Container2D, AuxiliaryContainer): #constant z
	def __init__(self, grid, x, y, z):
		self.grid = grid
		self.x = complete_slice(x, grid.width)
		self.y = complete_slice(y, grid.height)
		self.z = z		
		Container2D.__init__(self, slice_len(self.x, grid.width), slice_len(self.y, grid.height))
	def __getitem__(self,  p):
		if isinstance(p, int):
			return self[p, ...]			
		x, y = p	
		new_x = slice_mul(self.x, x, self.grid.width)		
		new_y = slice_mul(self.y, y, self.grid.height)
		return self.grid[new_x, new_y, self.z]

	def __setitem__(self, p, item):
		if isinstance(p, int):
			self[p, ...] = item
		x, y = p	
		new_x = slice_mul(self.x, x, self.grid.width)
		new_y = slice_mul(self.y, y, self.grid.height)

		if type(x) is int or type(y) is int:
			#delegate!
			self.grid[new_x, new_y, self.z] = item
		else: #slice!
			for i, item_i in zip(srange(new_x, self.grid.width), item):
				for j, item_j in zip(srange(new_y, self.grid.height), item_i):
					self.grid[i, j, self.z] = item_j

class GridSliceXZ (Container2D, AuxiliaryContainer): #constant Y
	def __init__(self, grid, x, y, z):
		self.grid = grid
		self.x = complete_slice(x, grid.width)
		self.y = y
		self.z = complete_slice(z, grid.depth)

		Container2D.__init__(self, slice_len(self.x, grid.width), slice_len(self.z, grid.depth))
	def __getitem__(self,  p):
		if isinstance(p, int):
			return self[p, ...]			
		x, z = p			
		new_x = slice_mul(self.x, x, self.grid.width)		
		new_z = slice_mul(self.z, z, self.grid.depth)
		return self.grid[new_x, self.y, new_z]

	def __setitem__(self, p, item):
		if isinstance(p, int):
			return self[p, ...]			
		x, z = p	
		new_x = slice_mul(self.x, x, self.grid.width)
		new_z = slice_mul(self.z, z, self.grid.depth)

		if type(x) is int or type(z) is int:
			#delegate!
			self.grid[new_x, self.y, new_z] = item
		else: #slice!
			for i, item_i in zip(srange(new_x, self.grid.width), item):
				for j, item_j in zip(srange(new_z, self.grid.depth), item_i):
					self.grid[i, self.y, j] = item_j		

class GridSliceYZ (Container2D, AuxiliaryContainer): #constant x
	def __init__(self, grid, x, y, z):
		self.grid = grid
		self.x = x
		self.y = complete_slice(y, grid.height)
		self.z = complete_slice(z, grid.depth)

		Container2D.__init__(self, slice_len(self.y, grid.height), slice_len(self.z, grid.depth))
	def __getitem__(self,  p):
		if isinstance(p, int):
			return self[p, ...]			
		y, z = p	
		new_y = slice_mul(self.y, y, self.grid.height)		
		new_z = slice_mul(self.z, z, self.grid.depth)
		return self.grid[self.x, new_y, new_z]

	def __setitem__(self, p, item):
		if isinstance(p, int):
			self[p, ...] = item
		y, z = p	
		new_y = slice_mul(self.y, y, self.grid.height)
		new_z = slice_mul(self.z, z, self.grid.depth)

		if type(y) is int or type(z) is int:
			#delegate!
			self.grid[self.x, new_y, new_z] = item
		else: #slice!
			for i, item_i in zip(srange(new_y), item):
				for j, item_j in zip(srange(new_z), item_i):
					self.grid[self.x, i, j] = item_j

class GridWindow3D (Container3D, AuxiliaryContainer):
	def __init__(self, grid, x, y, z):
		self.grid = grid
		self.x = complete_slice(x, grid.width)
		self.y = complete_slice(y, grid.height)
		self.z = complete_slice(z, grid.height)	

		Container3D.__init__(self, slice_len(self.x, grid.width), slice_len(self.y, grid.height), slice_len(self.z, grid.depth))
	def __getitem__(self, p):
		if isinstance(p, int):
			return self[p, ..., ...]			
		x, y, z = p	
		new_x = slice_mul(self.x, x, self.grid.width)
		new_y = slice_mul(self.y, y, self.grid.height)
		new_z = slice_mul(self.z, z, self.grid.depth)

		return self.grid[new_x, new_y, new_z]

	def __setitem__(self, p, item):
		if isinstance(p, int):
			self[p, ..., ...] = item
		x, y, z = p	
		new_x = slice_mul(self.x, x, self.grid.width)
		new_y = slice_mul(self.y, y, self.grid.height)
		new_z = slice_mul(self.z, z, self.grid.depth)

		if type(x) is int or type(y) is int or type(z) is int:
			#delegate!
			self.grid[new_x, new_y, self.z] = item
		else: #slice!
			for i, item_i in zip(srange(new_x, self.grid.width), item):
				for j, item_j in zip(srange(new_y, self.grid.height), item_i):
					for k, item_k in zip(srange(new_z, self.grid.depth), item_j):
						self.grid[i, j, k] = item_k

## Class that represent a 3D grid, with enhanced slicing notation.
class Grid3D (Container3D, PrincipleContainer):
	def __init__(self, dims, initial_item = None):
		(width, height, depth) = dims
		Container3D.__init__(self, width, height, depth)
		self.grid = make_grid_3d(width, height, depth, initial_item)

	def __getitem__(self, p):
		if isinstance(p, int):
			return self[p, ..., ...]
		x, y, z = p
		if type(x) is int:
			if type(y) is int:
				if type(z) is int:
					return self.grid[x][y][z]
				elif is_slice(z):
					return GridBar3D(self, x, y, z)
			elif is_slice(y):
				if type(z) is int:
					return GridCol3D(self, x, y, z)
				elif is_slice(z):
					return GridSliceYZ(self, x, y, z)
		elif is_slice(x):
			if type(y) is int:
				if type(z) is int:
					return GridRow3D(self, x, y, z)
				elif is_slice(z):
					return GridSliceXZ(self, x, y, z)
			elif is_slice(y):
				if type(z) is int:
					return GridSliceXY(self, x, y, z)
				elif is_slice(z):
					return GridWindow3D(self, x, y, z)

		raise TypeError

	def __setitem__(self, p, item):
		(x, y, z) = p
		if type(x) is int:
			if type(y) is int:
				if type(z) is int:
					self.grid[x][y][z] = item
				elif is_slice(z):
					g = GridBar3D(self, x, y, z)
					g[...] = item
			elif is_slice(y):
				if type(z) is int:
					g = GridCol3D(self, x, y, z)
					g[...] = item
				elif is_slice(z):
					g = GridSliceYZ(self, x, y, z)
					g[..., ...] = item
		elif is_slice(x):
			if type(y) is int:
				if type(z) is int:
					g = GridRow3D(self, x, y, z)
					g[...] = item
				elif is_slice(z):
					g = GridSliceXZ(self, x, y, z)
					g[..., ...] = item
			elif is_slice(y):
				if type(z) is int:
					g = GridSliceXY(self, x, y, z)
					g[..., ...] = item
				elif is_slice(z):
					g = GridWindow3D(self, x, y, z)
					g[..., ..., ...] = item
		else:
			raise TypeError

class ListGrid3D (Grid3D):
	def __init__(self, dims):
		(width, height, depth) = dims
		Grid3D.__init__(self, (width, height, depth))

		for index in self.index_iter():
			self[index] = []

	## @brief Sets the item at x, y.
	##
	# Use a tuplet (x, y) to access the item.
	def additem(self, p, b):
		(x, y, z) = p
		self[x, y, z].append(b)

class ListGrid2D (Grid2D):
	def __init__(self, dims):
		(width, height) = dims
		Grid2D.__init__(self, (width, height))

		for index in self.index_iter():
			self[index] = []

	## @brief Sets the item at x, y.
	##
	# Use a tuplet (x, y) to access the item.
	def additem(self, p, b):
		(x, y) = p
		self[x, y].append(b)