Rev 2397: Implement a NthNodeSelector. in file:///home/robertc/source/baz/netsim/
Robert Collins
robertc at robertcollins.net
Sun Apr 1 12:35:35 BST 2007
At file:///home/robertc/source/baz/netsim/
------------------------------------------------------------
revno: 2397
revision-id: robertc at robertcollins.net-20070401113531-onqhpzb37lexq17a
parent: robertc at robertcollins.net-20070401100816-j0298tbd10xjsguv
committer: Robert Collins <robertc at robertcollins.net>
branch nick: netsim
timestamp: Sun 2007-04-01 21:35:31 +1000
message:
Implement a NthNodeSelector.
modified:
bzrlib/graph.py graph.py-20050905070950-b47dce53236c5e48
bzrlib/tests/test_graph.py testgraph.py-20050905070950-42e6c958106610fd
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2007-04-01 10:08:16 +0000
+++ b/bzrlib/graph.py 2007-04-01 11:35:31 +0000
@@ -263,3 +263,46 @@
def __repr__(self):
return "GraphDelta heads=%r, cut_from=%r" % (self.heads, self.cut_from)
+
+
+class NthNodeSelector(object):
+ """A NodeSelector that selects event nth node chosen to meet a limit.
+
+ This is almost certainly not a most-optimal node selector for smart server
+ use, but it is extremely simple to build and sufficient to test the concept.
+ """
+
+ def __init__(self, limit=1):
+ """Construct a NthNodeSelector.
+
+ :param limit: The total number of nodes that may be returned from
+ select on any graph. This count may exceed the total size of the
+ graph.
+ """
+ if limit < 1:
+ raise ValueError("limit (%r) must be >= 1" % (limit))
+ self.limit = limit
+
+ def select(self, graph):
+ """Select nodes from graph.
+
+ The nodes chosen are those found by selecting every len(graph)/limit
+ node.
+ """
+ nodes = graph.get_ancestors().keys()
+ nodes.sort()
+ count = len(nodes)
+ interval = count/self.limit
+ if interval < 1:
+ # this performs badly when 2*limit >= count, as it selects only
+ # the first limit nodes: this can be addressed by using a
+ # floating point interval, but its not done yet. TODO XXX
+ interval = 1
+ pos = int(interval * 0.5)
+ result = []
+ while pos < count:
+ if len(result) == self.limit:
+ return result
+ result.append(nodes[pos])
+ pos += interval
+ return result
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2007-04-01 10:08:16 +0000
+++ b/bzrlib/tests/test_graph.py 2007-04-01 11:35:31 +0000
@@ -16,7 +16,12 @@
from bzrlib.errors import NotSubGraph
from bzrlib.tests import TestCase
-from bzrlib.graph import node_distances, nodes_by_distance, Graph, GraphDelta
+from bzrlib.graph import (node_distances,
+ nodes_by_distance,
+ Graph,
+ GraphDelta,
+ NthNodeSelector,
+ )
class TestBase(TestCase):
@@ -382,3 +387,70 @@
result.cut_from = set(['C1'])
self.check_delta(result, graph_from, graph_to)
+
+class TestNodeSelector(TestCase):
+
+ def check_selection(self, expected_selection, graph, selector):
+ """Check the node selection from graph using selector.
+
+ This will generate a new selection and check its identical to the
+ expected selection.
+ """
+ selection = selector.select(graph)
+ self.assertIsInstance(selection, list)
+ self.assertEqual(expected_selection, selection)
+
+ def test_constructor_bounds(self):
+ """NthNodeSelector cannot be constructed with a limit of 0."""
+ self.assertRaises(ValueError, NthNodeSelector, 0)
+
+ def test_nth_empty(self):
+ # the nth selector on an empty graph -> []
+ graph = Graph()
+ selector = NthNodeSelector()
+ self.check_selection([], graph, NthNodeSelector(1))
+ self.check_selection([], graph, NthNodeSelector(2))
+
+ def test_nth_one_node(self):
+ # the nth selector on {A:[B]} -> [A]
+ graph = Graph()
+ graph.add_node('A', ['B'])
+ self.check_selection(['A'], graph, NthNodeSelector(1))
+ self.check_selection(['A'], graph, NthNodeSelector(2))
+ self.check_selection(['A'], graph, NthNodeSelector(200))
+
+ def test_nth_two_nodes(self):
+ # the nth selector on {A:[B], C:[B]}
+ graph = Graph()
+ graph.add_node('A', ['B'])
+ graph.add_node('C', ['B'])
+ selector = NthNodeSelector()
+ self.check_selection(['C'], graph, NthNodeSelector(1))
+ self.check_selection(['A', 'C'], graph, NthNodeSelector(2))
+ self.check_selection(['A', 'C'], graph, NthNodeSelector(200))
+
+ def test_nth_three_nodes(self):
+ # the nth selector on {A:[B], C:[B], B:[]}
+ graph = Graph()
+ graph.add_node('A', ['B'])
+ graph.add_node('B', [])
+ graph.add_node('C', ['B'])
+ selector = NthNodeSelector()
+ self.check_selection(['B'], graph, NthNodeSelector(1))
+ self.check_selection(['A', 'B'], graph, NthNodeSelector(2))
+ self.check_selection(['A', 'B', 'C'], graph, NthNodeSelector(3))
+ self.check_selection(['A', 'B', 'C'], graph, NthNodeSelector(200))
+
+ def test_nth_four_nodes(self):
+ # the nth selector on {A:[B], C:[B], B:[], E:[A]}
+ graph = Graph()
+ graph.add_node('A', ['B'])
+ graph.add_node('B', [])
+ graph.add_node('C', ['B'])
+ graph.add_node('E', ['A'])
+ selector = NthNodeSelector()
+ self.check_selection(['C'], graph, NthNodeSelector(1))
+ self.check_selection(['B', 'E'], graph, NthNodeSelector(2))
+ self.check_selection(['A', 'B', 'C'], graph, NthNodeSelector(3))
+ self.check_selection(['A', 'B', 'C', 'E'], graph, NthNodeSelector(4))
+ self.check_selection(['A', 'B', 'C', 'E'], graph, NthNodeSelector(200))
More information about the bazaar-commits
mailing list