Initial Contributionv1.0

1 files changed, 421 insertions, 0 deletions

diff --git a/webapp/django/utils/datastructures.py b/webapp/django/utils/datastructures.py
new file mode 100644
index 0000000000..5837c3d236
--- /dev/null
+++ b/webapp/django/utils/datastructures.py
@@ -0,0 +1,421 @@
+class MergeDict(object):
+    """
+    A simple class for creating new "virtual" dictionaries that actually look
+    up values in more than one dictionary, passed in the constructor.
+
+    If a key appears in more than one of the given dictionaries, only the
+    first occurrence will be used.
+    """
+    def __init__(self, *dicts):
+        self.dicts = dicts
+
+    def __getitem__(self, key):
+        for dict_ in self.dicts:
+            try:
+                return dict_[key]
+            except KeyError:
+                pass
+        raise KeyError
+
+    def __copy__(self):
+        return self.__class__(*self.dicts)
+
+    def get(self, key, default=None):
+        try:
+            return self[key]
+        except KeyError:
+            return default
+
+    def getlist(self, key):
+        for dict_ in self.dicts:
+            if key in dict_.keys():
+                return dict_.getlist(key)
+        return []
+
+    def items(self):
+        item_list = []
+        for dict_ in self.dicts:
+            item_list.extend(dict_.items())
+        return item_list
+
+    def has_key(self, key):
+        for dict_ in self.dicts:
+            if key in dict_:
+                return True
+        return False
+
+    __contains__ = has_key
+
+    def copy(self):
+        """Returns a copy of this object."""
+        return self.__copy__()
+
+class SortedDict(dict):
+    """
+    A dictionary that keeps its keys in the order in which they're inserted.
+    """
+    def __new__(cls, *args, **kwargs):
+        instance = super(SortedDict, cls).__new__(cls, *args, **kwargs)
+        instance.keyOrder = []
+        return instance
+
+    def __init__(self, data=None):
+        if data is None:
+            data = {}
+        super(SortedDict, self).__init__(data)
+        if isinstance(data, dict):
+            self.keyOrder = data.keys()
+        else:
+            self.keyOrder = []
+            for key, value in data:
+                if key not in self.keyOrder:
+                    self.keyOrder.append(key)
+
+    def __deepcopy__(self, memo):
+        from copy import deepcopy
+        return self.__class__([(key, deepcopy(value, memo))
+                               for key, value in self.iteritems()])
+
+    def __setitem__(self, key, value):
+        super(SortedDict, self).__setitem__(key, value)
+        if key not in self.keyOrder:
+            self.keyOrder.append(key)
+
+    def __delitem__(self, key):
+        super(SortedDict, self).__delitem__(key)
+        self.keyOrder.remove(key)
+
+    def __iter__(self):
+        for k in self.keyOrder:
+            yield k
+
+    def pop(self, k, *args):
+        result = super(SortedDict, self).pop(k, *args)
+        try:
+            self.keyOrder.remove(k)
+        except ValueError:
+            # Key wasn't in the dictionary in the first place. No problem.
+            pass
+        return result
+
+    def popitem(self):
+        result = super(SortedDict, self).popitem()
+        self.keyOrder.remove(result[0])
+        return result
+
+    def items(self):
+        return zip(self.keyOrder, self.values())
+
+    def iteritems(self):
+        for key in self.keyOrder:
+            yield key, super(SortedDict, self).__getitem__(key)
+
+    def keys(self):
+        return self.keyOrder[:]
+
+    def iterkeys(self):
+        return iter(self.keyOrder)
+
+    def values(self):
+        return [super(SortedDict, self).__getitem__(k) for k in self.keyOrder]
+
+    def itervalues(self):
+        for key in self.keyOrder:
+            yield super(SortedDict, self).__getitem__(key)
+
+    def update(self, dict_):
+        for k, v in dict_.items():
+            self.__setitem__(k, v)
+
+    def setdefault(self, key, default):
+        if key not in self.keyOrder:
+            self.keyOrder.append(key)
+        return super(SortedDict, self).setdefault(key, default)
+
+    def value_for_index(self, index):
+        """Returns the value of the item at the given zero-based index."""
+        return self[self.keyOrder[index]]
+
+    def insert(self, index, key, value):
+        """Inserts the key, value pair before the item with the given index."""
+        if key in self.keyOrder:
+            n = self.keyOrder.index(key)
+            del self.keyOrder[n]
+            if n < index:
+                index -= 1
+        self.keyOrder.insert(index, key)
+        super(SortedDict, self).__setitem__(key, value)
+
+    def copy(self):
+        """Returns a copy of this object."""
+        # This way of initializing the copy means it works for subclasses, too.
+        obj = self.__class__(self)
+        obj.keyOrder = self.keyOrder[:]
+        return obj
+
+    def __repr__(self):
+        """
+        Replaces the normal dict.__repr__ with a version that returns the keys
+        in their sorted order.
+        """
+        return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])
+
+    def clear(self):
+        super(SortedDict, self).clear()
+        self.keyOrder = []
+
+class MultiValueDictKeyError(KeyError):
+    pass
+
+class MultiValueDict(dict):
+    """
+    A subclass of dictionary customized to handle multiple values for the
+    same key.
+
+    >>> d = MultiValueDict({'name': ['Adrian', 'Simon'], 'position': ['Developer']})
+    >>> d['name']
+    'Simon'
+    >>> d.getlist('name')
+    ['Adrian', 'Simon']
+    >>> d.get('lastname', 'nonexistent')
+    'nonexistent'
+    >>> d.setlist('lastname', ['Holovaty', 'Willison'])
+
+    This class exists to solve the irritating problem raised by cgi.parse_qs,
+    which returns a list for every key, even though most Web forms submit
+    single name-value pairs.
+    """
+    def __init__(self, key_to_list_mapping=()):
+        super(MultiValueDict, self).__init__(key_to_list_mapping)
+
+    def __repr__(self):
+        return "<%s: %s>" % (self.__class__.__name__,
+                             super(MultiValueDict, self).__repr__())
+
+    def __getitem__(self, key):
+        """
+        Returns the last data value for this key, or [] if it's an empty list;
+        raises KeyError if not found.
+        """
+        try:
+            list_ = super(MultiValueDict, self).__getitem__(key)
+        except KeyError:
+            raise MultiValueDictKeyError, "Key %r not found in %r" % (key, self)
+        try:
+            return list_[-1]
+        except IndexError:
+            return []
+
+    def __setitem__(self, key, value):
+        super(MultiValueDict, self).__setitem__(key, [value])
+
+    def __copy__(self):
+        return self.__class__(super(MultiValueDict, self).items())
+
+    def __deepcopy__(self, memo=None):
+        import copy
+        if memo is None:
+            memo = {}
+        result = self.__class__()
+        memo[id(self)] = result
+        for key, value in dict.items(self):
+            dict.__setitem__(result, copy.deepcopy(key, memo),
+                             copy.deepcopy(value, memo))
+        return result
+
+    def get(self, key, default=None):
+        """
+        Returns the last data value for the passed key. If key doesn't exist
+        or value is an empty list, then default is returned.
+        """
+        try:
+            val = self[key]
+        except KeyError:
+            return default
+        if val == []:
+            return default
+        return val
+
+    def getlist(self, key):
+        """
+        Returns the list of values for the passed key. If key doesn't exist,
+        then an empty list is returned.
+        """
+        try:
+            return super(MultiValueDict, self).__getitem__(key)
+        except KeyError:
+            return []
+
+    def setlist(self, key, list_):
+        super(MultiValueDict, self).__setitem__(key, list_)
+
+    def setdefault(self, key, default=None):
+        if key not in self:
+            self[key] = default
+        return self[key]
+
+    def setlistdefault(self, key, default_list=()):
+        if key not in self:
+            self.setlist(key, default_list)
+        return self.getlist(key)
+
+    def appendlist(self, key, value):
+        """Appends an item to the internal list associated with key."""
+        self.setlistdefault(key, [])
+        super(MultiValueDict, self).__setitem__(key, self.getlist(key) + [value])
+
+    def items(self):
+        """
+        Returns a list of (key, value) pairs, where value is the last item in
+        the list associated with the key.
+        """
+        return [(key, self[key]) for key in self.keys()]
+
+    def iteritems(self):
+        """
+        Yields (key, value) pairs, where value is the last item in the list
+        associated with the key.
+        """
+        for key in self.keys():
+            yield (key, self[key])
+
+    def lists(self):
+        """Returns a list of (key, list) pairs."""
+        return super(MultiValueDict, self).items()
+
+    def values(self):
+        """Returns a list of the last value on every key list."""
+        return [self[key] for key in self.keys()]
+
+    def copy(self):
+        """Returns a copy of this object."""
+        return self.__deepcopy__()
+
+    def update(self, *args, **kwargs):
+        """
+        update() extends rather than replaces existing key lists.
+        Also accepts keyword args.
+        """
+        if len(args) > 1:
+            raise TypeError, "update expected at most 1 arguments, got %d" % len(args)
+        if args:
+            other_dict = args[0]
+            if isinstance(other_dict, MultiValueDict):
+                for key, value_list in other_dict.lists():
+                    self.setlistdefault(key, []).extend(value_list)
+            else:
+                try:
+                    for key, value in other_dict.items():
+                        self.setlistdefault(key, []).append(value)
+                except TypeError:
+                    raise ValueError, "MultiValueDict.update() takes either a MultiValueDict or dictionary"
+        for key, value in kwargs.iteritems():
+            self.setlistdefault(key, []).append(value)
+
+class DotExpandedDict(dict):
+    """
+    A special dictionary constructor that takes a dictionary in which the keys
+    may contain dots to specify inner dictionaries. It's confusing, but this
+    example should make sense.
+
+    >>> d = DotExpandedDict({'person.1.firstname': ['Simon'], \
+            'person.1.lastname': ['Willison'], \
+            'person.2.firstname': ['Adrian'], \
+            'person.2.lastname': ['Holovaty']})
+    >>> d
+    {'person': {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}}
+    >>> d['person']
+    {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}
+    >>> d['person']['1']
+    {'lastname': ['Willison'], 'firstname': ['Simon']}
+
+    # Gotcha: Results are unpredictable if the dots are "uneven":
+    >>> DotExpandedDict({'c.1': 2, 'c.2': 3, 'c': 1})
+    {'c': 1}
+    """
+    def __init__(self, key_to_list_mapping):
+        for k, v in key_to_list_mapping.items():
+            current = self
+            bits = k.split('.')
+            for bit in bits[:-1]:
+                current = current.setdefault(bit, {})
+            # Now assign value to current position
+            try:
+                current[bits[-1]] = v
+            except TypeError: # Special-case if current isn't a dict.
+                current = {bits[-1]: v}
+
+class ImmutableList(tuple):
+    """
+    A tuple-like object that raises useful errors when it is asked to mutate.
+
+    Example::
+
+        >>> a = ImmutableList(range(5), warning="You cannot mutate this.")
+        >>> a[3] = '4'
+        Traceback (most recent call last):
+            ...
+        AttributeError: You cannot mutate this.
+    """
+
+    def __new__(cls, *args, **kwargs):
+        if 'warning' in kwargs:
+            warning = kwargs['warning']
+            del kwargs['warning']
+        else:
+            warning = 'ImmutableList object is immutable.'
+        self = tuple.__new__(cls, *args, **kwargs)
+        self.warning = warning
+        return self
+
+    def complain(self, *wargs, **kwargs):
+        if isinstance(self.warning, Exception):
+            raise self.warning
+        else:
+            raise AttributeError, self.warning
+
+    # All list mutation functions complain.
+    __delitem__  = complain
+    __delslice__ = complain
+    __iadd__     = complain
+    __imul__     = complain
+    __setitem__  = complain
+    __setslice__ = complain
+    append       = complain
+    extend       = complain
+    insert       = complain
+    pop          = complain
+    remove       = complain
+    sort         = complain
+    reverse      = complain
+
+class DictWrapper(dict):
+    """
+    Wraps accesses to a dictionary so that certain values (those starting with
+    the specified prefix) are passed through a function before being returned.
+    The prefix is removed before looking up the real value.
+
+    Used by the SQL construction code to ensure that values are correctly
+    quoted before being used.
+    """
+    def __init__(self, data, func, prefix):
+        super(DictWrapper, self).__init__(data)
+        self.func = func
+        self.prefix = prefix
+
+    def __getitem__(self, key):
+        """
+        Retrieves the real value after stripping the prefix string (if
+        present). If the prefix is present, pass the value through self.func
+        before returning, otherwise return the raw value.
+        """
+        if key.startswith(self.prefix):
+            use_func = True
+            key = key[len(self.prefix):]
+        else:
+            use_func = False
+        value = super(DictWrapper, self).__getitem__(key)
+        if use_func:
+            return self.func(value)
+        return value
+