Mercurial Repositories > eric / file comparison
comparison: src/eric7/Graphics/GraphicsUtilities.py
src/eric7/Graphics/GraphicsUtilities.py
- branch
- eric7
- changeset 9209
- b99e7fd55fd3
- parent 8881
- 54e42bc2437a
- child 9221
- bf71ee032bb4
equal
deleted
inserted
replaced
| 9208:3fc8dfeb6ebe | 9209:b99e7fd55fd3 |
|---|---|
| 1 # -*- coding: utf-8 -*- | |
| 2 | |
| 3 # Copyright (c) 2004 - 2022 Detlev Offenbach <detlev@die-offenbachs.de> | |
| 4 # | |
| 5 | |
| 6 """ | |
| 7 Module implementing some graphical utility functions. | |
| 8 """ | |
| 9 | |
| 10 | |
| 11 class RecursionError(OverflowError, ValueError): | |
| 12 """ | |
| 13 Unable to calculate result because of recursive structure. | |
| 14 """ | |
| 15 pass | |
| 16 | |
| 17 | |
| 18 def sort(nodes, routes, noRecursion=False): | |
| 19 """ | |
| 20 Function to sort widgets topographically. | |
| 21 | |
| 22 Passed a list of nodes and a list of source, dest routes, it attempts | |
| 23 to create a list of stages, where each sub list is one stage in a process. | |
| 24 | |
| 25 The algorithm was taken from Boa Constructor. | |
| 26 | |
| 27 @param nodes list of nodes to be sorted | |
| 28 @type str | |
| 29 @param routes list of routes between the nodes | |
| 30 @type list of tuple of (str, str) | |
| 31 @param noRecursion flag indicating, if recursion errors should be raised | |
| 32 @type bool | |
| 33 @return list of stages | |
| 34 @rtype list of lists of str | |
| 35 @exception RecursionError a recursion error was detected | |
| 36 """ | |
| 37 children, parents = _buildChildrenLists(routes) | |
| 38 | |
| 39 # first stage is those nodes having no incoming routes... | |
| 40 stage = [] | |
| 41 stages = [stage] | |
| 42 taken = [] | |
| 43 for node in nodes: | |
| 44 if not parents.get(node): | |
| 45 stage.append(node) | |
| 46 | |
| 47 if nodes and not stage: | |
| 48 # there is no element, which does not depend on some other element! | |
| 49 stage.append(nodes[0]) | |
| 50 | |
| 51 taken.extend(stage) | |
| 52 nodes = list(filter(lambda x, li=stage: x not in li, nodes)) | |
| 53 while nodes: | |
| 54 previousStageChildren = [] | |
| 55 nodelen = len(nodes) | |
| 56 | |
| 57 # second stage are those nodes, which are direct children of the | |
| 58 # first stage | |
| 59 for node in stage: | |
| 60 for child in children.get(node, []): | |
| 61 if child not in previousStageChildren and child not in taken: | |
| 62 previousStageChildren.append(child) | |
| 63 elif child in taken and noRecursion: | |
| 64 raise RecursionError((child, node)) | |
| 65 | |
| 66 # unless they are children of other direct children... | |
| 67 stage = previousStageChildren | |
| 68 removes = [] | |
| 69 for current in stage: | |
| 70 currentParents = parents.get(current, []) | |
| 71 for parent in currentParents: | |
| 72 if ( | |
| 73 parent in stage and | |
| 74 parent != current and | |
| 75 current not in parents.get(parent, []) | |
| 76 ): | |
| 77 # is not mutually dependant | |
| 78 removes.append(current) | |
| 79 | |
| 80 for remove in removes: | |
| 81 while remove in stage: | |
| 82 stage.remove(remove) | |
| 83 | |
| 84 stages.append(stage) | |
| 85 taken.extend(stage) | |
| 86 nodes = list(filter(lambda x, li=stage: x not in li, nodes)) | |
| 87 if nodelen == len(nodes): | |
| 88 if noRecursion: | |
| 89 raise RecursionError(nodes) | |
| 90 else: | |
| 91 stages.append(nodes[:]) | |
| 92 nodes = [] | |
| 93 | |
| 94 return stages | |
| 95 | |
| 96 | |
| 97 def _buildChildrenLists(routes): | |
| 98 """ | |
| 99 Function to build up parent - child relationships. | |
| 100 | |
| 101 Taken from Boa Constructor. | |
| 102 | |
| 103 @param routes list of routes between nodes | |
| 104 @type list of tuple of (str, str) | |
| 105 @return dictionary of child and dictionary of parent relationships | |
| 106 @rtype tuple of (dict, dict) | |
| 107 """ | |
| 108 childrenTable = {} | |
| 109 parentTable = {} | |
| 110 for sourceID, destinationID in routes: | |
| 111 currentChildren = childrenTable.get(sourceID, []) | |
| 112 currentParents = parentTable.get(destinationID, []) | |
| 113 if destinationID not in currentChildren: | |
| 114 currentChildren.append(destinationID) | |
| 115 if sourceID not in currentParents: | |
| 116 currentParents.append(sourceID) | |
| 117 childrenTable[sourceID] = currentChildren | |
| 118 parentTable[destinationID] = currentParents | |
| 119 return childrenTable, parentTable |
