1 | |
---|

2 | |
---|

3 | class 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 | |
---|

32 | def 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 | |
---|

68 | print(vote( |
---|

69 | [ProtoSet([(1,10)]), |
---|

70 | ProtoSet([(1,8),(9,12)]), |
---|

71 | ProtoSet([(2,4),(6,6)])], |
---|

72 | q=3)) |
---|

73 | |
---|