1 #!/usr/bin/env python 2 3 """ 4 Object set support. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013 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 __len__(self): 59 return len(self.keys()) 60 61 def __iter__(self): 62 return iter(self.keys()) 63 64 def __nonzero__(self): 65 return self.objects != {} 66 67 # List methods. 68 69 def __add__(self, other): 70 obj = ObjectSet(self) 71 for key in other: 72 obj.add(key) 73 return obj 74 75 # Set membership and comparisons. 76 77 def __hash__(self): 78 l = self.keys() 79 l.sort() 80 return hash(tuple(l)) 81 82 def __eq__(self, other): 83 if hasattr(other, "objects"): 84 return self.objects == other.objects 85 else: 86 return set(self.objects.keys()) == set(other) 87 88 # Set methods. 89 90 def add(self, obj): 91 if not self.has_key(obj): 92 self[obj] = set() 93 94 def issubset(self, other): 95 return set(self).issubset(other) 96 97 # Dictionary and related methods. 98 99 def __getitem__(self, key): 100 return self.objects[key] 101 102 def get(self, key, default=None): 103 return self.objects.get(key, default) 104 105 def __setitem__(self, key, value): 106 self.objects[key] = value 107 108 def has_key(self, key): 109 return self.objects.has_key(key) 110 111 def keys(self): 112 return self.objects.keys() 113 114 def values(self): 115 return self.objects.values() 116 117 def items(self): 118 return self.objects.items() 119 120 def update(self, other): 121 122 # Combining dictionary-like objects involves combining values. 123 124 if hasattr(other, "items"): 125 for key, value in other.items(): 126 self[key] = add_sets(value, self.get(key, [])) 127 128 # Combining sequence-like objects involves just adding members. 129 130 else: 131 for key in other: 132 self.add(key) 133 134 def merge(self, other): 135 136 """ 137 Merge this object set with an 'other' set, combining the values where 138 possible, and incorporating values present in only one of the sets. 139 """ 140 141 return combine(self, other, ObjectSet(), add_sets) 142 143 def deepen_mapping_dict(d): 144 145 "Convert the values of 'd' to be elements of a potentially larger set." 146 147 new_dict = {} 148 for key, value in d.items(): 149 if value is None: 150 new_dict[key] = None 151 else: 152 new_dict[key] = ObjectSet([value]) 153 return new_dict 154 155 def merge_mapping_dicts(dicts): 156 157 "Merge the given 'dicts' mapping keys to sets of objects." 158 159 new_dict = {} 160 update_mapping_dict(new_dict, dicts) 161 return new_dict 162 163 def update_mapping_dict(new_dict, dicts): 164 165 """ 166 Update 'new_dict' with the contents of the set dictionary 'dicts'. 167 None entries may be incorporated into object sets. For example: 168 169 d1: {'a' : None} 170 d2: {'a' : x} 171 -> {'a' : {None, x}} 172 173 Here, None might be used to represent an empty set and x may be an existing 174 set. 175 """ 176 177 for old_dict in dicts: 178 for key, value in old_dict.items(): 179 180 # Add existing mappings within an object set. 181 182 if not new_dict.has_key(key): 183 if value is not None: 184 new_dict[key] = ObjectSet(value) 185 else: 186 new_dict[key] = None 187 elif new_dict[key] is not None: 188 if value is not None: 189 new_dict[key].update(value) 190 else: 191 new_dict[key].add(value) 192 else: 193 if value is not None: 194 objset = new_dict[key] = ObjectSet(value) 195 objset.add(None) 196 197 def combine_mapping_dicts(d1, d2): 198 199 """ 200 Combine dictionaries 'd1' and 'd2' in a resulting dictionary, with the 201 values of the contributing dictionaries being themselves combined such that 202 a "product" of the values for a given key are stored in the combined 203 dictionary. 204 205 For example: 206 207 d1: {'a' : [{'f', 'g'}, {'f', 'h'}], ...} 208 d2: {'a' : [{'f'}, {'e', 'f', 'g'}], ...} 209 -> {'a' : [{'f', 'g'}, {'f', 'h'}, {'e', 'f', 'g'}, {'e', 'f', 'g', 'h'}], ...} 210 211 Note that items of 'd2' whose keys are not in 'd1' are not added to 'd1' 212 since this, in the context of propagating attribute usage observations, 213 would result in spurious usage details being made available in places where 214 the names may not have been defined. 215 """ 216 217 return combine(d1, d2, {}, combine_object_set_lists, True) 218 219 def combine(d1, d2, combined, combine_op, only_d1_keys=False): 220 221 """ 222 Combine dictionaries 'd1' and 'd2' in the 'combined' object provided, using 223 the 'combine_op' to merge values from the dictionaries. 224 225 If 'only_d1_keys' is set to a true value, items from 'd2' employing keys not 226 in 'd1' will not be added to 'd1'. 227 """ 228 229 if d2 is not None: 230 d2_keys = d2.keys() 231 232 for key in d2_keys: 233 if not d1.has_key(key): 234 if not only_d1_keys: 235 combined[key] = d2[key] 236 else: 237 combined[key] = combine_op(d1[key], d2[key]) 238 else: 239 d2_keys = () 240 241 for key in d1.keys(): 242 if key not in d2_keys: 243 combined[key] = d1[key] 244 245 return combined 246 247 def combine_object_set_lists(l1, l2): 248 249 """ 250 Combine lists of object sets 'l1' and 'l2' to make a product of their 251 members. 252 """ 253 254 # If either list is undefined (indicated by None), return the defined list, 255 # or return None if neither is defined. 256 257 if l1 is None: 258 if l2 is None: 259 return None 260 else: 261 return l2 + [] 262 elif l2 is None: 263 return l1 + [] 264 265 combined = ObjectSet() 266 for i1 in l1: 267 for i2 in l2: 268 combined.add(i1.merge(i2)) 269 return combined 270 271 def add_sets(s1, s2): 272 return set(list(s1) + list(s2)) 273 274 # vim: tabstop=4 expandtab shiftwidth=4