codekingpro/portable-devtools

1# OrderedSet2# Copyright (c) 2009 Raymond Hettinger3#4# Permission is hereby granted, free of charge, to any person5# obtaining a copy of this software and associated documentation files6# (the "Software"), to deal in the Software without restriction,7# including without limitation the rights to use, copy, modify, merge,8# publish, distribute, sublicense, and/or sell copies of the Software,9# and to permit persons to whom the Software is furnished to do so,10# subject to the following conditions:11#12#     The above copyright notice and this permission notice shall be13#     included in all copies or substantial portions of the Software.14#15#     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,16#     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES17#     OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND18#     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT19#     HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,20#     WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING21#     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR22#     OTHER DEALINGS IN THE SOFTWARE.23from collections.abc import MutableSet24 25 26class OrderedSet(MutableSet):27    def __init__(self, iterable=None):28        self.end = end = []29        end += [None, end, end]  # sentinel node for doubly linked list30        self.map = {}  # key --> [key, prev, next]31        if iterable is not None:32            self |= iterable33 34    def __len__(self):35        return len(self.map)36 37    def __contains__(self, key):38        return key in self.map39 40    def add(self, key):41        if key not in self.map:42            end = self.end43            curr = end[1]44            curr[2] = end[1] = self.map[key] = [key, curr, end]45 46    def discard(self, key):47        if key in self.map:48            key, prev, next = self.map.pop(key)  # noqa: A00149            prev[2] = next50            next[1] = prev51 52    def __iter__(self):53        end = self.end54        curr = end[2]55        while curr is not end:56            yield curr[0]57            curr = curr[2]58 59    def __reversed__(self):60        end = self.end61        curr = end[1]62        while curr is not end:63            yield curr[0]64            curr = curr[1]65 66    def pop(self, last=True):67        if not self:68            raise KeyError("set is empty")69        key = self.end[1][0] if last else self.end[2][0]70        self.discard(key)71        return key72 73    def __repr__(self):74        if not self:75            return f"{self.__class__.__name__}()"76        return f"{self.__class__.__name__}({list(self)!r})"77 78    def __eq__(self, other):79        if isinstance(other, OrderedSet):80            return len(self) == len(other) and list(self) == list(other)81        return set(self) == set(other)82 83 84if __name__ == "__main__":85    s = OrderedSet("abracadaba")86    t = OrderedSet("simsalabim")87    print(s | t)88    print(s & t)89    print(s - t)90