Debian Codegraph @

perfprofd/scripts/sorted_collection.py

raw
1 # Note: Taken from https://code.activestate.com/recipes/577197-sortedcollection/.
2 #
3 # Copyright 2010 Raymond Hettinger
4 #
5 # Permission is hereby granted, free of charge, to any person obtaining a copy of
6 # this software and associated documentation files (the "Software"), to deal in the
7 # Software without restriction, including without limitation the rights to use, copy,
8 # modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
9 # and to permit persons to whom the Software is furnished to do so, subject to the
10 # following conditions:
11 #
12 # The above copyright notice and this permission notice shall be included in all copies
13 # or substantial portions of the Software.
14 #
15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
16 # INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
17 # PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
18 # FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
19 # OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 # DEALINGS IN THE SOFTWARE.
21
22 from bisect import bisect_left, bisect_right
23
24
25 class SortedCollection(object):
26 def __init__(self, iterable=(), key=None):
27 self._given_key = key
28 key = (lambda x: x) if key is None else key
29 decorated = sorted((key(item), item) for item in iterable)
30 self._keys = [k for k, item in decorated]
31 self._items = [item for k, item in decorated]
32 self._key = key
33
34 def _getkey(self):
35 return self._key
36
37 def _setkey(self, key):
38 if key is not self._key:
39 self.__init__(self._items, key=key)
40
41 def _delkey(self):
42 self._setkey(None)
43
44 key = property(_getkey, _setkey, _delkey, 'key function')
45
46 def clear(self):
47 self.__init__([], self._key)
48
49 def copy(self):
50 return self.__class__(self, self._key)
51
52 def __len__(self):
53 return len(self._items)
54
55 def __getitem__(self, i):
56 return self._items[i]
57
58 def __iter__(self):
59 return iter(self._items)
60
61 def __reversed__(self):
62 return reversed(self._items)
63
64 def __repr__(self):
65 return '%s(%r, key=%s)' % (
66 self.__class__.__name__,
67 self._items,
68 getattr(self._given_key, '__name__', repr(self._given_key))
69 )
70
71 def __reduce__(self):
72 return self.__class__, (self._items, self._given_key)
73
74 def __contains__(self, item):
75 k = self._key(item)
76 i = bisect_left(self._keys, k)
77 j = bisect_right(self._keys, k)
78 return item in self._items[i:j]
79
80 def index(self, item):
81 'Find the position of an item. Raise ValueError if not found.'
82 k = self._key(item)
83 i = bisect_left(self._keys, k)
84 j = bisect_right(self._keys, k)
85 return self._items[i:j].index(item) + i
86
87 def count(self, item):
88 'Return number of occurrences of item'
89 k = self._key(item)
90 i = bisect_left(self._keys, k)
91 j = bisect_right(self._keys, k)
92 return self._items[i:j].count(item)
93
94 def insert(self, item):
95 'Insert a new item. If equal keys are found, add to the left'
96 k = self._key(item)
97 i = bisect_left(self._keys, k)
98 self._keys.insert(i, k)
99 self._items.insert(i, item)
100
101 def insert_right(self, item):
102 'Insert a new item. If equal keys are found, add to the right'
103 k = self._key(item)
104 i = bisect_right(self._keys, k)
105 self._keys.insert(i, k)
106 self._items.insert(i, item)
107
108 def remove(self, item):
109 'Remove first occurence of item. Raise ValueError if not found'
110 i = self.index(item)
111 del self._keys[i]
112 del self._items[i]
113
114 def find(self, k):
115 'Return first item with a key == k. Raise ValueError if not found.'
116 i = bisect_left(self._keys, k)
117 if i != len(self) and self._keys[i] == k:
118 return self._items[i]
119 raise ValueError('No item found with key equal to: %r' % (k,))
120
121 def find_le(self, k):
122 'Return last item with a key <= k. Raise ValueError if not found.'
123 i = bisect_right(self._keys, k)
124 if i:
125 return self._items[i-1]
126 raise ValueError('No item found with key at or below: %r' % (k,))
127
128 def find_lt(self, k):
129 'Return last item with a key < k. Raise ValueError if not found.'
130 i = bisect_left(self._keys, k)
131 if i:
132 return self._items[i-1]
133 raise ValueError('No item found with key below: %r' % (k,))
134
135 def find_ge(self, k):
136 'Return first item with a key >= equal to k. Raise ValueError if not found'
137 i = bisect_left(self._keys, k)
138 if i != len(self):
139 return self._items[i]
140 raise ValueError('No item found with key at or above: %r' % (k,))
141
142 def find_gt(self, k):
143 'Return first item with a key > k. Raise ValueError if not found'
144 i = bisect_right(self._keys, k)
145 if i != len(self):
146 return self._items[i]
147 raise ValueError('No item found with key above: %r' % (k,))