Data Structures

class OrderedMultiDict(dict):
    """Dictionary that retains insertion order and allows multiple values per key."""
    def add(self, key, value): ...
    def getlist(self, key): ...
    def poplist(self, key): ...
    def items(self, multi=False): ...

class FastIterOrderedMultiDict(OrderedMultiDict):
    """OMD optimized for iteration performance."""
    pass

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

class ManyToMany:
    """Many-to-many mapping data structure."""
    def add(self, left, right): ...
    def remove(self, left, right=None): ...
    def get_lefts(self, right): ...
    def get_rights(self, left): ...

class FrozenDict(dict):
    """Immutable dictionary that raises FrozenHashError on modification attempts."""
    def __setitem__(self, key, value): ...
    def __delitem__(self, key): ...
    def clear(self): ...
    def pop(self, key, *args): ...
    def popitem(self): ...
    def setdefault(self, key, default=None): ...
    def update(self, *args, **kwargs): ...

from boltons.dictutils import OrderedMultiDict, OneToOne, FrozenDict

# OrderedMultiDict - multiple values per key
omd = OrderedMultiDict()
omd.add('color', 'red')
omd.add('color', 'blue')
omd.add('size', 'large')
print(omd.getlist('color'))  # ['red', 'blue']

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

# FrozenDict - immutable dictionary
frozen = FrozenDict({'key': 'value'})
# frozen['key'] = 'new_value'  # Raises FrozenHashError

class BarrelList(list):
    """List that can be rolled/rotated efficiently."""
    def __init__(self, iterable=None): ...
    def rl(self, steps=1): ...  # Roll left
    def rr(self, steps=1): ...  # Roll right

class SplayList(list):
    """List with efficient insertion/deletion operations."""
    def __init__(self, iterable=None): ...
    def shift(self, index, steps): ...
    def swap(self, index_a, index_b): ...

from boltons.listutils import BarrelList, SplayList

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

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

class IndexedSet(MutableSet):
    """Set that maintains insertion order and supports indexing."""
    def __init__(self, iterable=None): ...
    def __getitem__(self, index): ...
    def add(self, item): ...
    def discard(self, item): ...
    def pop(self, index=-1): ...
    def index(self, item): ...

from boltons.setutils import IndexedSet

# IndexedSet - ordered set with indexing
indexed_set = IndexedSet(['a', 'b', 'c', 'a'])  # Duplicates ignored
print(indexed_set[0])    # 'a'
print(indexed_set[1])    # 'b'
print(list(indexed_set)) # ['a', 'b', 'c']

class BasePriorityQueue:
    """Abstract base class for priority queues."""
    def put(self, priority, item): ...
    def get(self): ...
    def peek(self): ...
    def __len__(self): ...

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

class SortedPriorityQueue(BasePriorityQueue):
    """Sorted list-based priority queue implementation."""
    def __init__(self): ...

from boltons.queueutils import HeapPriorityQueue, SortedPriorityQueue

# HeapPriorityQueue - efficient for large datasets
heap_queue = HeapPriorityQueue()
heap_queue.put(3, 'low priority')
heap_queue.put(1, 'high priority')
heap_queue.put(2, 'medium priority')

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

# SortedPriorityQueue - maintains sorted order
sorted_queue = SortedPriorityQueue()
sorted_queue.put(3, 'task_c')
sorted_queue.put(1, 'task_a')
print(sorted_queue.peek())  # 'task_a' (highest priority)

def subdict(d, keep=None, drop=None):
    """
    Create dictionary subset by keeping/dropping keys.
    
    Parameters:
    - d (dict): Source dictionary
    - keep (iterable): Keys to keep (mutually exclusive with drop)
    - drop (iterable): Keys to drop (mutually exclusive with keep)
    
    Returns:
    dict: Dictionary subset
    """

def complement(wrapped):
    """
    Decorator to create complement operations for set-like objects.
    
    Parameters:
    - wrapped (callable): Function to create complement for
    
    Returns:
    callable: Complement function
    """

from boltons.dictutils import subdict
from boltons.setutils import complement

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

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

# Exceptions
class FrozenHashError(TypeError):
    """Exception raised when attempting to modify FrozenDict."""
    pass

# Aliases for convenience
OMD = OrderedMultiDict
MultiDict = OrderedMultiDict