1 """
2 Generic containers, data structures and language extensions.
3
4 This module has several functions:
5
6 1. provides a set of reusable, probably encapsulated collection containers
7 and supporting infrastructure: L{BaseDictionaryContainer},
8 L{BaseCollectionContainer}; also L{AbstractIndexer}
9
10 2. provides some missing generic data structures or data types:
11 L{OrderedDict}, L{Stack}; also the heavily used, type-safe L{enum} class
12 and some generic pattern implementations like L{singleton} or L{Proxy}
13
14 3. serves as a compatibility layer, making it possible to develop CSB as
15 platform- and Python version-independent: string, L{iterable}, L{metaclass}
16
17 In order to ensure cross-interpreter compatibility, checking for string instances
18 in CSB must always be implemented like this:
19
20 >>> isinstance("s", string)
21
22 because "basestring" is not available in Python 3. Also, metaclass definitions
23 other than abstract classes must be implemented as follows:
24
25 >>> MyClassBase = metaclass(MetaClass, base=BaseClass)
26 >>> class MyClass(MyClassBase):
27 pass
28
29 See also the notes about compatibility in L{csb.io}.
30 """
31
32 import re
33 import sys
34 import time
35 import threading
36
37 from abc import ABCMeta, abstractproperty, abstractmethod
38
39 try:
40 string = basestring
41 except NameError:
42 string = str
46
47 - def __init__(self, target, name=None, args=[], kwargs={}):
56
57 @property
60
62 try:
63 self.__result = self.__target(*self.__args, **self.__kwargs)
64 except Exception as ex:
65 sys.stderr.write(ex)
66 self.__result = None
67
69 """
70 Singleton class decorator.
71 """
72 instances = {}
73
74 def get():
75 if klass not in instances:
76 instances[klass] = klass()
77 return instances[klass]
78
79 return get
80
82 """
83 Property decorator with predefined getter/setter and value checking
84 or casting in the setter. The provided function will be the validator
85 and must take and return a value.
86
87 If the property is named C{foo}, a private field named C{_foo} will
88 be used to store the value.
89
90 Example:
91
92 >>> @validatedproperty
93 >>> def a(v):
94 >>> v = int(v)
95 >>> if v < 0:
96 >>> raise ValueError(v)
97 >>> return v
98
99 """
101 self.name = '_' + validator.__name__
102 self.__doc__ = validator.__doc__
103 self.validator = validator
104 self.argcount = validator.__code__.co_argcount
105 assert 1 <= self.argcount <= 2
106
108 if instance is None:
109 return self
110 return getattr(instance, self.name)
111
112 - def __set__(self, instance, value):
113 value = self.validator(value) if self.argcount == 1 else \
114 self.validator(instance, value)
115 setattr(instance, self.name, value)
116
118 """
119 Property decorator for convenient creation of typed, encapsulated fields.
120 The provided function must be a dummy, only its name is used.
121
122 Example:
123
124 >>> @typedproperty(float)
125 >>> def b():
126 >>> pass
127
128 """
131
133 assert func() is None
134 self.name = '_' + func.__name__
135 self.__doc__ = func.__doc__ or ''
136 if '@type:' not in self.__doc__:
137 self.__doc__ += '@type: ' + self.type.__name__
138 return self
139
141 if instance is None:
142 return self
143 return getattr(instance, self.name)
144
145 - def __set__(self, instance, value):
149
151 """
152 Base class implementing the proxy pattern. Subclasses that define
153 a customized constructor must call super().__init__(subject) for proper
154 initialization.
155
156 @param subject: an arbitrary object, hidden behind the proxy
157 """
158
161
163 try:
164 return object.__getattribute__(self, name)
165 except AttributeError:
166 subject = object.__getattribute__(self, '_subject')
167 return getattr(subject, name)
168
170
180
181 - def start(self, group=0):
182 try:
183 if not group >= 0:
184 raise IndexError
185 return self._start[group]
186 except IndexError:
187 raise IndexError('no such group')
188
189 - def end(self, group=0):
190 try:
191 if not group >= 0:
192 raise IndexError
193 return self._end[group]
194 except IndexError:
195 raise IndexError('no such group')
196
199
201
202 - def push(self, item):
203 """
204 Push an item onto the top of the stack
205 """
206 self.append(item)
207
209 """
210 Return the object at the top of the stack without removing it
211 """
212 if self.empty():
213 raise IndexError('peek in empty list')
214 return self[-1]
215
217 """
218 Return True if the stack is empty
219 """
220 return len(self) == 0
221
223 """
224 Return True if C{obj} is a collection or iterator, but not string.
225 This is guaranteed to work in both python 2 and 3.
226
227 @rtype: bool
228 """
229 if hasattr(obj, '__iter__'):
230 if not isinstance(obj, string):
231 return True
232
233 return False
234
241
243 """
244 Perform a deep copy of obj using cPickle. Faster than copy.deepcopy()
245 for large objects.
246
247 @param obj: the object to copy
248 @return: a deep copy of obj
249 @param recursion: maximum recursion limit
250 @type recursion: int
251 """
252 from csb.io import Pickle
253
254 current = sys.getrecursionlimit()
255 sys.setrecursionlimit(recursion)
256
257 tmp = Pickle.dumps(obj, Pickle.HIGHEST_PROTOCOL)
258 copy = Pickle.loads(tmp)
259
260 sys.setrecursionlimit(current)
261 return copy
262
265
268
271
273
275 self.__name = name
276 self.__value = value
277 self.__container = enum
278
280 return (_deserialize_enum, (self.enum, self.name))
286 return '{0}'.format(self.__name, self.__value)
288 return str(self.__value)
290 return int(self.__value)
292 return float(self.__value)
294 return hash(self.__value)
296 if isinstance(other, EnumItem):
297 return self.__value < other.value
298 else:
299 return self.__value < other
301 if isinstance(other, EnumItem):
302 return self.__value == other.value
303 else:
304 return self.__value == other
306 return not (self == other)
307
308 @property
311
312 @property
315
316 @property
318 return self.__container
319
321 assert getattr(enum, self.__name) is self
322 self.__container = enum
323
383
384
385 EnumBase = metaclass(EnumMeta)
386
387 -class enum(EnumBase):
388 """
389 Base class for all enumeration types. Supports both string and integer
390 enumeration values. Examples:
391
392 >>> class MolTypes(enum): DNA, RNA = range(2)
393 <MolTypes: RNA=1, DNA=0>
394 >>> class MolTypes(enum): DNA=1; RNA=2
395 <MolTypes: RNA=2, DNA=1>
396 >>> MolTypes.DNA
397 1
398 >>> MolTypes.DNA == 1
399 True
400 >>> int(MolTypes.DNA)
401 1
402 >>> repr(MolTypes.DNA)
403 'DNA'
404 >>> type(MolTypes.DNA)
405 L{EnumItem} instance
406
407 @note: The recommended way to create an enum is to define a public
408 subclass of L{enum} in the global namespace of your module. Nesting
409 the enum in another class for example will break pickling.
410 """
412 raise TypeError("Can't instantiate static enum type {0}".format(self.__class__))
413
415 """
416 A collection of efficient static methods for working with L{enum}
417 classes.
418 """
419
420 @staticmethod
421 - def create(classname, **members):
422 """
423 Dynamically create a new enum from a list of key:value pairs.
424 Note that each key must be a valid python identifier, and the
425 values must be unique.
426
427 @param classname: class name for the new enum
428 @type classname: str
429
430 @note: The recommended way to create an enum is to define a public
431 subclass of L{enum} in the global namespace of your module.
432 You should avoid creating enums dynamically if static
433 construction is possible, because dynamically created enums
434 cannot be pickled.
435 """
436
437 return type(classname, (enum,), members)
438
439 @staticmethod
441 """
442 Return all member items of the C{enumclass}.
443
444 @param enumclass: the enumeration class to traverse
445 @type enumclass: type
446
447 @return: a set of all enumclass members
448 @rtype: frozenset
449 """
450 return frozenset([enumclass.__dict__[i] for i in enumclass._names])
451
452 @staticmethod
454 """
455 Return the names of all items in the C{enumclass}.
456
457 @param enumclass: the enumeration class to traverse
458 @type enumclass: type
459
460 @return: a set of all enumclass member names
461 @rtype: frozenset
462 """
463 return frozenset(enumclass._names)
464
465 @staticmethod
467 """
468 Return all values of the C{enumclass}.
469
470 @param enumclass: the enumeration class to traverse
471 @type enumclass: type
472
473 @return: a set of all enum values
474 @rtype: frozenset
475 """
476 return frozenset(enumclass._values)
477
478 @staticmethod
479 - def parse(enumclass, value, ignore_case=True):
480 """
481 Parse C{value} as an C{enumclass} member value.
482
483 @param enumclass: target L{enum} subclass
484 @type enumclass: type
485 @type value: str, int, float
486 @param ignore_case: if set to True, triggers case insensitive parsing
487 @type ignore_case: bool
488
489 @return: a member of enumclass, having such value
490 @rtype: L{EnumItem}
491
492 @raise EnumValueError: when such value is not found in enumclass
493 """
494
495 if isinstance(value, string) and ignore_case:
496 values = enumclass._valuesci
497 value = value.lower()
498 else:
499 values = enumclass._values
500
501 if value in values:
502 return enumclass.__dict__[ values[value] ]
503 else:
504 raise EnumValueError('No such value {0} in {1}'.format(value, enumclass))
505
506 @staticmethod
507 - def parsename(enumclass, name, ignore_case=True):
508 """
509 Parse C{name} as a member of C{enumclass}.
510
511 @param enumclass: target L{enum} subclass
512 @type enumclass: type
513 @param name: enumclass member name to parse
514 @type name: str
515 @param ignore_case: if set to True, triggers case insensitive parsing
516 @type ignore_case: bool
517
518 @return: a member of enumclass, having such name
519 @rtype: L{EnumItem}
520
521 @raise EnumValueError: when such name is not found in enumclass's members
522 """
523
524 if isinstance(name, string) and ignore_case:
525 names = enumclass._namesci
526 name = name.lower()
527 else:
528 names = enumclass._names
529
530 if name in names:
531 return enumclass.__dict__[ names[name] ]
532 else:
533 raise EnumMemberError('No such item {0} in {1}'.format(name, enumclass))
534
535 @staticmethod
537 """
538 Return a string representation of the enum item.
539
540 @param item: an enum item to be converted to a string
541 @type item: L{EnumItem}
542
543 @return: the value of the enum member
544 @rtype: str
545 """
546 return item.name
547
548 @staticmethod
550 """
551 Return True if item is a member of enumclass.
552
553 @param enumclass: target enumeration type
554 @type enumclass: type
555 @param item: the enum item to be tested
556 @type item: L{EnumItem}
557 @rtype: bool
558 """
559 if not issubclass(enumclass, enum):
560 raise TypeError(enumclass)
561 return item.enum is enumclass
562
565
568
571
573
574 @abstractmethod
577
578 @abstractmethod
580 """
581 Implementing classes are expected to provide direct access to the
582 requested element in the internal data structure via this method.
583 """
584 pass
585
587 """
588 Base class which defines the behavior of a read only key-value collection
589 container.
590
591 @note: Methods for editing an existing dictionary are also defined in the
592 base class, but left internal on purpose. Subclasses which are
593 supposed to be write-enabled containers must provide their own
594 public methods for editing which might do some custom work and then
595 finally call any of the internal methods in the base class to do the
596 real data editing.
597
598 @param items: an initialization dictionary
599 @param restrict: a list of keys allowed for this dictionary
600 """
601
602 - def __init__(self, items=None, restrict=None):
611
613 try:
614 return self._items[key]
615 except KeyError:
616 raise self._exception(key)
617
619 return self._items[key]
620
622 return item in self._items
623
625 return len(self._items)
626
629
632
633 @property
636
637 @property
640
642 return self._items.keys()
643
645 return iter(self._items)
646
648 return '<{0.__class__.__name__}: {0.length} items>'.format(self)
649
651 new_items = OrderedDict(new_items)
652
653 if self._keys and not self._keys.issuperset(new_items):
654 raise InvalidKeyError("One or more of the keys provided are not allowed for this collection.")
655
656 self._items = new_items
657
659 new_items = OrderedDict(new_items)
660
661 if self._keys:
662 if not set(self).issuperset(new_items) or not set(self).issuperset(named_items):
663 raise ItemNotFoundError("One or more of the keys provided were not found in this collection.")
664
665 self._items.update(new_items)
666 self._items.update(named_items)
667
669
670 if self._keys and key not in self._keys:
671 raise InvalidKeyError("Key {0} is not allowed for this collection.".format(key))
672 if key in self:
673 raise DuplicateKeyError("Key {0} already exists in this collection.".format(key))
674 self._items[key] = item
675
677
678 if key not in self._items:
679 raise self._exception(key)
680 del self._items[key]
681
683 """
684 This is a write-once container, which is filled with items only at object
685 construction.
686 """
687 pass
688
690 """
691 Write-enabled Dictionary Container. New items can be added using a public
692 C{append} method. Subclasses may also override the internal C{_update}
693 and C{_set} to expose them to the clients.
694 """
695 - def __init__(self, items=None, restrict=None):
698
700 """
701 Append a new key-value to the collection.
702
703 @param key: key
704 @param item: value
705
706 @raise InvalidKeyError: when the key is not allowed for this container
707 @raise DuplicateKeyError: when such a key already exists
708 """
709 self._append_item(key, item)
710
711 - def _set(self, new_items):
712 """
713 Set the collection to the dictionary provided in the new_items parameter.
714
715 @param new_items: the new value of the dictionary container
716 @type new_items: dict
717 """
718 self._set_items(new_items)
719
720 - def _update(self, new_items={ }, **named_items):
721 """
722 Update the collection with the dictionary provided in the C{new_items} parameter.
723 Update also specific items with the values provided as keyword arguments.
724
725 @param new_items: a dictionary that provides new values for certain keys
726 @type new_items: dict
727 """
728 self._update_items(new_items, **named_items)
729
731 """
732 Delete C{item}.
733
734 @param item: key to remove
735 """
736 self._remove_item(item)
737
740
742 """
743 Base class which defines the behavior of a read-only collection container.
744
745 @note: Methods for editing an existing collection are also defined in the
746 base class, but left internal on purpose. Subclasses which are
747 supposed to be write-enabled containers must provide their own
748 public methods for editing which might do some custom work and then
749 finally call any of the internal methods in the base class to do the
750 real data editing.
751
752 @param items: initialization list
753 @type items: list
754 @param type: if defined, makes the container type-safe
755 @type type: type
756 @param start_index: the index of the zero element
757 @type start_index: int
758 """
759
760 - def __init__(self, items=None, type=None, start_index=0):
761
762 self._items = [ ]
763 self._type = type
764
765 if not (isinstance(start_index, int) or start_index >= 0):
766 raise ValueError('start_index must be a positive integer.')
767
768 self._start = start_index
769
770 if items is not None:
771 self._update_items(items)
772
774 if i is not None and i >= 0:
775 if i < self._start:
776 return None
777 return i - self._start
778 else:
779 return i
780
782 try:
783 if isinstance(i, slice):
784 sl = slice(self.__fix(i.start), self.__fix(i.stop), i.step)
785 return self._items[sl]
786 else:
787 if 0 <= i < self._start:
788 raise IndexError
789 return self._items[self.__fix(i)]
790
791 except IndexError:
792 if len(self) > 0:
793 raise self._exception('Position {0} is out of range [{1}, {2}]'.format(
794 i, self.start_index, self.last_index))
795 else:
796 raise self._exception('This collection is empty.')
797
799 return self._items[i]
800
802 return item in self._items
803
805 return len(self._items)
806
809
812
813 @property
816
817 @property
820
821 @property
824
825 @property
827 length = len(self._items)
828 if length > 0:
829 return length + self._start - 1
830 else:
831 return None
832
834 return iter(self._items)
835
837 return '<{0.__class__.__name__}: {0.length} items>'.format(self)
838
840
841 if self._type:
842 if not isinstance(item, self._type):
843 raise TypeError("Item {0} is not of the required {1} type.".format(
844 item, self._type.__name__))
845 self._items.append(item)
846
847 return len(self) + self._start - 1
848
850
851 if self._type:
852 for a in new_items:
853 if not isinstance(a, self._type):
854 raise TypeError("Item {0} is not of the required {1} type.".format(
855 a, self._type.__name__))
856 self._items = list(new_items)
857
860
862 """
863 This is a write-once container, which is filled with items only at object
864 construction.
865 """
866 pass
867
869 """
870 Write-enabled Collection Container. New items can be added using a public
871 C{append} method. Subclasses may also override the internal C{_update}
872 to expose it to the clients.
873 """
874
875 - def __init__(self, items=None, type=None, start_index=0):
878
880 """
881 Append a new item to the collection.
882
883 @param item: the new item to append
884
885 @return: the index of the new element
886 @rtype: int
887
888 @raise TypeError: when the container is type-safe and item has an
889 incorrect type
890 """
891 return self._append_item(item)
892
894 """
895 Set the collection to the list provided in the new_items parameter.
896
897 @param new_items: a list providing the new items for the container
898 @type new_items: list
899 """
900 self._update_items(new_items)
901
903 """
904 Defines the behavior of a high-level object, which can hold an array of
905 elements. Implementing classes automatically provide iterable and index/key
906 based access to those objects in a read-only encapsulated manner.
907
908 This is an abstract class with an abstract property C{_children}. Subclasses
909 must override this property. The overridden implementation is usually
910 extremely simple - you just need to return a reference to an iterable and
911 subscriptable object, containing the elements.
912 """
913
914 __metaclass__ = ABCMeta
915
917 return self._children[i]
918
920 return len(self._children)
921
924
925 __bool__ = __nonzero__
926
928 for i in self._children:
929 yield i
930
931 @abstractproperty
934
936 """
937 Generic implementation of L{AbstractContainer}. Provides an easy way to
938 encapsulate class properties that behave like read-only collections or
939 dictionaries. This container is super lightweight and completely dynamic:
940 it serves as a proxy to an internal list or dict and stores no data in its
941 own instance. Owning classes are therefore free to modify those internal
942 data structures, which provides advantages over using
943 L{ReadOnlyCollectionContainer}s.
944 """
945
948
949 @property
952
954 """
955 Same as the L{AbstractContainer}, but provides access to the child elements
956 through C{AbstractNativeIndexer._getinternal} instead of the standard
957 __getitem__.
958
959 Therefore, the C{self._children} property must return an object which
960 implements L{AbstractIndexer}.
961 """
963 return self._children._getinternal(i)
964
965 try:
966 from collections import OrderedDict as _dict
969 except ImportError:
970 import UserDict
973
975 if len(args) > 1:
976 raise TypeError('expected at most 1 arguments, got {0}'.format(len(args)))
977 try:
978 self.__end
979 except AttributeError:
980 self.clear()
981 self.update(*args, **kwds)
982
984 self.__end = end = []
985 end += [None, end, end]
986 self.__map = {}
987 dict.clear(self)
988
990 if key not in self:
991 end = self.__end
992 curr = end[1]
993 curr[2] = end[1] = self.__map[key] = [key, curr, end]
994 dict.__setitem__(self, key, value)
995
997 dict.__delitem__(self, key)
998 key, prev, next = self.__map.pop(key)
999 prev[2] = next
1000 next[1] = prev
1001
1003 end = self.__end
1004 curr = end[2]
1005 while curr is not end:
1006 yield curr[0]
1007 curr = curr[2]
1008
1010 end = self.__end
1011 curr = end[1]
1012 while curr is not end:
1013 yield curr[0]
1014 curr = curr[1]
1015
1017 if not self:
1018 raise KeyError('dictionary is empty')
1019 if last:
1020 key = next(reversed(self))
1021 else:
1022 key = next(iter(self))
1023 value = self.pop(key)
1024 return key, value
1025
1027 items = [[k, self[k]] for k in self]
1028 tmp = self.__map, self.__end
1029 del self.__map, self.__end
1030 inst_dict = vars(self).copy()
1031 self.__map, self.__end = tmp
1032 if inst_dict:
1033 return (self.__class__, (items,), inst_dict)
1034 return self.__class__, (items,)
1035
1038
1039 setdefault = UserDict.DictMixin.setdefault
1040 update = UserDict.DictMixin.update
1041 pop = UserDict.DictMixin.pop
1042 values = UserDict.DictMixin.values
1043 items = UserDict.DictMixin.items
1044 iterkeys = UserDict.DictMixin.iterkeys
1045 itervalues = UserDict.DictMixin.itervalues
1046 iteritems = UserDict.DictMixin.iteritems
1047
1049 if not self:
1050 return '{0}()'.format(self.__class__.__name__)
1051 return '{0}({1!r})'.format(self.__class__.__name__, self.items())
1052
1054 return self.__class__(self)
1055
1056 @classmethod
1057 - def fromkeys(cls, iterable, value=None):
1058 d = cls()
1059 for key in iterable:
1060 d[key] = value
1061 return d
1062
1064 if isinstance(other, OrderedDict):
1065 return len(self)==len(other) and self.items() == other.items()
1066 return dict.__eq__(self, other)
1067
1069 return not self == other
1070