python (3.11.7)
1 import itertools
2
3 from .compat import collections_abc
4
5
6 class ESC[4;38;5;81mDirectedGraph(ESC[4;38;5;149mobject):
7 """A graph structure with directed edges."""
8
9 def __init__(self):
10 self._vertices = set()
11 self._forwards = {} # <key> -> Set[<key>]
12 self._backwards = {} # <key> -> Set[<key>]
13
14 def __iter__(self):
15 return iter(self._vertices)
16
17 def __len__(self):
18 return len(self._vertices)
19
20 def __contains__(self, key):
21 return key in self._vertices
22
23 def copy(self):
24 """Return a shallow copy of this graph."""
25 other = DirectedGraph()
26 other._vertices = set(self._vertices)
27 other._forwards = {k: set(v) for k, v in self._forwards.items()}
28 other._backwards = {k: set(v) for k, v in self._backwards.items()}
29 return other
30
31 def add(self, key):
32 """Add a new vertex to the graph."""
33 if key in self._vertices:
34 raise ValueError("vertex exists")
35 self._vertices.add(key)
36 self._forwards[key] = set()
37 self._backwards[key] = set()
38
39 def remove(self, key):
40 """Remove a vertex from the graph, disconnecting all edges from/to it."""
41 self._vertices.remove(key)
42 for f in self._forwards.pop(key):
43 self._backwards[f].remove(key)
44 for t in self._backwards.pop(key):
45 self._forwards[t].remove(key)
46
47 def connected(self, f, t):
48 return f in self._backwards[t] and t in self._forwards[f]
49
50 def connect(self, f, t):
51 """Connect two existing vertices.
52
53 Nothing happens if the vertices are already connected.
54 """
55 if t not in self._vertices:
56 raise KeyError(t)
57 self._forwards[f].add(t)
58 self._backwards[t].add(f)
59
60 def iter_edges(self):
61 for f, children in self._forwards.items():
62 for t in children:
63 yield f, t
64
65 def iter_children(self, key):
66 return iter(self._forwards[key])
67
68 def iter_parents(self, key):
69 return iter(self._backwards[key])
70
71
72 class ESC[4;38;5;81mIteratorMapping(ESC[4;38;5;149mcollections_abcESC[4;38;5;149m.ESC[4;38;5;149mMapping):
73 def __init__(self, mapping, accessor, appends=None):
74 self._mapping = mapping
75 self._accessor = accessor
76 self._appends = appends or {}
77
78 def __repr__(self):
79 return "IteratorMapping({!r}, {!r}, {!r})".format(
80 self._mapping,
81 self._accessor,
82 self._appends,
83 )
84
85 def __bool__(self):
86 return bool(self._mapping or self._appends)
87
88 __nonzero__ = __bool__ # XXX: Python 2.
89
90 def __contains__(self, key):
91 return key in self._mapping or key in self._appends
92
93 def __getitem__(self, k):
94 try:
95 v = self._mapping[k]
96 except KeyError:
97 return iter(self._appends[k])
98 return itertools.chain(self._accessor(v), self._appends.get(k, ()))
99
100 def __iter__(self):
101 more = (k for k in self._appends if k not in self._mapping)
102 return itertools.chain(self._mapping, more)
103
104 def __len__(self):
105 more = sum(1 for k in self._appends if k not in self._mapping)
106 return len(self._mapping) + more
107
108
109 class ESC[4;38;5;81m_FactoryIterableView(ESC[4;38;5;149mobject):
110 """Wrap an iterator factory returned by `find_matches()`.
111
112 Calling `iter()` on this class would invoke the underlying iterator
113 factory, making it a "collection with ordering" that can be iterated
114 through multiple times, but lacks random access methods presented in
115 built-in Python sequence types.
116 """
117
118 def __init__(self, factory):
119 self._factory = factory
120 self._iterable = None
121
122 def __repr__(self):
123 return "{}({})".format(type(self).__name__, list(self))
124
125 def __bool__(self):
126 try:
127 next(iter(self))
128 except StopIteration:
129 return False
130 return True
131
132 __nonzero__ = __bool__ # XXX: Python 2.
133
134 def __iter__(self):
135 iterable = (
136 self._factory() if self._iterable is None else self._iterable
137 )
138 self._iterable, current = itertools.tee(iterable)
139 return current
140
141
142 class ESC[4;38;5;81m_SequenceIterableView(ESC[4;38;5;149mobject):
143 """Wrap an iterable returned by find_matches().
144
145 This is essentially just a proxy to the underlying sequence that provides
146 the same interface as `_FactoryIterableView`.
147 """
148
149 def __init__(self, sequence):
150 self._sequence = sequence
151
152 def __repr__(self):
153 return "{}({})".format(type(self).__name__, self._sequence)
154
155 def __bool__(self):
156 return bool(self._sequence)
157
158 __nonzero__ = __bool__ # XXX: Python 2.
159
160 def __iter__(self):
161 return iter(self._sequence)
162
163
164 def build_iter_view(matches):
165 """Build an iterable view from the value returned by `find_matches()`."""
166 if callable(matches):
167 return _FactoryIterableView(matches)
168 if not isinstance(matches, collections_abc.Sequence):
169 matches = list(matches)
170 return _SequenceIterableView(matches)
Browse
Usage
Versions