TreeMap实现

Question

我只是尝试为TreeMap编写一些代码。TreeMap的概念可以找到这里。作为一项练习，我试图在不读这篇文章的情况下找到解决方案。

然后，我发现了这个密码。主要的问题是我错过了算法，我的代码不是那么简单，优雅，简短和干净。我之所以使用OOP，是因为我不知道如何没有它(在大学里，我没有学到C，没有函数式编程，只有OOP)。

另一个问题是，我想要从呈现引擎(没有matplotlib，也许我正在为openGL和pyqt编写一些东西)生成一个没有依赖项的矩形列表，所以我需要一些坐标在0到1之间的矩形。

这是我的代码，我对此并不感到自豪:它过于冗长、多余且不亲吻，也许它还可以更易读：

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()

Answer 1

repr不应该被用作一般的漂亮打印方法。它应该给出一个对象的简短描述，最好是一个看起来像代码的对象。

最好在变名中使用正确的英语，即儿童而不是儿童。

而不是组合许多字符串，使用StringIO

TreeMap.build方法主要涉及一个节点。它确实应该在节点类上。它与TreeMap的唯一交互是矩形。但是，由于您无论如何都是将这些存储在对象上，所以我们将为这些对象提供一个单独的迭代。

一旦我们将构建转移到Node中，TreeMap就什么也不做了，所以我们消除了它。

似乎没有什么好的理由让节点担心自己的深度。

我不喜欢节点构造器。我不认为构造函数应该关注从这种独立格式的转换。格式转换应在其他功能中进行。因为iter_method和size_method只用于这种转换，所以它们应该是参数。

棘手的一点是Node.build函数。您有两个for循环，它们看起来几乎相同。我们可以通过提取每个方向特有的逻辑片段来组合它们。

我的研究结果：

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()