patternpythonMinor
TreeMap implementation
Viewed 0 times
implementationtreemapstackoverflow
Problem
I've just tried to do some code for
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
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
Solution
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:
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".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()Code Snippets
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()Context
StackExchange Code Review Q#1644, answer score: 7
Revisions (0)
No revisions yet.