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