gmisclib.nice

1

2 -class DontHashThis(Exception):

3 """If your trimmer funcion raises this exception, then the input 4 to nice_hash.add() will be ignored.""" 5

6 - def __init__(self):

7 Exception.__init__(self)

8 9

10 -class NotInHash(KeyError):

11 - def __init__(self, s):

12 KeyError.__init__(self, s)

13 14 15 16

17 -class simple(object):

18 __doc__ = """This class generates a map from inputs to integers, 19 where an equivalence class is defined by the trimmer function. 20 It is just a stripped-down version of the L{hash} class 21 defined above. Faster and less memory consumption, if 22 you don't need the rmap method. 23 """ 24 25 26

27 - def __init__(self, trimmer=None):

28 """ 29 @param trimmer: Defines equivalence classes on list; 30 it can be some sort of projection operation. 31 The default (None) makes the identity class equal to the inputs. 32 It can also specify which inputs to ignore by raising the 33 L{DontHashThis} exception. 34 """ 35 self.trimmed_seen = {} 36 self.n = 0 37 if trimmer is None: 38 def trimmer(x): 39 return x

40 self.trimmer = trimmer

41 42

43 - def add(self, x):

44 """Returns an integer which is shared among all x in the 45 equivalence class, but different from all other x. 46 If the trimmer function raises the DontHashThis exception, 47 it will ignore the input and return None. 48 @returns: int 49 """ 50 51 try: 52 xt = self.trimmer(x) 53 except DontHashThis: 54 return None 55 56 try: 57 i = self.trimmed_seen[xt] 58 except KeyError: 59 i = self.n 60 self.trimmed_seen[xt] = i 61 self.n += 1 62 return i

63 64

65 - def add_newonly(self, x):

66 """Similar to add, except it returns None if the equivalence 67 class has already appeared. 68 @returns: int or None 69 """ 70 71 try: 72 xt = self.trimmer(x) 73 except DontHashThis: 74 return None 75 76 if xt in self.trimmed_seen: 77 return None 78 79 i = self.n 80 self.trimmed_seen[xt] = i 81 self.n += 1 82 return i

83 84

85 - def get_image(self, x):

86 """Returns an integer which is shared among all x in the 87 equivalence class, but different from all other x. 88 @note: the return value is the same as L{add}, except that 89 this doesn't add anything: rather than increasing the 90 size of the mapping, it raises NotInHash. 91 @raise NotInHash: when x is not in the hash table. 92 """ 93 94 try: 95 xt = self.trimmer(x) 96 except DontHashThis: 97 raise NotInHash('Trimmer raised DontHashThis') 98 try: 99 i = self.trimmed_seen[xt] 100 except KeyError: 101 raise NotInHash('Key: %s' % str(xt)) 102 return i

103 104

105 - def map(self):

106 """Return the map from classes (as returned by the trimmer function) 107 to integers.""" 108 return self.trimmed_seen.copy()

109 110

111 - def classes(self):

112 """Return a list over all the classes that have been seen.""" 113 return list(self.trimmed_seen.keys())

114 115

116 - def classmap(self):

117 """Return the map from integers to classes. 118 @return: [classname, classsname, ...] 119 """ 120 o = [None] * len(self.trimmed_seen) 121 for (x, i) in self.trimmed_seen.iteritems(): 122 o[i] = x 123 return o

124 125

126 -class hash(simple):

127 - def __init__(self, trimmer=None):

128 """This adds the L{rmap} method to the L{simple} class. 129 """ 130 simple.__init__(self, trimmer) 131 self.seen = []

132 133

134 - def rmap(self):

135 """Returns the map from integers to inputs.""" 136 # o = [ [] for i in range(len(self.trimmed_seen)) ] 137 o = [ [] for q in self.trimmed_seen.keys() ] 138 for (x, cl) in self.seen: 139 o[self.trimmed_seen[cl]].append(x) 140 return o

141 142

143 - def test(self):

144 map = self.map() 145 rmap = self.rmap() 146 for (intg, inpt) in rmap.iteritems(): 147 for s in inpt: 148 assert map[s] == intg

149

150 - def add(self, x):

151 """Returns an integer which is shared among all x in the 152 equivalence class, but different from all other x. 153 If the trimmer function raises the DontHashThis exception, 154 it will ignore the input and return None. 155 Note that if you add an item twice, it will appear twice in rmap(). 156 @returns: int 157 """ 158 159 try: 160 xt = self.trimmer(x) 161 except DontHashThis: 162 return None 163 self.seen.append((x, xt)) 164 165 try: 166 i = self.trimmed_seen[xt] 167 except KeyError: 168 i = self.n 169 self.trimmed_seen[xt] = i 170 self.n += 1 171 return i

172 173

174 - def add_newonly(self, x):

175 """Similar to add, except it returns None if the equivalence 176 class has already appeared. 177 178 The list of classes seen (self.seen) then 179 contains only the first item that was added in each class, 180 so L{rmap}() will produce a dictionary containing single-item lists: 181 C{{int1:[item1],int2:[item2],int3:[item3], ...}}. 182 Calls to L{add}() and L{add_newonly}() can be intermixed safely, 183 though the result of L{rmap}() will then not contain all added items. 184 @returns: int or None 185 """ 186 187 try: 188 xt = self.trimmer(x) 189 except DontHashThis: 190 return None 191 192 if xt in self.trimmed_seen: 193 return None 194 195 self.seen.append((x, xt)) 196 i = self.n 197 self.trimmed_seen[xt] = i 198 self.n += 1 199 return i

200 201 202 203 nice_hash = hash 204 205

206 -def map(list, trimmer=lambda x:x):

207 h = simple(trimmer) 208 for x in list: 209 h.add(x) 210 return h.map()

211 212 213 214 if __name__ == '__main___': 215 h = nice_hash(lambda x : x) 216 assert h.add('foo') == 0 217 assert h.add('bar') == 1 218 assert h.add('gleep') == 2 219 assert h.add('bar') == 1 220 h.test() 221 assert h.map()['bar'] == 1 222 assert h.rmap()[0] == ['foo'] 223 assert h.classmap()[1] == 'bar' 224

Source Code for Module gmisclib.nice_hash