Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 1 | # ex:ts=4:sw=4:sts=4:et |
| 2 | # -*- tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- |
| 3 | # |
| 4 | # This is a copy on write dictionary and set which abuses classes to try and be nice and fast. |
| 5 | # |
| 6 | # Copyright (C) 2006 Tim Amsell |
| 7 | # |
| 8 | # This program is free software; you can redistribute it and/or modify |
| 9 | # it under the terms of the GNU General Public License version 2 as |
| 10 | # published by the Free Software Foundation. |
| 11 | # |
| 12 | # This program is distributed in the hope that it will be useful, |
| 13 | # but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 14 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 15 | # GNU General Public License for more details. |
| 16 | # |
| 17 | # You should have received a copy of the GNU General Public License along |
| 18 | # with this program; if not, write to the Free Software Foundation, Inc., |
| 19 | # 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
| 20 | # |
| 21 | #Please Note: |
| 22 | # Be careful when using mutable types (ie Dict and Lists) - operations involving these are SLOW. |
| 23 | # Assign a file to __warn__ to get warnings about slow operations. |
| 24 | # |
| 25 | |
| 26 | from __future__ import print_function |
| 27 | import copy |
| 28 | import types |
| 29 | ImmutableTypes = ( |
| 30 | types.NoneType, |
| 31 | bool, |
| 32 | complex, |
| 33 | float, |
| 34 | int, |
| 35 | long, |
| 36 | tuple, |
| 37 | frozenset, |
| 38 | basestring |
| 39 | ) |
| 40 | |
| 41 | MUTABLE = "__mutable__" |
| 42 | |
| 43 | class COWMeta(type): |
| 44 | pass |
| 45 | |
| 46 | class COWDictMeta(COWMeta): |
| 47 | __warn__ = False |
| 48 | __hasmutable__ = False |
| 49 | __marker__ = tuple() |
| 50 | |
| 51 | def __str__(cls): |
| 52 | # FIXME: I have magic numbers! |
| 53 | return "<COWDict Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) - 3) |
| 54 | __repr__ = __str__ |
| 55 | |
| 56 | def cow(cls): |
| 57 | class C(cls): |
| 58 | __count__ = cls.__count__ + 1 |
| 59 | return C |
| 60 | copy = cow |
| 61 | __call__ = cow |
| 62 | |
| 63 | def __setitem__(cls, key, value): |
| 64 | if not isinstance(value, ImmutableTypes): |
| 65 | if not isinstance(value, COWMeta): |
| 66 | cls.__hasmutable__ = True |
| 67 | key += MUTABLE |
| 68 | setattr(cls, key, value) |
| 69 | |
| 70 | def __getmutable__(cls, key, readonly=False): |
| 71 | nkey = key + MUTABLE |
| 72 | try: |
| 73 | return cls.__dict__[nkey] |
| 74 | except KeyError: |
| 75 | pass |
| 76 | |
| 77 | value = getattr(cls, nkey) |
| 78 | if readonly: |
| 79 | return value |
| 80 | |
| 81 | if not cls.__warn__ is False and not isinstance(value, COWMeta): |
| 82 | print("Warning: Doing a copy because %s is a mutable type." % key, file=cls.__warn__) |
| 83 | try: |
| 84 | value = value.copy() |
| 85 | except AttributeError as e: |
| 86 | value = copy.copy(value) |
| 87 | setattr(cls, nkey, value) |
| 88 | return value |
| 89 | |
| 90 | __getmarker__ = [] |
| 91 | def __getreadonly__(cls, key, default=__getmarker__): |
| 92 | """\ |
| 93 | Get a value (even if mutable) which you promise not to change. |
| 94 | """ |
| 95 | return cls.__getitem__(key, default, True) |
| 96 | |
| 97 | def __getitem__(cls, key, default=__getmarker__, readonly=False): |
| 98 | try: |
| 99 | try: |
| 100 | value = getattr(cls, key) |
| 101 | except AttributeError: |
| 102 | value = cls.__getmutable__(key, readonly) |
| 103 | |
| 104 | # This is for values which have been deleted |
| 105 | if value is cls.__marker__: |
| 106 | raise AttributeError("key %s does not exist." % key) |
| 107 | |
| 108 | return value |
| 109 | except AttributeError as e: |
| 110 | if not default is cls.__getmarker__: |
| 111 | return default |
| 112 | |
| 113 | raise KeyError(str(e)) |
| 114 | |
| 115 | def __delitem__(cls, key): |
| 116 | cls.__setitem__(key, cls.__marker__) |
| 117 | |
| 118 | def __revertitem__(cls, key): |
| 119 | if not cls.__dict__.has_key(key): |
| 120 | key += MUTABLE |
| 121 | delattr(cls, key) |
| 122 | |
| 123 | def __contains__(cls, key): |
| 124 | return cls.has_key(key) |
| 125 | |
| 126 | def has_key(cls, key): |
| 127 | value = cls.__getreadonly__(key, cls.__marker__) |
| 128 | if value is cls.__marker__: |
| 129 | return False |
| 130 | return True |
| 131 | |
| 132 | def iter(cls, type, readonly=False): |
| 133 | for key in dir(cls): |
| 134 | if key.startswith("__"): |
| 135 | continue |
| 136 | |
| 137 | if key.endswith(MUTABLE): |
| 138 | key = key[:-len(MUTABLE)] |
| 139 | |
| 140 | if type == "keys": |
| 141 | yield key |
| 142 | |
| 143 | try: |
| 144 | if readonly: |
| 145 | value = cls.__getreadonly__(key) |
| 146 | else: |
| 147 | value = cls[key] |
| 148 | except KeyError: |
| 149 | continue |
| 150 | |
| 151 | if type == "values": |
| 152 | yield value |
| 153 | if type == "items": |
| 154 | yield (key, value) |
| 155 | raise StopIteration() |
| 156 | |
| 157 | def iterkeys(cls): |
| 158 | return cls.iter("keys") |
| 159 | def itervalues(cls, readonly=False): |
| 160 | if not cls.__warn__ is False and cls.__hasmutable__ and readonly is False: |
| 161 | print("Warning: If you arn't going to change any of the values call with True.", file=cls.__warn__) |
| 162 | return cls.iter("values", readonly) |
| 163 | def iteritems(cls, readonly=False): |
| 164 | if not cls.__warn__ is False and cls.__hasmutable__ and readonly is False: |
| 165 | print("Warning: If you arn't going to change any of the values call with True.", file=cls.__warn__) |
| 166 | return cls.iter("items", readonly) |
| 167 | |
| 168 | class COWSetMeta(COWDictMeta): |
| 169 | def __str__(cls): |
| 170 | # FIXME: I have magic numbers! |
| 171 | return "<COWSet Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) -3) |
| 172 | __repr__ = __str__ |
| 173 | |
| 174 | def cow(cls): |
| 175 | class C(cls): |
| 176 | __count__ = cls.__count__ + 1 |
| 177 | return C |
| 178 | |
| 179 | def add(cls, value): |
| 180 | COWDictMeta.__setitem__(cls, repr(hash(value)), value) |
| 181 | |
| 182 | def remove(cls, value): |
| 183 | COWDictMeta.__delitem__(cls, repr(hash(value))) |
| 184 | |
| 185 | def __in__(cls, value): |
| 186 | return COWDictMeta.has_key(repr(hash(value))) |
| 187 | |
| 188 | def iterkeys(cls): |
| 189 | raise TypeError("sets don't have keys") |
| 190 | |
| 191 | def iteritems(cls): |
| 192 | raise TypeError("sets don't have 'items'") |
| 193 | |
| 194 | # These are the actual classes you use! |
| 195 | class COWDictBase(object): |
| 196 | __metaclass__ = COWDictMeta |
| 197 | __count__ = 0 |
| 198 | |
| 199 | class COWSetBase(object): |
| 200 | __metaclass__ = COWSetMeta |
| 201 | __count__ = 0 |
| 202 | |
| 203 | if __name__ == "__main__": |
| 204 | import sys |
| 205 | COWDictBase.__warn__ = sys.stderr |
| 206 | a = COWDictBase() |
| 207 | print("a", a) |
| 208 | |
| 209 | a['a'] = 'a' |
| 210 | a['b'] = 'b' |
| 211 | a['dict'] = {} |
| 212 | |
| 213 | b = a.copy() |
| 214 | print("b", b) |
| 215 | b['c'] = 'b' |
| 216 | |
| 217 | print() |
| 218 | |
| 219 | print("a", a) |
| 220 | for x in a.iteritems(): |
| 221 | print(x) |
| 222 | print("--") |
| 223 | print("b", b) |
| 224 | for x in b.iteritems(): |
| 225 | print(x) |
| 226 | print() |
| 227 | |
| 228 | b['dict']['a'] = 'b' |
| 229 | b['a'] = 'c' |
| 230 | |
| 231 | print("a", a) |
| 232 | for x in a.iteritems(): |
| 233 | print(x) |
| 234 | print("--") |
| 235 | print("b", b) |
| 236 | for x in b.iteritems(): |
| 237 | print(x) |
| 238 | print() |
| 239 | |
| 240 | try: |
| 241 | b['dict2'] |
| 242 | except KeyError as e: |
| 243 | print("Okay!") |
| 244 | |
| 245 | a['set'] = COWSetBase() |
| 246 | a['set'].add("o1") |
| 247 | a['set'].add("o1") |
| 248 | a['set'].add("o2") |
| 249 | |
| 250 | print("a", a) |
| 251 | for x in a['set'].itervalues(): |
| 252 | print(x) |
| 253 | print("--") |
| 254 | print("b", b) |
| 255 | for x in b['set'].itervalues(): |
| 256 | print(x) |
| 257 | print() |
| 258 | |
| 259 | b['set'].add('o3') |
| 260 | |
| 261 | print("a", a) |
| 262 | for x in a['set'].itervalues(): |
| 263 | print(x) |
| 264 | print("--") |
| 265 | print("b", b) |
| 266 | for x in b['set'].itervalues(): |
| 267 | print(x) |
| 268 | print() |
| 269 | |
| 270 | a['set2'] = set() |
| 271 | a['set2'].add("o1") |
| 272 | a['set2'].add("o1") |
| 273 | a['set2'].add("o2") |
| 274 | |
| 275 | print("a", a) |
| 276 | for x in a.iteritems(): |
| 277 | print(x) |
| 278 | print("--") |
| 279 | print("b", b) |
| 280 | for x in b.iteritems(readonly=True): |
| 281 | print(x) |
| 282 | print() |
| 283 | |
| 284 | del b['b'] |
| 285 | try: |
| 286 | print(b['b']) |
| 287 | except KeyError: |
| 288 | print("Yay! deleted key raises error") |
| 289 | |
| 290 | if b.has_key('b'): |
| 291 | print("Boo!") |
| 292 | else: |
| 293 | print("Yay - has_key with delete works!") |
| 294 | |
| 295 | print("a", a) |
| 296 | for x in a.iteritems(): |
| 297 | print(x) |
| 298 | print("--") |
| 299 | print("b", b) |
| 300 | for x in b.iteritems(readonly=True): |
| 301 | print(x) |
| 302 | print() |
| 303 | |
| 304 | b.__revertitem__('b') |
| 305 | |
| 306 | print("a", a) |
| 307 | for x in a.iteritems(): |
| 308 | print(x) |
| 309 | print("--") |
| 310 | print("b", b) |
| 311 | for x in b.iteritems(readonly=True): |
| 312 | print(x) |
| 313 | print() |
| 314 | |
| 315 | b.__revertitem__('dict') |
| 316 | print("a", a) |
| 317 | for x in a.iteritems(): |
| 318 | print(x) |
| 319 | print("--") |
| 320 | print("b", b) |
| 321 | for x in b.iteritems(readonly=True): |
| 322 | print(x) |
| 323 | print() |