1 | # Licensed to the StackStorm, Inc ('StackStorm') under one or more |
||
2 | # contributor license agreements. See the NOTICE file distributed with |
||
3 | # this work for additional information regarding copyright ownership. |
||
4 | # The ASF licenses this file to You under the Apache License, Version 2.0 |
||
5 | # (the "License"); you may not use this file except in compliance with |
||
6 | # the License. You may obtain a copy of the License at |
||
7 | # |
||
8 | # http://www.apache.org/licenses/LICENSE-2.0 |
||
9 | # |
||
10 | # Unless required by applicable law or agreed to in writing, software |
||
11 | # distributed under the License is distributed on an "AS IS" BASIS, |
||
12 | # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
||
13 | # See the License for the specific language governing permissions and |
||
14 | # limitations under the License. |
||
15 | |||
16 | """ |
||
17 | Based on http://code.activestate.com/recipes/576694/ (MIT license) |
||
18 | """ |
||
19 | |||
20 | from __future__ import absolute_import |
||
21 | import collections |
||
22 | |||
23 | __all__ = [ |
||
24 | 'OrderedSet' |
||
25 | ] |
||
26 | |||
27 | |||
28 | class OrderedSet(collections.MutableSet): |
||
29 | |||
30 | def __init__(self, iterable=None): |
||
31 | self.end = end = [] |
||
32 | end += [None, end, end] # sentinel node for doubly linked list |
||
33 | self.map = {} # key --> [key, prev, next] |
||
34 | if iterable is not None: |
||
35 | self |= iterable |
||
36 | |||
37 | def __len__(self): |
||
38 | return len(self.map) |
||
39 | |||
40 | def __contains__(self, key): |
||
41 | return key in self.map |
||
42 | |||
43 | def add(self, key): |
||
44 | if key not in self.map: |
||
45 | end = self.end |
||
46 | curr = end[1] |
||
47 | curr[2] = end[1] = self.map[key] = [key, curr, end] |
||
48 | |||
49 | def discard(self, key): |
||
50 | if key in self.map: |
||
51 | key, prev, next = self.map.pop(key) |
||
52 | prev[2] = next |
||
53 | next[1] = prev |
||
54 | |||
55 | def __iter__(self): |
||
56 | end = self.end |
||
57 | curr = end[2] |
||
58 | while curr is not end: |
||
59 | yield curr[0] |
||
60 | curr = curr[2] |
||
61 | |||
62 | def __reversed__(self): |
||
63 | end = self.end |
||
64 | curr = end[1] |
||
65 | while curr is not end: |
||
66 | yield curr[0] |
||
67 | curr = curr[1] |
||
68 | |||
69 | def pop(self, last=True): |
||
0 ignored issues
–
show
Bug
introduced
by
Loading history...
|
|||
70 | if not self: |
||
71 | raise KeyError('set is empty') |
||
72 | key = self.end[1][0] if last else self.end[2][0] |
||
73 | self.discard(key) |
||
74 | return key |
||
75 | |||
76 | def __repr__(self): |
||
77 | if not self: |
||
78 | return '%s()' % (self.__class__.__name__,) |
||
79 | return '%s(%r)' % (self.__class__.__name__, list(self)) |
||
80 | |||
81 | def __eq__(self, other): |
||
82 | if isinstance(other, OrderedSet): |
||
83 | return len(self) == len(other) and list(self) == list(other) |
||
84 | return set(self) == set(other) |
||
85 |