blob: bec62080967cc6563ad2e2ffae9ca04323a18e2d [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#
Brad Bishopd7bf8c12018-02-25 22:55:05 -05006# Copyright (C) 2006 Tim Ansell
Patrick Williamsc124f4f2015-09-15 14:41:29 -05007#
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
Patrick Williamsc0f7c042017-02-23 20:41:17 -060026
Patrick Williamsc124f4f2015-09-15 14:41:29 -050027import copy
28import types
29ImmutableTypes = (
Patrick Williamsc124f4f2015-09-15 14:41:29 -050030 bool,
31 complex,
32 float,
33 int,
Patrick Williamsc124f4f2015-09-15 14:41:29 -050034 tuple,
35 frozenset,
Patrick Williamsc0f7c042017-02-23 20:41:17 -060036 str
Patrick Williamsc124f4f2015-09-15 14:41:29 -050037)
38
39MUTABLE = "__mutable__"
40
41class COWMeta(type):
42 pass
43
44class COWDictMeta(COWMeta):
45 __warn__ = False
46 __hasmutable__ = False
47 __marker__ = tuple()
48
49 def __str__(cls):
50 # FIXME: I have magic numbers!
51 return "<COWDict Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) - 3)
52 __repr__ = __str__
53
54 def cow(cls):
55 class C(cls):
56 __count__ = cls.__count__ + 1
57 return C
58 copy = cow
59 __call__ = cow
60
61 def __setitem__(cls, key, value):
Patrick Williamsc0f7c042017-02-23 20:41:17 -060062 if value is not None and not isinstance(value, ImmutableTypes):
Patrick Williamsc124f4f2015-09-15 14:41:29 -050063 if not isinstance(value, COWMeta):
64 cls.__hasmutable__ = True
65 key += MUTABLE
66 setattr(cls, key, value)
67
68 def __getmutable__(cls, key, readonly=False):
69 nkey = key + MUTABLE
70 try:
71 return cls.__dict__[nkey]
72 except KeyError:
73 pass
74
75 value = getattr(cls, nkey)
76 if readonly:
77 return value
78
79 if not cls.__warn__ is False and not isinstance(value, COWMeta):
80 print("Warning: Doing a copy because %s is a mutable type." % key, file=cls.__warn__)
81 try:
82 value = value.copy()
83 except AttributeError as e:
84 value = copy.copy(value)
85 setattr(cls, nkey, value)
86 return value
87
88 __getmarker__ = []
89 def __getreadonly__(cls, key, default=__getmarker__):
90 """\
91 Get a value (even if mutable) which you promise not to change.
92 """
93 return cls.__getitem__(key, default, True)
94
95 def __getitem__(cls, key, default=__getmarker__, readonly=False):
96 try:
97 try:
98 value = getattr(cls, key)
99 except AttributeError:
100 value = cls.__getmutable__(key, readonly)
101
102 # This is for values which have been deleted
103 if value is cls.__marker__:
104 raise AttributeError("key %s does not exist." % key)
105
106 return value
107 except AttributeError as e:
108 if not default is cls.__getmarker__:
109 return default
110
111 raise KeyError(str(e))
112
113 def __delitem__(cls, key):
114 cls.__setitem__(key, cls.__marker__)
115
116 def __revertitem__(cls, key):
Patrick Williamsc0f7c042017-02-23 20:41:17 -0600117 if key not in cls.__dict__:
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500118 key += MUTABLE
119 delattr(cls, key)
120
121 def __contains__(cls, key):
122 return cls.has_key(key)
123
124 def has_key(cls, key):
125 value = cls.__getreadonly__(key, cls.__marker__)
126 if value is cls.__marker__:
127 return False
128 return True
129
130 def iter(cls, type, readonly=False):
131 for key in dir(cls):
132 if key.startswith("__"):
133 continue
134
135 if key.endswith(MUTABLE):
136 key = key[:-len(MUTABLE)]
137
138 if type == "keys":
139 yield key
140
141 try:
142 if readonly:
143 value = cls.__getreadonly__(key)
144 else:
145 value = cls[key]
146 except KeyError:
147 continue
148
149 if type == "values":
150 yield value
151 if type == "items":
152 yield (key, value)
153 raise StopIteration()
154
155 def iterkeys(cls):
156 return cls.iter("keys")
157 def itervalues(cls, readonly=False):
158 if not cls.__warn__ is False and cls.__hasmutable__ and readonly is False:
159 print("Warning: If you arn't going to change any of the values call with True.", file=cls.__warn__)
160 return cls.iter("values", readonly)
161 def iteritems(cls, readonly=False):
162 if not cls.__warn__ is False and cls.__hasmutable__ and readonly is False:
163 print("Warning: If you arn't going to change any of the values call with True.", file=cls.__warn__)
164 return cls.iter("items", readonly)
165
166class COWSetMeta(COWDictMeta):
167 def __str__(cls):
168 # FIXME: I have magic numbers!
169 return "<COWSet Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) -3)
170 __repr__ = __str__
171
172 def cow(cls):
173 class C(cls):
174 __count__ = cls.__count__ + 1
175 return C
176
177 def add(cls, value):
178 COWDictMeta.__setitem__(cls, repr(hash(value)), value)
179
180 def remove(cls, value):
181 COWDictMeta.__delitem__(cls, repr(hash(value)))
182
183 def __in__(cls, value):
Patrick Williamsc0f7c042017-02-23 20:41:17 -0600184 return repr(hash(value)) in COWDictMeta
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500185
186 def iterkeys(cls):
187 raise TypeError("sets don't have keys")
188
189 def iteritems(cls):
190 raise TypeError("sets don't have 'items'")
191
192# These are the actual classes you use!
Patrick Williamsc0f7c042017-02-23 20:41:17 -0600193class COWDictBase(object, metaclass = COWDictMeta):
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500194 __count__ = 0
195
Patrick Williamsc0f7c042017-02-23 20:41:17 -0600196class COWSetBase(object, metaclass = COWSetMeta):
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500197 __count__ = 0
198
199if __name__ == "__main__":
200 import sys
201 COWDictBase.__warn__ = sys.stderr
202 a = COWDictBase()
203 print("a", a)
204
205 a['a'] = 'a'
206 a['b'] = 'b'
207 a['dict'] = {}
208
209 b = a.copy()
210 print("b", b)
211 b['c'] = 'b'
212
213 print()
214
215 print("a", a)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500216 for x in a.iteritems():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500217 print(x)
218 print("--")
219 print("b", b)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500220 for x in b.iteritems():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500221 print(x)
222 print()
223
224 b['dict']['a'] = 'b'
225 b['a'] = 'c'
226
227 print("a", a)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500228 for x in a.iteritems():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500229 print(x)
230 print("--")
231 print("b", b)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500232 for x in b.iteritems():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500233 print(x)
234 print()
235
236 try:
237 b['dict2']
238 except KeyError as e:
239 print("Okay!")
240
241 a['set'] = COWSetBase()
242 a['set'].add("o1")
243 a['set'].add("o1")
244 a['set'].add("o2")
245
246 print("a", a)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500247 for x in a['set'].itervalues():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500248 print(x)
249 print("--")
250 print("b", b)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500251 for x in b['set'].itervalues():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500252 print(x)
253 print()
254
255 b['set'].add('o3')
256
257 print("a", a)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500258 for x in a['set'].itervalues():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500259 print(x)
260 print("--")
261 print("b", b)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500262 for x in b['set'].itervalues():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500263 print(x)
264 print()
265
266 a['set2'] = set()
267 a['set2'].add("o1")
268 a['set2'].add("o1")
269 a['set2'].add("o2")
270
271 print("a", a)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500272 for x in a.iteritems():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500273 print(x)
274 print("--")
275 print("b", b)
276 for x in b.iteritems(readonly=True):
277 print(x)
278 print()
279
280 del b['b']
281 try:
282 print(b['b'])
283 except KeyError:
284 print("Yay! deleted key raises error")
285
Patrick Williamsc0f7c042017-02-23 20:41:17 -0600286 if 'b' in b:
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500287 print("Boo!")
288 else:
289 print("Yay - has_key with delete works!")
290
291 print("a", a)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500292 for x in a.iteritems():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500293 print(x)
294 print("--")
295 print("b", b)
296 for x in b.iteritems(readonly=True):
297 print(x)
298 print()
299
300 b.__revertitem__('b')
301
302 print("a", a)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500303 for x in a.iteritems():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500304 print(x)
305 print("--")
306 print("b", b)
307 for x in b.iteritems(readonly=True):
308 print(x)
309 print()
310
311 b.__revertitem__('dict')
312 print("a", a)
Brad Bishop6e60e8b2018-02-01 10:27:11 -0500313 for x in a.iteritems():
Patrick Williamsc124f4f2015-09-15 14:41:29 -0500314 print(x)
315 print("--")
316 print("b", b)
317 for x in b.iteritems(readonly=True):
318 print(x)
319 print()