Skip to content

omnipy.util.setdeque

Ordered unique queue utilities.

This module provides SetDeque, a deque-backed data structure that preserves insertion order like collections.deque while enforcing set-like uniqueness. It is useful for work queues, caches, and registration lists where membership checks must be fast and duplicates should be ignored instead of accumulated.

CLASS DESCRIPTION
SetDeque

Deque variant that keeps each element at most once.

SetDeque

Bases: deque, Generic[_ObjT]


              flowchart BT
              omnipy.util.setdeque.SetDeque[SetDeque]

              

              click omnipy.util.setdeque.SetDeque href "" "omnipy.util.setdeque.SetDeque"

Deque variant that keeps each element at most once.

SetDeque combines the ordered, append/pop-friendly behavior of collections.deque with an internal set for O(1) membership tests. Duplicate insertions are ignored, existing order is preserved, and explicit removals keep the deque and set views synchronized.

PARAMETER DESCRIPTION
iterable

Initial values. Later duplicates are discarded while keeping the first occurrence.

TYPE: Iterable DEFAULT: ()

maxlen

Optional deque length limit passed through to deque.

TYPE: int | None DEFAULT: None

Notes

When maxlen causes deque to evict elements during appends, this implementation does not proactively remove evicted values from the backing set. Use this type primarily without maxlen unless that edge case is acceptable for the calling code.

Returned by: Used by:
METHOD DESCRIPTION
__init__
append

Append a new element to the right side.
appendleft

Append a new element to the left side.
clear

Remove all elements and reset membership bookkeeping.
count

Return whether an element is present.
extend

Append unique elements from an iterable to the right side.
extendleft

Append unique elements from an iterable to the left side.
insert

Insert a new element at a position.
pop

Remove and return the rightmost element.
popleft

Remove and return the leftmost element.
remove

