From 27937b7f8bf0cfeb891cf14da12c7eab58e5d038 Mon Sep 17 00:00:00 2001
From: Ed Page <eopage@byu.net>
Date: Wed, 6 Jul 2011 20:33:01 -0500
Subject: [PATCH] Updating from skeleton

---
 src/dialcentral.py     |    7 -----
 src/util/algorithms.py |   80 ++++++++++++++++++++++++++++++++++++++++++++++++
 src/util/concurrent.py |    4 +--
 src/util/misc.py       |   29 ++++++++++++++++++
 src/util/qtpie.py      |    3 --
 5 files changed, 111 insertions(+), 12 deletions(-)

diff --git a/src/dialcentral.py b/src/dialcentral.py
index 86a0db1..a20d4fe 100755
--- 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
--- 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
--- 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
--- 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
--- 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)
 
-- 
1.7.9.5