Home       Trees       Index       Help   
Package pygraphlib :: Module util :: Class priorityDictionary
[show private | hide private]
[frames | no frames]

Type priorityDictionary

object --+    
         |    
      dict --+
             |
            priorityDictionary

Priority dictionary using binary heaps

David Eppstein, UC Irvine, 8 Mar 2002

Implements a data structure that acts almost like a dictionary, with two modifications:
  1. D.smallest() returns the value x minimizing D[x]. For this to work correctly, all values D[x] stored in the dictionary must be comparable.
  2. iterating "for x in D" finds and removes the items from D in sorted order. Each item is not removed until the next item is requested, so D[x] will still return a useful value until the next iteration of the for-loop. Each operation takes logarithmic amortized time.
Method Summary
  __init__(self)
Initialize priorityDictionary by creating binary heap of pairs (value,key).
  __iter__(self)
Create destructive sorted iterator of priorityDictionary.
  __setitem__(self, key, val)
Change value stored in dictionary and add corresponding pair to heap.
  setdefault(self, key, val)
Reimplement setdefault to pass through our customized __setitem__.
  smallest(self)
Find smallest item after removing deleted items from front of heap.
    Inherited from dict
  __cmp__(x, y)
x.__cmp__(y) <==> cmp(x,y)
  __contains__(x, y)
x.__contains__(y) <==> y in x
  __delitem__(x, y)
x.__delitem__(y) <==> del x[y]
  __eq__(x, y)
x.__eq__(y) <==> x==y
  __ge__(x, y)
x.__ge__(y) <==> x>=y
  __getattribute__(...)
x.__getattribute__('name') <==> x.name
  __getitem__(x, y)
x.__getitem__(y) <==> x[y]
  __gt__(x, y)
x.__gt__(y) <==> x>y
  __hash__(x)
x.__hash__() <==> hash(x)
  __le__(x, y)
x.__le__(y) <==> x<=y
  __len__(x)
x.__len__() <==> len(x)
  __lt__(x, y)
x.__lt__(y) <==> x<y
  __ne__(x, y)
x.__ne__(y) <==> x!=y
  __new__(T, S, ...)
T.__new__(S, ...) -> a new object with type S, a subtype of T
  __repr__(x)
x.__repr__() <==> repr(x)
  clear(D)
D.clear() -> None.
  copy(D)
D.copy() -> a shallow copy of D
  get(D, k, d)
D.get(k[,d]) -> D[k] if k in D, else d.
  has_key(D, k)
D.has_key(k) -> 1 if D has a key k, else 0
  items(D)
D.items() -> list of D's (key, value) pairs, as 2-tuples
  iteritems(D)
D.iteritems() -> an iterator over the (key, value) items of D
  iterkeys(D)
D.iterkeys() -> an iterator over the keys of D
  itervalues(D)
D.itervalues() -> an iterator over the values of D
  keys(D)
D.keys() -> list of D's keys
  pop(D, k, d)
If key is not found, d is returned if given, otherwise KeyError is raised
  popitem(D)
2-tuple; but raise KeyError if D is empty
  update(D, E)
D.update(E) -> None.
  values(D)
D.values() -> list of D's values
    Inherited from object
  __delattr__(...)
x.__delattr__('name') <==> del x.name
  __reduce__(...)
helper for pickle
  __reduce_ex__(...)
helper for pickle
  __setattr__(...)
x.__setattr__('name', value) <==> x.name = value
  __str__(x)
x.__str__() <==> str(x)
    Inherited from type
  fromkeys(dict, S, v)
v defaults to None.

Method Details

__init__(self)
(Constructor)

Initialize priorityDictionary by creating binary heap of pairs (value,key). Note that changing or removing a dict entry will not remove the old pair from the heap until it is found by smallest() or until the heap is rebuilt.
Overrides:
__builtin__.dict.__init__

__iter__(self)

Create destructive sorted iterator of priorityDictionary.
Overrides:
__builtin__.dict.__iter__

__setitem__(self, key, val)
(Index assignment operator)

Change value stored in dictionary and add corresponding pair to heap. Rebuilds the heap if the number of deleted items gets large, to avoid memory leakage.
Overrides:
__builtin__.dict.__setitem__

setdefault(self, key, val)

Reimplement setdefault to pass through our customized __setitem__.
Overrides:
__builtin__.dict.setdefault

smallest(self)

Find smallest item after removing deleted items from front of heap.

   Home       Trees       Index       Help   
Generated by Epydoc 2.1 on Wed Jan 5 09:38:28 2005 http://epydoc.sf.net