метод перечисления питонического дерева с использованием генератора - PullRequest
Новая
       13

метод перечисления питонического дерева с использованием генератора

1 голос
/ 16 октября 2011

Я на самом деле использую Jython и довольно плохо знаком с Python: ...

Когда я использую javax.swing.tree.DefaultMutableTreeNode, я могу просто перейти на deep / breadthFirstEnumeration () ...

Но если я делаю что-то с деревом DOM (например, из XML), такого эквивалента нет ... но меня поражает, что должен быть очень элегантный и мощный способ сделать это в Python/ Jython с использованием рекурсивного генератора.

Надеюсь, что я хочу, это наиболее общее назначение служебных методов, которые по существу будут выполнять перечисление с любым типом объекта дерева, который вы можете бросить в него ... поэтому вам, возможно, придется предоставить метод, который дает вампотомки данного узла ... в случае org.w3c.dom.Node это будет getChildNodes () ... тогда вам может понадобиться второй необязательный параметр, который будет указывать глубину или ширину ...

К моему удивлению, я не смог найти простой ответ, просто погуглив или посмотрев, например, сюда.

Ответы [ 2 ]

2 голосов
/ 17 октября 2011

AFAIK, встроенной реализации нет. Очень простое решение было бы: 

import collections

def depth_first_search(node, get_children, depth=0):
    yield node, depth
    for child in get_children(node):
        # In the upcoming Python 3.3, the following can be written as
        # yield from depth_first_search(child, get_children, depth + 1)
        for n, d in depth_first_search(child, get_children, depth + 1):
            yield n, d

def breadth_first_search(node, get_children, depth=0):
    queue = collections.deque([(node, depth)])
    while queue:
        node, depth = queue.popleft()
        queue.extend((n, depth + 1) for n in get_children(node))
        yield node, depth

Тогда вы можете легко использовать их следующим образом: 

def dom_get_children(node):
    nodeList = node.getNodeList()
    for i in range(nodeList.getLength()):
        yield nodeList.item(i)

for node, depth in depth_first_search(some_dom_element, dom_get_children):
    # do something
0 голосов
/ 17 октября 2011

спасибо ... пока я ждал, я пытался решить это сам ...

отказ от ответственности: я написал это до того, как Фердинанд придумал окончательную версию своего превосходного ответа

на самом деле ваше решение, по-видимому, отлично работает для дерева, состоящего из обычных списков Python ... к сожалению, org.w3c.dom.Node особенно "тупой" ... getChildNodes () фактически создает объект с именем NodeList, который, очевидно, является списком (Java Array) какого-то рода, остается герметически закрытым от самоанализа ... в частности, dir () скажет вам, что класс его поля "childNodes" - это org.apache.xerces.dom.DeferredElementImpl "... и мой опыт показывает, что с чем-то, заканчивающимся на" Impl ", играть будет не очень весело ...

Поэтому я, очевидно, не нашел способа передать метод в качестве параметра и вызвать его ... даже с более податливым Python-подобным классом. В настоящее время мне не ясно, как вы вызываете метод, который вы передаете в качестве параметра ... в любом случае ...

Итак, ниже представлены мои 3 предложения, довольно очевидные: 1) глубина вначале 2) выбор глубины или ширины вначале 3) то же самое, но с доставкой чего-либо с указанием глубины (так что вы можете форматировать распечатки) например). С решением № 3 я был вынужден создать новый класс, к сожалению, потому что я обнаружил, что было невозможно, например, добавить атрибут к объекту Node ... очевидно, у Jython есть ограничения и "примеси" по сравнению с Python. Я знаю, что есть модули Python для работы с XML и т. Д. ... мы рассмотрим это в свое время. (NB, конечно, один из замечательных аспектов Jython заключается в том, что вы можете постепенно переходить с Java на Python).

Было бы интересно, если кто-нибудь из опытных людей Python / Jython имеет какие-либо комментарии ...

  1. только для глубины: 

    def depthFirstTreeEnumeration( node ):
  nodeList = node.getChildNodes()
  for i in range( nodeList.getLength()):
    childNode = nodeList.item( i )
    yield childNode
    for item in depthFirstTreeEnumeration( childNode ):
      yield item

  2. выбор глубины или ширины 

    def treeEnumeration( node, depthFirst = True ):
  nodeList = node.getChildNodes()
  for i in range( nodeList.getLength()):
    childNode = nodeList.item( i )
    yield childNode
    if depthFirst:
      for item in treeEnumeration( childNode ):
        yield item
  if not depthFirst:
    for i in range( nodeList.getLength()):
      childNode = nodeList.item( i )
      for item in treeEnumeration( childNode, False ):
        yield item

  3. выбор глубины или ширины, с указанием глубины данного узла 

    class NodeWrapper():
  def __init__(self, node, depth ):
    self.node = node
    self.depth = depth
  def __repr__( self ):
    return "node %s, depth %d" % (self.node, self.depth)

def treeEnumerationShowDepth( node, depth = 0, depthFirst = True ):
  nodeList = node.getChildNodes()
  for i in range( nodeList.getLength()):
    wrapper = NodeWrapper( nodeList.item( i ), depth )
    yield wrapper
    if depthFirst:
      for item in treeEnumerationShowDepth( wrapper.node, depth + 1 ):
        yield item
  if not depthFirst:
    for i in range( nodeList.getLength()):
      childNode = nodeList.item( i )
      for item in treeEnumerationShowDepth( childNode, depth + 1, False ):
        yield item

from org.w3c.dom import Node

for wrapper in treeEnumerationShowDepth( dom.getDocumentElement(), 0, False ):
  print "%snode: %s" % ( wrapper.depth * "  ", wrapper.node )
...