Ticket #24031: protocol-vote.py

File protocol-vote.py, 1.6 KB (added by nickm, 2 months ago)

O(n*m) algorithm to compute consensus of n votes containing m protocol ranges each

Line 
1
2
3class ProtoSet:
4    def __init__(self, protos):
5        self._p = protos[:]
6        self._p.sort()
7        self._ok()
8
9    def _ok(self):
10        last_hi = None
11        for lo,hi in self._p:
12            if last_hi is not None:
13                assert lo > last_hi
14            assert hi >= lo
15            last_hi = hi
16
17    def unpack(self):
18        for lo,hi in self._p:
19            yield (lo, +1)
20            yield (hi+1, -1)
21
22    def __repr__(self):
23        return "ProtoSet([{}])".format(",".join(
24            "({},{})".format(lo,hi) for lo,hi in self._p))
25
26    def __contains__(self, n):
27        for lo, hi in self._p:
28            if lo <= n <= hi:
29                return True
30        return False
31
32def vote(sets, q):
33    """return a protoset containing the elements listed in at least q
34       of the input sets."""
35    borders = []
36    for ps in sets:
37        borders.extend(ps.unpack())
38    borders.sort()
39
40    ranges = []
41
42    count = 0
43    in_range = False
44    range_start = None
45    last_val = 0
46    for n, kind in borders:
47        assert n >= last_val
48        assert count >= 0
49        if (n > last_val):
50            if count >= q and not in_range:
51                range_start = last_val
52                in_range = True
53            elif count < q and in_range:
54                ranges.append((range_start, last_val-1))
55                in_range = False
56                range_start = None
57
58        count += kind
59
60        last_val = n
61
62    if in_range:
63        ranges.append((range_start, last_val-1))
64
65    return ProtoSet(ranges)
66
67
68print(vote(
69    [ProtoSet([(1,10)]),
70     ProtoSet([(1,8),(9,12)]),
71     ProtoSet([(2,4),(6,6)])],
72    q=3))
73