COW.py 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319
  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. import copy
  26. import types
  27. ImmutableTypes = (
  28. bool,
  29. complex,
  30. float,
  31. int,
  32. tuple,
  33. frozenset,
  34. str
  35. )
  36. MUTABLE = "__mutable__"
  37. class COWMeta(type):
  38. pass
  39. class COWDictMeta(COWMeta):
  40. __warn__ = False
  41. __hasmutable__ = False
  42. __marker__ = tuple()
  43. def __str__(cls):
  44. # FIXME: I have magic numbers!
  45. return "<COWDict Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) - 3)
  46. __repr__ = __str__
  47. def cow(cls):
  48. class C(cls):
  49. __count__ = cls.__count__ + 1
  50. return C
  51. copy = cow
  52. __call__ = cow
  53. def __setitem__(cls, key, value):
  54. if value is not None and not isinstance(value, ImmutableTypes):
  55. if not isinstance(value, COWMeta):
  56. cls.__hasmutable__ = True
  57. key += MUTABLE
  58. setattr(cls, key, value)
  59. def __getmutable__(cls, key, readonly=False):
  60. nkey = key + MUTABLE
  61. try:
  62. return cls.__dict__[nkey]
  63. except KeyError:
  64. pass
  65. value = getattr(cls, nkey)
  66. if readonly:
  67. return value
  68. if not cls.__warn__ is False and not isinstance(value, COWMeta):
  69. print("Warning: Doing a copy because %s is a mutable type." % key, file=cls.__warn__)
  70. try:
  71. value = value.copy()
  72. except AttributeError as e:
  73. value = copy.copy(value)
  74. setattr(cls, nkey, value)
  75. return value
  76. __getmarker__ = []
  77. def __getreadonly__(cls, key, default=__getmarker__):
  78. """\
  79. Get a value (even if mutable) which you promise not to change.
  80. """
  81. return cls.__getitem__(key, default, True)
  82. def __getitem__(cls, key, default=__getmarker__, readonly=False):
  83. try:
  84. try:
  85. value = getattr(cls, key)
  86. except AttributeError:
  87. value = cls.__getmutable__(key, readonly)
  88. # This is for values which have been deleted
  89. if value is cls.__marker__:
  90. raise AttributeError("key %s does not exist." % key)
  91. return value
  92. except AttributeError as e:
  93. if not default is cls.__getmarker__:
  94. return default
  95. raise KeyError(str(e))
  96. def __delitem__(cls, key):
  97. cls.__setitem__(key, cls.__marker__)
  98. def __revertitem__(cls, key):
  99. if key not in cls.__dict__:
  100. key += MUTABLE
  101. delattr(cls, key)
  102. def __contains__(cls, key):
  103. return cls.has_key(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("Warning: If you arn't going to change any of the values call with True.", file=cls.__warn__)
  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("Warning: If you arn't going to change any of the values call with True.", file=cls.__warn__)
  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 repr(hash(value)) in COWDictMeta
  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, metaclass = COWDictMeta):
  160. __count__ = 0
  161. class COWSetBase(object, metaclass = COWSetMeta):
  162. __count__ = 0
  163. if __name__ == "__main__":
  164. import sys
  165. COWDictBase.__warn__ = sys.stderr
  166. a = COWDictBase()
  167. print("a", a)
  168. a['a'] = 'a'
  169. a['b'] = 'b'
  170. a['dict'] = {}
  171. b = a.copy()
  172. print("b", b)
  173. b['c'] = 'b'
  174. print()
  175. print("a", a)
  176. for x in a.items():
  177. print(x)
  178. print("--")
  179. print("b", b)
  180. for x in b.items():
  181. print(x)
  182. print()
  183. b['dict']['a'] = 'b'
  184. b['a'] = 'c'
  185. print("a", a)
  186. for x in a.items():
  187. print(x)
  188. print("--")
  189. print("b", b)
  190. for x in b.items():
  191. print(x)
  192. print()
  193. try:
  194. b['dict2']
  195. except KeyError as e:
  196. print("Okay!")
  197. a['set'] = COWSetBase()
  198. a['set'].add("o1")
  199. a['set'].add("o1")
  200. a['set'].add("o2")
  201. print("a", a)
  202. for x in a['set'].values():
  203. print(x)
  204. print("--")
  205. print("b", b)
  206. for x in b['set'].values():
  207. print(x)
  208. print()
  209. b['set'].add('o3')
  210. print("a", a)
  211. for x in a['set'].values():
  212. print(x)
  213. print("--")
  214. print("b", b)
  215. for x in b['set'].values():
  216. print(x)
  217. print()
  218. a['set2'] = set()
  219. a['set2'].add("o1")
  220. a['set2'].add("o1")
  221. a['set2'].add("o2")
  222. print("a", a)
  223. for x in a.items():
  224. print(x)
  225. print("--")
  226. print("b", b)
  227. for x in b.iteritems(readonly=True):
  228. print(x)
  229. print()
  230. del b['b']
  231. try:
  232. print(b['b'])
  233. except KeyError:
  234. print("Yay! deleted key raises error")
  235. if 'b' in b:
  236. print("Boo!")
  237. else:
  238. print("Yay - has_key with delete works!")
  239. print("a", a)
  240. for x in a.items():
  241. print(x)
  242. print("--")
  243. print("b", b)
  244. for x in b.iteritems(readonly=True):
  245. print(x)
  246. print()
  247. b.__revertitem__('b')
  248. print("a", a)
  249. for x in a.items():
  250. print(x)
  251. print("--")
  252. print("b", b)
  253. for x in b.iteritems(readonly=True):
  254. print(x)
  255. print()
  256. b.__revertitem__('dict')
  257. print("a", a)
  258. for x in a.items():
  259. print(x)
  260. print("--")
  261. print("b", b)
  262. for x in b.iteritems(readonly=True):
  263. print(x)
  264. print()