← Back to branch summary

~0x44/nova/bug838466

« back to all changes in this revision

Viewing changes to vendor/tornado/website/markdown/odict.py

  • Committer: Jesse Andrews
  • Date: 2010-05-28 06:05:26 UTC
  • Revision ID: git-v1:bf6e6e718cdc7488e2da87b21e258ccc065fe499
initial commit

Show diffs side-by-side

added added

removed removed

Lines of Context:
vendor/tornado/website/markdown/odict.py
 
1
class OrderedDict(dict):
 
2
    """
 
3
    A dictionary that keeps its keys in the order in which they're inserted.
 
4
    
 
5
    Copied from Django's SortedDict with some modifications.
 
6
 
 
7
    """
 
8
    def __new__(cls, *args, **kwargs):
 
9
        instance = super(OrderedDict, cls).__new__(cls, *args, **kwargs)
 
10
        instance.keyOrder = []
 
11
        return instance
 
12
 
 
13
    def __init__(self, data=None):
 
14
        if data is None:
 
15
            data = {}
 
16
        super(OrderedDict, self).__init__(data)
 
17
        if isinstance(data, dict):
 
18
            self.keyOrder = data.keys()
 
19
        else:
 
20
            self.keyOrder = []
 
21
            for key, value in data:
 
22
                if key not in self.keyOrder:
 
23
                    self.keyOrder.append(key)
 
24
 
 
25
    def __deepcopy__(self, memo):
 
26
        from copy import deepcopy
 
27
        return self.__class__([(key, deepcopy(value, memo))
 
28
                               for key, value in self.iteritems()])
 
29
 
 
30
    def __setitem__(self, key, value):
 
31
        super(OrderedDict, self).__setitem__(key, value)
 
32
        if key not in self.keyOrder:
 
33
            self.keyOrder.append(key)
 
34
 
 
35
    def __delitem__(self, key):
 
36
        super(OrderedDict, self).__delitem__(key)
 
37
        self.keyOrder.remove(key)
 
38
 
 
39
    def __iter__(self):
 
40
        for k in self.keyOrder:
 
41
            yield k
 
42
 
 
43
    def pop(self, k, *args):
 
44
        result = super(OrderedDict, self).pop(k, *args)
 
45
        try:
 
46
            self.keyOrder.remove(k)
 
47
        except ValueError:
 
48
            # Key wasn't in the dictionary in the first place. No problem.
 
49
            pass
 
50
        return result
 
51
 
 
52
    def popitem(self):
 
53
        result = super(OrderedDict, self).popitem()
 
54
        self.keyOrder.remove(result[0])
 
55
        return result
 
56
 
 
57
    def items(self):
 
58
        return zip(self.keyOrder, self.values())
 
59
 
 
60
    def iteritems(self):
 
61
        for key in self.keyOrder:
 
62
            yield key, super(OrderedDict, self).__getitem__(key)
 
63
 
 
64
    def keys(self):
 
65
        return self.keyOrder[:]
 
66
 
 
67
    def iterkeys(self):
 
68
        return iter(self.keyOrder)
 
69
 
 
70
    def values(self):
 
71
        return [super(OrderedDict, self).__getitem__(k) for k in self.keyOrder]
 
72
 
 
73
    def itervalues(self):
 
74
        for key in self.keyOrder:
 
75
            yield super(OrderedDict, self).__getitem__(key)
 
76
 
 
77
    def update(self, dict_):
 
78
        for k, v in dict_.items():
 
79
            self.__setitem__(k, v)
 
80
 
 
81
    def setdefault(self, key, default):
 
82
        if key not in self.keyOrder:
 
83
            self.keyOrder.append(key)
 
84
        return super(OrderedDict, self).setdefault(key, default)
 
85
 
 
86
    def value_for_index(self, index):
 
87
        """Return the value of the item at the given zero-based index."""
 
88
        return self[self.keyOrder[index]]
 
89
 
 
90
    def insert(self, index, key, value):
 
91
        """Insert the key, value pair before the item with the given index."""
 
92
        if key in self.keyOrder:
 
93
            n = self.keyOrder.index(key)
 
94
            del self.keyOrder[n]
 
95
            if n < index:
 
96
                index -= 1
 
97
        self.keyOrder.insert(index, key)
 
98
        super(OrderedDict, self).__setitem__(key, value)
 
99
 
 
100
    def copy(self):
 
101
        """Return a copy of this object."""
 
102
        # This way of initializing the copy means it works for subclasses, too.
 
103
        obj = self.__class__(self)
 
104
        obj.keyOrder = self.keyOrder[:]
 
105
        return obj
 
106
 
 
107
    def __repr__(self):
 
108
        """
 
109
        Replace the normal dict.__repr__ with a version that returns the keys
 
110
        in their sorted order.
 
111
        """
 
112
        return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])
 
113
 
 
114
    def clear(self):
 
115
        super(OrderedDict, self).clear()
 
116
        self.keyOrder = []
 
117
 
 
118
    def index(self, key):
 
119
        """ Return the index of a given key. """
 
120
        return self.keyOrder.index(key)
 
121
 
 
122
    def index_for_location(self, location):
 
123
        """ Return index or None for a given location. """
 
124
        if location == '_begin':
 
125
            i = 0
 
126
        elif location == '_end':
 
127
            i = None
 
128
        elif location.startswith('<') or location.startswith('>'):
 
129
            i = self.index(location[1:])
 
130
            if location.startswith('>'):
 
131
                if i >= len(self):
 
132
                    # last item
 
133
                    i = None
 
134
                else:
 
135
                    i += 1
 
136
        else:
 
137
            raise ValueError('Not a valid location: "%s". Location key '
 
138
                             'must start with a ">" or "<".' % location)
 
139
        return i
 
140
 
 
141
    def add(self, key, value, location):
 
142
        """ Insert by key location. """
 
143
        i = self.index_for_location(location)
 
144
        if i is not None:
 
145
            self.insert(i, key, value)
 
146
        else:
 
147
            self.__setitem__(key, value)
 
148
 
 
149
    def link(self, key, location):
 
150
        """ Change location of an existing item. """
 
151
        n = self.keyOrder.index(key)
 
152
        del self.keyOrder[n]
 
153
        i = self.index_for_location(location)
 
154
        try:
 
155
            if i is not None:
 
156
                self.keyOrder.insert(i, key)
 
157
            else:
 
158
                self.keyOrder.append(key)
 
159
        except Error:
 
160
            # restore to prevent data loss and reraise
 
161
            self.keyOrder.insert(n, key)
 
162
            raise Error