0
# Data Structures
1

2
Advanced dictionary, list, set, and queue implementations with specialized behaviors for common programming patterns. These data structures extend Python's built-in types with additional functionality while maintaining familiar APIs.
3

4
## Capabilities
5

6
### Advanced Dictionaries
7

8
Enhanced dictionary implementations that provide additional functionality beyond standard Python dictionaries.
9

10
```python { .api }
11
class OrderedMultiDict(dict):
12
    """Dictionary that retains insertion order and allows multiple values per key."""
13
    def add(self, key, value): ...
14
    def getlist(self, key): ...
15
    def poplist(self, key): ...
16
    def items(self, multi=False): ...
17

18
class FastIterOrderedMultiDict(OrderedMultiDict):
19
    """OMD optimized for iteration performance."""
20
    pass
21

22
class OneToOne(dict):
23
    """Bidirectional dictionary ensuring 1:1 key-value mapping."""
24
    def __init__(self, items=None): ...
25
    @property
26
    def inv(self): ...
27

28
class ManyToMany:
29
    """Many-to-many mapping data structure."""
30
    def add(self, left, right): ...
31
    def remove(self, left, right=None): ...
32
    def get_lefts(self, right): ...
33
    def get_rights(self, left): ...
34

35
class FrozenDict(dict):
36
    """Immutable dictionary that raises FrozenHashError on modification attempts."""
37
    def __setitem__(self, key, value): ...
38
    def __delitem__(self, key): ...
39
    def clear(self): ...
40
    def pop(self, key, *args): ...
41
    def popitem(self): ...
42
    def setdefault(self, key, default=None): ...
43
    def update(self, *args, **kwargs): ...
44
```
45

46
**Usage Examples:**
47

48
```python
49
from boltons.dictutils import OrderedMultiDict, OneToOne, FrozenDict
50

51
# OrderedMultiDict - multiple values per key
52
omd = OrderedMultiDict()
53
omd.add('color', 'red')
54
omd.add('color', 'blue')
55
omd.add('size', 'large')
56
print(omd.getlist('color'))  # ['red', 'blue']
57

58
# OneToOne - bidirectional mapping
59
mapping = OneToOne({'a': 1, 'b': 2})
60
print(mapping['a'])      # 1
61
print(mapping.inv[1])    # 'a'
62

63
# FrozenDict - immutable dictionary
64
frozen = FrozenDict({'key': 'value'})
65
# frozen['key'] = 'new_value'  # Raises FrozenHashError
66
```
67

68
### Enhanced Lists
69

70
List implementations with specialized behaviors for efficient operations.
71

72
```python { .api }
73
class BarrelList(list):
74
    """List that can be rolled/rotated efficiently."""
75
    def __init__(self, iterable=None): ...
76
    def rl(self, steps=1): ...  # Roll left
77
    def rr(self, steps=1): ...  # Roll right
78

79
class SplayList(list):
80
    """List with efficient insertion/deletion operations."""
81
    def __init__(self, iterable=None): ...
82
    def shift(self, index, steps): ...
83
    def swap(self, index_a, index_b): ...
84
```
85

86
**Usage Examples:**
87

88
```python
89
from boltons.listutils import BarrelList, SplayList
90

91
# BarrelList - efficient rotation
92
barrel = BarrelList([1, 2, 3, 4, 5])
93
barrel.rl(2)  # Roll left 2 positions
94
print(list(barrel))  # [3, 4, 5, 1, 2]
95

96
# SplayList - efficient insertions/deletions
97
splay = SplayList([1, 2, 3, 4, 5])
98
splay.shift(2, 1)  # Shift element at index 2 by 1 position
99
```
100

101
### Enhanced Sets
102

103
Set implementations with additional functionality.
104

105
```python { .api }
106
class IndexedSet(MutableSet):
107
    """Set that maintains insertion order and supports indexing."""
108
    def __init__(self, iterable=None): ...
109
    def __getitem__(self, index): ...
110
    def add(self, item): ...
111
    def discard(self, item): ...
112
    def pop(self, index=-1): ...
113
    def index(self, item): ...
114
```
115

116
**Usage Examples:**
117

118
```python
119
from boltons.setutils import IndexedSet
120

121
# IndexedSet - ordered set with indexing
122
indexed_set = IndexedSet(['a', 'b', 'c', 'a'])  # Duplicates ignored
123
print(indexed_set[0])    # 'a'
124
print(indexed_set[1])    # 'b'
125
print(list(indexed_set)) # ['a', 'b', 'c']
126
```
127

128
### Priority Queues
129

130
Priority queue implementations with different underlying data structures.
131

132
```python { .api }
133
class BasePriorityQueue:
134
    """Abstract base class for priority queues."""
135
    def put(self, priority, item): ...
136
    def get(self): ...
137
    def peek(self): ...
138
    def __len__(self): ...
139

140
class HeapPriorityQueue(BasePriorityQueue):
141
    """Heap-based priority queue implementation."""
142
    def __init__(self): ...
143

144
class SortedPriorityQueue(BasePriorityQueue):
145
    """Sorted list-based priority queue implementation."""
146
    def __init__(self): ...
147
```
148

149
**Usage Examples:**
150

151
```python
152
from boltons.queueutils import HeapPriorityQueue, SortedPriorityQueue
153

154
# HeapPriorityQueue - efficient for large datasets
155
heap_queue = HeapPriorityQueue()
156
heap_queue.put(3, 'low priority')
157
heap_queue.put(1, 'high priority')
158
heap_queue.put(2, 'medium priority')
159

160
print(heap_queue.get())  # 'high priority' (priority 1)
161
print(heap_queue.get())  # 'medium priority' (priority 2)
162

163
# SortedPriorityQueue - maintains sorted order
164
sorted_queue = SortedPriorityQueue()
165
sorted_queue.put(3, 'task_c')
166
sorted_queue.put(1, 'task_a')
167
print(sorted_queue.peek())  # 'task_a' (highest priority)
168
```
169

170
### Utility Functions
171

172
Dictionary manipulation utilities.
173

174
```python { .api }
175
def subdict(d, keep=None, drop=None):
176
    """
177
    Create dictionary subset by keeping/dropping keys.
178
    
179
    Parameters:
180
    - d (dict): Source dictionary
181
    - keep (iterable): Keys to keep (mutually exclusive with drop)
182
    - drop (iterable): Keys to drop (mutually exclusive with keep)
183
    
184
    Returns:
185
    dict: Dictionary subset
186
    """
187

188
def complement(wrapped):
189
    """
190
    Decorator to create complement operations for set-like objects.
191
    
192
    Parameters:
193
    - wrapped (callable): Function to create complement for
194
    
195
    Returns:
196
    callable: Complement function
197
    """
198
```
199

200
**Usage Examples:**
201

202
```python
203
from boltons.dictutils import subdict
204
from boltons.setutils import complement
205

206
# Create dictionary subsets
207
data = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
208
subset = subdict(data, keep=['a', 'c'])
209
print(subset)  # {'a': 1, 'c': 3}
210

211
dropped = subdict(data, drop=['b', 'd'])
212
print(dropped)  # {'a': 1, 'c': 3}
213
```
214

215
## Types
216

217
```python { .api }
218
# Exceptions
219
class FrozenHashError(TypeError):
220
    """Exception raised when attempting to modify FrozenDict."""
221
    pass
222

223
# Aliases for convenience
224
OMD = OrderedMultiDict
225
MultiDict = OrderedMultiDict
226
```