'''
Created on Jun 2, 2010
@author: wolfgang
'''
import math
import threading
from Queue import Queue
from StringIO import StringIO
AWAKE,ASLEEP=0,1
class GridTree(object):
def __init__(self, dimensions):
self.dimensions = dimensions
l = self.dimensions[0]
if int(math.log(l, 2) % 1) != 0:
raise Exception("Dimensions for GridTree must be powers of 2")
for d in self.dimensions:
if d != l:
raise Exception("Dimensions for GridTree must all be equal")
self.branchBin = Queue(-1)
self.branchBinLock = threading.Lock()
self.leafBin = Queue(-1)
self.leafBinLock = threading.Lock()
span = int(math.floor(self.dimensions[0] * 0.25))
pos = int(math.floor(self.dimensions[0] * 0.5) - 1)
self.root = self.growBranch([pos,pos,pos], None, span)
def getValue(self, coordinates):
return self.root.getValue(coordinates)
def setValue(self, coordinates, value):
#TODO: check bounds, maybe increase grid size
self.root.setValue(coordinates, value)
def growBranch(self, coordinates, parent, span):
if self.branchBin.empty():
return GridTreeBranch(self, coordinates, parent, span)
else:
self.branchBinLock.acquire()
if self.branchBin.empty():
self.branchBinLock.release()
return GridTreeBranch(self, coordinates, parent, span)
else:
branch = self.branchBin.get()
self.branchBinLock.release()
branch.coordinates = coordinates
branch.parent = parent
branch.state = AWAKE
branch.tree = self
branch.span = span
return branch
def growLeaf(self, coordinates, parent):
if self.leafBin.empty():
return GridTreeLeaf(self, coordinates, parent)
else:
self.leafBinLock.acquire()
if self.leafBin.empty():
self.leafBinLock.release()
return GridTreeLeaf(self, coordinates, parent)
else:
leaf = self.leafBin.get()
self.leafBinLock.release()
leaf.coordinates = coordinates
leaf.parent = parent
leaf.state = AWAKE
leaf.tree = self
return leaf
def recycle(self, node):
toReset = []
toReset.append([None, node])
if isinstance(node, GridTreeBranch):
node._getAllChildren_(toReset, node.buds)
for container, node in toReset:
node.reset()
if isinstance(node, GridTreeBranch):
self.branchBin.put(node)
else:
self.leafBin.put(node)
class GridTreeNode(object):
def __init__(self, tree, coordinates, parent):
self.coordinates = coordinates
self.parent = parent
self.tree = tree
self.state = AWAKE
self.lock = threading.Lock()
def reset(self):
self.coordinates = None
self.parent = None
def printTree(self, depth=0):
s = StringIO()
for i in range(depth):
s.write(" ")
s.write(str(self))
print s.getvalue()
class GridTreeBranch(GridTreeNode):
def __init__(self, tree, coordinates, parent, span):
GridTreeNode.__init__(self, tree, coordinates, parent)
self.span = span
#print "Branch created: " + str(self.coordinates), " span: " + str(self.span)
self.buds = self.constructBuds(0)
self.childCount = 0
def __str__(self):
return "Branch: " + str(self.coordinates)
def printTree(self, depth=0):
GridTreeNode.printTree(self, depth)
children = []
self._getAllChildren_(result=children, bud=self.buds, recursive=False)
for container, child in children:
child.printTree(depth + 1)
def reset(self):
GridTreeNode.reset(self)
self.span = 0
self._resetBuds_(self.buds)
self.childCount = 0
def _getAllChildren_(self, result, bud, recursive=True):
"""For all children, create a list of 2 --
Container, Child.
"""
for i in range(0,2):
item = bud[i]
if item is not None:
if isinstance(item, list):
self._getAllChildren_(result, item, recursive)
else:
if isinstance(item, GridTreeBranch) and recursive:
item._getAllChildren_(result, item.buds, recursive)
result.append([bud, item])
def _resetBuds_(self, bud):
"""Return true only if it's a list -- False return
allows us to reset the entry (leaf) to None
"""
if isinstance(bud, list):
for i in range(0,2):
if not self._resetBuds_(bud[i]):
bud[i] = None
return True
else:
return False
def incChildren(self):
#self.lock.acquire()
self.childCount = self.childCount + 1
if self.parent is not None:
self.parent.incChildren()
#self.lock.release()
def decChildren(self, coordinates):
self.childCount = self.childCount - 1
if self.childCount != 0 or self.parent is None:
dest = self._getDestination_(coordinates)
direction = dest[-1]
container, child = self._getChild_(dest)
child.lock.acquire()
if child.childCount == 0:
child.state = ASLEEP
container[direction] = None
self.tree.recycle(child)
child.lock.release()
if self.parent is not None:
self.parent.decChildren(coordinates)
def constructBuds(self, depth):
result = None
if depth < len(self.coordinates):
result = []
for i in range(0,2):
result.append(self.constructBuds(depth + 1))
return result
def _getDestination_(self, coordinates):
dest = []
for i in range(len(coordinates)):
c1 = coordinates[i]
c2 = self.coordinates[i]
if c1 <= c2:
dest.append(0)
else:
dest.append(1)
return dest
def _getChild_(self, dest):
direction = dest[0]
container = self.buds[direction]
for i in range(1, len(dest)):
direction = dest[i]
cursor = container[direction]
if i < len(dest) - 1:
container = cursor
return container, cursor
def getValue(self, coordinates):
dest = self._getDestination_(coordinates)
container, cursor = self._getChild_(dest)
if cursor is None:
return None
else:
return cursor.getValue(coordinates)
def setValue(self, coordinates, value):
#print "Branch:", self.coordinates, "Coords:", coordinates
dest = self._getDestination_(coordinates)
#print "Dest:", dest
container, cursor = self._getChild_(dest)
#print "Cursor:", cursor
#TODO: use factory to create new nodes
if cursor is None:
#TODO: add support for not-power-of-two grids
newcoords = []
for i in range(len(self.coordinates)):
c = self.coordinates[i]
d = dest[i]
if self.span < 1:
nc = c + d
else:
if d == 0:
d = -1
nc = int((self.span) * d) + c
newcoords.append(nc)
#print "newcoords:", newcoords
direction = dest[-1]
if self.span < 1:
node = self.tree.growLeaf(newcoords, self)
#node = GridTreeLeaf(self.tree, newcoords, self)
container[direction] = node
cursor = node
else:
#TODO: round span up
#node = GridTreeBranch(self.tree, newcoords, self, int(self.span * 0.5))
node = self.tree.growBranch(newcoords, self, int(self.span * 0.5))
container[direction] = node
cursor = node
#print "Buds:", self.buds
cursor.setValue(coordinates, value)
class GridTreeLeaf(GridTreeNode):
def __init__(self, tree, coordinates, parent):
GridTreeNode.__init__(self, tree, coordinates, parent)
#print "Leaf created: " + str(self.coordinates)
self.value = None
def __str__(self):
return "Leaf: " + str(self.coordinates)
def setValue(self, coordinates, value):
if coordinates != self.coordinates:
raise Exception("Wrong GridTreeLeaf ("\
+ str(self.coordinates)\
+ ") received value for coordinates ("\
+ str(coordinates) + ")")
if value is None:
self.parent.decChildren(self.coordinates)
elif self.value is None:
self.parent.incChildren()
self.value = value
def getValue(self, coordinates):
if coordinates != self.coordinates:
raise Exception("Wrong GridTreeLeaf ("\
+ str(self.coordinates)\
+ ") received value for coordinates ("\
+ str(coordinates) + ")")
return self.value
def reset(self):
GridTreeNode.reset(self)
self.value = None
def getChildCount(self):
if self.value is None:
return 0
else:
return 1
childCount = property(getChildCount)