third_party/markdown/odict.py

   1 # markdown is released under the BSD license
   2 # Copyright 2007, 2008 The Python Markdown Project (v. 1.7 and later)
   3 # Copyright 2004, 2005, 2006 Yuri Takhteyev (v. 0.2-1.6b)
   4 # Copyright 2004 Manfred Stienstra (the original version)
   5 #
   6 # All rights reserved.
   7 #
   8 # Redistribution and use in source and binary forms, with or without
   9 # modification, are permitted provided that the following conditions are met:
  10 #
  11 # *   Redistributions of source code must retain the above copyright
  12 #     notice, this list of conditions and the following disclaimer.
  13 # *   Redistributions in binary form must reproduce the above copyright
  14 #     notice, this list of conditions and the following disclaimer in the
  15 #     documentation and/or other materials provided with the distribution.
  16 # *   Neither the name of the <organization> nor the
  17 #     names of its contributors may be used to endorse or promote products
  18 #     derived from this software without specific prior written permission.
  19 #
  20 # THIS SOFTWARE IS PROVIDED BY THE PYTHON MARKDOWN PROJECT ''AS IS'' AND ANY
  21 # EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  22 # WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  23 # DISCLAIMED. IN NO EVENT SHALL ANY CONTRIBUTORS TO THE PYTHON MARKDOWN PROJECT
  24 # BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  25 # CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  26 # SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  27 # INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28 # CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  29 # ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  30 # POSSIBILITY OF SUCH DAMAGE.
  31
  32
  33 from __future__ import unicode_literals
  34 from __future__ import absolute_import
  35 from . import util
  36
  37 from copy import deepcopy
  38
  39 def iteritems_compat(d):
  40     """Return an iterator over the (key, value) pairs of a dictionary.
  41     Copied from `six` module."""
  42     return iter(getattr(d, _iteritems)())
  43
  44 class OrderedDict(dict):
  45     """
  46     A dictionary that keeps its keys in the order in which they're inserted.
  47
  48     Copied from Django's SortedDict with some modifications.
  49
  50     """
  51     def __new__(cls, *args, **kwargs):
  52         instance = super(OrderedDict, cls).__new__(cls, *args, **kwargs)
  53         instance.keyOrder = []
  54         return instance
  55
  56     def __init__(self, data=None):
  57         if data is None or isinstance(data, dict):
  58             data = data or []
  59             super(OrderedDict, self).__init__(data)
  60             self.keyOrder = list(data) if data else []
  61         else:
  62             super(OrderedDict, self).__init__()
  63             super_set = super(OrderedDict, self).__setitem__
  64             for key, value in data:
  65                 # Take the ordering from first key
  66                 if key not in self:
  67                     self.keyOrder.append(key)
  68                 # But override with last value in data (dict() does this)
  69                 super_set(key, value)
  70
  71     def __deepcopy__(self, memo):
  72         return self.__class__([(key, deepcopy(value, memo))
  73                                for key, value in self.items()])
  74
  75     def __copy__(self):
  76         # The Python's default copy implementation will alter the state
  77         # of self. The reason for this seems complex but is likely related to
  78         # subclassing dict.
  79         return self.copy()
  80
  81     def __setitem__(self, key, value):
  82         if key not in self:
  83             self.keyOrder.append(key)
  84         super(OrderedDict, self).__setitem__(key, value)
  85
  86     def __delitem__(self, key):
  87         super(OrderedDict, self).__delitem__(key)
  88         self.keyOrder.remove(key)
  89
  90     def __iter__(self):
  91         return iter(self.keyOrder)
  92
  93     def __reversed__(self):
  94         return reversed(self.keyOrder)
  95
  96     def pop(self, k, *args):
  97         result = super(OrderedDict, self).pop(k, *args)
  98         try:
  99             self.keyOrder.remove(k)
 100         except ValueError:
 101             # Key wasn't in the dictionary in the first place. No problem.
 102             pass
 103         return result
 104
 105     def popitem(self):
 106         result = super(OrderedDict, self).popitem()
 107         self.keyOrder.remove(result[0])
 108         return result
 109
 110     def _iteritems(self):
 111         for key in self.keyOrder:
 112             yield key, self[key]
 113
 114     def _iterkeys(self):
 115         for key in self.keyOrder:
 116             yield key
 117
 118     def _itervalues(self):
 119         for key in self.keyOrder:
 120             yield self[key]
 121
 122     if util.PY3:
 123         items = _iteritems
 124         keys = _iterkeys
 125         values = _itervalues
 126     else:
 127         iteritems = _iteritems
 128         iterkeys = _iterkeys
 129         itervalues = _itervalues
 130
 131         def items(self):
 132             return [(k, self[k]) for k in self.keyOrder]
 133
 134         def keys(self):
 135             return self.keyOrder[:]
 136
 137         def values(self):
 138             return [self[k] for k in self.keyOrder]
 139
 140     def update(self, dict_):
 141         for k, v in iteritems_compat(dict_):
 142             self[k] = v
 143
 144     def setdefault(self, key, default):
 145         if key not in self:
 146             self.keyOrder.append(key)
 147         return super(OrderedDict, self).setdefault(key, default)
 148
 149     def value_for_index(self, index):
 150         """Returns the value of the item at the given zero-based index."""
 151         return self[self.keyOrder[index]]
 152
 153     def insert(self, index, key, value):
 154         """Inserts the key, value pair before the item with the given index."""
 155         if key in self.keyOrder:
 156             n = self.keyOrder.index(key)
 157             del self.keyOrder[n]
 158             if n < index:
 159                 index -= 1
 160         self.keyOrder.insert(index, key)
 161         super(OrderedDict, self).__setitem__(key, value)
 162
 163     def copy(self):
 164         """Returns a copy of this object."""
 165         # This way of initializing the copy means it works for subclasses, too.
 166         return self.__class__(self)
 167
 168     def __repr__(self):
 169         """
 170         Replaces the normal dict.__repr__ with a version that returns the keys
 171         in their Ordered order.
 172         """
 173         return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in iteritems_compat(self)])
 174
 175     def clear(self):
 176         super(OrderedDict, self).clear()
 177         self.keyOrder = []
 178
 179     def index(self, key):
 180         """ Return the index of a given key. """
 181         try:
 182             return self.keyOrder.index(key)
 183         except ValueError:
 184             raise ValueError("Element '%s' was not found in OrderedDict" % key)
 185
 186     def index_for_location(self, location):
 187         """ Return index or None for a given location. """
 188         if location == '_begin':
 189             i = 0
 190         elif location == '_end':
 191             i = None
 192         elif location.startswith('<') or location.startswith('>'):
 193             i = self.index(location[1:])
 194             if location.startswith('>'):
 195                 if i >= len(self):
 196                     # last item
 197                     i = None
 198                 else:
 199                     i += 1
 200         else:
 201             raise ValueError('Not a valid location: "%s". Location key '
 202                              'must start with a ">" or "<".' % location)
 203         return i
 204
 205     def add(self, key, value, location):
 206         """ Insert by key location. """
 207         i = self.index_for_location(location)
 208         if i is not None:
 209             self.insert(i, key, value)
 210         else:
 211             self.__setitem__(key, value)
 212
 213     def link(self, key, location):
 214         """ Change location of an existing item. """
 215         n = self.keyOrder.index(key)
 216         del self.keyOrder[n]
 217         try:
 218             i = self.index_for_location(location)
 219             if i is not None:
 220                 self.keyOrder.insert(i, key)
 221             else:
 222                 self.keyOrder.append(key)
 223         except Exception as e:
 224             # restore to prevent data loss and reraise
 225             self.keyOrder.insert(n, key)
 226             raise e