ParameterSet/python/OrderedSet.py

0001 from __future__ import print_function
0002 # The MIT License (MIT)
0003 #
0004 # Copyright (c) 19 March 2009 Created by Raymond Hettinger (MIT)
0005 #
0006 # Permission is hereby granted, free of charge, to any person obtaining a copy
0007 # of this software and associated documentation files (the "Software"), to deal
0008 # in the Software without restriction, including without limitation the rights
0009 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
0010 # copies of the Software, and to permit persons to whom the Software is
0011 # furnished to do so, subject to the following conditions:
0012 #
0013 # The above copyright notice and this permission notice shall be included in
0014 # all copies or substantial portions of the Software.
0015 #
0016 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0017 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0018 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
0019 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0020 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
0021 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
0022 # DEALINGS IN THE SOFTWARE.
0023 #
0024 # Copied from URL http://code.activestate.com/recipes/576694-orderedset/
0025 # on 15 November 2016
0026
0027 import collections.abc
0028
0029 class OrderedSet(collections.abc.MutableSet):
0030
0031     def __init__(self, iterable=None):
0032         self.end = end = []
0033         end += [None, end, end]         # sentinel node for doubly linked list
0034         self.map = {}                   # key --> [key, prev, next]
0035         if iterable is not None:
0036             self |= iterable
0037
0038     def __len__(self):
0039         return len(self.map)
0040
0041     def __contains__(self, key):
0042         return key in self.map
0043
0044     def add(self, key):
0045         if key not in self.map:
0046             end = self.end
0047             curr = end[1]
0048             curr[2] = end[1] = self.map[key] = [key, curr, end]
0049
0050     def discard(self, key):
0051         if key in self.map:
0052             key, prev, next = self.map.pop(key)
0053             prev[2] = next
0054             next[1] = prev
0055
0056     def __iter__(self):
0057         end = self.end
0058         curr = end[2]
0059         while curr is not end:
0060             yield curr[0]
0061             curr = curr[2]
0062
0063     def __reversed__(self):
0064         end = self.end
0065         curr = end[1]
0066         while curr is not end:
0067             yield curr[0]
0068             curr = curr[1]
0069
0070     def pop(self, last=True):
0071         if not self:
0072             raise KeyError('set is empty')
0073         key = self.end[1][0] if last else self.end[2][0]
0074         self.discard(key)
0075         return key
0076
0077     def __repr__(self):
0078         if not self:
0079             return '%s()' % (self.__class__.__name__,)
0080         return '%s(%r)' % (self.__class__.__name__, list(self))
0081
0082     def __eq__(self, other):
0083         if isinstance(other, OrderedSet):
0084             return len(self) == len(other) and list(self) == list(other)
0085         return set(self) == set(other)
0086
0087
0088 if __name__ == '__main__':
0089     import unittest
0090     class TestModuleCommand(unittest.TestCase):
0091         def setUp(self):
0092             """Nothing to do """
0093             pass
0094         def testSetOperations(self):
0095             s = OrderedSet('abracadaba')
0096             t = OrderedSet('simsalabim')
0097             self.assertEqual(str((s | t)), "OrderedSet(['a', 'b', 'r', 'c', 'd', 's', 'i', 'm', 'l'])")
0098             self.assertEqual(str((s & t)), "OrderedSet(['a', 'b'])")
0099             self.assertEqual(str(s - t),"OrderedSet(['r', 'c', 'd'])")
0100     unittest.main()