← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Robert Collins
  • Date: 2008-01-16 01:25:39 UTC
  • mto: (3184.3.1 use-SearchResult)
  • mto: This revision was merged to the branch mainline in revision 3192.
  • Revision ID: robertc@robertcollins.net-20080116012539-k9p8rn82m02cat2m
Create a SearchResult object which can be used as a replacement for sets.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
526
526
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
527
527
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
528
528
 
529
 
    def get_recipe(self):
530
 
        """Return a recipe that can be used to replay this search.
 
529
    def get_result(self):
 
530
        """Get a SearchResult for the current state of this searcher.
531
531
        
532
 
        The recipe allows reconstruction of the same results at a later date
533
 
        without knowing all the found keys. The essential elements are a list
534
 
        of keys to start and and to stop at. In order to give reproducible
535
 
        results when ghosts are encountered by a search they are automatically
536
 
        added to the exclude list (or else ghost filling may alter the
537
 
        results).
538
 
 
539
 
        :return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
540
 
            recreate the results of this search, create a breadth first
541
 
            searcher on the same graph starting at start_keys. Then call next()
542
 
            (or next_with_ghosts()) repeatedly, and on every result, call
543
 
            stop_searching_any on any keys from the exclude_keys set. The
544
 
            revision_count value acts as a trivial cross-check - the found
545
 
            revisions of the new search should have as many elements as
546
 
            revision_count. If it does not, then additional revisions have been
547
 
            ghosted since the search was executed the first time and the second
548
 
            time.
 
532
        :return: A SearchResult for this search so far. The SearchResult is
 
533
            static - the search can be advanced and the search result will not
 
534
            be invalidated or altered.
549
535
        """
550
536
        if self._returning == 'next':
551
537
            # We have to know the current nodes children to be able to list the
561
547
        else:
562
548
            next_query = self._next_query
563
549
        excludes = self._stopped_keys.union(next_query)
564
 
        return (self._started_keys, excludes,
565
 
            len(self.seen.difference(excludes)))
 
550
        included_keys = self.seen.difference(excludes)
 
551
        return SearchResult(self._started_keys, excludes, len(included_keys),
 
552
            included_keys)
566
553
 
567
554
    def next(self):
568
555
        """Return the next ancestors of this revision.
724
711
            self._next_query.update(query)
725
712
            self._current_parents.update(parents)
726
713
            return revs, ghosts
 
714
 
 
715
 
 
716
class SearchResult(object):
 
717
    """The result of a breadth first search.
 
718
 
 
719
    A SearchResult provides the ability to reconstruct the search or access a
 
720
    set of the keys the search found.
 
721
    """
 
722
 
 
723
    def __init__(self, start_keys, exclude_keys, key_count, keys):
 
724
        """Create a SearchResult.
 
725
 
 
726
        :param start_keys: The keys the search started at.
 
727
        :param exclude_keys: The keys the search excludes.
 
728
        :param key_count: The total number of keys (from start to but not
 
729
            including exclude).
 
730
        :param keys: The keys the search found. Note that in future we may get
 
731
            a SearchResult from a smart server, in which case the keys list is
 
732
            not necessarily immediately available.
 
733
        """
 
734
        self._recipe = (start_keys, exclude_keys, key_count)
 
735
        self._keys = frozenset(keys)
 
736
 
 
737
    def get_recipe(self):
 
738
        """Return a recipe that can be used to replay this search.
 
739
        
 
740
        The recipe allows reconstruction of the same results at a later date
 
741
        without knowing all the found keys. The essential elements are a list
 
742
        of keys to start and and to stop at. In order to give reproducible
 
743
        results when ghosts are encountered by a search they are automatically
 
744
        added to the exclude list (or else ghost filling may alter the
 
745
        results).
 
746
 
 
747
        :return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
 
748
            recreate the results of this search, create a breadth first
 
749
            searcher on the same graph starting at start_keys. Then call next()
 
750
            (or next_with_ghosts()) repeatedly, and on every result, call
 
751
            stop_searching_any on any keys from the exclude_keys set. The
 
752
            revision_count value acts as a trivial cross-check - the found
 
753
            revisions of the new search should have as many elements as
 
754
            revision_count. If it does not, then additional revisions have been
 
755
            ghosted since the search was executed the first time and the second
 
756
            time.
 
757
        """
 
758
        return self._recipe
 
759
 
 
760
    def get_keys(self):
 
761
        """Return the keys found in this search.
 
762
 
 
763
        :return: A set of keys.
 
764
        """
 
765
        return self._keys
 
766