fork download
copy 
  1. class Node:
  2.     def __init__(self, name=None, parent=None, available=True):
  3.         self.name = name
  4.         self.parent = parent
  5.         self.available = available
  6.         self.children = []
  7.  
  8.     @property
  9.     def next_sibling(self):
  10.         """Return next node on the same level."""
  11.         try:
  12.             return self.parent.children[self.parent.children.index(self)+1]
  13.         except (AttributeError, IndexError):
  14.             return None
  15.  
  16.     @property
  17.     def next_node(self):
  18.         """Return next available node using depth-first search."""
  19.         def f(node):
  20.             return node if node.available else node.next_node
  21.  
  22.         if self.available and self.children:
  23.             return f(self.children[0])
  24.  
  25.         elif self.next_sibling:
  26.             return f(self.next_sibling)
  27.  
  28.         node = self
  29.         while node.parent is not None:
  30.             node = node.parent
  31.             if node.next_sibling:
  32.                 return f(node.next_sibling)
  33.  
  34.         return None
  35.  
  36.  
  37. def print_tree(node, only_available=False):
  38.     todo = [node]
  39.     while todo:
  40.         node = todo.pop()      
  41.         if only_available and not node.available:
  42.             continue
  43.         todo.extend(reversed(node.children))
  44.         print(node.name + (' (unavailable)' if not node.available else ''))
  45.  
  46.  
  47. def traverse(node):
  48.     while True:
  49.         print(node.name)
  50.         node = node.next_node
  51.         if not node:
  52.             break
  53.  
  54.  
  55. grandparent = Node(name='grandparent')
  56. parent0 = Node(name='    parent0', parent=grandparent)
  57. parent1 = Node(name='    parent1', parent=grandparent)
  58. parent2 = Node(name='    parent2', parent=grandparent, available=False)
  59. parent3 = Node(name='    parent3', parent=grandparent)
  60. child0 = Node(name='        child0', parent=parent0, available=False)
  61. child1 = Node(name='        child1', parent=parent0, available=False)
  62. child2 = Node(name='        child2', parent=parent1, available=False)
  63. child3 = Node(name='        child3', parent=parent1)
  64. child4 = Node(name='        child4', parent=parent2)
  65. child5 = Node(name='        child5', parent=parent3)
  66. child6 = Node(name='        child6', parent=parent3, available=False)
  67. grandchild0 = Node(name='            grandchild0', parent=child0)
  68. grandchild1 = Node(name='            grandchild1', parent=child0)
  69. grandchild2 = Node(name='            grandchild2', parent=child3)
  70. grandparent.children = [parent0, parent1, parent2, parent3]
  71. parent0.children = [child0, child1]
  72. parent1.children = [child2, child3]
  73. parent2.children = [child4]
  74. parent3.children = [child5, child6]
  75. child0.children = [grandchild0, grandchild1]
  76. child3.children = [grandchild2]
  77. print('Full node tree:\n')
  78. print_tree(grandparent, only_available=False)
  79. print('\n\nGoal sequence:\n')
  80. print_tree(grandparent, only_available=True)
  81. print('\n\nTraverse using Node.next_node() method (must be equal to "Goal sequence"):\n')
  82. traverse(grandparent)
Success #stdin #stdout 0.02s 9120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Full node tree:

grandparent
    parent0
        child0 (unavailable)
            grandchild0
            grandchild1
        child1 (unavailable)
    parent1
        child2 (unavailable)
        child3
            grandchild2
    parent2 (unavailable)
        child4
    parent3
        child5
        child6 (unavailable)


Goal sequence:

grandparent
    parent0
    parent1
        child3
            grandchild2
    parent3
        child5


Traverse using Node.next_node() method (must be equal to "Goal sequence"):

grandparent
    parent0
    parent1
        child3
            grandchild2
    parent3
        child5
https://ideone.com/pHxZ1E
language:
Python 3 (python  3.12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!