Source Code for Module DataStructs.TopNContainer

 1  # $Id: TopNContainer.py 2 2006-05-06 22:54:39Z glandrum $ 
 2  # 
 3  #  Copyright (C) 2003-2006 Rational Discovery LLC 
 4  # 
 5  #   @@ All Rights Reserved  @@ 
 6  # 
 7  import bisect 
 8 -class TopNContainer(object): 
 9    """ maintains a sorted list of a particular number of data elements. 
10   
11    """ 
12 -  def __init__(self,size,mostNeg=-1e99): 
13      self._size = size 
14      self.best = [mostNeg]*self._size 
15      self.extras = [None]*self._size 
16 -  def Insert(self,val,extra=None): 
17      """ only does the insertion if val fits """ 
18      if val > self.best[0]: 
19        idx = bisect.bisect(self.best,val) 
20        # insert the new element 
21        if idx == self._size: 
22          self.best.append(val) 
23          self.extras.append(extra) 
24        else: 
25          self.best.insert(idx,val) 
26          self.extras.insert(idx,extra) 
27        # and pop off the head 
28        self.best.pop(0) 
29        self.extras.pop(0) 
30   
31 -  def GetPts(self): 
32      """ returns our set of points """ 
33      return self.best 
34 -  def GetExtras(self): 
35      """ returns our set of extras """ 
36      return self.extras 
37   
38 -  def __len__(self): 
39      return self._size 
40 -  def __getitem__(self,which): 
41      return self.best[which],self.extras[which] 
42     
43 -  def reverse(self): 
44      self.best.reverse() 
45      self.extras.reverse() 
46     
47  if __name__ == '__main__': 
48    import random 
49    pts = [int(100*random.random()) for x in range(10)] 
50     
51    c = TopNContainer(4) 
52    for pt in pts: 
53      c.Insert(pt,extra=str(pt)) 
54    print c.GetPts() 
55    print c.GetExtras() 
56