+++ /dev/null
-#!/usr/bin/env python
-
-"""
-@note Source http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66448
-"""
-
-import itertools
-import functools
-import datetime
-import types
-import array
-import random
-
-
-def ordered_itr(collection):
- """
- >>> [v for v in ordered_itr({"a": 1, "b": 2})]
- [('a', 1), ('b', 2)]
- >>> [v for v in ordered_itr([3, 1, 10, -20])]
- [-20, 1, 3, 10]
- """
- if isinstance(collection, types.DictType):
- keys = list(collection.iterkeys())
- keys.sort()
- for key in keys:
- yield key, collection[key]
- else:
- values = list(collection)
- values.sort()
- for value in values:
- yield value
-
-
-def itercat(*iterators):
- """
- Concatenate several iterators into one.
-
- >>> [v for v in itercat([1, 2, 3], [4, 1, 3])]
- [1, 2, 3, 4, 1, 3]
- """
- for i in iterators:
- for x in i:
- 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.
- >>> through = lambda b: b
- >>> [v for v in iterwhile(through, [True, True, False])]
- [True, True]
- """
- iterator = iter(iterator)
- while 1:
- next = iterator.next()
- if not func(next):
- raise StopIteration
- yield next
-
-
-def iterfirst(iterator, count=1):
- """
- Iterate through 'count' first values.
-
- >>> [v for v in iterfirst([1, 2, 3, 4, 5], 3)]
- [1, 2, 3]
- """
- iterator = iter(iterator)
- for i in xrange(count):
- yield iterator.next()
-
-
-def iterstep(iterator, n):
- """
- Iterate every nth value.
-
- >>> [v for v in iterstep([1, 2, 3, 4, 5], 1)]
- [1, 2, 3, 4, 5]
- >>> [v for v in iterstep([1, 2, 3, 4, 5], 2)]
- [1, 3, 5]
- >>> [v for v in iterstep([1, 2, 3, 4, 5], 3)]
- [1, 4]
- """
- iterator = iter(iterator)
- while True:
- yield iterator.next()
- # skip n-1 values
- for dummy in xrange(n-1):
- iterator.next()
-
-
-def itergroup(iterator, count, padValue = None):
- """
- Iterate in groups of 'count' values. If there
- aren't enough values, the last result is padded with
- None.
-
- >>> for val in itergroup([1, 2, 3, 4, 5, 6], 3):
- ... print tuple(val)
- (1, 2, 3)
- (4, 5, 6)
- >>> for val in itergroup([1, 2, 3, 4, 5, 6], 3):
- ... print list(val)
- [1, 2, 3]
- [4, 5, 6]
- >>> for val in itergroup([1, 2, 3, 4, 5, 6, 7], 3):
- ... print tuple(val)
- (1, 2, 3)
- (4, 5, 6)
- (7, None, None)
- >>> for val in itergroup("123456", 3):
- ... print tuple(val)
- ('1', '2', '3')
- ('4', '5', '6')
- >>> for val in itergroup("123456", 3):
- ... print repr("".join(val))
- '123'
- '456'
- """
- paddedIterator = itertools.chain(iterator, itertools.repeat(padValue, count-1))
- nIterators = (paddedIterator, ) * count
- return itertools.izip(*nIterators)
-
-
-def xzip(*iterators):
- """Iterative version of builtin 'zip'."""
- iterators = itertools.imap(iter, iterators)
- while 1:
- yield tuple([x.next() for x in iterators])
-
-
-def xmap(func, *iterators):
- """Iterative version of builtin 'map'."""
- iterators = itertools.imap(iter, iterators)
- values_left = [1]
-
- def values():
- # Emulate map behaviour, i.e. shorter
- # sequences are padded with None when
- # they run out of values.
- values_left[0] = 0
- for i in range(len(iterators)):
- iterator = iterators[i]
- if iterator is None:
- yield None
- else:
- try:
- yield iterator.next()
- values_left[0] = 1
- except StopIteration:
- iterators[i] = None
- yield None
- while 1:
- args = tuple(values())
- if not values_left[0]:
- raise StopIteration
- yield func(*args)
-
-
-def xfilter(func, iterator):
- """Iterative version of builtin 'filter'."""
- iterator = iter(iterator)
- while 1:
- next = iterator.next()
- if func(next):
- yield next
-
-
-def xreduce(func, iterator, default=None):
- """Iterative version of builtin 'reduce'."""
- iterator = iter(iterator)
- try:
- prev = iterator.next()
- except StopIteration:
- return default
- single = 1
- for next in iterator:
- single = 0
- prev = func(prev, next)
- if single:
- return func(prev, default)
- return prev
-
-
-def daterange(begin, end, delta = datetime.timedelta(1)):
- """
- Form a range of dates and iterate over them.
-
- Arguments:
- begin -- a date (or datetime) object; the beginning of the range.
- end -- a date (or datetime) object; the end of the range.
- delta -- (optional) a datetime.timedelta object; how much to step each iteration.
- Default step is 1 day.
-
- Usage:
- """
- if not isinstance(delta, datetime.timedelta):
- delta = datetime.timedelta(delta)
-
- ZERO = datetime.timedelta(0)
-
- if begin < end:
- if delta <= ZERO:
- raise StopIteration
- test = end.__gt__
- else:
- if delta >= ZERO:
- raise StopIteration
- test = end.__lt__
-
- while test(begin):
- yield begin
- begin += delta
-
-
-class LazyList(object):
- """
- A Sequence whose values are computed lazily by an iterator.
-
- Module for the creation and use of iterator-based lazy lists.
- this module defines a class LazyList which can be used to represent sequences
- of values generated lazily. One can also create recursively defined lazy lists
- that generate their values based on ones previously generated.
-
- Backport to python 2.5 by Michael Pust
- """
-
- __author__ = 'Dan Spitz'
-
- def __init__(self, iterable):
- self._exhausted = False
- self._iterator = iter(iterable)
- self._data = []
-
- def __len__(self):
- """Get the length of a LazyList's computed data."""
- return len(self._data)
-
- def __getitem__(self, i):
- """Get an item from a LazyList.
- i should be a positive integer or a slice object."""
- if isinstance(i, int):
- #index has not yet been yielded by iterator (or iterator exhausted
- #before reaching that index)
- if i >= len(self):
- self.exhaust(i)
- elif i < 0:
- raise ValueError('cannot index LazyList with negative number')
- return self._data[i]
-
- #LazyList slices are iterators over a portion of the list.
- elif isinstance(i, slice):
- start, stop, step = i.start, i.stop, i.step
- if any(x is not None and x < 0 for x in (start, stop, step)):
- raise ValueError('cannot index or step through a LazyList with'
- 'a negative number')
- #set start and step to their integer defaults if they are None.
- if start is None:
- start = 0
- if step is None:
- step = 1
-
- def LazyListIterator():
- count = start
- predicate = (
- (lambda: True)
- if stop is None
- else (lambda: count < stop)
- )
- while predicate():
- try:
- yield self[count]
- #slices can go out of actual index range without raising an
- #error
- except IndexError:
- break
- count += step
- return LazyListIterator()
-
- raise TypeError('i must be an integer or slice')
-
- def __iter__(self):
- """return an iterator over each value in the sequence,
- whether it has been computed yet or not."""
- return self[:]
-
- def computed(self):
- """Return an iterator over the values in a LazyList that have
- already been computed."""
- return self[:len(self)]
-
- def exhaust(self, index = None):
- """Exhaust the iterator generating this LazyList's values.
- if index is None, this will exhaust the iterator completely.
- Otherwise, it will iterate over the iterator until either the list
- has a value for index or the iterator is exhausted.
- """
- if self._exhausted:
- return
- if index is None:
- ind_range = itertools.count(len(self))
- else:
- ind_range = range(len(self), index + 1)
-
- for ind in ind_range:
- try:
- self._data.append(self._iterator.next())
- except StopIteration: #iterator is fully exhausted
- self._exhausted = True
- break
-
-
-class RecursiveLazyList(LazyList):
-
- def __init__(self, prod, *args, **kwds):
- super(RecursiveLazyList, self).__init__(prod(self, *args, **kwds))
-
-
-class RecursiveLazyListFactory:
-
- def __init__(self, producer):
- self._gen = producer
-
- def __call__(self, *a, **kw):
- return RecursiveLazyList(self._gen, *a, **kw)
-
-
-def lazylist(gen):
- """
- Decorator for creating a RecursiveLazyList subclass.
- This should decorate a generator function taking the LazyList object as its
- first argument which yields the contents of the list in order.
-
- >>> #fibonnacci sequence in a lazy list.
- >>> @lazylist
- ... def fibgen(lst):
- ... yield 0
- ... yield 1
- ... for a, b in itertools.izip(lst, lst[1:]):
- ... yield a + b
- ...
- >>> #now fibs can be indexed or iterated over as if it were an infinitely long list containing the fibonnaci sequence
- >>> fibs = fibgen()
- >>>
- >>> #prime numbers in a lazy list.
- >>> @lazylist
- ... def primegen(lst):
- ... yield 2
- ... for candidate in itertools.count(3): #start at next number after 2
- ... #if candidate is not divisible by any smaller prime numbers,
- ... #it is a prime.
- ... if all(candidate % p for p in lst.computed()):
- ... yield candidate
- ...
- >>> #same for primes- treat it like an infinitely long list containing all prime numbers.
- >>> primes = primegen()
- >>> print fibs[0], fibs[1], fibs[2], primes[0], primes[1], primes[2]
- 0 1 1 2 3 5
- >>> print list(fibs[:10]), list(primes[:10])
- [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
- """
- return RecursiveLazyListFactory(gen)
-
-
-def map_func(f):
- """
- >>> import misc
- >>> misc.validate_decorator(map_func)
- """
-
- @functools.wraps(f)
- def wrapper(*args):
- result = itertools.imap(f, args)
- return result
- return wrapper
-
-
-def reduce_func(function):
- """
- >>> import misc
- >>> misc.validate_decorator(reduce_func(lambda x: x))
- """
-
- def decorator(f):
-
- @functools.wraps(f)
- def wrapper(*args):
- result = reduce(function, f(args))
- return result
- return wrapper
- return decorator
-
-
-def any_(iterable):
- """
- @note Python Version <2.5
-
- >>> any_([True, True])
- True
- >>> any_([True, False])
- True
- >>> any_([False, False])
- False
- """
-
- for element in iterable:
- if element:
- return True
- return False
-
-
-def all_(iterable):
- """
- @note Python Version <2.5
-
- >>> all_([True, True])
- True
- >>> all_([True, False])
- False
- >>> all_([False, False])
- False
- """
-
- for element in iterable:
- if not element:
- return False
- return True
-
-
-def for_every(pred, seq):
- """
- for_every takes a one argument predicate function and a sequence.
- @param pred The predicate function should return true or false.
- @returns true if every element in seq returns true for predicate, else returns false.
-
- >>> for_every (lambda c: c > 5,(6,7,8,9))
- True
-
- @author Source:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52907
- """
-
- for i in seq:
- if not pred(i):
- return False
- return True
-
-
-def there_exists(pred, seq):
- """
- there_exists takes a one argument predicate function and a sequence.
- @param pred The predicate function should return true or false.
- @returns true if any element in seq returns true for predicate, else returns false.
-
- >>> there_exists (lambda c: c > 5,(6,7,8,9))
- True
-
- @author Source:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52907
- """
-
- for i in seq:
- if pred(i):
- return True
- return False
-
-
-def func_repeat(quantity, func, *args, **kwd):
- """
- Meant to be in connection with "reduce"
- """
- for i in xrange(quantity):
- yield func(*args, **kwd)
-
-
-def function_map(preds, item):
- """
- Meant to be in connection with "reduce"
- """
- results = (pred(item) for pred in preds)
-
- return results
-
-
-def functional_if(combiner, preds, item):
- """
- Combines the result of a list of predicates applied to item according to combiner
-
- @see any, every for example combiners
- """
- pass_bool = lambda b: b
-
- bool_results = function_map(preds, item)
- return combiner(pass_bool, bool_results)
-
-
-def pushback_itr(itr):
- """
- >>> list(pushback_itr(xrange(5)))
- [0, 1, 2, 3, 4]
- >>>
- >>> first = True
- >>> itr = pushback_itr(xrange(5))
- >>> for i in itr:
- ... print i
- ... if first and i == 2:
- ... first = False
- ... print itr.send(i)
- 0
- 1
- 2
- None
- 2
- 3
- 4
- >>>
- >>> first = True
- >>> itr = pushback_itr(xrange(5))
- >>> for i in itr:
- ... print i
- ... if first and i == 2:
- ... first = False
- ... print itr.send(i)
- ... print itr.send(i)
- 0
- 1
- 2
- None
- None
- 2
- 2
- 3
- 4
- >>>
- >>> itr = pushback_itr(xrange(5))
- >>> print itr.next()
- 0
- >>> print itr.next()
- 1
- >>> print itr.send(10)
- None
- >>> print itr.next()
- 10
- >>> print itr.next()
- 2
- >>> print itr.send(20)
- None
- >>> print itr.send(30)
- None
- >>> print itr.send(40)
- None
- >>> print itr.next()
- 40
- >>> print itr.next()
- 30
- >>> print itr.send(50)
- None
- >>> print itr.next()
- 50
- >>> print itr.next()
- 20
- >>> print itr.next()
- 3
- >>> print itr.next()
- 4
- """
- for item in itr:
- maybePushedBack = yield item
- queue = []
- while queue or maybePushedBack is not None:
- if maybePushedBack is not None:
- queue.append(maybePushedBack)
- maybePushedBack = yield None
- else:
- item = queue.pop()
- maybePushedBack = yield item
-
-
-def itr_available(queue, initiallyBlock = False):
- if initiallyBlock:
- yield queue.get()
- while not queue.empty():
- 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()
projects / gc-dialer / blobdiff