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