Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

I've just tried to do some code for Treemap. 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: http://www.scipy.org/Cookbook/Matplotlib/TreeMap. 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()
share|improve this question

1 Answer

up vote 5 down vote accepted

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()
share|improve this answer
thank you very much! – nkint Apr 5 '11 at 9:06
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.