Show More
@@ -308,18 +308,11 b' class lazyancestors(object):' | |||||
308 | self._stoprev = stoprev |
|
308 | self._stoprev = stoprev | |
309 | self._inclusive = inclusive |
|
309 | self._inclusive = inclusive | |
310 |
|
310 | |||
311 | # Initialize data structures for __contains__. |
|
|||
312 | # For __contains__, we use a heap rather than a deque because |
|
|||
313 | # (a) it minimizes the number of parentrevs calls made |
|
|||
314 | # (b) it makes the loop termination condition obvious |
|
|||
315 | # Python's heap is a min-heap. Multiply all values by -1 to convert it |
|
|||
316 | # into a max-heap. |
|
|||
317 | self._containsvisit = [-rev for rev in revs] |
|
|||
318 | heapq.heapify(self._containsvisit) |
|
|||
319 | if inclusive: |
|
|||
320 | self._containsseen = set(revs) |
|
|||
321 | else: |
|
|||
322 |
|
|
311 | self._containsseen = set() | |
|
312 | self._containsiter = _lazyancestorsiter(self._parentrevs, | |||
|
313 | self._initrevs, | |||
|
314 | self._stoprev, | |||
|
315 | self._inclusive) | |||
323 |
|
316 | |||
324 | def __nonzero__(self): |
|
317 | def __nonzero__(self): | |
325 | """False if the set is empty, True otherwise.""" |
|
318 | """False if the set is empty, True otherwise.""" | |
@@ -348,35 +341,29 b' class lazyancestors(object):' | |||||
348 |
|
341 | |||
349 | def __contains__(self, target): |
|
342 | def __contains__(self, target): | |
350 | """Test whether target is an ancestor of self._initrevs.""" |
|
343 | """Test whether target is an ancestor of self._initrevs.""" | |
351 | # Trying to do both __iter__ and __contains__ using the same visit |
|
|||
352 | # heap and seen set is complex enough that it slows down both. Keep |
|
|||
353 | # them separate. |
|
|||
354 | seen = self._containsseen |
|
344 | seen = self._containsseen | |
355 | if target in seen: |
|
345 | if target in seen: | |
356 | return True |
|
346 | return True | |
|
347 | iter = self._containsiter | |||
|
348 | if iter is None: | |||
|
349 | # Iterator exhausted | |||
|
350 | return False | |||
357 | # Only integer target is valid, but some callers expect 'None in self' |
|
351 | # Only integer target is valid, but some callers expect 'None in self' | |
358 | # to be False. So we explicitly allow it. |
|
352 | # to be False. So we explicitly allow it. | |
359 | if target is None: |
|
353 | if target is None: | |
360 | return False |
|
354 | return False | |
361 |
|
355 | |||
362 | parentrevs = self._parentrevs |
|
|||
363 | visit = self._containsvisit |
|
|||
364 | stoprev = self._stoprev |
|
|||
365 | heappop = heapq.heappop |
|
|||
366 | heappush = heapq.heappush |
|
|||
367 | see = seen.add |
|
356 | see = seen.add | |
368 |
|
357 | try: | ||
369 | targetseen = False |
|
358 | while True: | |
370 |
|
359 | rev = next(iter) | ||
371 | while visit and -visit[0] > target and not targetseen: |
|
360 | see(rev) | |
372 | for parent in parentrevs(-heappop(visit)): |
|
361 | if rev == target: | |
373 | if parent < stoprev or parent in seen: |
|
362 | return True | |
374 |
|
|
363 | if rev < target: | |
375 | # We need to make sure we push all parents into the heap so |
|
364 | return False | |
376 | # that we leave it in a consistent state for future calls. |
|
365 | except StopIteration: | |
377 | heappush(visit, -parent) |
|
366 | # Set to None to indicate fast-path can be used next time, and to | |
378 |
|
|
367 | # free up memory. | |
379 | if parent == target: |
|
368 | self._containsiter = None | |
380 | targetseen = True |
|
369 | return False | |
381 |
|
||||
382 | return targetseen |
|
General Comments 0
You need to be logged in to leave comments.
Login now