Updating from skeleton

diff --git a/src/dialcentral.py b/src/dialcentral.py
index 86a0db1..a20d4fe 100755 (executable)
--- a/src/dialcentral.py
+++ b/src/dialcentral.py
@@ -1,13 +1,6 @@
 #!/usr/bin/env python
 # -*- coding: utf-8 -*-
 
-"""
-Copyright (C) 2007 Christoph Würstle
-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.
-"""
-
 
 import sys
 

diff --git a/src/util/algorithms.py b/src/util/algorithms.py
index 7052b98..e94fb61 100644 (file)
--- a/src/util/algorithms.py
+++ b/src/util/algorithms.py
@@ -8,6 +8,8 @@ import itertools
 import functools
 import datetime
 import types
+import array
+import random
 
 
 def ordered_itr(collection):
@@ -41,6 +43,17 @@ def itercat(*iterators):
                        yield x
 
 
+def product(*args, **kwds):
+       # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
+       # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
+       pools = map(tuple, args) * kwds.get('repeat', 1)
+       result = [[]]
+       for pool in pools:
+               result = [x+[y] for x in result for y in pool]
+       for prod in result:
+               yield tuple(prod)
+
+
 def iterwhile(func, iterator):
        """
        Iterate for as long as func(value) returns true.
@@ -579,6 +592,73 @@ def itr_available(queue, initiallyBlock = False):
                yield queue.get_nowait()
 
 
+class BloomFilter(object):
+       """
+       http://en.wikipedia.org/wiki/Bloom_filter
+       Sources:
+       http://code.activestate.com/recipes/577684-bloom-filter/
+       http://code.activestate.com/recipes/577686-bloom-filter/
+
+       >>> from random import sample
+       >>> from string import ascii_letters
+       >>> states = '''Alabama Alaska Arizona Arkansas California Colorado Connecticut
+       ... Delaware Florida Georgia Hawaii Idaho Illinois Indiana Iowa Kansas
+       ... Kentucky Louisiana Maine Maryland Massachusetts Michigan Minnesota
+       ... Mississippi Missouri Montana Nebraska Nevada NewHampshire NewJersey
+       ... NewMexico NewYork NorthCarolina NorthDakota Ohio Oklahoma Oregon
+       ... Pennsylvania RhodeIsland SouthCarolina SouthDakota Tennessee Texas Utah
+       ... Vermont Virginia Washington WestVirginia Wisconsin Wyoming'''.split()
+       >>> bf = BloomFilter(num_bits=1000, num_probes=14)
+       >>> for state in states:
+       ...     bf.add(state)
+       >>> numStatesFound = sum(state in bf for state in states)
+       >>> numStatesFound, len(states)
+       (50, 50)
+       >>> trials = 100
+       >>> numGarbageFound = sum(''.join(sample(ascii_letters, 5)) in bf for i in range(trials))
+       >>> numGarbageFound, trials
+       (0, 100)
+       """
+
+       def __init__(self, num_bits, num_probes):
+               num_words = (num_bits + 31) // 32
+               self._arr = array.array('B', [0]) * num_words
+               self._num_probes = num_probes
+
+       def add(self, key):
+               for i, mask in self._get_probes(key):
+                       self._arr[i] |= mask
+
+       def union(self, bfilter):
+               if self._match_template(bfilter):
+                       for i, b in enumerate(bfilter._arr):
+                               self._arr[i] |= b
+               else:
+                       # Union b/w two unrelated bloom filter raises this
+                       raise ValueError("Mismatched bloom filters")
+
+       def intersection(self, bfilter):
+               if self._match_template(bfilter):
+                       for i, b in enumerate(bfilter._arr):
+                               self._arr[i] &= b
+               else:
+                       # Intersection b/w two unrelated bloom filter raises this
+                       raise ValueError("Mismatched bloom filters")
+
+       def __contains__(self, key):
+               return all(self._arr[i] & mask for i, mask in self._get_probes(key))
+
+       def _match_template(self, bfilter):
+               return self.num_bits == bfilter.num_bits and self.num_probes == bfilter.num_probes
+
+       def _get_probes(self, key):
+               hasher = random.Random(key).randrange
+               for _ in range(self._num_probes):
+                       array_index = hasher(len(self._arr))
+                       bit_index = hasher(32)
+                       yield array_index, 1 << bit_index
+
+
 if __name__ == "__main__":
        import doctest
        print doctest.testmod()

diff --git a/src/util/concurrent.py b/src/util/concurrent.py
index 4d31468..f5f6e1d 100644 (file)
--- a/src/util/concurrent.py
+++ b/src/util/concurrent.py
@@ -23,7 +23,7 @@ class AsyncTaskQueue(object):
 
        def add_async(self, func):
                self.flush()
-               a = _AsyncGeneratorTask(self._taskPool, func)
+               a = AsyncGeneratorTask(self._taskPool, func)
                self._asyncs.append(a)
                return a
 
@@ -31,7 +31,7 @@ class AsyncTaskQueue(object):
                self._asyncs = [a for a in self._asyncs if not a.isDone]
 
 
-class _AsyncGeneratorTask(object):
+class AsyncGeneratorTask(object):
 
        def __init__(self, pool, func):
                self._pool = pool

diff --git a/src/util/misc.py b/src/util/misc.py
index c0a70a9..9b8d88c 100644 (file)
--- a/src/util/misc.py
+++ b/src/util/misc.py
@@ -649,6 +649,35 @@ def call_trace(f):
 
 
 @contextlib.contextmanager
+def nested_break():
+       """
+       >>> with nested_break() as mylabel:
+       ...     for i in xrange(3):
+       ...             print "Outer", i
+       ...             for j in xrange(3):
+       ...                     if i == 2: raise mylabel
+       ...                     if j == 2: break
+       ...                     print "Inner", j
+       ...             print "more processing"
+       Outer 0
+       Inner 0
+       Inner 1
+       Outer 1
+       Inner 0
+       Inner 1
+       Outer 2
+       """
+
+       class NestedBreakException(Exception):
+               pass
+
+       try:
+               yield NestedBreakException
+       except NestedBreakException:
+               pass
+
+
+@contextlib.contextmanager
 def lexical_scope(*args):
        """
        @note Source: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/520586

diff --git a/src/util/qtpie.py b/src/util/qtpie.py
index 1338362..6b77d5d 100755 (executable)
--- a/src/util/qtpie.py
+++ b/src/util/qtpie.py
@@ -603,9 +603,6 @@ class QPieButton(QtGui.QWidget):
 
        @misc_utils.log_exception(_moduleLogger)
        def _on_delayed_popup(self):
-               self.__on_delayed_popup()
-
-       def __on_delayed_popup(self):
                assert self._popupLocation is not None, "Widget location abuse"
                self._popup_child(self._popupLocation)