File indexing completed on 2024-12-01 23:40:19
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018
0019
0020
0021
0022
0023
0024
0025
0026 import collections.abc
0027
0028 class OrderedSet(collections.abc.MutableSet):
0029
0030 def __init__(self, iterable=None):
0031 self.end = end = []
0032 end += [None, end, end]
0033 self.map = {}
0034 if iterable is not None:
0035 self |= iterable
0036
0037 def __len__(self):
0038 return len(self.map)
0039
0040 def __contains__(self, key):
0041 return key in self.map
0042
0043 def add(self, key):
0044 if key not in self.map:
0045 end = self.end
0046 curr = end[1]
0047 curr[2] = end[1] = self.map[key] = [key, curr, end]
0048
0049 def discard(self, key):
0050 if key in self.map:
0051 key, prev, next = self.map.pop(key)
0052 prev[2] = next
0053 next[1] = prev
0054
0055 def __iter__(self):
0056 end = self.end
0057 curr = end[2]
0058 while curr is not end:
0059 yield curr[0]
0060 curr = curr[2]
0061
0062 def __reversed__(self):
0063 end = self.end
0064 curr = end[1]
0065 while curr is not end:
0066 yield curr[0]
0067 curr = curr[1]
0068
0069 def pop(self, last=True):
0070 if not self:
0071 raise KeyError('set is empty')
0072 key = self.end[1][0] if last else self.end[2][0]
0073 self.discard(key)
0074 return key
0075
0076 def __repr__(self):
0077 if not self:
0078 return '%s()' % (self.__class__.__name__,)
0079 return '%s(%r)' % (self.__class__.__name__, list(self))
0080
0081 def __eq__(self, other):
0082 if isinstance(other, OrderedSet):
0083 return len(self) == len(other) and list(self) == list(other)
0084 return set(self) == set(other)
0085
0086
0087 if __name__ == '__main__':
0088 import unittest
0089 class TestModuleCommand(unittest.TestCase):
0090 def setUp(self):
0091 """Nothing to do """
0092 pass
0093 def testSetOperations(self):
0094 s = OrderedSet('abracadaba')
0095 t = OrderedSet('simsalabim')
0096 self.assertEqual(str((s | t)), "OrderedSet(['a', 'b', 'r', 'c', 'd', 's', 'i', 'm', 'l'])")
0097 self.assertEqual(str((s & t)), "OrderedSet(['a', 'b'])")
0098 self.assertEqual(str(s - t),"OrderedSet(['r', 'c', 'd'])")
0099 unittest.main()