blob: 6917ec378a37bd10d0d020079388f71a7cac4d60 [file] [log] [blame]
Patrick Williamsc124f4f2015-09-15 14:41:29 -05001# 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
26from __future__ import print_function
27import copy
28import types
29ImmutableTypes = (
30 types.NoneType,
31 bool,
32 complex,
33 float,
34 int,
35 long,
36 tuple,
37 frozenset,
38 basestring
39)
40
41MUTABLE = "__mutable__"
42
43class COWMeta(type):
44 pass
45
46class 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
168class 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!
195class COWDictBase(object):
196 __metaclass__ = COWDictMeta
197 __count__ = 0
198
199class COWSetBase(object):
200 __metaclass__ = COWSetMeta
201 __count__ = 0
202
203if __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()