priodict.py
Go to the documentation of this file.
00001 ## {{{ http://code.activestate.com/recipes/117228/ (r1)
00002 # Priority dictionary using binary heaps
00003 # David Eppstein, UC Irvine, 8 Mar 2002
00004 
00005 from __future__ import generators
00006 
00007 class priorityDictionary(dict):
00008     def __init__(self):
00009         '''Initialize priorityDictionary by creating binary heap
00010 of pairs (value,key).  Note that changing or removing a dict entry will
00011 not remove the old pair from the heap until it is found by smallest() or
00012 until the heap is rebuilt.'''
00013         self.__heap = []
00014         dict.__init__(self)
00015 
00016     def smallest(self):
00017         '''Find smallest item after removing deleted items from heap.'''
00018         if len(self) == 0:
00019             raise IndexError, "smallest of empty priorityDictionary"
00020         heap = self.__heap
00021         while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]:
00022             lastItem = heap.pop()
00023             insertionPoint = 0
00024             while 1:
00025                 smallChild = 2*insertionPoint+1
00026                 if smallChild+1 < len(heap) and \
00027                         heap[smallChild] > heap[smallChild+1]:
00028                     smallChild += 1
00029                 if smallChild >= len(heap) or lastItem <= heap[smallChild]:
00030                     heap[insertionPoint] = lastItem
00031                     break
00032                 heap[insertionPoint] = heap[smallChild]
00033                 insertionPoint = smallChild
00034         return heap[0][1]
00035         
00036     def __iter__(self):
00037         '''Create destructive sorted iterator of priorityDictionary.'''
00038         def iterfn():
00039             while len(self) > 0:
00040                 x = self.smallest()
00041                 yield x
00042                 del self[x]
00043         return iterfn()
00044         
00045     def __setitem__(self,key,val):
00046         '''Change value stored in dictionary and add corresponding
00047 pair to heap.  Rebuilds the heap if the number of deleted items grows
00048 too large, to avoid memory leakage.'''
00049         dict.__setitem__(self,key,val)
00050         heap = self.__heap
00051         if len(heap) > 2 * len(self):
00052             self.__heap = [(v,k) for k,v in self.iteritems()]
00053             self.__heap.sort()  # builtin sort likely faster than O(n) heapify
00054         else:
00055             newPair = (val,key)
00056             insertionPoint = len(heap)
00057             heap.append(None)
00058             while insertionPoint > 0 and \
00059                     newPair < heap[(insertionPoint-1)//2]:
00060                 heap[insertionPoint] = heap[(insertionPoint-1)//2]
00061                 insertionPoint = (insertionPoint-1)//2
00062             heap[insertionPoint] = newPair
00063         
00064     def setdefault(self,key,val):
00065         '''Reimplement setdefault to call our customized __setitem__.'''
00066         if key not in self:
00067             self[key] = val
00068         return self[key]
00069 ## end of http://code.activestate.com/recipes/117228/ }}}
00070 


saap_pkg
Author(s): Joao Manuel Leitao Quintas
autogenerated on Mon Jan 6 2014 11:26:19