~bzr-pqm/bzr/bzr.dev : contents of equivalence

~bzr-pqm/bzr/bzr.dev : (revision 0.23.52)

# Copyright (C) 2008 Canonical Limited.
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License version 2 as published
# by the Free Software Foundation.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
#

"""Functions for dealing with a persistent equivalency table."""


SENTINEL = -1


class EquivalenceTable(object):
    """This class tracks equivalencies between lists of hashable objects.

    :ivar lines: The 'static' lines that will be preserved between runs.
    :ival _matching_lines: A dict of {line:[matching offsets]}
    """

    def __init__(self, lines):
        self.lines = lines
        self._right_lines = None
        # For each line in 'left' give the offset to the other lines which
        # match it.
        self._generate_matching_lines()

    def _generate_matching_lines(self):
        matches = {}
        for idx, line in enumerate(self.lines):
            matches.setdefault(line, []).append(idx)
        self._matching_lines = matches

    def _update_matching_lines(self, new_lines, index):
        matches = self._matching_lines
        start_idx = len(self.lines)
        for idx, do_index in enumerate(index):
            if not do_index:
                continue
            matches.setdefault(new_lines[idx], []).append(start_idx + idx)

    def get_matches(self, line):
        """Return the lines which match the line in right."""
        try:
            return self._matching_lines[line]
        except KeyError:
            return None

    def _get_matching_lines(self):
        """Return a dictionary showing matching lines."""
        matching = {}
        for line in self.lines:
            matching[line] = self.get_matches(line)
        return matching

    def get_idx_matches(self, right_idx):
        """Return the left lines matching the right line at the given offset."""
        line = self._right_lines[right_idx]
        try:
            return self._matching_lines[line]
        except KeyError:
            return None

    def extend_lines(self, lines, index):
        """Add more lines to the left-lines list.

        :param lines: A list of lines to add
        :param index: A True/False for each node to define if it should be
            indexed.
        """
        self._update_matching_lines(lines, index)
        self.lines.extend(lines)

    def set_right_lines(self, lines):
        """Set the lines we will be matching against."""
        self._right_lines = lines

0.18.1 by John Arbash Meinel Start working on an EquivalenceTable construct.	1	# Copyright (C) 2008 Canonical Limited.
	2	#
	3	# This program is free software; you can redistribute it and/or modify
	4	# it under the terms of the GNU General Public License version 2 as published
	5	# by the Free Software Foundation.
	6	#
	7	# This program is distributed in the hope that it will be useful,
	8	# but WITHOUT ANY WARRANTY; without even the implied warranty of
	9	# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	10	# GNU General Public License for more details.
	11	#
	12	# You should have received a copy of the GNU General Public License
	13	# along with this program; if not, write to the Free Software
	14	# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
	15	#
	16
	17	"""Functions for dealing with a persistent equivalency table."""
	18
	19
	20	SENTINEL = -1
	21
	22
	23	class EquivalenceTable(object):
	24	"""This class tracks equivalencies between lists of hashable objects.
	25
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	26	:ivar lines: The 'static' lines that will be preserved between runs.
0.18.8 by John Arbash Meinel We don't actually care much about the right-line relationships. We only need to track the left-hand side.	27	:ival _matching_lines: A dict of {line:[matching offsets]}
0.18.1 by John Arbash Meinel Start working on an EquivalenceTable construct.	28	"""
	29
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	30	def __init__(self, lines):
	31	self.lines = lines
0.18.11 by John Arbash Meinel Convert back into grabbing a right-lines ahead of time.	32	self._right_lines = None
0.18.1 by John Arbash Meinel Start working on an EquivalenceTable construct.	33	# For each line in 'left' give the offset to the other lines which
	34	# match it.
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	35	self._generate_matching_lines()
0.18.1 by John Arbash Meinel Start working on an EquivalenceTable construct.	36
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	37	def _generate_matching_lines(self):
0.18.1 by John Arbash Meinel Start working on an EquivalenceTable construct.	38	matches = {}
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	39	for idx, line in enumerate(self.lines):
0.18.8 by John Arbash Meinel We don't actually care much about the right-line relationships. We only need to track the left-hand side.	40	matches.setdefault(line, []).append(idx)
0.18.1 by John Arbash Meinel Start working on an EquivalenceTable construct.	41	self._matching_lines = matches
	42
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	43	def _update_matching_lines(self, new_lines, index):
0.18.3 by John Arbash Meinel We can now add more lines to left lines, and continue to track the right info.	44	matches = self._matching_lines
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	45	start_idx = len(self.lines)
0.18.8 by John Arbash Meinel We don't actually care much about the right-line relationships. We only need to track the left-hand side.	46	for idx, do_index in enumerate(index):
0.18.4 by John Arbash Meinel Allow ignoring some of the new lines.	47	if not do_index:
	48	continue
0.18.8 by John Arbash Meinel We don't actually care much about the right-line relationships. We only need to track the left-hand side.	49	matches.setdefault(new_lines[idx], []).append(start_idx + idx)
	50
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	51	def get_matches(self, line):
0.18.2 by John Arbash Meinel we can now extract what lines in left match the right	52	"""Return the lines which match the line in right."""
0.18.8 by John Arbash Meinel We don't actually care much about the right-line relationships. We only need to track the left-hand side.	53	try:
	54	return self._matching_lines[line]
	55	except KeyError:
	56	return None
0.18.3 by John Arbash Meinel We can now add more lines to left lines, and continue to track the right info.	57
0.18.12 by John Arbash Meinel Switch away from probing hidden member variables	58	def _get_matching_lines(self):
	59	"""Return a dictionary showing matching lines."""
	60	matching = {}
	61	for line in self.lines:
	62	matching[line] = self.get_matches(line)
	63	return matching
	64
0.18.11 by John Arbash Meinel Convert back into grabbing a right-lines ahead of time.	65	def get_idx_matches(self, right_idx):
	66	"""Return the left lines matching the right line at the given offset."""
	67	line = self._right_lines[right_idx]
	68	try:
	69	return self._matching_lines[line]
	70	except KeyError:
	71	return None
	72
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	73	def extend_lines(self, lines, index):
0.18.4 by John Arbash Meinel Allow ignoring some of the new lines.	74	"""Add more lines to the left-lines list.
	75
	76	:param lines: A list of lines to add
	77	:param index: A True/False for each node to define if it should be
	78	indexed.
	79	"""
0.18.9 by John Arbash Meinel If we are going to do it this way, we don't need to explicitly distinguish left and right	80	self._update_matching_lines(lines, index)
	81	self.lines.extend(lines)
0.18.11 by John Arbash Meinel Convert back into grabbing a right-lines ahead of time.	82
	83	def set_right_lines(self, lines):
	84	"""Set the lines we will be matching against."""
	85	self._right_lines = lines