1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
# -*- coding: utf-8 -*-
# Copyright (C) 2015 Yahoo! Inc. All Rights Reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License"); you may
# not use this file except in compliance with the License. You may obtain
# a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
# License for the specific language governing permissions and limitations
# under the License.
import collections
from collections import abc
import itertools
# Used for values that don't matter in sets backed by dicts...
_sentinel = object()
def _merge_in(target, iterable=None, sentinel=_sentinel):
"""Merges iterable into the target and returns the target."""
if iterable is not None:
for value in iterable:
target.setdefault(value, sentinel)
return target
class OrderedSet(abc.Set, abc.Hashable):
"""A read-only hashable set that retains insertion/initial ordering.
It should work in all existing places that ``frozenset`` is used.
See: https://mail.python.org/pipermail/python-ideas/2009-May/004567.html
for an idea thread that *may* eventually (*someday*) result in this (or
similar) code being included in the mainline python codebase (although
the end result of that thread is somewhat discouraging in that regard).
"""
__slots__ = ['_data']
def __init__(self, iterable=None):
self._data = _merge_in(collections.OrderedDict(), iterable)
def __hash__(self):
return self._hash()
def __contains__(self, value):
return value in self._data
def __len__(self):
return len(self._data)
def __iter__(self):
for value in self._data.keys():
yield value
def __setstate__(self, items):
self.__init__(iterable=iter(items))
def __getstate__(self):
return tuple(self)
def __repr__(self):
return "%s(%s)" % (type(self).__name__, list(self))
def copy(self):
"""Return a shallow copy of a set."""
return self._from_iterable(iter(self))
def intersection(self, *sets):
"""Return the intersection of two or more sets as a new set.
(i.e. elements that are common to all of the sets.)
"""
def absorb_it(sets):
for value in iter(self):
matches = 0
for s in sets:
if value in s:
matches += 1
else:
break
if matches == len(sets):
yield value
return self._from_iterable(absorb_it(sets))
def issuperset(self, other):
"""Report whether this set contains another set."""
for value in other:
if value not in self:
return False
return True
def issubset(self, other):
"""Report whether another set contains this set."""
for value in iter(self):
if value not in other:
return False
return True
def difference(self, *sets):
"""Return the difference of two or more sets as a new set.
(i.e. all elements that are in this set but not the others.)
"""
def absorb_it(sets):
for value in iter(self):
seen = False
for s in sets:
if value in s:
seen = True
break
if not seen:
yield value
return self._from_iterable(absorb_it(sets))
def union(self, *sets):
"""Return the union of sets as a new set.
(i.e. all elements that are in either set.)
"""
return self._from_iterable(itertools.chain(iter(self), *sets))
|
