1"""
2
3Available at repository https://github.com/LuminosoInsight/ordered-set
4
5    salt.utils.oset
6    ~~~~~~~~~~~~~~~~
7
8An OrderedSet is a custom MutableSet that remembers its order, so that every
9entry has an index that can be looked up.
10
11Based on a recipe originally posted to ActiveState Recipes by Raymond Hettiger,
12and released under the MIT license.
13
14Rob Speer's changes are as follows:
15
16    - changed the content from a doubly-linked list to a regular Python list.
17      Seriously, who wants O(1) deletes but O(N) lookups by index?
18    - add() returns the index of the added item
19    - index() just returns the index of an item
20    - added a __getstate__ and __setstate__ so it can be pickled
21    - added __getitem__
22"""
23
24from collections.abc import MutableSet
25
26SLICE_ALL = slice(None)
27__version__ = "2.0.1"
28
29
30def is_iterable(obj):
31    """
32    Are we being asked to look up a list of things, instead of a single thing?
33    We check for the `__iter__` attribute so that this can cover types that
34    don't have to be known by this module, such as NumPy arrays.
35
36    Strings, however, should be considered as atomic values to look up, not
37    iterables. The same goes for tuples, since they are immutable and therefore
38    valid entries.
39
40    We don't need to check for the Python 2 `unicode` type, because it doesn't
41    have an `__iter__` attribute anyway.
42    """
43    return (
44        hasattr(obj, "__iter__")
45        and not isinstance(obj, str)
46        and not isinstance(obj, tuple)
47    )
48
49
50class OrderedSet(MutableSet):
51    """
52    An OrderedSet is a custom MutableSet that remembers its order, so that
53    every entry has an index that can be looked up.
54    """
55
56    def __init__(self, iterable=None):
57        self.items = []
58        self.map = {}
59        if iterable is not None:
60            self |= iterable
61
62    def __len__(self):
63        return len(self.items)
64
65    def __getitem__(self, index):
66        """
67        Get the item at a given index.
68
69        If `index` is a slice, you will get back that slice of items. If it's
70        the slice [:], exactly the same object is returned. (If you want an
71        independent copy of an OrderedSet, use `OrderedSet.copy()`.)
72
73        If `index` is an iterable, you'll get the OrderedSet of items
74        corresponding to those indices. This is similar to NumPy's
75        "fancy indexing".
76        """
77        if index == SLICE_ALL:
78            return self
79        elif hasattr(index, "__index__") or isinstance(index, slice):
80            result = self.items[index]
81            if isinstance(result, list):
82                return OrderedSet(result)
83            else:
84                return result
85        elif is_iterable(index):
86            return OrderedSet([self.items[i] for i in index])
87        else:
88            raise TypeError(
89                "Don't know how to index an OrderedSet by {}".format(repr(index))
90            )
91
92    def copy(self):
93        return OrderedSet(self)
94
95    def __getstate__(self):
96        if not self.items:
97            # The state can't be an empty list.
98            # We need to return a truthy value, or else __setstate__ won't be run.
99            #
100            # This could have been done more gracefully by always putting the state
101            # in a tuple, but this way is backwards- and forwards- compatible with
102            # previous versions of OrderedSet.
103            return (None,)
104        else:
105            return list(self)
106
107    def __setstate__(self, state):
108        if state == (None,):
109            self.__init__([])
110        else:
111            self.__init__(state)
112
113    def __contains__(self, key):
114        return key in self.map
115
116    def add(self, key):  # pylint: disable=arguments-differ
117        """
118        Add `key` as an item to this OrderedSet, then return its index.
119
120        If `key` is already in the OrderedSet, return the index it already
121        had.
122        """
123        if key not in self.map:
124            self.map[key] = len(self.items)
125            self.items.append(key)
126        return self.map[key]
127
128    append = add
129
130    def update(self, sequence):
131        """
132        Update the set with the given iterable sequence, then return the index
133        of the last element inserted.
134        """
135        item_index = None
136        try:
137            for item in sequence:
138                item_index = self.add(item)
139        except TypeError:
140            raise ValueError(
141                "Argument needs to be an iterable, got {}".format(type(sequence))
142            )
143        return item_index
144
145    def index(self, key):
146        """
147        Get the index of a given entry, raising an IndexError if it's not
148        present.
149
150        `key` can be an iterable of entries that is not a string, in which case
151        this returns a list of indices.
152        """
153        if is_iterable(key):
154            return [self.index(subkey) for subkey in key]
155        return self.map[key]
156
157    def pop(self):
158        """
159        Remove and return the last element from the set.
160
161        Raises KeyError if the set is empty.
162        """
163        if not self.items:
164            raise KeyError("Set is empty")
165
166        elem = self.items[-1]
167        del self.items[-1]
168        del self.map[elem]
169        return elem
170
171    def discard(self, key):  # pylint: disable=arguments-differ
172        """
173        Remove an element.  Do not raise an exception if absent.
174
175        The MutableSet mixin uses this to implement the .remove() method, which
176        *does* raise an error when asked to remove a non-existent item.
177        """
178        if key in self:
179            i = self.map[key]
180            del self.items[i]
181            del self.map[key]
182            for k, v in self.map.items():
183                if v >= i:
184                    self.map[k] = v - 1
185
186    def clear(self):
187        """
188        Remove all items from this OrderedSet.
189        """
190        del self.items[:]
191        self.map.clear()
192
193    def __iter__(self):
194        return iter(self.items)
195
196    def __reversed__(self):
197        return reversed(self.items)
198
199    def __repr__(self):
200        if not self:
201            return "{}()".format(self.__class__.__name__)
202        return "{}({})".format(self.__class__.__name__, repr(list(self)))
203
204    def __eq__(self, other):
205        if isinstance(other, OrderedSet):
206            return len(self) == len(other) and self.items == other.items
207        try:
208            other_as_set = set(other)
209        except TypeError:
210            # If `other` can't be converted into a set, it's not equal.
211            return False
212        else:
213            return set(self) == other_as_set
214