0
# Multiset
1

2
An implementation of a multiset data structure for Python that allows elements to occur multiple times. Provides both mutable (Multiset) and immutable (FrozenMultiset) variants with full support for set operations including union, intersection, difference, and symmetric difference.
3

4
## Package Information
5

6
- **Package Name**: multiset
7
- **Language**: Python  
8
- **Installation**: `pip install multiset`
9

10
## Core Imports
11

12
```python
13
from multiset import Multiset, FrozenMultiset, BaseMultiset
14
```
15

16
## Basic Usage
17

18
```python
19
from multiset import Multiset, FrozenMultiset
20

21
# Create a mutable multiset
22
ms1 = Multiset('aab')
23
ms2 = Multiset(['a', 'b', 'c'])
24

25
# Set operations
26
union_result = ms1 | ms2        # Union: ['a', 'a', 'b', 'c']
27
intersection = ms1 & ms2        # Intersection: ['a', 'b']  
28
difference = ms1 - ms2          # Difference: ['a']
29

30
# Check membership and get multiplicity  
31
'a' in ms1                      # True
32
ms1['a']                        # 2 (multiplicity of 'a')
33

34
# Modify multiset
35
ms1.add('c', multiplicity=2)    # Add 'c' twice
36
ms1.remove('a')                 # Remove one 'a'
37

38
# Create immutable multiset
39
frozen_ms = FrozenMultiset('abc')
40
hash(frozen_ms)                 # Hashable, can be used in sets/dicts
41
```
42

43
## Architecture
44

45
The multiset implementation is based on three main classes:
46

47
- **BaseMultiset**: Abstract base class providing core functionality including set operations, comparisons, and dictionary-like access
48
- **Multiset**: Mutable variant with additional mutating operations like add, remove, update
49
- **FrozenMultiset**: Immutable, hashable variant suitable for use in sets or as dictionary keys
50

51
All variants use efficient dictionary mapping internally where keys are elements and values are their multiplicities. Zero-count elements are automatically removed.
52

53
## Capabilities
54

55
### Set Operations
56

57
Mathematical set operations supporting both multiset and regular set operands. Operations include union (maximum multiplicities), intersection (minimum multiplicities), difference, symmetric difference, and combination (sum multiplicities).
58

59
```python { .api }
60
def union(self, *others) -> BaseMultiset: ...
61
def intersection(self, *others) -> BaseMultiset: ...  
62
def difference(self, *others) -> BaseMultiset: ...
63
def symmetric_difference(self, other) -> BaseMultiset: ...
64
def combine(self, *others) -> BaseMultiset: ...
65
def times(self, factor: int) -> BaseMultiset: ...
66
def isdisjoint(self, other) -> bool: ...
67
def issubset(self, other) -> bool: ...
68
def issuperset(self, other) -> bool: ...
69
```
70

71
[Set Operations](./set-operations.md)
72

73
### Element Management
74

75
Core functionality for accessing, checking, and manipulating individual elements including membership testing, multiplicity access, and element counting with dictionary-like interface.
76

77
```python { .api }
78
def __contains__(self, element) -> bool: ...
79
def __getitem__(self, element) -> int: ...
80
def get(self, element, default: int) -> int: ...
81
def distinct_elements(self) -> KeysView: ...
82
def multiplicities(self) -> ValuesView: ...
83
def values(self) -> ValuesView: ...
84
def copy(self) -> BaseMultiset: ...
85
@classmethod
86
def from_elements(cls, elements, multiplicity: int) -> BaseMultiset: ...
87
```
88

89
[Element Management](./element-management.md)
90

91
### Mutable Operations
92

93
Mutating operations available only on Multiset instances for modifying multiset contents including adding/removing elements, updating from other collections, and in-place set operations.
94

95
```python { .api }
96
def add(self, element, multiplicity: int = 1) -> None: ...
97
def remove(self, element, multiplicity: Optional[int] = None) -> int: ...
98
def discard(self, element, multiplicity: Optional[int] = None) -> int: ...
99
def update(self, *others, **kwargs) -> None: ...
100
def clear(self) -> None: ...
101
def pop(self, element, default: int) -> int: ...
102
def setdefault(self, element, default: int) -> int: ...
103
```
104

105
[Mutable Operations](./mutable-operations.md)
106

107
## Types
108

109
```python { .api }
110
class BaseMultiset(MappingType[_TElement, int], Generic[_TElement]):
111
    """Abstract base multiset implementation."""
112
    def __init__(self, iterable: Optional[Union[Iterable[_TElement], Mapping[_TElement, int]]] = None): ...
113
    def __len__(self) -> int: ...
114
    def __bool__(self) -> bool: ...
115
    def __iter__(self) -> Iterator[_TElement]: ...
116
    def copy(self) -> BaseMultiset: ...
117

118
class Multiset(BaseMultiset[_TElement], MutableMappingType[_TElement, int]):
119
    """Mutable multiset implementation."""
120
    def __setitem__(self, element: _TElement, multiplicity: int) -> None: ...
121
    def __delitem__(self, element: _TElement) -> None: ...
122

123
class FrozenMultiset(BaseMultiset[_TElement]):
124
    """Immutable, hashable multiset implementation."""  
125
    def __hash__(self) -> int: ...
126

127
# Type aliases
128
_TElement = TypeVar('_TElement', bound=Hashable)
129
_OtherType = Union[Iterable[_TElement], Mapping[_TElement, int]]
130
```