COW.py 8.0 KB

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