Remove an element from the deque and membership set.
Source code in src/omnipy/util/setdeque.py 
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
class SetDeque(deque, Generic[_ObjT]):
    """Deque variant that keeps each element at most once.

    ``SetDeque`` combines the ordered, append/pop-friendly behavior of
    ``collections.deque`` with an internal set for ``O(1)`` membership tests.
    Duplicate insertions are ignored, existing order is preserved, and explicit
    removals keep the deque and set views synchronized.

    Args:
        iterable: Initial values. Later duplicates are discarded while keeping the
            first occurrence.
        maxlen: Optional deque length limit passed through to ``deque``.

    Notes:
        When ``maxlen`` causes ``deque`` to evict elements during appends, this
        implementation does not proactively remove evicted values from the backing
        set. Use this type primarily without ``maxlen`` unless that edge case is
        acceptable for the calling code.
    """
    def __init__(self, iterable: Iterable = (), maxlen: int | None = None):
        unique_ordered_els = dict.fromkeys(iterable).keys()
        super().__init__(iterable=unique_ordered_els, maxlen=maxlen)
        self._set: set[_ObjT] = set(self.__iter__())

    def _add_element(self, method_name: str, *args: object, el: _ObjT) -> bool:
        if el not in self._set:
            getattr(super(), method_name)(*args, el)
            self._set.add(el)
            return True
        return False

    def _add_elements(self, method_name: str, el_iter: Iterable[_ObjT]) -> None:
        unique_ordered_els = dict.fromkeys(el_iter).keys()
        new_unique_ordered_els = (el for el in unique_ordered_els if el not in self._set)
        getattr(super(), method_name)(new_unique_ordered_els)
        self._set |= unique_ordered_els

    def _remove_returned_element(self, method_name: str) -> _ObjT:
        el = getattr(super(), method_name)()
        self._set.remove(el)
        return el

    def _remove_explicit_element(self,
                                 method_name: str,
                                 *args: object,
                                 el: _ObjT,
                                 add_el_to_args: bool) -> None:
        if add_el_to_args:
            args = args + (el,)
        getattr(super(), method_name)(*args)
        self._set.remove(el)

    def append(self, el: _ObjT) -> None:
        """Append a new element to the right side.

        Args:
            el: Element to append when it is not already present.
        """
        self._add_element('append', el=el)

    def appendleft(self, el: _ObjT) -> None:
        """Append a new element to the left side.

        Args:
            el: Element to append when it is not already present.
        """
        self._add_element('appendleft', el=el)

    def extend(self, el_iter: Iterable[_ObjT]) -> None:
        """Append unique elements from an iterable to the right side.

        Args:
            el_iter: Source iterable. Duplicate values are ignored.
        """
        self._add_elements('extend', el_iter)

    def extendleft(self, el_iter: Iterable[_ObjT]) -> None:
        """Append unique elements from an iterable to the left side.

        Args:
            el_iter: Source iterable. Duplicate values are ignored.
        """
        self._add_elements('extendleft', el_iter)

    def insert(self, __i: int, __x: _ObjT) -> None:
        """Insert a new element at a position.

        Args:
            __i: Index at which to insert.
            __x: Element to insert when it is not already present.
        """
        self._add_element('insert', __i, el=__x)

    def pop(self) -> _ObjT:  # type: ignore[override]
        """Remove and return the rightmost element.

        Returns:
            The removed element.

        Raises:
            IndexError: If the deque is empty.
        """
        return self._remove_returned_element('pop')

    def popleft(self) -> _ObjT:
        """Remove and return the leftmost element.

        Returns:
            The removed element.

        Raises:
            IndexError: If the deque is empty.
        """
        return self._remove_returned_element('popleft')

    def remove(self, __value) -> None:
        """Remove an element from the deque and membership set.

        Args:
            __value: Element to remove.

        Raises:
            ValueError: If the element is not present.
        """
        self._remove_explicit_element('remove', el=__value, add_el_to_args=True)

    def clear(self) -> None:
        """Remove all elements and reset membership bookkeeping.

        This keeps deque contents and the internal uniqueness set synchronized.
        """
        super().clear()
        self._set.clear()

    def count(self, __x: _ObjT) -> int:
        """Return whether an element is present.

        Args:
            __x: Element to check for membership.

        Returns:
            ``1`` if the element is present, otherwise ``0``.
        """
        return 1 if __x in self._set else 0

    def __setitem__(self, __key: SupportsIndex, __value: _ObjT) -> None:  # type: ignore[override]
        old_val = super().__getitem__(__key)
        if __value != old_val:
            added = self._add_element('__setitem__', __key, el=__value)
            if added:
                self._set.remove(old_val)

    def __delitem__(self, __key: SupportsIndex) -> None:  # type: ignore[override]
        self._remove_explicit_element(
            '__delitem__',
            __key,
            el=super().__getitem__(__key),
            add_el_to_args=False,
        )

    def __add__(self, __value: 'SetDeque[_ObjT]') -> 'SetDeque[_ObjT] | NotImplementedType':
        if not isinstance(__value, SetDeque):
            return NotImplemented
        self_copy = copy(self)
        self_copy.extend(__value)
        return self_copy

    def __iadd__(self, __value: Iterable[_ObjT]):  # type: ignore[misc]
        self.extend(__value)
        return self

    def __eq__(self, __value: object):
        return super().__eq__(__value) and self._set == cast(SetDeque[_ObjT], __value)._set

    def __reduce__(self):
        ret = super().__reduce__()
        return ret[0], ret[1], None, ret[3]

    def __contains__(self, __key: object) -> bool:
        return self._set.__contains__(__key)

    def _common_mul(self, __value: int):
        if __value > 0:
            return SetDeque[_ObjT](self.__iter__())
        else:
            return SetDeque[_ObjT]()

    def __mul__(self, __value: int):
        return self._common_mul(__value)

    def __rmul__(self, __value: int):
        return self._common_mul(__value)

    def __imul__(self, __value: int):
        if __value <= 0:
            self.clear()
        return self

    def __repr__(self):
        arg_repr = ''
        if hasattr(self, '__orig_class__'):
            args = get_args(self.__orig_class__)  # pyright: ignore [reportAttributeAccessIssue]
            if len(args) == 1:
                arg = args[0]
                arg_repr = f'[{arg.__name__ if inspect.isclass(arg) else repr(arg)}]'
        maxlen_repr = f', maxlen={self.maxlen}' if self.maxlen is not None else ''
        return f'{self.__class__.__name__}{arg_repr}({list(self)}{maxlen_repr})'

    def __sizeof__(self):
        return super().__sizeof__() + sys.getsizeof(self._set)

__init__ 

__init__(iterable: Iterable = (), maxlen: int | None = None)
Source code in src/omnipy/util/setdeque.py 
38
39
40
41
def __init__(self, iterable: Iterable = (), maxlen: int | None = None):
    unique_ordered_els = dict.fromkeys(iterable).keys()
    super().__init__(iterable=unique_ordered_els, maxlen=maxlen)
    self._set: set[_ObjT] = set(self.__iter__())

append 

append(el: _ObjT) -> None

Append a new element to the right side.

PARAMETER DESCRIPTION
el

Element to append when it is not already present.

TYPE: _ObjT

Source code in src/omnipy/util/setdeque.py 
71
72
73
74
75
76
77
def append(self, el: _ObjT) -> None:
    """Append a new element to the right side.

    Args:
        el: Element to append when it is not already present.
    """
    self._add_element('append', el=el)

appendleft 

appendleft(el: _ObjT) -> None

Append a new element to the left side.

PARAMETER DESCRIPTION
el

