Package csb :: Package core

[frames] | no frames]

# Source Code for Package csb.core

       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