git.maemo.org Git - gonvert/blob - gonvert/util/algorithms.py

   1 #!/usr/bin/env python
   2
   3 """
   4 @note Source http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66448
   5 """
   6
   7 import itertools
   8 import functools
   9 import datetime
  10 import types
  11 import array
  12 import random
  13
  14
  15 def ordered_itr(collection):
  16         """
  17         >>> [v for v in ordered_itr({"a": 1, "b": 2})]
  18         [('a', 1), ('b', 2)]
  19         >>> [v for v in ordered_itr([3, 1, 10, -20])]
  20         [-20, 1, 3, 10]
  21         """
  22         if isinstance(collection, types.DictType):
  23                 keys = list(collection.iterkeys())
  24                 keys.sort()
  25                 for key in keys:
  26                         yield key, collection[key]
  27         else:
  28                 values = list(collection)
  29                 values.sort()
  30                 for value in values:
  31                         yield value
  32
  33
  34 def itercat(*iterators):
  35         """
  36         Concatenate several iterators into one.
  37
  38         >>> [v for v in itercat([1, 2, 3], [4, 1, 3])]
  39         [1, 2, 3, 4, 1, 3]
  40         """
  41         for i in iterators:
  42                 for x in i:
  43                         yield x
  44
  45
  46 def product(*args, **kwds):
  47         # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
  48         # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
  49         pools = map(tuple, args) * kwds.get('repeat', 1)
  50         result = [[]]
  51         for pool in pools:
  52                 result = [x+[y] for x in result for y in pool]
  53         for prod in result:
  54                 yield tuple(prod)
  55
  56
  57 def iterwhile(func, iterator):
  58         """
  59         Iterate for as long as func(value) returns true.
  60         >>> through = lambda b: b
  61         >>> [v for v in iterwhile(through, [True, True, False])]
  62         [True, True]
  63         """
  64         iterator = iter(iterator)
  65         while 1:
  66                 next = iterator.next()
  67                 if not func(next):
  68                         raise StopIteration
  69                 yield next
  70
  71
  72 def iterfirst(iterator, count=1):
  73         """
  74         Iterate through 'count' first values.
  75
  76         >>> [v for v in iterfirst([1, 2, 3, 4, 5], 3)]
  77         [1, 2, 3]
  78         """
  79         iterator = iter(iterator)
  80         for i in xrange(count):
  81                 yield iterator.next()
  82
  83
  84 def iterstep(iterator, n):
  85         """
  86         Iterate every nth value.
  87
  88         >>> [v for v in iterstep([1, 2, 3, 4, 5], 1)]
  89         [1, 2, 3, 4, 5]
  90         >>> [v for v in iterstep([1, 2, 3, 4, 5], 2)]
  91         [1, 3, 5]
  92         >>> [v for v in iterstep([1, 2, 3, 4, 5], 3)]
  93         [1, 4]
  94         """
  95         iterator = iter(iterator)
  96         while True:
  97                 yield iterator.next()
  98                 # skip n-1 values
  99                 for dummy in xrange(n-1):
 100                         iterator.next()
 101
 102
 103 def itergroup(iterator, count, padValue = None):
 104         """
 105         Iterate in groups of 'count' values. If there
 106         aren't enough values, the last result is padded with
 107         None.
 108
 109         >>> for val in itergroup([1, 2, 3, 4, 5, 6], 3):
 110         ...     print tuple(val)
 111         (1, 2, 3)
 112         (4, 5, 6)
 113         >>> for val in itergroup([1, 2, 3, 4, 5, 6], 3):
 114         ...     print list(val)
 115         [1, 2, 3]
 116         [4, 5, 6]
 117         >>> for val in itergroup([1, 2, 3, 4, 5, 6, 7], 3):
 118         ...     print tuple(val)
 119         (1, 2, 3)
 120         (4, 5, 6)
 121         (7, None, None)
 122         >>> for val in itergroup("123456", 3):
 123         ...     print tuple(val)
 124         ('1', '2', '3')
 125         ('4', '5', '6')
 126         >>> for val in itergroup("123456", 3):
 127         ...     print repr("".join(val))
 128         '123'
 129         '456'
 130         """
 131         paddedIterator = itertools.chain(iterator, itertools.repeat(padValue, count-1))
 132         nIterators = (paddedIterator, ) * count
 133         return itertools.izip(*nIterators)
 134
 135
 136 def xzip(*iterators):
 137         """Iterative version of builtin 'zip'."""
 138         iterators = itertools.imap(iter, iterators)
 139         while 1:
 140                 yield tuple([x.next() for x in iterators])
 141
 142
 143 def xmap(func, *iterators):
 144         """Iterative version of builtin 'map'."""
 145         iterators = itertools.imap(iter, iterators)
 146         values_left = [1]
 147
 148         def values():
 149                 # Emulate map behaviour, i.e. shorter
 150                 # sequences are padded with None when
 151                 # they run out of values.
 152                 values_left[0] = 0
 153                 for i in range(len(iterators)):
 154                         iterator = iterators[i]
 155                         if iterator is None:
 156                                 yield None
 157                         else:
 158                                 try:
 159                                         yield iterator.next()
 160                                         values_left[0] = 1
 161                                 except StopIteration:
 162                                         iterators[i] = None
 163                                         yield None
 164         while 1:
 165                 args = tuple(values())
 166                 if not values_left[0]:
 167                         raise StopIteration
 168                 yield func(*args)
 169
 170
 171 def xfilter(func, iterator):
 172         """Iterative version of builtin 'filter'."""
 173         iterator = iter(iterator)
 174         while 1:
 175                 next = iterator.next()
 176                 if func(next):
 177                         yield next
 178
 179
 180 def xreduce(func, iterator, default=None):
 181         """Iterative version of builtin 'reduce'."""
 182         iterator = iter(iterator)
 183         try:
 184                 prev = iterator.next()
 185         except StopIteration:
 186                 return default
 187         single = 1
 188         for next in iterator:
 189                 single = 0
 190                 prev = func(prev, next)
 191         if single:
 192                 return func(prev, default)
 193         return prev
 194
 195
 196 def daterange(begin, end, delta = datetime.timedelta(1)):
 197         """
 198         Form a range of dates and iterate over them.
 199
 200         Arguments:
 201         begin -- a date (or datetime) object; the beginning of the range.
 202         end   -- a date (or datetime) object; the end of the range.
 203         delta -- (optional) a datetime.timedelta object; how much to step each iteration.
 204                         Default step is 1 day.
 205
 206         Usage:
 207         """
 208         if not isinstance(delta, datetime.timedelta):
 209                 delta = datetime.timedelta(delta)
 210
 211         ZERO = datetime.timedelta(0)
 212
 213         if begin < end:
 214                 if delta <= ZERO:
 215                         raise StopIteration
 216                 test = end.__gt__
 217         else:
 218                 if delta >= ZERO:
 219                         raise StopIteration
 220                 test = end.__lt__
 221
 222         while test(begin):
 223                 yield begin
 224                 begin += delta
 225
 226
 227 class LazyList(object):
 228         """
 229         A Sequence whose values are computed lazily by an iterator.
 230
 231         Module for the creation and use of iterator-based lazy lists.
 232         this module defines a class LazyList which can be used to represent sequences
 233         of values generated lazily. One can also create recursively defined lazy lists
 234         that generate their values based on ones previously generated.
 235
 236         Backport to python 2.5 by Michael Pust
 237         """
 238
 239         __author__ = 'Dan Spitz'
 240
 241         def __init__(self, iterable):
 242                 self._exhausted = False
 243                 self._iterator = iter(iterable)
 244                 self._data = []
 245
 246         def __len__(self):
 247                 """Get the length of a LazyList's computed data."""
 248                 return len(self._data)
 249
 250         def __getitem__(self, i):
 251                 """Get an item from a LazyList.
 252                 i should be a positive integer or a slice object."""
 253                 if isinstance(i, int):
 254                         #index has not yet been yielded by iterator (or iterator exhausted
 255                         #before reaching that index)
 256                         if i >= len(self):
 257                                 self.exhaust(i)
 258                         elif i < 0:
 259                                 raise ValueError('cannot index LazyList with negative number')
 260                         return self._data[i]
 261
 262                 #LazyList slices are iterators over a portion of the list.
 263                 elif isinstance(i, slice):
 264                         start, stop, step = i.start, i.stop, i.step
 265                         if any(x is not None and x < 0 for x in (start, stop, step)):
 266                                 raise ValueError('cannot index or step through a LazyList with'
 267                                                                 'a negative number')
 268                         #set start and step to their integer defaults if they are None.
 269                         if start is None:
 270                                 start = 0
 271                         if step is None:
 272                                 step = 1
 273
 274                         def LazyListIterator():
 275                                 count = start
 276                                 predicate = (
 277                                         (lambda: True)
 278                                         if stop is None
 279                                         else (lambda: count < stop)
 280                                 )
 281                                 while predicate():
 282                                         try:
 283                                                 yield self[count]
 284                                         #slices can go out of actual index range without raising an
 285                                         #error
 286                                         except IndexError:
 287                                                 break
 288                                         count += step
 289                         return LazyListIterator()
 290
 291                 raise TypeError('i must be an integer or slice')
 292
 293         def __iter__(self):
 294                 """return an iterator over each value in the sequence,
 295                 whether it has been computed yet or not."""
 296                 return self[:]
 297
 298         def computed(self):
 299                 """Return an iterator over the values in a LazyList that have
 300                 already been computed."""
 301                 return self[:len(self)]
 302
 303         def exhaust(self, index = None):
 304                 """Exhaust the iterator generating this LazyList's values.
 305                 if index is None, this will exhaust the iterator completely.
 306                 Otherwise, it will iterate over the iterator until either the list
 307                 has a value for index or the iterator is exhausted.
 308                 """
 309                 if self._exhausted:
 310                         return
 311                 if index is None:
 312                         ind_range = itertools.count(len(self))
 313                 else:
 314                         ind_range = range(len(self), index + 1)
 315
 316                 for ind in ind_range:
 317                         try:
 318                                 self._data.append(self._iterator.next())
 319                         except StopIteration: #iterator is fully exhausted
 320                                 self._exhausted = True
 321                                 break
 322
 323
 324 class RecursiveLazyList(LazyList):
 325
 326         def __init__(self, prod, *args, **kwds):
 327                 super(RecursiveLazyList, self).__init__(prod(self, *args, **kwds))
 328
 329
 330 class RecursiveLazyListFactory:
 331
 332         def __init__(self, producer):
 333                 self._gen = producer
 334
 335         def __call__(self, *a, **kw):
 336                 return RecursiveLazyList(self._gen, *a, **kw)
 337
 338
 339 def lazylist(gen):
 340         """
 341         Decorator for creating a RecursiveLazyList subclass.
 342         This should decorate a generator function taking the LazyList object as its
 343         first argument which yields the contents of the list in order.
 344
 345         >>> #fibonnacci sequence in a lazy list.
 346         >>> @lazylist
 347         ... def fibgen(lst):
 348         ...     yield 0
 349         ...     yield 1
 350         ...     for a, b in itertools.izip(lst, lst[1:]):
 351         ...             yield a + b
 352         ...
 353         >>> #now fibs can be indexed or iterated over as if it were an infinitely long list containing the fibonnaci sequence
 354         >>> fibs = fibgen()
 355         >>>
 356         >>> #prime numbers in a lazy list.
 357         >>> @lazylist
 358         ... def primegen(lst):
 359         ...     yield 2
 360         ...     for candidate in itertools.count(3): #start at next number after 2
 361         ...             #if candidate is not divisible by any smaller prime numbers,
 362         ...             #it is a prime.
 363         ...             if all(candidate % p for p in lst.computed()):
 364         ...                     yield candidate
 365         ...
 366         >>> #same for primes- treat it like an infinitely long list containing all prime numbers.
 367         >>> primes = primegen()
 368         >>> print fibs[0], fibs[1], fibs[2], primes[0], primes[1], primes[2]
 369         0 1 1 2 3 5
 370         >>> print list(fibs[:10]), list(primes[:10])
 371         [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
 372         """
 373         return RecursiveLazyListFactory(gen)
 374
 375
 376 def map_func(f):
 377         """
 378         >>> import misc
 379         >>> misc.validate_decorator(map_func)
 380         """
 381
 382         @functools.wraps(f)
 383         def wrapper(*args):
 384                 result = itertools.imap(f, args)
 385                 return result
 386         return wrapper
 387
 388
 389 def reduce_func(function):
 390         """
 391         >>> import misc
 392         >>> misc.validate_decorator(reduce_func(lambda x: x))
 393         """
 394
 395         def decorator(f):
 396
 397                 @functools.wraps(f)
 398                 def wrapper(*args):
 399                         result = reduce(function, f(args))
 400                         return result
 401                 return wrapper
 402         return decorator
 403
 404
 405 def any_(iterable):
 406         """
 407         @note Python Version <2.5
 408
 409         >>> any_([True, True])
 410         True
 411         >>> any_([True, False])
 412         True
 413         >>> any_([False, False])
 414         False
 415         """
 416
 417         for element in iterable:
 418                 if element:
 419                         return True
 420         return False
 421
 422
 423 def all_(iterable):
 424         """
 425         @note Python Version <2.5
 426
 427         >>> all_([True, True])
 428         True
 429         >>> all_([True, False])
 430         False
 431         >>> all_([False, False])
 432         False
 433         """
 434
 435         for element in iterable:
 436                 if not element:
 437                         return False
 438         return True
 439
 440
 441 def for_every(pred, seq):
 442         """
 443         for_every takes a one argument predicate function and a sequence.
 444         @param pred The predicate function should return true or false.
 445         @returns true if every element in seq returns true for predicate, else returns false.
 446
 447         >>> for_every (lambda c: c > 5,(6,7,8,9))
 448         True
 449
 450         @author Source:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52907
 451         """
 452
 453         for i in seq:
 454                 if not pred(i):
 455                         return False
 456         return True
 457
 458
 459 def there_exists(pred, seq):
 460         """
 461         there_exists takes a one argument predicate     function and a sequence.
 462         @param pred The predicate function should return true or false.
 463         @returns true if any element in seq returns true for predicate, else returns false.
 464
 465         >>> there_exists (lambda c: c > 5,(6,7,8,9))
 466         True
 467
 468         @author Source:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52907
 469         """
 470
 471         for i in seq:
 472                 if pred(i):
 473                         return True
 474         return False
 475
 476
 477 def func_repeat(quantity, func, *args, **kwd):
 478         """
 479         Meant to be in connection with "reduce"
 480         """
 481         for i in xrange(quantity):
 482                 yield func(*args, **kwd)
 483
 484
 485 def function_map(preds, item):
 486         """
 487         Meant to be in connection with "reduce"
 488         """
 489         results = (pred(item) for pred in preds)
 490
 491         return results
 492
 493
 494 def functional_if(combiner, preds, item):
 495         """
 496         Combines the result of a list of predicates applied to item according to combiner
 497
 498         @see any, every for example combiners
 499         """
 500         pass_bool = lambda b: b
 501
 502         bool_results = function_map(preds, item)
 503         return combiner(pass_bool, bool_results)
 504
 505
 506 def pushback_itr(itr):
 507         """
 508         >>> list(pushback_itr(xrange(5)))
 509         [0, 1, 2, 3, 4]
 510         >>>
 511         >>> first = True
 512         >>> itr = pushback_itr(xrange(5))
 513         >>> for i in itr:
 514         ...     print i
 515         ...     if first and i == 2:
 516         ...             first = False
 517         ...             print itr.send(i)
 518         0
 519         1
 520         2
 521         None
 522         2
 523         3
 524         4
 525         >>>
 526         >>> first = True
 527         >>> itr = pushback_itr(xrange(5))
 528         >>> for i in itr:
 529         ...     print i
 530         ...     if first and i == 2:
 531         ...             first = False
 532         ...             print itr.send(i)
 533         ...             print itr.send(i)
 534         0
 535         1
 536         2
 537         None
 538         None
 539         2
 540         2
 541         3
 542         4
 543         >>>
 544         >>> itr = pushback_itr(xrange(5))
 545         >>> print itr.next()
 546         0
 547         >>> print itr.next()
 548         1
 549         >>> print itr.send(10)
 550         None
 551         >>> print itr.next()
 552         10
 553         >>> print itr.next()
 554         2
 555         >>> print itr.send(20)
 556         None
 557         >>> print itr.send(30)
 558         None
 559         >>> print itr.send(40)
 560         None
 561         >>> print itr.next()
 562         40
 563         >>> print itr.next()
 564         30
 565         >>> print itr.send(50)
 566         None
 567         >>> print itr.next()
 568         50
 569         >>> print itr.next()
 570         20
 571         >>> print itr.next()
 572         3
 573         >>> print itr.next()
 574         4
 575         """
 576         for item in itr:
 577                 maybePushedBack = yield item
 578                 queue = []
 579                 while queue or maybePushedBack is not None:
 580                         if maybePushedBack is not None:
 581                                 queue.append(maybePushedBack)
 582                                 maybePushedBack = yield None
 583                         else:
 584                                 item = queue.pop()
 585                                 maybePushedBack = yield item
 586
 587
 588 def itr_available(queue, initiallyBlock = False):
 589         if initiallyBlock:
 590                 yield queue.get()
 591         while not queue.empty():
 592                 yield queue.get_nowait()
 593
 594
 595 class BloomFilter(object):
 596         """
 597         http://en.wikipedia.org/wiki/Bloom_filter
 598         Sources:
 599         http://code.activestate.com/recipes/577684-bloom-filter/
 600         http://code.activestate.com/recipes/577686-bloom-filter/
 601
 602         >>> from random import sample
 603         >>> from string import ascii_letters
 604         >>> states = '''Alabama Alaska Arizona Arkansas California Colorado Connecticut
 605         ... Delaware Florida Georgia Hawaii Idaho Illinois Indiana Iowa Kansas
 606         ... Kentucky Louisiana Maine Maryland Massachusetts Michigan Minnesota
 607         ... Mississippi Missouri Montana Nebraska Nevada NewHampshire NewJersey
 608         ... NewMexico NewYork NorthCarolina NorthDakota Ohio Oklahoma Oregon
 609         ... Pennsylvania RhodeIsland SouthCarolina SouthDakota Tennessee Texas Utah
 610         ... Vermont Virginia Washington WestVirginia Wisconsin Wyoming'''.split()
 611         >>> bf = BloomFilter(num_bits=1000, num_probes=14)
 612         >>> for state in states:
 613         ...     bf.add(state)
 614         >>> numStatesFound = sum(state in bf for state in states)
 615         >>> numStatesFound, len(states)
 616         (50, 50)
 617         >>> trials = 100
 618         >>> numGarbageFound = sum(''.join(sample(ascii_letters, 5)) in bf for i in range(trials))
 619         >>> numGarbageFound, trials
 620         (0, 100)
 621         """
 622
 623         def __init__(self, num_bits, num_probes):
 624                 num_words = (num_bits + 31) // 32
 625                 self._arr = array.array('B', [0]) * num_words
 626                 self._num_probes = num_probes
 627
 628         def add(self, key):
 629                 for i, mask in self._get_probes(key):
 630                         self._arr[i] |= mask
 631
 632         def union(self, bfilter):
 633                 if self._match_template(bfilter):
 634                         for i, b in enumerate(bfilter._arr):
 635                                 self._arr[i] |= b
 636                 else:
 637                         # Union b/w two unrelated bloom filter raises this
 638                         raise ValueError("Mismatched bloom filters")
 639
 640         def intersection(self, bfilter):
 641                 if self._match_template(bfilter):
 642                         for i, b in enumerate(bfilter._arr):
 643                                 self._arr[i] &= b
 644                 else:
 645                         # Intersection b/w two unrelated bloom filter raises this
 646                         raise ValueError("Mismatched bloom filters")
 647
 648         def __contains__(self, key):
 649                 return all(self._arr[i] & mask for i, mask in self._get_probes(key))
 650
 651         def _match_template(self, bfilter):
 652                 return self.num_bits == bfilter.num_bits and self.num_probes == bfilter.num_probes
 653
 654         def _get_probes(self, key):
 655                 hasher = random.Random(key).randrange
 656                 for _ in range(self._num_probes):
 657                         array_index = hasher(len(self._arr))
 658                         bit_index = hasher(32)
 659                         yield array_index, 1 << bit_index
 660
 661
 662 if __name__ == "__main__":
 663         import doctest
 664         print doctest.testmod()