Element to append when it is not already present.

TYPE: _ObjT

Source code in src/omnipy/util/setdeque.py 
79
80
81
82
83
84
85
def appendleft(self, el: _ObjT) -> None:
    """Append a new element to the left side.

    Args:
        el: Element to append when it is not already present.
    """
    self._add_element('appendleft', el=el)

clear 

clear() -> None

Remove all elements and reset membership bookkeeping.

This keeps deque contents and the internal uniqueness set synchronized.

Source code in src/omnipy/util/setdeque.py 
145
146
147
148
149
150
151
def clear(self) -> None:
    """Remove all elements and reset membership bookkeeping.

    This keeps deque contents and the internal uniqueness set synchronized.
    """
    super().clear()
    self._set.clear()

count 

count(__x: _ObjT) -> int

Return whether an element is present.

PARAMETER DESCRIPTION
__x

Element to check for membership.

TYPE: _ObjT

RETURNS DESCRIPTION
int

1 if the element is present, otherwise 0.
Source code in src/omnipy/util/setdeque.py 
153
154
155
156
157
158
159
160
161
162
def count(self, __x: _ObjT) -> int:
    """Return whether an element is present.

    Args:
        __x: Element to check for membership.

    Returns:
        ``1`` if the element is present, otherwise ``0``.
    """
    return 1 if __x in self._set else 0

extend 

extend(el_iter: Iterable[_ObjT]) -> None

Append unique elements from an iterable to the right side.

PARAMETER DESCRIPTION
el_iter

Source iterable. Duplicate values are ignored.

TYPE: Iterable[_ObjT]

Source code in src/omnipy/util/setdeque.py 
87
88
89
90
91
92
93
def extend(self, el_iter: Iterable[_ObjT]) -> None:
    """Append unique elements from an iterable to the right side.

    Args:
        el_iter: Source iterable. Duplicate values are ignored.
    """
    self._add_elements('extend', el_iter)

extendleft 

extendleft(el_iter: Iterable[_ObjT]) -> None

Append unique elements from an iterable to the left side.

PARAMETER DESCRIPTION
el_iter

Source iterable. Duplicate values are ignored.

TYPE: Iterable[_ObjT]

Source code in src/omnipy/util/setdeque.py 
 95
 96
 97
 98
 99
100
101
def extendleft(self, el_iter: Iterable[_ObjT]) -> None:
    """Append unique elements from an iterable to the left side.

    Args:
        el_iter: Source iterable. Duplicate values are ignored.
    """
    self._add_elements('extendleft', el_iter)

insert 

insert(__i: int, __x: _ObjT) -> None

Insert a new element at a position.

PARAMETER DESCRIPTION
__i

Index at which to insert.

TYPE: int

__x

Element to insert when it is not already present.

TYPE: _ObjT

Source code in src/omnipy/util/setdeque.py 
103
104
105
106
107
108
109
110
def insert(self, __i: int, __x: _ObjT) -> None:
    """Insert a new element at a position.

    Args:
        __i: Index at which to insert.
        __x: Element to insert when it is not already present.
    """
    self._add_element('insert', __i, el=__x)

pop 

pop() -> _ObjT

Remove and return the rightmost element.

RETURNS DESCRIPTION
_ObjT

The removed element.
RAISES DESCRIPTION
IndexError

If the deque is empty.
Source code in src/omnipy/util/setdeque.py 
112
113
114
115
116
117
118
119
120
121
def pop(self) -> _ObjT:  # type: ignore[override]
    """Remove and return the rightmost element.

    Returns:
        The removed element.

    Raises:
        IndexError: If the deque is empty.
    """
    return self._remove_returned_element('pop')

popleft 

popleft() -> _ObjT

Remove and return the leftmost element.

RETURNS DESCRIPTION
_ObjT

The removed element.
RAISES DESCRIPTION
IndexError

If the deque is empty.
Source code in src/omnipy/util/setdeque.py 
123
124
125
126
127
128
129
130
131
132
def popleft(self) -> _ObjT:
    """Remove and return the leftmost element.

    Returns:
        The removed element.

    Raises:
        IndexError: If the deque is empty.
    """
    return self._remove_returned_element('popleft')

remove 

remove(__value) -> None

Remove an element from the deque and membership set.

PARAMETER DESCRIPTION
__value

Element to remove.
RAISES DESCRIPTION
ValueError

If the element is not present.
Source code in src/omnipy/util/setdeque.py 
134
135
136
137
138
139
140
141
142
143
def remove(self, __value) -> None:
    """Remove an element from the deque and membership set.

    Args:
        __value: Element to remove.

    Raises:
        ValueError: If the element is not present.
    """
    self._remove_explicit_element('remove', el=__value, add_el_to_args=True)