# TreeMap implementation

I've just tried to do some code for TreeMap. The TreeMap concept can be found here. As an exercise I've tried to find the solution without reading the article.

Then, I came across this code. The main problem is that I missed the algorithm, my code is not so simple, elegant, short and clean. And I used OOP because I didn't know how to do without it (at university I learned no C, no functional programming, only OOP).

Another issue is that I wanted to make a list of rectangles with no dependencies from the render engine (no matplotlib, maybe I'm writing something for openGL and pyqt), so I need some Rectangle with coordinates normalized between 0 and 1.

This is my code, which I'm no proud of: it is too verbose, redundant and not KISS, and maybe it could also be a bit more readable:

class Rectangle(object):

def __init__(self, x, y, width, height):
self.x = x
self.y = y
self.width = width
self.height = height

def __repr__(self):
return "Rect - x:{0}, y:{1}, width:{2}, height:{3}".format(self.x, self.y, self.width, self.height)

class Node(object):
iter_method = iter
size_method = int

def __init__(self, content, depth=0):
self.depth = depth
self.childs = []
try:
self.value = Node.size_method(content)
except TypeError:
self.childs = [Node(x, depth+1) for x in Node.iter_method(content)]
self.value = sum(child.value for child in self.childs)

@property
def leaf(self):
return len(self.childs)>0

def __repr__(self):
s = "{0}Node:{1}".format('\t'*self.depth, self.value)
if self.leaf:
s += '\n'+'\n'.join(str(child) for child in self.childs)
return s

class TreeMap(object):

def __init__(self, root):
self.root = root

self.rects = []
self.build(self.root, Rectangle(0,0,1,1))

def build(self, node, rect, horizzontal=True):
node.rect = rect
self.rects.append( rect )

sizes = [child.value for child in node.childs]
total_size = node.value

if horizzontal:
x = 0.0
for child in node.childs:
y = rect.y
w = (child.value*rect.width) / float(total_size)
h = rect.height
self.build(child, Rectangle(x,y,w,h), not horizzontal)
x += w
else:
y = 0.0
for child in node.childs:
x = rect.x
h = (child.value*rect.height) / float(total_size)
w = rect.width
self.build(child, Rectangle(x,y,w,h), not horizzontal)
x += w

import unittest

class Test_TreeMap(unittest.TestCase):

def test_build_depth0(self):
nodes = (2,1,(2,2))

known = (1,     1), (2.0/7, 1), (1.0/7, 1), (4.0/7, 1), (4.0/7, 0.5), (4.0/7, 0.5)

Node.iter_method = iter
Node.size_method = int
root = Node(nodes)

t = TreeMap(root)
widths = tuple((rect.width, rect.height) for rect in t.rects)
self.assertEqual(known, widths)
unittest.main()


repr shouldn't be used as a general pretty print method. It should give a short description of an object, preferably one which looks like code.

Its best to use correct english in variable names, i.e. children not childs.

Rather then combining a lot of strings, use StringIO

The TreeMap.build method is mostly concerned with a node. It should really be on the node class. The only interaction it has with TreeMap is the rectangles. But since you store those on the object anyway, we will provide a seperate iteration for those.

Once we've moved build into Node, TreeMap doesn't do anything, so we eliminate it.

There doesn't seem to be a really good reason for a Node to worry about its own depth.

I don't like the Node constructor. I don't think that a constructor should be concerned with conversion from a seperate format like that. Format conversions should be done in other functions. Since iter_method and size_method are only for that conversion, they should be arguments there

The tricky bit is the Node.build function. You have two for loops which look pretty much the same. We can combine them by pulling the bits of logic unique to each direction out.

My results:

from StringIO import StringIO

class Rectangle(object):

def __init__(self, x, y, width, height):
self.x = x
self.y = y
self.width = width
self.height = height

def __repr__(self):
return "Rectangle({0},{1},{2},{3})".format(
self.x, self.y, self.width, self.height)

def slice(self, horizontal, start, length):
if horizontal:
return Rectangle(self.x + start, self.y, length, self.height)
else:
return Rectangle(self.x, self.y + start, self.width, length)

class Node(object):

def __init__(self, children, value):
self.children = children
self.value = value

@classmethod
def from_nested_tuple(class_, data):
return class_.from_data(data, iter, int)

@classmethod
def from_data(class_, data, iter_method, size_method):
try:
iterable = iter_method(data)
except TypeError:
value = size_method(data)
return class_([], value)
else:
children = [ class_.from_data(item, iter_method, size_method)
for item in iterable]
return Node(children, sum(child.value for child in children))

def __repr__(self):
return "Node< {}, {} children>".format( self.value, len(self.children))

def _pretty_print(self, output, depth):
output.write('\t' * depth)
output.write('Node: {}'.format(self.value))
output.write('\n')
for child in self.children:
child.pretty_print(output, depth + 1)

def pretty_print(self):
output = StringIO()
self._pretty_print(output, 0)
return output.get_value()

def build(self, rect, horizontal=True):
self.rect = rect

sizes = [child.value for child in self.children]
total_size = self.value

if horizontal:
space = rect.width
else:
space = rect.height

position = 0.0
for child in self.children:
length = child.value * space
child.build( rect.slice(horizontal, position, length),
not horizontal)
position += length

def rectangles(self):
yield self.rect
for child in self.children:
for rect in child.rectangles():
yield rect

import unittest

class Test_TreeMap(unittest.TestCase):

def test_build_depth0(self):
nodes = (2,1,(2,2))

known = (1, 1), (2.0/7, 1), (1.0/7, 1), (4.0/7, 1), (4.0/7, 0.5), (4.0/7, 0.5)

Node.iter_method = iter
Node.size_method = int
root = Node.from_nested_tuple(nodes)
root.build( Rectangle(0,0,1,1) )

widths = tuple((rect.width, rect.height) for rect in root.rectangles())
self.assertEqual(known, widths)
unittest.main()

• going farther in the project moving the recursion to contructor the tree in a separate method (from_data) and not in constructor is revealed a very useful advice! – nkint Apr 5 '11 at 12:22