COW.py 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320
  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. from inspect import getmro
  26. import copy
  27. import types, sets
  28. types.ImmutableTypes = tuple([ \
  29. types.BooleanType, \
  30. types.ComplexType, \
  31. types.FloatType, \
  32. types.IntType, \
  33. types.LongType, \
  34. types.NoneType, \
  35. types.TupleType, \
  36. sets.ImmutableSet] + \
  37. list(types.StringTypes))
  38. MUTABLE = "__mutable__"
  39. class COWMeta(type):
  40. pass
  41. class COWDictMeta(COWMeta):
  42. __warn__ = False
  43. __hasmutable__ = False
  44. __marker__ = tuple()
  45. def __str__(cls):
  46. # FIXME: I have magic numbers!
  47. return "<COWDict Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) - 3)
  48. __repr__ = __str__
  49. def cow(cls):
  50. class C(cls):
  51. __count__ = cls.__count__ + 1
  52. return C
  53. copy = cow
  54. __call__ = cow
  55. def __setitem__(cls, key, value):
  56. if not isinstance(value, types.ImmutableTypes):
  57. if not isinstance(value, COWMeta):
  58. cls.__hasmutable__ = True
  59. key += MUTABLE
  60. setattr(cls, key, value)
  61. def __getmutable__(cls, key, readonly=False):
  62. nkey = key + MUTABLE
  63. try:
  64. return cls.__dict__[nkey]
  65. except KeyError:
  66. pass
  67. value = getattr(cls, nkey)
  68. if readonly:
  69. return value
  70. if not cls.__warn__ is False and not isinstance(value, COWMeta):
  71. print >> cls.__warn__, "Warning: Doing a copy because %s is a mutable type." % key
  72. try:
  73. value = value.copy()
  74. except AttributeError, e:
  75. value = copy.copy(value)
  76. setattr(cls, nkey, value)
  77. return value
  78. __getmarker__ = []
  79. def __getreadonly__(cls, key, default=__getmarker__):
  80. """\
  81. Get a value (even if mutable) which you promise not to change.
  82. """
  83. return cls.__getitem__(key, default, True)
  84. def __getitem__(cls, key, default=__getmarker__, readonly=False):
  85. try:
  86. try:
  87. value = getattr(cls, key)
  88. except AttributeError:
  89. value = cls.__getmutable__(key, readonly)
  90. # This is for values which have been deleted
  91. if value is cls.__marker__:
  92. raise AttributeError("key %s does not exist." % key)
  93. return value
  94. except AttributeError, e:
  95. if not default is cls.__getmarker__:
  96. return default
  97. raise KeyError(str(e))
  98. def __delitem__(cls, key):
  99. cls.__setitem__(key, cls.__marker__)
  100. def __revertitem__(cls, key):
  101. if not cls.__dict__.has_key(key):
  102. key += MUTABLE
  103. delattr(cls, key)
  104. def has_key(cls, key):
  105. value = cls.__getreadonly__(key, cls.__marker__)
  106. if value is cls.__marker__:
  107. return False
  108. return True
  109. def iter(cls, type, readonly=False):
  110. for key in dir(cls):
  111. if key.startswith("__"):
  112. continue
  113. if key.endswith(MUTABLE):
  114. key = key[:-len(MUTABLE)]
  115. if type == "keys":
  116. yield key
  117. try:
  118. if readonly:
  119. value = cls.__getreadonly__(key)
  120. else:
  121. value = cls[key]
  122. except KeyError:
  123. continue
  124. if type == "values":
  125. yield value
  126. if type == "items":
  127. yield (key, value)
  128. raise StopIteration()
  129. def iterkeys(cls):
  130. return cls.iter("keys")
  131. def itervalues(cls, readonly=False):
  132. if not cls.__warn__ is False and cls.__hasmutable__ and readonly is False:
  133. print >> cls.__warn__, "Warning: If you arn't going to change any of the values call with True."
  134. return cls.iter("values", readonly)
  135. def iteritems(cls, readonly=False):
  136. if not cls.__warn__ is False and cls.__hasmutable__ and readonly is False:
  137. print >> cls.__warn__, "Warning: If you arn't going to change any of the values call with True."
  138. return cls.iter("items", readonly)
  139. class COWSetMeta(COWDictMeta):
  140. def __str__(cls):
  141. # FIXME: I have magic numbers!
  142. return "<COWSet Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) -3)
  143. __repr__ = __str__
  144. def cow(cls):
  145. class C(cls):
  146. __count__ = cls.__count__ + 1
  147. return C
  148. def add(cls, value):
  149. COWDictMeta.__setitem__(cls, repr(hash(value)), value)
  150. def remove(cls, value):
  151. COWDictMeta.__delitem__(cls, repr(hash(value)))
  152. def __in__(cls, value):
  153. return COWDictMeta.has_key(repr(hash(value)))
  154. def iterkeys(cls):
  155. raise TypeError("sets don't have keys")
  156. def iteritems(cls):
  157. raise TypeError("sets don't have 'items'")
  158. # These are the actual classes you use!
  159. class COWDictBase(object):
  160. __metaclass__ = COWDictMeta
  161. __count__ = 0
  162. class COWSetBase(object):
  163. __metaclass__ = COWSetMeta
  164. __count__ = 0
  165. if __name__ == "__main__":
  166. import sys
  167. COWDictBase.__warn__ = sys.stderr
  168. a = COWDictBase()
  169. print "a", a
  170. a['a'] = 'a'
  171. a['b'] = 'b'
  172. a['dict'] = {}
  173. b = a.copy()
  174. print "b", b
  175. b['c'] = 'b'
  176. print
  177. print "a", a
  178. for x in a.iteritems():
  179. print x
  180. print "--"
  181. print "b", b
  182. for x in b.iteritems():
  183. print x
  184. print
  185. b['dict']['a'] = 'b'
  186. b['a'] = 'c'
  187. print "a", a
  188. for x in a.iteritems():
  189. print x
  190. print "--"
  191. print "b", b
  192. for x in b.iteritems():
  193. print x
  194. print
  195. try:
  196. b['dict2']
  197. except KeyError, e:
  198. print "Okay!"
  199. a['set'] = COWSetBase()
  200. a['set'].add("o1")
  201. a['set'].add("o1")
  202. a['set'].add("o2")
  203. print "a", a
  204. for x in a['set'].itervalues():
  205. print x
  206. print "--"
  207. print "b", b
  208. for x in b['set'].itervalues():
  209. print x
  210. print
  211. b['set'].add('o3')
  212. print "a", a
  213. for x in a['set'].itervalues():
  214. print x
  215. print "--"
  216. print "b", b
  217. for x in b['set'].itervalues():
  218. print x
  219. print
  220. a['set2'] = set()
  221. a['set2'].add("o1")
  222. a['set2'].add("o1")
  223. a['set2'].add("o2")
  224. print "a", a
  225. for x in a.iteritems():
  226. print x
  227. print "--"
  228. print "b", b
  229. for x in b.iteritems(readonly=True):
  230. print x
  231. print
  232. del b['b']
  233. try:
  234. print b['b']
  235. except KeyError:
  236. print "Yay! deleted key raises error"
  237. if b.has_key('b'):
  238. print "Boo!"
  239. else:
  240. print "Yay - has_key with delete works!"
  241. print "a", a
  242. for x in a.iteritems():
  243. print x
  244. print "--"
  245. print "b", b
  246. for x in b.iteritems(readonly=True):
  247. print x
  248. print
  249. b.__revertitem__('b')
  250. print "a", a
  251. for x in a.iteritems():
  252. print x
  253. print "--"
  254. print "b", b
  255. for x in b.iteritems(readonly=True):
  256. print x
  257. print
  258. b.__revertitem__('dict')
  259. print "a", a
  260. for x in a.iteritems():
  261. print x
  262. print "--"
  263. print "b", b
  264. for x in b.iteritems(readonly=True):
  265. print x
  266. print