|
|
|---|
| 0 |
- |
1 |
#!/usr/bin/python2.7 |
|
|
2 |
# coding: utf-8 |
| 3 |
# |
| 4 |
# Univention Common Python Library |
| 5 |
# OrderedSet |
| 6 |
# |
| 7 |
# Copyright 2017 Univention GmbH |
| 8 |
# |
| 9 |
# http://www.univention.de/ |
| 10 |
# |
| 11 |
# All rights reserved. |
| 12 |
# |
| 13 |
# The source code of this program is made available |
| 14 |
# under the terms of the GNU Affero General Public License version 3 |
| 15 |
# (GNU AGPL V3) as published by the Free Software Foundation. |
| 16 |
# |
| 17 |
# Binary versions of this program provided by Univention to you as |
| 18 |
# well as other copyrighted, protected or trademarked materials like |
| 19 |
# Logos, graphics, fonts, specific documentations and configurations, |
| 20 |
# cryptographic keys etc. are subject to a license agreement between |
| 21 |
# you and Univention and not subject to the GNU AGPL V3. |
| 22 |
# |
| 23 |
# In the case you use this program under the terms of the GNU AGPL V3, |
| 24 |
# the program is provided in the hope that it will be useful, |
| 25 |
# but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 26 |
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 27 |
# GNU Affero General Public License for more details. |
| 28 |
# |
| 29 |
# You should have received a copy of the GNU Affero General Public |
| 30 |
# License with the Debian GNU/Linux or Univention distribution in file |
| 31 |
# /usr/share/common-licenses/AGPL-3; if not, see |
| 32 |
# <http://www.gnu.org/licenses/>. |
| 33 |
|
| 34 |
import unittest |
| 35 |
import collections |
| 36 |
|
| 37 |
|
| 38 |
class OrderedSet(collections.MutableSet): |
| 39 |
""" |
| 40 |
A `set()` that remembers insertion order. |
| 41 |
""" |
| 42 |
def __init__(self, iterable=None): |
| 43 |
raw = ((k, None) for k in iterable) if iterable else () |
| 44 |
self._data = collections.OrderedDict(raw) |
| 45 |
|
| 46 |
@property |
| 47 |
def _name(self): |
| 48 |
return self.__class__.__name__ |
| 49 |
|
| 50 |
def __repr__(self): |
| 51 |
return "{}({!r})".format(self._name, [x for x in self]) |
| 52 |
|
| 53 |
def __len__(self): |
| 54 |
return len(self._data) |
| 55 |
|
| 56 |
def __contains__(self, key): |
| 57 |
return key in self._data |
| 58 |
|
| 59 |
def __getitem__(self, index): |
| 60 |
try: |
| 61 |
return self._data.keys()[index] |
| 62 |
except IndexError: |
| 63 |
raise IndexError("{} index out of range".format(self._name)) |
| 64 |
|
| 65 |
def add(self, key): |
| 66 |
self._data[key] = None |
| 67 |
|
| 68 |
def update(self, sequence): |
| 69 |
self._data.update((k, None) for k in sequence) |
| 70 |
|
| 71 |
def clear(self): |
| 72 |
self._data.clear() |
| 73 |
|
| 74 |
def pop(self): |
| 75 |
if not self: |
| 76 |
raise KeyError("{} is empty".format(self._name)) |
| 77 |
first = next(iter(self)) |
| 78 |
self.discard(first) |
| 79 |
return first |
| 80 |
|
| 81 |
def discard(self, key): |
| 82 |
del self._data[key] |
| 83 |
|
| 84 |
def __iter__(self): |
| 85 |
return iter(self._data) |
| 86 |
|
| 87 |
def __eq__(self, other): |
| 88 |
if isinstance(other, OrderedSet): |
| 89 |
return self._data == other._data |
| 90 |
if isinstance(other, collections.Set): |
| 91 |
return set(self) == other |
| 92 |
return False |
| 93 |
|
| 94 |
def __reversed__(self): |
| 95 |
return OrderedSet(reversed(self._data)) |
| 96 |
|
| 97 |
def isdisjoint(self, other): |
| 98 |
return bool(self & other) |
| 99 |
|
| 100 |
def issubset(self, other): |
| 101 |
return self <= other |
| 102 |
|
| 103 |
def issuperset(self, other): |
| 104 |
return self >= other |
| 105 |
|
| 106 |
def difference(self, other): |
| 107 |
return self - other |
| 108 |
|
| 109 |
def intersection(self, other): |
| 110 |
return self & other |
| 111 |
|
| 112 |
def symmetric_difference(self, other): |
| 113 |
return self ^ other |
| 114 |
|
| 115 |
def union(self, other): |
| 116 |
return self | other |
| 117 |
|
| 118 |
|
| 119 |
class OrderedSetTest(unittest.TestCase): |
| 120 |
def test_empty_init(self): |
| 121 |
os = OrderedSet() |
| 122 |
self.assertEqual(len(os), 0) |
| 123 |
os = OrderedSet([]) |
| 124 |
self.assertEqual(len(os), 0) |
| 125 |
|
| 126 |
def test_simple_init(self): |
| 127 |
os = OrderedSet([1]) |
| 128 |
self.assertEqual(len(os), 1) |
| 129 |
|
| 130 |
def test_large_init(self): |
| 131 |
os = OrderedSet([1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]) |
| 132 |
self.assertEqual(len(os), 4) |
| 133 |
|
| 134 |
def test_contains(self): |
| 135 |
os = OrderedSet([1, 2, 3]) |
| 136 |
self.assertIn(1, os) |
| 137 |
self.assertNotIn(4, os) |
| 138 |
|
| 139 |
def test_getitem(self): |
| 140 |
os = OrderedSet([1, 2, 3]) |
| 141 |
self.assertEqual(os[0], 1) |
| 142 |
self.assertEqual(os[1], 2) |
| 143 |
self.assertEqual(os[2], 3) |
| 144 |
with self.assertRaises(IndexError): |
| 145 |
os[42] |
| 146 |
|
| 147 |
def test_add(self): |
| 148 |
os = OrderedSet([1, 2, 3]) |
| 149 |
self.assertEqual(len(os), 3) |
| 150 |
os.add(3) |
| 151 |
self.assertIn(3, os) |
| 152 |
self.assertEqual(len(os), 3) |
| 153 |
os.add(4) |
| 154 |
self.assertIn(4, os) |
| 155 |
self.assertEqual(len(os), 4) |
| 156 |
|
| 157 |
def test_update(self): |
| 158 |
os = OrderedSet([1, 2, 3]) |
| 159 |
self.assertEqual(len(os), 3) |
| 160 |
os.update([3, 4, 5, 6]) |
| 161 |
self.assertEqual(len(os), 6) |
| 162 |
for x in (1, 2, 3, 4, 5, 6): |
| 163 |
self.assertIn(x, os) |
| 164 |
|
| 165 |
def test_clear(self): |
| 166 |
os = OrderedSet([1, 2, 3]) |
| 167 |
os.clear() |
| 168 |
self.assertEqual(len(os), 0) |
| 169 |
for x in (1, 2, 3): |
| 170 |
self.assertNotIn(x, os) |
| 171 |
|
| 172 |
def test_pop(self): |
| 173 |
os = OrderedSet([1, 2, 3]) |
| 174 |
self.assertEqual(os.pop(), 1) |
| 175 |
self.assertNotIn(1, os) |
| 176 |
self.assertEqual(len(os), 2) |
| 177 |
self.assertEqual(os.pop(), 2) |
| 178 |
self.assertNotIn(2, os) |
| 179 |
self.assertEqual(len(os), 1) |
| 180 |
self.assertEqual(os.pop(), 3) |
| 181 |
self.assertNotIn(3, os) |
| 182 |
self.assertEqual(len(os), 0) |
| 183 |
with self.assertRaises(KeyError): |
| 184 |
os.pop() |
| 185 |
|
| 186 |
def test_discard(self): |
| 187 |
os = OrderedSet([1, 2, 3]) |
| 188 |
os.discard(2) |
| 189 |
self.assertNotIn(2, os) |
| 190 |
self.assertEqual(len(os), 2) |
| 191 |
for x in (1, 3): |
| 192 |
self.assertIn(x, os) |
| 193 |
|
| 194 |
def test_iter(self): |
| 195 |
os = OrderedSet([]) |
| 196 |
collected = [x for x in os] |
| 197 |
self.assertEqual(collected, []) |
| 198 |
os = OrderedSet([1, 2, 3]) |
| 199 |
collected = [x for x in os] |
| 200 |
self.assertEqual(collected, [1, 2, 3]) |
| 201 |
os = OrderedSet([3, 2, 1]) |
| 202 |
collected = [x for x in os] |
| 203 |
self.assertEqual(collected, [3, 2, 1]) |
| 204 |
|
| 205 |
def test_eq_empty(self): |
| 206 |
os_emtpy_a = OrderedSet() |
| 207 |
os_emtpy_b = OrderedSet([]) |
| 208 |
self.assertEqual(os_emtpy_a, os_emtpy_b) |
| 209 |
self.assertEqual(os_emtpy_a, set()) |
| 210 |
self.assertNotEqual(os_emtpy_a, []) |
| 211 |
self.assertNotEqual(os_emtpy_a, ()) |
| 212 |
|
| 213 |
def test_eq_single(self): |
| 214 |
os_one_a = OrderedSet([1]) |
| 215 |
os_one_b = OrderedSet([1]) |
| 216 |
os_one_c = OrderedSet([2]) |
| 217 |
self.assertEqual(os_one_a, os_one_b) |
| 218 |
self.assertNotEqual(os_one_a, os_one_c) |
| 219 |
self.assertEqual(os_one_a, set([1])) |
| 220 |
self.assertNotEqual(os_one_a, [1]) |
| 221 |
self.assertNotEqual(os_one_a, (1,)) |
| 222 |
|
| 223 |
def test_eq_multiple(self): |
| 224 |
os_one = OrderedSet([1]) |
| 225 |
os_multiple_a = OrderedSet([1, 2, 3]) |
| 226 |
os_multiple_b = OrderedSet([1, 2, 3, 3]) |
| 227 |
os_multiple_c = OrderedSet([3, 2, 1]) |
| 228 |
os_multiple_d = OrderedSet([4, 5, 6]) |
| 229 |
|
| 230 |
self.assertNotEqual(os_one, os_multiple_a) |
| 231 |
self.assertEqual(os_multiple_a, os_multiple_b) |
| 232 |
self.assertNotEqual(os_multiple_a, os_multiple_c) |
| 233 |
self.assertNotEqual(os_multiple_a, os_multiple_d) |
| 234 |
|
| 235 |
def test_reversed(self): |
| 236 |
self.assertEqual(reversed(OrderedSet([])), OrderedSet([])) |
| 237 |
self.assertEqual(reversed(OrderedSet([1])), OrderedSet([1])) |
| 238 |
self.assertEqual(reversed(OrderedSet([1, 2])), OrderedSet([2, 1])) |
| 239 |
self.assertEqual(reversed(OrderedSet([1, 2, 3])), OrderedSet([3, 2, 1])) |
| 240 |
self.assertEqual(reversed(OrderedSet([1, 2, 2, 3])), OrderedSet([3, 3, 2, 1])) |
| 241 |
|
| 242 |
# With the methods as tested above, several are available through |
| 243 |
# `collections.MutableSet`. The typical `set` operations are available |
| 244 |
# through `collections.Set`. |
| 245 |
|
| 246 |
def test_remove(self): |
| 247 |
os = OrderedSet([1, 2, 3]) |
| 248 |
os.remove(2) |
| 249 |
self.assertNotIn(2, os) |
| 250 |
self.assertEqual(len(os), 2) |
| 251 |
with self.assertRaises(KeyError): |
| 252 |
os.remove(2) |
| 253 |
|
| 254 |
def test_is_subset(self): |
| 255 |
os_a = OrderedSet([1, 2, 3]) |
| 256 |
os_b = OrderedSet([1, 2, 3, 3, 4, 5]) |
| 257 |
self.assertTrue(os_a <= os_b) |
| 258 |
self.assertFalse(os_b <= os_a) |
| 259 |
self.assertTrue(os_a.issubset(os_b)) |
| 260 |
self.assertFalse(os_b.issubset(os_a)) |
| 261 |
self.assertTrue(set([1]) <= OrderedSet([1, 2])) |
| 262 |
self.assertTrue(OrderedSet([1]) <= set([1, 2])) |
| 263 |
|
| 264 |
def test_is_superset(self): |
| 265 |
os_a = OrderedSet([1, 2, 3]) |
| 266 |
os_b = OrderedSet([1, 2, 3, 3, 4, 5]) |
| 267 |
self.assertTrue(os_b >= os_a) |
| 268 |
self.assertFalse(os_a >= os_b) |
| 269 |
self.assertTrue(os_b.issuperset(os_a)) |
| 270 |
self.assertFalse(os_a.issuperset(os_b)) |
| 271 |
self.assertTrue(set([1, 2]) >= OrderedSet([1])) |
| 272 |
self.assertTrue(OrderedSet([1, 2]) >= set([1])) |
| 273 |
|
| 274 |
def test_union(self): |
| 275 |
self.assertEqual(OrderedSet() | OrderedSet(), OrderedSet()) |
| 276 |
self.assertEqual(OrderedSet([1]) | OrderedSet([1]), OrderedSet([1])) |
| 277 |
self.assertEqual(OrderedSet([1]) | OrderedSet([2]), OrderedSet([1, 2])) |
| 278 |
self.assertEqual(OrderedSet([1, 2]) | OrderedSet([2, 3]), OrderedSet([1, 2, 3])) |
| 279 |
self.assertEqual(OrderedSet([1, 2]).union(OrderedSet([2, 3])), OrderedSet([1, 2, 3])) |
| 280 |
|
| 281 |
def test_union_set(self): |
| 282 |
self.assertEqual(set([1]) | OrderedSet([2]), set([1, 2])) |
| 283 |
self.assertEqual(OrderedSet([1]) | set([2]), OrderedSet([1, 2])) |
| 284 |
self.assertEqual(set([1]).union(OrderedSet([2])), set([1, 2])) |
| 285 |
self.assertEqual(OrderedSet([1]).union(set([2])), OrderedSet([1, 2])) |
| 286 |
|
| 287 |
def test_intersection(self): |
| 288 |
self.assertEqual(OrderedSet() & OrderedSet(), OrderedSet()) |
| 289 |
self.assertEqual(OrderedSet([1]) & OrderedSet([1]), OrderedSet([1])) |
| 290 |
self.assertEqual(OrderedSet([1]) & OrderedSet([2]), OrderedSet([])) |
| 291 |
self.assertEqual(OrderedSet([1, 2]) & OrderedSet([2, 3]), OrderedSet([2])) |
| 292 |
self.assertEqual(OrderedSet([1, 2]).intersection(OrderedSet([2, 3])), OrderedSet([2])) |
| 293 |
|
| 294 |
def test_intersection_set(self): |
| 295 |
self.assertEqual(set([1, 2, 3]) & OrderedSet([2, 3, 4]), set([2, 3])) |
| 296 |
self.assertEqual(OrderedSet([1, 2, 3]) & set([2, 3, 4]), OrderedSet([2, 3])) |
| 297 |
self.assertEqual(set([1, 2, 3]).intersection(OrderedSet([2, 3, 4])), set([2, 3])) |
| 298 |
self.assertEqual(OrderedSet([1, 2, 3]).intersection(set([2, 3, 4])), OrderedSet([2, 3])) |
| 299 |
|
| 300 |
def test_difference(self): |
| 301 |
self.assertEqual(OrderedSet() - OrderedSet(), OrderedSet()) |
| 302 |
self.assertEqual(OrderedSet([1]) - OrderedSet([1]), OrderedSet([])) |
| 303 |
self.assertEqual(OrderedSet([1]) - OrderedSet([2]), OrderedSet([1])) |
| 304 |
self.assertEqual(OrderedSet([1, 2]) - OrderedSet([2, 3]), OrderedSet([1])) |
| 305 |
self.assertEqual(OrderedSet([1, 2, 3]) - OrderedSet([4, 5]), OrderedSet([1, 2, 3])) |
| 306 |
self.assertEqual(OrderedSet([1, 2, 3]).difference(OrderedSet([4, 5])), OrderedSet([1, 2, 3])) |
| 307 |
|
| 308 |
def test_difference_set(self): |
| 309 |
self.assertEqual(set([1, 2, 3]) - OrderedSet([3, 4]), set([1, 2])) |
| 310 |
self.assertEqual(OrderedSet([1, 2, 3]) - set([3, 4]), OrderedSet([1, 2])) |
| 311 |
self.assertEqual(set([1, 2, 3]).difference(OrderedSet([3, 4])), set([1, 2])) |
| 312 |
self.assertEqual(OrderedSet([1, 2, 3]).difference(set([3, 4])), OrderedSet([1, 2])) |
| 313 |
|
| 314 |
def test_symmetric_difference(self): |
| 315 |
self.assertEqual(OrderedSet() ^ OrderedSet(), OrderedSet()) |
| 316 |
self.assertEqual(OrderedSet([1]) ^ OrderedSet([1]), OrderedSet([])) |
| 317 |
self.assertEqual(OrderedSet([1]) ^ OrderedSet([2]), OrderedSet([1, 2])) |
| 318 |
self.assertEqual(OrderedSet([1, 2]) ^ OrderedSet([2, 3]), OrderedSet([1, 3])) |
| 319 |
self.assertEqual(OrderedSet([1, 4, 3]) ^ OrderedSet([4, 5]), OrderedSet([1, 3, 5])) |
| 320 |
self.assertEqual(OrderedSet([1, 4, 3]).symmetric_difference(OrderedSet([4, 5])), OrderedSet([1, 3, 5])) |
| 321 |
|
| 322 |
def test_symmetric_difference_set(self): |
| 323 |
self.assertEqual(set([1, 2]) ^ OrderedSet([2, 3]), set([1, 3])) |
| 324 |
self.assertEqual(OrderedSet([1, 2]) ^ set([2, 3]), OrderedSet([1, 3])) |
| 325 |
self.assertEqual(set([1, 2]).symmetric_difference(OrderedSet([2, 3])), set([1, 3])) |
| 326 |
self.assertEqual(OrderedSet([1, 2]).symmetric_difference(set([2, 3])), OrderedSet([1, 3])) |
| 327 |
|
| 328 |
|
| 329 |
if __name__ == '__main__': |
| 330 |
unittest.main() |