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