Debian Codegraph @

csb/core/__init__.py

raw
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
43
44
45 class InterruptibleThread(threading.Thread):
46
47 def __init__(self, target, name=None, args=[], kwargs={}):
48
49 super(InterruptibleThread, self).__init__(target=target, name=name, args=args, kwargs=kwargs)
50 self.setDaemon(True)
51 self.__result = None
52 self.__target = target
53 self.__name = name
54 self.__args = args
55 self.__kwargs = kwargs
56
57 @property
58 def result(self):
59 return self.__result
60
61 def run(self):
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
68 def singleton(klass):
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
81 class validatedproperty(property):
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 """
100 def __init__(self, validator):
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
107 def __get__(self, instance, cls):
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
117 class typedproperty(property):
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 """
129 def __init__(self, type):
130 self.type = type
131
132 def __call__(self, func):
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
140 def __get__(self, instance, cls):
141 if instance is None:
142 return self
143 return getattr(instance, self.name)
144
145 def __set__(self, instance, value):
146 if not isinstance(value, self.type):
147 raise TypeError('expected {0}, got {1}'.format(self.type, type(value)))
148 setattr(instance, self.name, value)
149
150 class Proxy(object):
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
159 def __init__(self, subject):
160 self._subject = subject
161
162 def __getattr__(self, name):
163 try:
164 return object.__getattribute__(self, name)
165 except AttributeError:
166 subject = object.__getattribute__(self, '_subject')
167 return getattr(subject, name)
168
169 class REMatchProxy(object):
170
171 def __init__(self, match):
172
173 self._start = [match.start()]
174 self._end = [match.end()]
175 self._groups = match.groups()
176
177 for i, dummy in enumerate(self._groups, start=1):
178 self._start.append(match.start(i))
179 self._end.append(match.end(i))
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
197 def groups(self):
198 return self._groups
199
200 class Stack(list):
201
202 def push(self, item):
203 """
204 Push an item onto the top of the stack
205 """
206 self.append(item)
207
208 def peek(self):
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
216 def empty(self):
217 """
218 Return True if the stack is empty
219 """
220 return len(self) == 0
221
222 def iterable(obj):
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
235 def metaclass(meta, base=object):
236 """
237 Return a new class with parent class C{base} and metaclass C{meta}.
238 This works in both python 2 and 3.
239 """
240 return meta("NewBase", (base,), {})
241
242 def deepcopy(obj, recursion=100000):
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
263 def _deserialize_enum(enum, name):
264 return getattr(enum, name)
265
266 class EnumValueError(ValueError):
267 pass
268
269 class EnumMemberError(AttributeError):
270 pass
271
272 class EnumItem(object):
273
274 def __init__(self, name, value, enum):
275 self.__name = name
276 self.__value = value
277 self.__container = enum
278
279 def __reduce__(self):
280 return (_deserialize_enum, (self.enum, self.name))
281 def __deepcopy__(self, memo):
282 return self
283 def __copy__(self):
284 return self
285 def __repr__(self):
286 return '{0}'.format(self.__name, self.__value)
287 def __str__(self):
288 return str(self.__value)
289 def __int__(self):
290 return int(self.__value)
291 def __float__(self):
292 return float(self.__value)
293 def __hash__(self):
294 return hash(self.__value)
295 def __lt__(self, other):
296 if isinstance(other, EnumItem):
297 return self.__value < other.value
298 else:
299 return self.__value < other
300 def __eq__(self, other):
301 if isinstance(other, EnumItem):
302 return self.__value == other.value
303 else:
304 return self.__value == other
305 def __ne__(self, other):
306 return not (self == other)
307
308 @property
309 def name(self):
310 return self.__name
311
312 @property
313 def value(self):
314 return self.__value
315
316 @property
317 def enum(self):
318 return self.__container
319
320 def _attach(self, enum):
321 assert getattr(enum, self.__name) is self
322 self.__container = enum
323
324 class EnumMeta(type):
325 """
326 Metaclass for enum types.
327 """
328
329 def __new__(cls, name, bases, items):
330
331 enumdict = {}
332
333 enumdict['_name'] = name
334 enumdict['_names'] = {}
335 enumdict['_namesci'] = {}
336 enumdict['_values'] = {}
337 enumdict['_valuesci'] = {}
338
339 for attribute in items:
340 value = items[attribute]
341
342 if attribute.startswith('_'):
343 enumdict[attribute] = value
344 else:
345 if value in enumdict['_values']:
346 raise EnumValueError('Duplicate value {0} in enum {1}.'.format(value, name))
347
348 enumdict['_names'][attribute] = attribute
349 enumdict['_namesci'][attribute.lower()] = attribute
350 enumdict['_values'][value] = attribute
351 if isinstance(value, string):
352 enumdict['_valuesci'][value.lower()] = attribute
353
354 enumdict[attribute] = EnumItem(attribute, value, None)
355
356 enum = super(EnumMeta, cls).__new__(cls, name, bases, enumdict)
357
358 for attribute in items:
359 if not attribute.startswith('_'):
360 value = items[attribute]
361 enum.__dict__[attribute]._attach(enum)
362
363 return enum
364
365 def __setattr__(self, attribute, value):
366 raise AttributeError("enum types are immutable")
367
368 def __repr__(self):
369 items = list(self._names)[:2]
370 preview = [ '{0}={1}'.format(i, getattr(self, i)) for i in items ]
371 if len(preview) < len(self._names):
372 preview.append('...')
373 return '<{0}: {1}>'.format(self._name, ', '.join(preview))
374
375 def __str__(self):
376 return repr(self)
377
378 def __iter__(self):
379 return iter(self.__dict__[i] for i in self._names)
380
381 def __contains__(self, item):
382 return item.enum is self
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 """
411 def __init__(self):
412 raise TypeError("Can't instantiate static enum type {0}".format(self.__class__))
413
414 class Enum(object):
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
440 def members(enumclass):
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
453 def names(enumclass):
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
466 def values(enumclass):
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
536 def tostring(item):
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
549 def ismember(item, enumclass):
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
563 class ItemNotFoundError(KeyError):
564 pass
565
566 class InvalidKeyError(KeyError):
567 pass
568
569 class DuplicateKeyError(InvalidKeyError):
570 pass
571
572 class AbstractIndexer(object):
573
574 @abstractmethod
575 def __getitem__(self, i):
576 pass
577
578 @abstractmethod
579 def _getinternal(self, i):
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
586 class BaseDictionaryContainer(AbstractIndexer):
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):
603
604 self._keys = None
605 self._items = OrderedDict({})
606
607 if restrict:
608 self._keys = frozenset(restrict)
609 if items is not None:
610 self._set_items(items)
611
612 def __getitem__(self, key):
613 try:
614 return self._items[key]
615 except KeyError:
616 raise self._exception(key)
617
618 def _getinternal(self, key):
619 return self._items[key]
620
621 def __contains__(self, item):
622 return item in self._items
623
624 def __len__(self):
625 return len(self._items)
626
627 def __nonzero__(self):
628 return self.__bool__()
629
630 def __bool__(self):
631 return len(self) > 0
632
633 @property
634 def _exception(self):
635 return ItemNotFoundError
636
637 @property
638 def length(self):
639 return len(self)
640
641 def keys(self):
642 return self._items.keys()
643
644 def __iter__(self):
645 return iter(self._items)
646
647 def __repr__(self):
648 return '<{0.__class__.__name__}: {0.length} items>'.format(self)
649
650 def _set_items(self, new_items):
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
658 def _update_items(self, new_items={ }, **named_items):
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
668 def _append_item(self, key, item):
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
676 def _remove_item(self, key):
677
678 if key not in self._items:
679 raise self._exception(key)
680 del self._items[key]
681
682 class ReadOnlyDictionaryContainer(BaseDictionaryContainer):
683 """
684 This is a write-once container, which is filled with items only at object
685 construction.
686 """
687 pass
688
689 class DictionaryContainer(BaseDictionaryContainer):
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):
696
697 super(DictionaryContainer, self).__init__(items, restrict)
698
699 def append(self, key, item):
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
730 def _remove(self, item):
731 """
732 Delete C{item}.
733
734 @param item: key to remove
735 """
736 self._remove_item(item)
737
738 class CollectionIndexError(IndexError):
739 pass
740
741 class BaseCollectionContainer(AbstractIndexer):
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
773 def __fix(self, i):
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
781 def __getitem__(self, i):
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
798 def _getinternal(self, i):
799 return self._items[i]
800
801 def __contains__(self, item):
802 return item in self._items
803
804 def __len__(self):
805 return len(self._items)
806
807 def __nonzero__(self):
808 return self.__bool__()
809
810 def __bool__(self):
811 return len(self) > 0
812
813 @property
814 def _exception(self):
815 return CollectionIndexError
816
817 @property
818 def length(self):
819 return len(self)
820
821 @property
822 def start_index(self):
823 return self._start
824
825 @property
826 def last_index(self):
827 length = len(self._items)
828 if length > 0:
829 return length + self._start - 1
830 else:
831 return None
832
833 def __iter__(self):
834 return iter(self._items)
835
836 def __repr__(self):
837 return '<{0.__class__.__name__}: {0.length} items>'.format(self)
838
839 def _append_item(self, item):
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
849 def _update_items(self, new_items):
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
858 def _sort(self):
859 self._items.sort()
860
861 class ReadOnlyCollectionContainer(BaseCollectionContainer):
862 """
863 This is a write-once container, which is filled with items only at object
864 construction.
865 """
866 pass
867
868 class CollectionContainer(BaseCollectionContainer):
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):
876
877 super(CollectionContainer, self).__init__(items, type, start_index)
878
879 def append(self, item):
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
893 def _update(self, new_items):
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
902 class AbstractContainer(object):
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
916 def __getitem__(self, i):
917 return self._children[i]
918
919 def __len__(self):
920 return len(self._children)
921
922 def __nonzero__(self):
923 return True
924
925 __bool__ = __nonzero__
926
927 def __iter__(self):
928 for i in self._children:
929 yield i
930
931 @abstractproperty
932 def _children(self):
933 pass
934
935 class Container(AbstractContainer):
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
946 def __init__(self, data):
947 self._data = data
948
949 @property
950 def _children(self):
951 return self._data
952
953 class AbstractNIContainer(AbstractContainer):
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 """
962 def __getitem__(self, i):
963 return self._children._getinternal(i)
964
965 try:
966 from collections import OrderedDict as _dict
967 class OrderedDict(_dict):
968 pass
969 except ImportError:
970 import UserDict
971
972 class OrderedDict(dict, UserDict.DictMixin):
973
974 def __init__(self, *args, **kwds):
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
983 def clear(self):
984 self.__end = end = []
985 end += [None, end, end] # sentinel node for doubly linked list
986 self.__map = {} # key --> [key, prev, next]
987 dict.clear(self)
988
989 def __setitem__(self, key, value):
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
996 def __delitem__(self, key):
997 dict.__delitem__(self, key)
998 key, prev, next = self.__map.pop(key)
999 prev[2] = next
1000 next[1] = prev
1001
1002 def __iter__(self):
1003 end = self.__end
1004 curr = end[2]
1005 while curr is not end:
1006 yield curr[0]
1007 curr = curr[2]
1008
1009 def __reversed__(self):
1010 end = self.__end
1011 curr = end[1]
1012 while curr is not end:
1013 yield curr[0]
1014 curr = curr[1]
1015
1016 def popitem(self, last=True):
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
1026 def __reduce__(self):
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
1036 def keys(self):
1037 return list(self)
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
1048 def __repr__(self):
1049 if not self:
1050 return '{0}()'.format(self.__class__.__name__)
1051 return '{0}({1!r})'.format(self.__class__.__name__, self.items())
1052
1053 def copy(self):
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
1063 def __eq__(self, other):
1064 if isinstance(other, OrderedDict):
1065 return len(self)==len(other) and self.items() == other.items()
1066 return dict.__eq__(self, other)
1067
1068 def __ne__(self, other):
1069 return not self == other
1070