#! /usr/bin/env python # -*- coding: utf-8 -*- ############################################################################## ## DendroPy Phylogenetic Computing Library. ## ## Copyright 2010-2015 Jeet Sukumaran and Mark T. Holder. ## All rights reserved. ## ## See "LICENSE.rst" for terms and conditions of usage. ## ## If you use this work or any portion thereof in published work, ## please cite it as: ## ## Sukumaran, J. and M. T. Holder. 2010. DendroPy: a Python library ## for phylogenetic computing. Bioinformatics 26: 1569-1571. ## ############################################################################## """ Various data structures. """ import collections import copy import sys import csv try: from collections.abc import MutableMapping except ImportError: # Python 2 from collections import MutableMapping ############################################################################### ## OrderedSet class OrderedSet(object): """ Ordered collection of unique objects with O(1) look-ups, addition, and deletion. """ def __init__(self, *args): self._item_list = [] self._item_set = set() if len(args) > 1: raise TypeError("OrderedSet expected at most 1 arguments, got 2") elif len(args) == 1: for a in args[0]: if a not in self._item_set: self._item_set.add(a) self._item_list.append(a) def __copy__(self, memo=None): o = OrderedSet(self._item_list) return o def __deepcopy__(self, memo=None): other = self.__class__() memo[id(self)] = other memo[id(self._item_set)] = other._item_set memo[id(self._item_list)] = other._item_list for item in self._item_list: c = copy.deepcopy(item, memo) memo[id(item)] = c other._item_set.add(c) other._item_list.append(c) for k in self.__dict__: if k in other.__dict__: continue other.__dict__[k] = copy.deepcopy(self.__dict__[k], memo) memo[id(self.__dict__[k])] = other.__dict__[k] return other def __len__(self): return len(self._item_list) def __getitem__(self, index): """ Returns value at ``index``. Note takes *index* of than value as key. """ return self._item_list[index] def __setitem__(self, index, value): """ Sets value at ``index``. Note takes *index* of than value as key. """ item = self._item_list[index] self._item_set.remove(item) self._item_set.add(value) self._item_list[index] = value def __delitem__(self, index): """ Deletes value at ``index``. Note takes *index* of than value as key. """ self._item_set.remove(self._item_list[index]) del self._item_list[index] def discard(self, key): """ Deletes value of ``key`` from ``self``. No error if no value of ``key`` is not in ``self``. """ if key in self._item_set: self._item_set.remove(key) self._item_list.remove(key) def remove(self, key): """ Deletes value of ``key`` from ``self``. KeyErrorif no value of ``key`` is not in ``self``. """ self._item_set.remove(key) self._item_list.remove(key) def __iter__(self): """ Returns iterator over values in ``self``. """ return iter(self._item_list) def next(self): """ Returns iterator over values in ``self``. """ return self.__iter__() def __reversed__(self): """ Returns ``OrderedSet`` with values in reversed order. """ return OrderedSet(reversed(self._item_list)) def __add__(self, other): """ Returns ``OrderedSet`` consisting of union of values in ``self`` and ``other``. """ v = self._item_list + other._item_list return OrderedSet(v) def index(self, value): """ Returns index of element with value of ``value``. """ return self._item_list.index(value) def __contains__(self, value): """ Returns |True| if ``value`` is in ``self`` or |False| otherwise. """ return value in self._item_set def add(self, value): """ Adds a new element, ``value``, to ``self`` if ``value`` is not already in ``self``. """ if value not in self._item_set: self._item_set.add(value) self._item_list.append(value) return value else: return None def update(self, other): """ Updates ``self`` with values in ``other`` for each value in ``other`` that is not already in ``self``. """ for i in other: if i not in self._item_set: self._item_set.add(i) self._item_list.append(i) def __str__(self): return "[{}]".format(", ".join([str(i) for i in self._item_list])) def __repr__(self): return "{}([{}])".format(self.__class__.__name__, ", ".join([str(i) for i in self._item_list])) def __hash__(self): return id(self) # return hash( (t for t in self._item_list) ) def __eq__(self, o): return self._item_list == o._item_list def __lt__(self, o): return self._item_list < o._item_list def pop(self, last=True): """ Removes and return value in ``self``. By default, removes last value. """ if not self._item_set: raise KeyError('OrderedSet is empty') if last: key = self._item_list[-1] else: key = self._item_list[0] self.discard(key) return key def clear(self): self._item_set = set() self._item_list = [] ############################################################################### ## NormalizedBitmaskDict class NormalizedBitmaskDict(collections.OrderedDict): """ Keys, {K_i}, are longs. ``fill_bitmask`` must be provided before elements can be added removed from dictionary. All keys are normalized such that the least- significant bit is '0'. That is, if the key's least-significant bit is '0', it is added as-is, otherwise it is complemented by XOR'ing it with 'fill_bitmask'. """ def least_significant_set_bit(s): """ Returns least-significant bit in integer 's' that is set. """ m = s & (s - 1) return m ^ s least_significant_set_bit = staticmethod(least_significant_set_bit) # this is for the least-significant-bit-is-1 normalization convention # def normalize(key, fill_bitmask, lowest_relevant_bit): # if key & lowest_relevant_bit: # return key & fill_bitmask # keep least-significant bit to 1 # else: # return (~key) & fill_bitmask # force least-significant bit as 1 # normalize = staticmethod(normalize) # this is for the least-significant-bit-is-0 normalization convention def normalize(key, fill_bitmask, lowest_relevant_bit): if key & lowest_relevant_bit: return (~key) & fill_bitmask # force least-significant bit to 0 else: return key & fill_bitmask # keep least-significant bit as 0 normalize = staticmethod(normalize) def __init__(self, other=None, fill_bitmask=None): """ Parameters ---------- fill_bitmask : integer A bitmask where all possible bits that can be set to 1 are set to 1. When representing a taxon namespaces, with 8 taxa, for example, this would be 0b11111111. Incomplete leaf-sets on trees need to having the missing taxa bits set to 0. For example, for a tree missing taxa 2, 3, and 5, ``fill_bitmask`` would be 0b11101001. """ collections.OrderedDict.__init__(self) self.lowest_relevant_bit = NormalizedBitmaskDict.least_significant_set_bit(fill_bitmask) self.fill_bitmask = fill_bitmask if other is not None: if isinstance(other, NormalizedBitmaskDict): self.fill_bitmask = other.fill_bitmask self.lowest_relevant_bit = other.lowest_relevant_bit if isinstance(other, dict): for key, val in other.items(): self[key] = val def __deepcopy__(self, memo): o = NormalizedBitmaskDict(fill_bitmask=self.fill_bitmask) memo[id(self)] = o o.fill_bitmask = self.fill_bitmask o.lowest_relevant_bit = self.lowest_relevant_bit for key, val in self.items(): o[key] = copy.deepcopy(val, memo) return o def normalize_key_and_assign_value(self, key, value): "*Almost* like __setitem__(), but returns value of normalized key to calling code." normalized_key = self.normalize_key(key) dict.__setitem__(self, normalized_key, value) return normalized_key def normalize_key(self, key): return NormalizedBitmaskDict.normalize(key, self.fill_bitmask, self.lowest_relevant_bit) def __setitem__(self, key, value): "Sets item with normalized key." self.normalize_key_and_assign_value(key, value) def __getitem__(self, key): "Gets an item by its key." key = self.normalize_key(key) return dict.__getitem__(self, key) def __delitem__(self, key): "Remove item with normalized key." key = self.normalize_key(key) dict.__delitem__(self, key) def __contains__(self, key): "Returns true if has normalized key." key = self.normalize_key(key) return dict.__contains__(self, key) def pop(self, key, alt_val=None): "a.pop(k[, x]): a[k] if k in a, else x (and remove k)" key = self.normalize_key(key) return dict.pop(self, key) def get(self, key, def_val=None): "Gets an item by its key, returning default if key not present." key = self.normalize_key(key) return dict.get(self, key, def_val) def setdefault(self, key, def_val=None): "Sets the default value to return if key not present." dict.setdefault(self, self.normalize_key(key), def_val) def update(self, other): """ updates (and overwrites) key/value pairs: k = { 'a':'A', 'b':'B', 'c':'C'} q = { 'c':'C', 'd':'D', 'f':'F'} k.update(q) {'a': 'A', 'c': 'C', 'b': 'B', 'd': 'D', 'f': 'F'} """ for key, val in other.items(): dict.__setitem__(self, self.normalize_key(key), val) def fromkeys(self, iterable, value=None): "Creates a new dictionary with keys from seq and values set to value." raise NotImplementedError ############################################################################### # CaseInsensitiveDict # # From: # https://github.com/kennethreitz/requests # # Copyright 2014 Kenneth Reitz # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. class CaseInsensitiveDict(MutableMapping): """ A case-insensitive ``dict``-like object. Implements all methods and operations of ``collections.MutableMapping`` as well as dict's ``copy``. Also provides ``lower_items``. All keys are expected to be strings. The structure remembers the case of the last key to be set, and ``iter(instance)``, ``keys()``, ``items()``, ``iterkeys()``, and ``iteritems()`` will contain case-sensitive keys. However, querying and contains testing is case insensitive: cid = CaseInsensitiveDict() cid['Accept'] = 'application/json' cid['aCCEPT'] == 'application/json' # True list(cid) == ['Accept'] # True For example, ``headers['content-encoding']`` will return the value of a ``'Content-Encoding'`` response header, regardless of how the header name was originally stored. If the constructor, ``.update``, or equality comparison operations are given keys that have equal ``.lower()``s, the behavior is undefined. """ def __init__(self, data=None, **kwargs): self._store = dict() if data is None: data = {} self.update(data, **kwargs) def __setitem__(self, key, value): # Use the lowercased key for lookups, but store the actual # key alongside the value. self._store[key.lower()] = (key, value) def __getitem__(self, key): return self._store[key.lower()][1] def __delitem__(self, key): del self._store[key.lower()] def __iter__(self): return (casedkey for casedkey, mappedvalue in self._store.values()) def __len__(self): return len(self._store) def lower_items(self): """Like iteritems(), but with all lowercase keys.""" return ( (lowerkey, keyval[1]) for (lowerkey, keyval) in self._store.items() ) def __eq__(self, other): if isinstance(other, collections.Mapping): other = CaseInsensitiveDict(other) else: return NotImplementedError # Compare insensitively return dict(self.lower_items()) == dict(other.lower_items()) # Copy is required def copy(self): return CaseInsensitiveDict(self._store.values()) def __repr__(self): return '%s(%r)' % (self.__class__.__name__, dict(self.items())) # CaseInsensitiveDict ############################################################################### ############################################################################### ## OrderedCaselessDict class OrderedCaselessDict(dict): """ Inherits from dict. Maintains two sets of keys: the first the keys belonging to dict, which actually accesses the container items. This is always cast to lower() whenever it is called, thus ensuring that keys are always of the same case. The second set of keys it maintains locally in an list, thus maintaining the order in which they were added. The second set of keys is not cast to lower(), which means that client code can always recover the original 'canonical' casing of the keys. ONLY TAKES STRING KEYS! """ def __init__(self, other=None): """ __init__ creates the local set of keys, and then initializes self with arguments, if any, by using the superclass methods, keeping the ordered keys in sync. """ super(OrderedCaselessDict, self).__init__() self._ordered_keys = [] if other is not None: if isinstance(other, dict): for key, val in other.items(): if key.lower() not in self: self._ordered_keys.append(str(key)) super(OrderedCaselessDict, \ self).__setitem__(key.lower(), val) else: for key, val in other: if key.lower() not in self: self._ordered_keys.append(str(key)) super(OrderedCaselessDict, \ self).__setitem__(key.lower(), val) def __deepcopy__(self, memo): o = self.__class__() memo[id(self)] = o for key, val in self.items(): o[key] = copy.deepcopy(val, memo) return o def copy(self): "Returns a shallow copy of self." return self.__class__(self) def iterkeys(self): "Returns an iterator over self's ordered keys." return iter(self._ordered_keys) def itervalues(self): "Returns an iterator over self's key, value pairs." for key in self.iterkeys(): yield self[key.lower()] def iteritems(self): "Returns an iterator over self's values." for key in self.iterkeys(): yield (key, self[key.lower()]) def items(self): "Returns key, value pairs in key-order." return [(key, self[key]) for key in self.iterkeys()] def values(self): "Returns list of key, value pairs." return [v for v in self.itervalues()] def __iter__(self): "Returns an iterator over self's ordered keys." return self.iterkeys() def __getitem__(self, key): "Gets an item using a case-insensitive key." return super(OrderedCaselessDict, self).__getitem__(key.lower()) def __setitem__(self, key, value): "Sets an item using a case-insensitive key," if key.lower() not in self: self._ordered_keys.append(str(key)) super(OrderedCaselessDict, self).__setitem__(key.lower(), value) def __delitem__(self, key): "Remove item with specified key." del(self._ordered_keys[self.index(key)]) super(OrderedCaselessDict, \ self).__delitem__(key.lower()) def __contains__(self, key): "Returns true if has key, regardless of case." return super(OrderedCaselessDict, self).__contains__(key.lower()) def pop(self, key, alt_val=None): "a.pop(k[, x]): a[k] if k in a, else x (and remove k)" if key.lower() in self: val = self[key] self.__delitem__(key.lower()) return val else: return alt_val def popitem(self): "a.popitem() remove and last (key, value) pair" key = self._ordered_keys[-1] item = (key, self[key.lower()]) self.__delitem__(key) return item def caseless_keys(self): "Returns a copy of the ordered list of keys." return [k.lower() for k in self._ordered_keys] def index(self, key): """ Return the index of (caseless) key. Raise KeyError if not found. """ count = 0 for k in self._ordered_keys: if k.lower() == key.lower(): return count count = count + 1 raise KeyError(key) def keys(self): "Returns a copy of the ordered list of keys." return list(self._ordered_keys) def clear(self): "Deletes all items from the dictionary." self._ordered_keys = [] super(OrderedCaselessDict, self).clear() def has_key(self, key): "Returns true if has key, regardless of case." return key.lower() in self def get(self, key, def_val=None): "Gets an item by its key, returning default if key not present." return super(OrderedCaselessDict, self).get(key.lower(), def_val) def setdefault(self, key, def_val=None): "Sets the default value to return if key not present." return super(OrderedCaselessDict, self).setdefault(key.lower(), def_val) def update(self, other): """ updates (and overwrites) key/value pairs: k = { 'a':'A', 'b':'B', 'c':'C'} q = { 'c':'C', 'd':'D', 'f':'F'} k.update(q) {'a': 'A', 'c': 'C', 'b': 'B', 'd': 'D', 'f': 'F'} """ for key, val in other.items(): if key.lower() not in self: self._ordered_keys.append(str(key)) super(OrderedCaselessDict, self).__setitem__(key.lower(), val) def fromkeys(self, iterable, value=None): "Creates a new dictionary with keys from seq and values set to value." ocd = OrderedCaselessDict() for key in iterable: if key.lower() not in self: self[key] = value return ocd ############################################################################### ## FrozenOrderedDict class FrozenOrderedDict(collections.OrderedDict): class ImmutableTypeError(TypeError): def __init__(self, *args, **kwargs): super(FrozenOrderedDict.ImmutableTypeError, self).__init__(*args, **kwargs) def __init__(self, *args, **kwargs): self._is_frozen = False super(FrozenOrderedDict, self).__init__(*args, **kwargs) self._is_frozen = True def __setitem__(self, key, value): if self._is_frozen: raise FrozenOrderedDict.ImmutableTypeError("{} is immutable".format(self.__class__.__name__)) else: super(FrozenOrderedDict, self).__setitem__(key, value) def __delitem__(self, key): if self._is_frozen: raise FrozenOrderedDict.ImmutableTypeError("{} is immutable".format(self.__class__.__name__)) else: super(FrozenOrderedDict, self).__delitem__(key) def pop(self, key, alt_val=None): if self._is_frozen: raise FrozenOrderedDict.ImmutableTypeError("{} is immutable".format(self.__class__.__name__)) else: super(FrozenOrderedDict, self).pop(key, alt_val) def popitem(self): if self._is_frozen: raise FrozenOrderedDict.ImmutableTypeError("{} is immutable".format(self.__class__.__name__)) else: super(FrozenOrderedDict, self).popitem() def clear(self): if self._is_frozen: raise FrozenOrderedDict.ImmutableTypeError("{} is immutable".format(self.__class__.__name__)) else: super(FrozenOrderedDict, self).clear() def update(self, other): if self._is_frozen: raise FrozenOrderedDict.ImmutableTypeError("{} is immutable".format(self.__class__.__name__)) else: super(FrozenOrderedDict, self).update(other) def fromkeys(self, iterable, value=None): if self._is_frozen: raise FrozenOrderedDict.ImmutableTypeError("{} is immutable".format(self.__class__.__name__)) else: super(FrozenOrderedDict, self).fromkeys(iterable, value) def __deepcopy__(self, memo): temp = FrozenOrderedDict() temp._is_frozen = False for k in self: k2 = copy.deepcopy(k, memo) memo[id(k)] = k2 v = self[k] v2 = copy.deepcopy(v, memo) memo[id(v)] = v2 temp[k2] = v2 temp._is_frozen = True return temp def __copy__(self): temp = FrozenOrderedDict() temp._is_frozen = False for k in self: temp[k] = self[k] temp._is_frozen = True return temp ############################################################################## ## DataTable class DataTable(object): @classmethod def from_csv(cls, src, is_first_row_column_names=True, is_first_column_row_names=True, is_trim_space=True, default_data_type=None, column_data_types=None, label_transform_fn=None, **csv_reader_kwargs ): """ Returns table from a full-configured csv.Reader instance. Parameters ----------- csv_reader : a csv.Reader instance The source of the data. is_first_row_column_names : bool If True, then the first row is interpreted as column names; otherwise, treated as data row. is_first_column_row_names : bool If True, then the first column is interpreted as row names; otherwise, treated as data column. is_trim_space : bool If True, then will strip space from both sides of all tokens before processing. Note that only spaces will be trimmed, not tabs. default_data_type : type or function object Any callable that, when passed a value, returns the coerced-to-type equivalent for the data. column_data_types : dict A dictionary where the key are the column names and the corresponding value the type (see ``default_data_type`` for description). Returns ------- t: a DataTable instance Returns table from a full-configured csv.Reader instance. """ if isinstance(src, str): with open(src, "r") as fsrc: return cls._from_csv_file( src=fsrc, is_first_row_column_names=is_first_row_column_names, is_first_column_row_names=is_first_column_row_names, is_trim_space=is_trim_space, default_data_type=default_data_type, column_data_types=column_data_types, label_transform_fn=label_transform_fn, **csv_reader_kwargs) else: return cls._from_csv_file( src=src, is_first_row_column_names=is_first_row_column_names, is_first_column_row_names=is_first_column_row_names, is_trim_space=is_trim_space, default_data_type=default_data_type, column_data_types=column_data_types, label_transform_fn=label_transform_fn, **csv_reader_kwargs) @classmethod def _from_csv_file(cls, src, is_first_row_column_names=True, is_first_column_row_names=True, is_trim_space=True, default_data_type=None, column_data_types=None, label_transform_fn=None, **csv_reader_kwargs ): ncols = None data_table = cls() if is_first_row_column_names: first_data_row_offset = 1 else: first_data_row_offset = 0 if is_first_column_row_names: first_data_column_offset = 1 else: first_data_column_offset = 0 if column_data_types is None: column_data_types = {} if label_transform_fn is None: label_transform_fn = lambda x: x csv_reader = csv.reader(src, **csv_reader_kwargs) for row_idx, row in enumerate(csv_reader): if ncols is None: ncols = len(row) else: if len(row) == 1 and row[0].strip() == "" and is_trim_space: # blank row continue assert ncols == len(row), "{} != {}".format(ncols, len(row)) for cell_idx, cell in enumerate(row): if is_trim_space: cell = cell.strip(" ") if row_idx == 0 and is_first_row_column_names: if cell_idx == 0 and is_first_column_row_names: continue data_table.add_column( column_name=label_transform_fn(cell), data_type=column_data_types.get(cell, default_data_type)) elif cell_idx == 0 and is_first_column_row_names: data_table.add_row(label_transform_fn(cell)) else: if row_idx == 0 and not is_first_row_column_names: data_table.add_column(data_type=column_data_types.get(cell, default_data_type)) if cell_idx == 0 and not is_first_column_row_names: data_table.add_row() effective_row_idx = row_idx - first_data_row_offset assert effective_row_idx < len(data_table._row_names), "{}: {}".format(effective_row_idx, data_table._row_names) effective_column_idx = cell_idx - first_data_column_offset assert effective_column_idx < len(data_table._column_names), "{}: {}".format(effective_column_idx, data_table._column_names) data_table[effective_row_idx, effective_column_idx] = cell return data_table def __init__(self): self._row_names = [] self._row_name_set = set() self._column_names = [] self._column_data_types = {} self._column_name_set = set() self._data = {} def add_column(self, column_name=None, pos=None, data_type=None): column_name = self._validate_new_column_name(column_name) assert column_name not in self._column_name_set if pos is None: pos = len(self._column_names) self._column_names.insert(pos, column_name) self._column_name_set.add(column_name) self._column_data_types[column_name] = data_type def add_row(self, row_name=None, pos=None): row_name = self._validate_new_row_name(row_name) assert row_name not in self._row_name_set if pos is None: pos = len(self._row_names) self._row_names.insert(pos, row_name) self._row_name_set.add(row_name) def __getitem__(self, key): row_name = self._dereference_key( key=key[0], name_list=self._row_names, name_set=self._row_name_set) column_name = self._dereference_key( key=key[1], name_list=self._column_names, name_set=self._column_name_set) if row_name not in self._data: return None if column_name not in self._data[row_name]: return None return self._data[row_name][column_name] def __setitem__(self, key, value): row_name = self._dereference_key( key=key[0], name_list=self._row_names, name_set=self._row_name_set) column_name = self._dereference_key( key=key[1], name_list=self._column_names, name_set=self._column_name_set) if row_name not in self._data: self._data[row_name] = {} if self._column_data_types[column_name] is not None: value = self._column_data_types[column_name](value) self._data[row_name][column_name] = value def row_name_iter(self): for row_name in self._row_names: yield row_name def column_name_iter(self): for column_name in self._column_names: yield column_name def row_value_iter(self, column_name): column_name = self._dereference_key( key=column_name, name_list=self._column_names, name_set=self._column_name_set) for row_name in self._row_names: yield self[row_name, column_name] def column_value_iter(self, row_name): row_name = self._dereference_key( key=row_name, name_list=self._row_names, name_set=self._row_name_set) for column_name in self._column_names: yield self[row_name, column_name] def write_csv(self, out, is_first_row_column_names=True, is_first_column_row_names=True, missing_data_value="NA", **csv_writer_kwargs ): if isinstance(out, str): dest = open(out, "w") else: dest = out if "delimiter" not in csv_writer_kwargs: csv_writer_kwargs["delimiter"] = "," csv_writer = csv.writer(dest, csv_writer_kwargs) if is_first_row_column_names: header = [] if is_first_column_row_names: header.append("") header.extend(self._column_names) csv_writer.writerow(header) for row_name in self._row_names: row = [] if is_first_column_row_names: row.append(row_name) for column_name in self._column_names: v = self[row_name, column_name] if v is None: v = missing_data_value row.append(v) csv_writer.writerow(row) def _validate_new_column_name(self, column_name=None): if column_name is None: column_name = "V{}".format(len(self._column_names)) else: column_name = str(column_name) return column_name def _validate_new_row_name(self, row_name=None): if row_name is None: row_name = "V{}".format(len(self._row_names)) else: row_name = str(row_name) return row_name def _dereference_key(self, key, name_list, name_set): if isinstance(key, int): return name_list[key] else: if key not in name_set: raise KeyError(key) else: return key def num_rows(self): return len(self._row_names) def num_columns(self): return len(self._column_names) def __len__(self): return self.num_rows() ############################################################################### ## Generic Container Interace (for reference) class _ContainerInterface(list): """ The following methods can be defined to implement container objects. Containers usually are sequences (such as lists or tuples) or mappings (like dictionaries), but can represent other containers as well. The first set of methods is used either to emulate a sequence or to emulate a mapping; the difference is that for a sequence, the allowable keys should be the integers k for which 0 <= k < N where N is the length of the sequence, or slice objects, which define a range of items. (For backwards compatibility, the method __getslice__() (see below) can also be defined to handle simple, but not extended slices.) It is also recommended that mappings provide the methods keys(), values(), items(), has_key(), get(), clear(), setdefault(), iterkeys(), itervalues(), iteritems(), pop(), popitem(), copy(), and update() behaving similar to those for Python's standard dictionary objects. The UserDict module provides a DictMixin class to help create those methods from a base set of __getitem__(), __setitem__(), __delitem__(), and keys(). Mutable sequences should provide methods append(), count(), index(), extend(), insert(), pop(), remove(), reverse() and sort(), like Python standard list objects. Finally, sequence types should implement addition (meaning concatenation) and multiplication (meaning repetition) by defining the methods __add__(), __radd__(), __iadd__(), __mul__(), __rmul__() and __imul__() described below; they should not define __coerce__() or other numerical operators. It is recommended that both mappings and sequences implement the __contains__() method to allow efficient use of the in operator; for mappings, in should be equivalent of has_key(); for sequences, it should search through the values. It is further recommended that both mappings and sequences implement the __iter__() method to allow efficient iteration through the container; for mappings, __iter__() should be the same as iterkeys(); for sequences, it should iterate through the values. """ def __len__(self): """ Called to implement the built-in function len(). Should return the length of the object, an integer >= 0. Also, an object that doesn't define a __nonzero__() method and whose __len__() method returns zero is considered to be false in a Boolean context. """ pass def __getitem__(self, key): """ Called to implement evaluation of self[key]. For sequence types, the accepted keys should be integers and slice objects. Note that the special interpretation of negative indices (if the class wishes to emulate a sequence type) is up to the __getitem__() method. If key is of an inappropriate type, TypeError may be raised; if of a value outside the set of indices for the sequence (after any special interpretation of negative values), IndexError should be raised. For mapping types, if key is missing (not in the container), KeyError should be raised. Note for loops expect that an IndexError will be raised for illegal indices to allow proper detection of the end of the sequence. """ pass def __setitem__(self, key, value): """ Called to implement assignment to self[key]. Same note as for __getitem__(). This should only be implemented for mappings if the objects support changes to the values for keys, or if new keys can be added, or for sequences if elements can be replaced. The same exceptions should be raised for improper key values as for the __getitem__() method. """ pass def __delitem__(self, key): """ Called to implement deletion of self[key]. Same note as for __getitem__(). This should only be implemented for mappings if the objects support removal of keys, or for sequences if elements can be removed from the sequence. The same exceptions should be raised for improper key values as for the __getitem__() method. """ pass def __iter__(self): """ This method is called when an iterator is required for a container. This method should return a new iterator object that can iterate over all the objects in the container. For mappings, it should iterate over the keys of the container, and should also be made available as the method iterkeys(). Iterator objects also need to implement this method; they are required to return themselves. For more information on iterator objects, see Iterator Types. """ pass def __reversed__(self): """ Called (if present) by the reversed() builtin to implement reverse iteration. It should return a new iterator object that iterates over all the objects in the container in reverse order. If the __reversed__() method is not provided, the reversed() builtin will fall back to using the sequence protocol (__len__() and __getitem__()). Objects that support the sequence protocol should only provide __reversed__() if they can provide an implementation that is more efficient than the one provided by reversed(). New in version 2.6. """ pass def __contains__(self, item): """ The membership test operators (in and not in) are normally implemented as an iteration through a sequence. However, container objects can supply the following special method with a more efficient implementation, which also does not require the object be a sequence. Called to implement membership test operators. Should return true if item is in self, false otherwise. For mapping objects, this should consider the keys of the mapping rather than the values or the key-item pairs. """ pass ############################################################################### ## RecastingIterator class RecastingIterator(object): """ Given an iterator I_X that returns objects of type X {x1, x2, x3, ... etc.}, and a function F(X), that takes objects of type X as an argument and returns objects of type Y, F(X) = Y, this class will act as an iterator that returns objects of type Y, I_Y, given an iterator on X. The 'function' given can be a class if the class's constructor takes a single argument of type X. """ def __init__(self, source_iter, casting_fn=None, filter_fn=None): """ ``source_iter`` is an iterator. ``casting_fn`` is a function that takes objects returned by ``source_iter`` and returns other objects. ``filter_fn`` is what will be applied to the SOURCE object to decide if it will be returned. """ self.source_iter = iter(source_iter) self.casting_fn = casting_fn self.filter_fn = filter_fn def __iter__(self): "Returns self." return self def next(self): """ Gets next item from the underlying iterator, and if filter_fn returns True on it, applies casting_fn to it and returns it. """ while True: source_next = self.source_iter.next() if self.filter_fn is None or self.filter_fn(source_next): if self.casting_fn is not None: return self.casting_fn(source_next) else: return source_next ############################################################################### ## ItemAttributeProviderList class ItemAttributeProxyList(list): """ This list will return the attribute of its elements instead of the elements themselves. """ def __init__(self, attr_name, *args): """ __init__ calls the list.__init__ with all unnamed args. ``attr_name`` is the name of the attribute or property that should be returned. """ self.bound_attr_name = attr_name list.__init__(self, *args) def __getitem__(self, *args): item = list.__getitem__(self, *args) # assert hasattr(item, self.bound_attr_name) return getattr(item, self.bound_attr_name) def __iter__(self): """ Iterates over all elements in self, returning their `` attribute. """ for item in list.__iter__(self): yield getattr(item, self.bound_attr_name) def aggregate(self): """ Returns a shallow-copy list of the `` attribute of self's members. """ return [getattr(item, self.bound_attr_name) for item in self] ############################################################################### ## ItemSublistProxyList class ItemSublistProxyList(list): """ This list will return a the elements of the bound list attribute of its own elements instead of the element themselves. """ def __init__(self, attr_name, *args): """ __init__ calls the list.__init__ with all unnamed args. ``attr_name`` is the name of the attribute or property that should be returned. """ self.bound_attr_name = attr_name list.__init__(self, *args) def __str__(self): return str([str(i) for i in self]) def __getitem__(self, *args): req_idx = int(args[0]) for idx, i in enumerate(self): if idx == req_idx: return i raise IndexError("list index out of range: %d (max=%d)" % (req_idx, idx)) def __len__(self): return len([i for i in self]) def __iter__(self): """ Iterates over all elements in self, returning their `` attribute. """ for item in list.__iter__(self): for sublist_item in getattr(item, self.bound_attr_name): yield sublist_item def aggregate(self): """ Returns a shallow-copy list of the `` attribute of self's members. """ return [i for i in self]