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