Source Code for Module gmisclib.rubber_array

 1   
 2   
 3   
 4  """This acts like a dictionary, but indexed by integers and 
 5  stored rather more efficiently, at least in terms of memory. 
 6  It is designed for very sparse arrays. 
 7  """ 
 8   
 9  import Num 
10   
11 -class ext_block(object): 
12 -        def __init__(self, n, vtype=Num.Float): 
13                  self.v = Num.zeros((n,), vtype) 
14                  self.mask = Num.zeros((n,), Num.bool_) 
15   
16 -        def set(self, k, v): 
17                  self.v[k] = v 
18                  self.mask[k] = 1 
19   
20   
21 -        def get(self, k, IdxErrArg): 
22                  if self.mask[k]: 
23                          return self.v[k] 
24                  else: 
25                          raise IndexError, IdxErrArg 
26   
27   
28                  def unset(self, key): 
29                          self.mask[key] = 0 
30                          return Num.sum(self.mask) == 0 
31   
32   
33 -        def contains(self, value): 
34                  return value in self.v.take(indices=self.mask) 
35                   
36 -class extensible_array(object): 
37 -        def __init__(self, bsz=300): 
38                  self.x = {} 
39                  self.sz = bsz 
40                  self._len = 0 
41   
42 -        def __len__(self): 
43                  return self._len 
44   
45 -        def __setitem__(self, k, v): 
46                  """Doesn't do slice objects.""" 
47                  iblock = k//self.sz 
48                  try: 
49                          block = self.x[iblock] 
50                  except KeyError: 
51                          block = ext_block(self.sz) 
52                          self.x[iblock] = block 
53                  self._len = max(self._len, k) 
54                  block.set(k - iblock*self.sz, v) 
55   
56   
57 -        def __getitem__(self, k): 
58                  iblock = k//self.sz 
59                  try: 
60                          block = self.x[iblock] 
61                  except KeyError: 
62                          raise IndexError, k 
63                  return self.get(k - iblock*self.sz, k) 
64           
65   
66 -        def unset(self, key): 
67                  iblock = key//self.sz 
68                  try: 
69                          block = self.x[iblock] 
70                  except KeyError: 
71                          return 
72                  if block.unset(key - iblock*self.sz): 
73                          del self.x[iblock] 
74   
75   
76 -        def __contains__(self, item): 
77                  for b in self.x.itervalues(): 
78                          if b.contains(item): 
79                                  return True 
80                  return False 
81   
82 -        def __iter__(self): 
83                  for b in self.x.itervalues(): 
84                          nz = Num.nonzero(b.mask) 
85                          v = b.v 
86                          for i in nz: 
87                                  yield v[i] 
88