Rev 2397: Implement a NthNodeSelector. in file:///home/robertc/source/baz/netsim/

[Robert Collins]

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))