cengal.data_manipulation.tree_traversal.versions.v_0.tree_traversal
1#!/usr/bin/env python 2# coding=utf-8 3 4# Copyright © 2012-2024 ButenkoMS. All rights reserved. Contacts: <gtalk@butenkoms.space> 5# 6# Licensed under the Apache License, Version 2.0 (the "License"); 7# you may not use this file except in compliance with the License. 8# You may obtain a copy of the License at 9# 10# http://www.apache.org/licenses/LICENSE-2.0 11# 12# Unless required by applicable law or agreed to in writing, software 13# distributed under the License is distributed on an "AS IS" BASIS, 14# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15# See the License for the specific language governing permissions and 16# limitations under the License. 17 18 19__all__ = ['AnAppropriateValues', 'AllPossibleValues', 'AnAppropriateContainers', 'data_2_tuple', 'TreeTraversalType', 'TreeTraversal'] 20 21 22from typing import Union, Dict, Set, List, Tuple, Optional, Callable 23from enum import Enum 24from collections import deque 25from cengal.code_flow_control.smart_values import ValueExistence 26from cengal.data_containers.stack import StackItem, TreeStackItem, Stack, recursion_insureness 27 28""" 29Module Docstring 30Docstrings: http://www.python.org/dev/peps/pep-0257/ 31""" 32 33__author__ = "ButenkoMS <gtalk@butenkoms.space>" 34__copyright__ = "Copyright © 2012-2024 ButenkoMS. All rights reserved. Contacts: <gtalk@butenkoms.space>" 35__credits__ = ["ButenkoMS <gtalk@butenkoms.space>", ] 36__license__ = "Apache License, Version 2.0" 37__version__ = "4.4.1" 38__maintainer__ = "ButenkoMS <gtalk@butenkoms.space>" 39__email__ = "gtalk@butenkoms.space" 40# __status__ = "Prototype" 41__status__ = "Development" 42# __status__ = "Production" 43 44 45AnAppropriateValues = Union[str, bytes, int, float, None] 46AllPossibleValues = Union['AnAppropriateContainers', AnAppropriateValues] 47AnAppropriateContainers = Union[Dict[AnAppropriateValues, AllPossibleValues], 48 Set[AllPossibleValues], 49 List[AllPossibleValues], 50 Tuple[AllPossibleValues]] 51 52 53def data_2_tuple(data: AllPossibleValues) -> AllPossibleValues: 54 if isinstance(data, (dict, tuple, list, set, deque)): 55 if isinstance(data, dict): 56 return tuple(data.values()) 57 elif isinstance(data, (tuple, list, deque)): 58 return data 59 elif isinstance(data, set): 60 return tuple(data) 61 else: 62 return data 63 64 65class TreeTraversalType(Enum): 66 recursive = 0 67 stack_based = 1 68 recursive_with_stack_based_insureness = 2 69 70 71class TreeTraversal: 72 def __init__(self, 73 tree: AnAppropriateContainers=None, 74 on_node: Optional[Callable]=None, 75 on_child: Optional[Callable]=None, 76 on_switched_to_stack_based_implementation: Optional[Callable]=None 77 ): 78 self._tree = tree # type: AnAppropriateContainers 79 80 self._callback_on_node = on_node # type: Optional[Callable] 81 self._callback_on_child = on_child # type: Optional[Callable] 82 self._on_switched_to_stack_based_implementation = \ 83 on_switched_to_stack_based_implementation # type: Optional[Callable] 84 85 self._last_tree_node = ValueExistence(False, None) 86 self._last_tree_child = ValueExistence(False, None) 87 self._empty_child = ValueExistence(False, None) 88 89 def set_callback_on_node(self, functor: Optional[Callable]): 90 self._callback_on_node = functor 91 92 def set_callback_on_child(self, functor: Optional[Callable]): 93 self._callback_on_child = functor 94 95 def set_callback_on_both_node_and_child(self, functor: Optional[Callable]): 96 self._callback_on_node = self._callback_on_child = functor 97 98 def set_callback_on_switched_to_stack_based_implementation(self, functor: Optional[Callable]): 99 self._on_switched_to_stack_based_implementation = functor 100 101 @property 102 def tree(self) -> AnAppropriateContainers: 103 return self._tree 104 105 @tree.setter 106 def tree(self, tree: AnAppropriateContainers): 107 self._tree = tree 108 109 def _traversal_recursive(self): 110 tree_tuple = data_2_tuple(self.tree) 111 if isinstance(self.tree, dict): 112 self._last_tree_node.value = self.tree 113 if self._callback_on_node: 114 self._callback_on_node(self._last_tree_node, self._empty_child, None) 115 self._last_tree_node.value = tree_tuple 116 else: 117 self._last_tree_child.value = self.tree 118 if self._callback_on_child: 119 self._callback_on_child(self._last_tree_node, self._last_tree_child, None) 120 121 self._traversal_recursive_impl(tree_tuple) 122 123 def _traversal_recursive_impl(self, tree: AnAppropriateContainers): 124 if isinstance(tree, (tuple, list, deque)): 125 index = 0 126 for item in tree: 127 next_child = item 128 next_child_tuple = data_2_tuple(next_child) 129 if isinstance(next_child, (dict, set, tuple, list, deque)): 130 self._last_tree_node.value = next_child 131 if self._callback_on_node: 132 self._callback_on_node(self._last_tree_node, self._empty_child, None) 133 self._last_tree_node.value = next_child_tuple 134 else: 135 self._last_tree_child.value = next_child 136 if self._callback_on_child: 137 self._callback_on_child(self._last_tree_node, self._last_tree_child, index) 138 139 self._traversal_recursive_impl(next_child_tuple) 140 index += 1 141 142 def _traversal_stack_based(self): 143 tree_tuple = data_2_tuple(self.tree) 144 if isinstance(self.tree, dict): 145 self._last_tree_node.value = self.tree 146 if self._callback_on_node: 147 self._callback_on_node(self._last_tree_node, self._empty_child, None) 148 self._last_tree_node.value = tree_tuple 149 else: 150 self._last_tree_child.value = self.tree 151 if self._callback_on_child: 152 self._callback_on_child(self._last_tree_node, self._last_tree_child, None) 153 154 stack = Stack(TreeStackItem(tree_tuple)) 155 while stack: 156 if stack.top().child is None: 157 if isinstance(stack.top().node, (tuple, list, deque)): 158 if stack.top().node: 159 stack.top().child = -1 160 continue 161 else: 162 stack.pop() 163 continue 164 else: 165 stack.pop() 166 continue 167 else: 168 stack.top().child += 1 169 if len(stack.top().node) > stack.top().child: 170 next_child = stack.top().node[stack.top().child] 171 next_child_tuple = data_2_tuple(next_child) 172 if isinstance(next_child, (dict, set, tuple, list, deque)): 173 self._last_tree_node.value = next_child 174 if self._callback_on_node: 175 self._callback_on_node(self._last_tree_node, self._empty_child, None) 176 self._last_tree_node.value = next_child_tuple 177 else: 178 self._last_tree_child.value = next_child 179 if self._callback_on_child: 180 self._callback_on_child(self._last_tree_node, self._last_tree_child, stack.top().child) 181 182 stack.push(TreeStackItem(next_child_tuple)) 183 continue 184 else: 185 stack.pop() 186 continue 187 188 def __call__(self, traversal_type: TreeTraversalType=TreeTraversalType.recursive_with_stack_based_insureness): 189 if TreeTraversalType.recursive == traversal_type: 190 self._traversal_recursive() 191 elif TreeTraversalType.stack_based == traversal_type: 192 self._traversal_stack_based() 193 else: 194 recursion_insureness(self._traversal_recursive, 195 self._traversal_stack_based, 196 self._on_switched_to_stack_based_implementation)
AnAppropriateValues =
typing.Union[str, bytes, int, float, NoneType]
AllPossibleValues =
typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]
AnAppropriateContainers =
typing.Union[typing.Dict[typing.Union[str, bytes, int, float, NoneType], typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Set[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.List[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Tuple[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]]
def
data_2_tuple( data: typing.Union[typing.Union[typing.Dict[typing.Union[str, bytes, int, float, NoneType], typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Set[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.List[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Tuple[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]) -> Union[Union[Dict[Union[str, bytes, int, float, NoneType], Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Set[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], List[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Tuple[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]:
54def data_2_tuple(data: AllPossibleValues) -> AllPossibleValues: 55 if isinstance(data, (dict, tuple, list, set, deque)): 56 if isinstance(data, dict): 57 return tuple(data.values()) 58 elif isinstance(data, (tuple, list, deque)): 59 return data 60 elif isinstance(data, set): 61 return tuple(data) 62 else: 63 return data
class
TreeTraversalType(enum.Enum):
66class TreeTraversalType(Enum): 67 recursive = 0 68 stack_based = 1 69 recursive_with_stack_based_insureness = 2
An enumeration.
recursive =
<TreeTraversalType.recursive: 0>
stack_based =
<TreeTraversalType.stack_based: 1>
recursive_with_stack_based_insureness =
<TreeTraversalType.recursive_with_stack_based_insureness: 2>
Inherited Members
- enum.Enum
- name
- value
class
TreeTraversal:
72class TreeTraversal: 73 def __init__(self, 74 tree: AnAppropriateContainers=None, 75 on_node: Optional[Callable]=None, 76 on_child: Optional[Callable]=None, 77 on_switched_to_stack_based_implementation: Optional[Callable]=None 78 ): 79 self._tree = tree # type: AnAppropriateContainers 80 81 self._callback_on_node = on_node # type: Optional[Callable] 82 self._callback_on_child = on_child # type: Optional[Callable] 83 self._on_switched_to_stack_based_implementation = \ 84 on_switched_to_stack_based_implementation # type: Optional[Callable] 85 86 self._last_tree_node = ValueExistence(False, None) 87 self._last_tree_child = ValueExistence(False, None) 88 self._empty_child = ValueExistence(False, None) 89 90 def set_callback_on_node(self, functor: Optional[Callable]): 91 self._callback_on_node = functor 92 93 def set_callback_on_child(self, functor: Optional[Callable]): 94 self._callback_on_child = functor 95 96 def set_callback_on_both_node_and_child(self, functor: Optional[Callable]): 97 self._callback_on_node = self._callback_on_child = functor 98 99 def set_callback_on_switched_to_stack_based_implementation(self, functor: Optional[Callable]): 100 self._on_switched_to_stack_based_implementation = functor 101 102 @property 103 def tree(self) -> AnAppropriateContainers: 104 return self._tree 105 106 @tree.setter 107 def tree(self, tree: AnAppropriateContainers): 108 self._tree = tree 109 110 def _traversal_recursive(self): 111 tree_tuple = data_2_tuple(self.tree) 112 if isinstance(self.tree, dict): 113 self._last_tree_node.value = self.tree 114 if self._callback_on_node: 115 self._callback_on_node(self._last_tree_node, self._empty_child, None) 116 self._last_tree_node.value = tree_tuple 117 else: 118 self._last_tree_child.value = self.tree 119 if self._callback_on_child: 120 self._callback_on_child(self._last_tree_node, self._last_tree_child, None) 121 122 self._traversal_recursive_impl(tree_tuple) 123 124 def _traversal_recursive_impl(self, tree: AnAppropriateContainers): 125 if isinstance(tree, (tuple, list, deque)): 126 index = 0 127 for item in tree: 128 next_child = item 129 next_child_tuple = data_2_tuple(next_child) 130 if isinstance(next_child, (dict, set, tuple, list, deque)): 131 self._last_tree_node.value = next_child 132 if self._callback_on_node: 133 self._callback_on_node(self._last_tree_node, self._empty_child, None) 134 self._last_tree_node.value = next_child_tuple 135 else: 136 self._last_tree_child.value = next_child 137 if self._callback_on_child: 138 self._callback_on_child(self._last_tree_node, self._last_tree_child, index) 139 140 self._traversal_recursive_impl(next_child_tuple) 141 index += 1 142 143 def _traversal_stack_based(self): 144 tree_tuple = data_2_tuple(self.tree) 145 if isinstance(self.tree, dict): 146 self._last_tree_node.value = self.tree 147 if self._callback_on_node: 148 self._callback_on_node(self._last_tree_node, self._empty_child, None) 149 self._last_tree_node.value = tree_tuple 150 else: 151 self._last_tree_child.value = self.tree 152 if self._callback_on_child: 153 self._callback_on_child(self._last_tree_node, self._last_tree_child, None) 154 155 stack = Stack(TreeStackItem(tree_tuple)) 156 while stack: 157 if stack.top().child is None: 158 if isinstance(stack.top().node, (tuple, list, deque)): 159 if stack.top().node: 160 stack.top().child = -1 161 continue 162 else: 163 stack.pop() 164 continue 165 else: 166 stack.pop() 167 continue 168 else: 169 stack.top().child += 1 170 if len(stack.top().node) > stack.top().child: 171 next_child = stack.top().node[stack.top().child] 172 next_child_tuple = data_2_tuple(next_child) 173 if isinstance(next_child, (dict, set, tuple, list, deque)): 174 self._last_tree_node.value = next_child 175 if self._callback_on_node: 176 self._callback_on_node(self._last_tree_node, self._empty_child, None) 177 self._last_tree_node.value = next_child_tuple 178 else: 179 self._last_tree_child.value = next_child 180 if self._callback_on_child: 181 self._callback_on_child(self._last_tree_node, self._last_tree_child, stack.top().child) 182 183 stack.push(TreeStackItem(next_child_tuple)) 184 continue 185 else: 186 stack.pop() 187 continue 188 189 def __call__(self, traversal_type: TreeTraversalType=TreeTraversalType.recursive_with_stack_based_insureness): 190 if TreeTraversalType.recursive == traversal_type: 191 self._traversal_recursive() 192 elif TreeTraversalType.stack_based == traversal_type: 193 self._traversal_stack_based() 194 else: 195 recursion_insureness(self._traversal_recursive, 196 self._traversal_stack_based, 197 self._on_switched_to_stack_based_implementation)
TreeTraversal( tree: typing.Union[dict[typing.Union[str, bytes, int, float, NoneType], typing.Union[typing.Union[typing.Dict[typing.Union[str, bytes, int, float, NoneType], typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Set[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.List[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Tuple[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]], set[typing.Union[typing.Union[typing.Dict[typing.Union[str, bytes, int, float, NoneType], typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Set[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.List[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Tuple[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]], list[typing.Union[typing.Union[typing.Dict[typing.Union[str, bytes, int, float, NoneType], typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Set[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.List[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Tuple[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]], tuple[typing.Union[typing.Union[typing.Dict[typing.Union[str, bytes, int, float, NoneType], typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Set[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.List[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], typing.Tuple[typing.Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]]] = None, on_node: typing.Union[typing.Callable, NoneType] = None, on_child: typing.Union[typing.Callable, NoneType] = None, on_switched_to_stack_based_implementation: typing.Union[typing.Callable, NoneType] = None)
73 def __init__(self, 74 tree: AnAppropriateContainers=None, 75 on_node: Optional[Callable]=None, 76 on_child: Optional[Callable]=None, 77 on_switched_to_stack_based_implementation: Optional[Callable]=None 78 ): 79 self._tree = tree # type: AnAppropriateContainers 80 81 self._callback_on_node = on_node # type: Optional[Callable] 82 self._callback_on_child = on_child # type: Optional[Callable] 83 self._on_switched_to_stack_based_implementation = \ 84 on_switched_to_stack_based_implementation # type: Optional[Callable] 85 86 self._last_tree_node = ValueExistence(False, None) 87 self._last_tree_child = ValueExistence(False, None) 88 self._empty_child = ValueExistence(False, None)
def
set_callback_on_switched_to_stack_based_implementation(self, functor: typing.Union[typing.Callable, NoneType]):
tree: Union[dict[Union[str, bytes, int, float, NoneType], Union[Union[Dict[Union[str, bytes, int, float, NoneType], Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Set[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], List[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Tuple[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]], set[Union[Union[Dict[Union[str, bytes, int, float, NoneType], Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Set[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], List[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Tuple[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]], list[Union[Union[Dict[Union[str, bytes, int, float, NoneType], Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Set[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], List[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Tuple[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]], tuple[Union[Union[Dict[Union[str, bytes, int, float, NoneType], Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Set[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], List[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]], Tuple[Union[ForwardRef('AnAppropriateContainers'), str, bytes, int, float, NoneType]]], str, bytes, int, float, NoneType]]]