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 33from __future__ import unicode_literals 34from __future__ import absolute_import 35from . import util 36 37from copy import deepcopy 38 39def 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 44class 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 227