1 #!/usr/bin/env python 2 3 """ 4 Object set support. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 import operator 23 24 try: 25 set 26 except NameError: 27 from sets import Set as set 28 29 class ObjectSet: 30 31 "A set of objects with optional associated data." 32 33 def __init__(self, d=None): 34 if d is None: 35 self.objects = {} 36 elif hasattr(d, "items"): 37 self.objects = dict(d) 38 else: 39 self.objects = {} 40 for key in d: 41 self.add(key) 42 43 def __repr__(self): 44 out = ["{"] 45 first = True 46 for key, value in self.items(): 47 if not first: 48 out.append(", ") 49 else: 50 first = False 51 out.append(repr(key)) 52 if value: 53 out.append(" : ") 54 out.append(repr(value)) 55 out.append("}") 56 return "".join(out) 57 58 def __iter__(self): 59 return iter(self.keys()) 60 61 def __nonzero__(self): 62 return self.objects != {} 63 64 # List methods. 65 66 def __add__(self, other): 67 obj = ObjectSet(self) 68 for key in other: 69 obj.add(key) 70 return obj 71 72 # Set membership and comparisons. 73 74 def __hash__(self): 75 l = self.keys() 76 l.sort() 77 return hash(tuple(l)) 78 79 def __eq__(self, other): 80 if hasattr(other, "objects"): 81 return self.objects == other.objects 82 else: 83 return set(self.objects.keys()) == set(other) 84 85 # Set methods. 86 87 def add(self, obj): 88 if not self.has_key(obj): 89 self[obj] = set() 90 91 def issubset(self, other): 92 return set(self).issubset(other) 93 94 # Dictionary and related methods. 95 96 def __getitem__(self, key): 97 return self.objects[key] 98 99 def get(self, key, default=None): 100 return self.objects.get(key, default) 101 102 def __setitem__(self, key, value): 103 self.objects[key] = value 104 105 def has_key(self, key): 106 return self.objects.has_key(key) 107 108 def keys(self): 109 return self.objects.keys() 110 111 def values(self): 112 return self.objects.values() 113 114 def items(self): 115 return self.objects.items() 116 117 def update(self, other): 118 119 # Combining dictionary-like objects involves combining values. 120 121 if hasattr(other, "items"): 122 for key, value in other.items(): 123 self[key] = add_sets(value, self.get(key, [])) 124 125 # Combining sequence-like objects involves just adding members. 126 127 else: 128 for key in other: 129 self.add(key) 130 131 def merge(self, other): 132 133 """ 134 Merge this object set with an 'other' set, combining the values where 135 possible, and incorporating values present in only one of the sets. 136 """ 137 138 return combine(self, other, ObjectSet(), add_sets) 139 140 def deepen_mapping_dict(d): 141 142 "Convert the values of 'd' to be elements of a potentially larger set." 143 144 new_dict = {} 145 for key, value in d.items(): 146 if value is None: 147 new_dict[key] = None 148 else: 149 new_dict[key] = ObjectSet([value]) 150 return new_dict 151 152 def merge_mapping_dicts(dicts): 153 154 "Merge the given 'dicts' mapping keys to sets of objects." 155 156 new_dict = {} 157 update_mapping_dict(new_dict, dicts) 158 return new_dict 159 160 def update_mapping_dict(new_dict, dicts): 161 162 """ 163 Update 'new_dict' with the contents of the set dictionary 'dicts'. 164 None entries may be incorporated into object sets. For example: 165 166 d1: {'a' : None} 167 d2: {'a' : x} 168 -> {'a' : {None, x}} 169 170 Here, None might be used to represent an empty set and x may be an existing 171 set. 172 """ 173 174 for old_dict in dicts: 175 for key, value in old_dict.items(): 176 177 # Add existing mappings within an object set. 178 179 if not new_dict.has_key(key): 180 if value is not None: 181 new_dict[key] = ObjectSet(value) 182 else: 183 new_dict[key] = None 184 elif new_dict[key] is not None: 185 if value is not None: 186 new_dict[key].update(value) 187 else: 188 new_dict[key].add(value) 189 else: 190 if value is not None: 191 objset = new_dict[key] = ObjectSet(value) 192 objset.add(None) 193 194 def combine_mapping_dicts(d1, d2): 195 196 """ 197 Combine dictionaries 'd1' and 'd2' in a resulting dictionary, with the 198 values of the contributing dictionaries being themselves combined such that 199 a "product" of the values for a given key are stored in the combined 200 dictionary. 201 202 For example: 203 204 d1: {'a' : [{'f', 'g'}, {'f', 'h'}], ...} 205 d2: {'a' : [{'f'}, {'e', 'f', 'g'}], ...} 206 -> {'a' : [{'f', 'g'}, {'f', 'h'}, {'e', 'f', 'g'}, {'e', 'f', 'g', 'h'}], ...} 207 208 Note that items of 'd2' whose keys are not in 'd1' are not added to 'd1' 209 since this, in the context of propagating attribute usage observations, 210 would result in spurious usage details being made available in places where 211 the names may not have been defined. 212 """ 213 214 return combine(d1, d2, {}, combine_object_set_lists, True) 215 216 def combine(d1, d2, combined, combine_op, only_d1_keys=False): 217 218 """ 219 Combine dictionaries 'd1' and 'd2' in the 'combined' object provided, using 220 the 'combine_op' to merge values from the dictionaries. 221 222 If 'only_d1_keys' is set to a true value, items from 'd2' employing keys not 223 in 'd1' will not be added to 'd1'. 224 """ 225 226 if d2 is not None: 227 d2_keys = d2.keys() 228 229 for key in d2_keys: 230 if not d1.has_key(key): 231 if not only_d1_keys: 232 combined[key] = d2[key] 233 else: 234 combined[key] = combine_op(d1[key], d2[key]) 235 else: 236 d2_keys = () 237 238 for key in d1.keys(): 239 if key not in d2_keys: 240 combined[key] = d1[key] 241 242 return combined 243 244 def combine_object_set_lists(l1, l2): 245 246 """ 247 Combine lists of object sets 'l1' and 'l2' to make a product of their 248 members. 249 """ 250 251 # If either list is undefined (indicated by None), return the defined list, 252 # or return None if neither is defined. 253 254 if l1 is None: 255 if l2 is None: 256 return None 257 else: 258 return l2 + [] 259 elif l2 is None: 260 return l1 + [] 261 262 combined = ObjectSet() 263 for i1 in l1: 264 for i2 in l2: 265 combined.add(i1.merge(i2)) 266 return combined 267 268 def add_sets(s1, s2): 269 return set(list(s1) + list(s2)) 270 271 # vim: tabstop=4 expandtab shiftwidth=4