Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2024-12-01 23:40:19

0001 # The MIT License (MIT)
0002 #
0003 # Copyright (c) 19 March 2009 Created by Raymond Hettinger (MIT)
0004 #
0005 # Permission is hereby granted, free of charge, to any person obtaining a copy 
0006 # of this software and associated documentation files (the "Software"), to deal
0007 # in the Software without restriction, including without limitation the rights
0008 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
0009 # copies of the Software, and to permit persons to whom the Software is
0010 # furnished to do so, subject to the following conditions:
0011 #
0012 # The above copyright notice and this permission notice shall be included in
0013 # all copies or substantial portions of the Software.
0014 #
0015 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0016 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0017 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
0018 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0019 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
0020 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
0021 # DEALINGS IN THE SOFTWARE.
0022 #
0023 # Copied from URL http://code.activestate.com/recipes/576694-orderedset/
0024 # on 15 November 2016
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]         # sentinel node for doubly linked list
0033         self.map = {}                   # key --> [key, prev, next]
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()