cp_library/ds/que/deque_cls.py

• View this file on GitHub
• Last update: 2025-08-24 20:27:05+09:00

Depends on

• cp_library/ds/list/list_find_fn.py

Required by

• cp_library/ds/slidingmax_cls.py
• cp_library/ds/slidingmin_cls.py
• cp_library/ds/slidingminmax_cls.py
• perf/deque.py
• perf/que.py

Verified with

• test/atcoder/agc/agc038_b_sliding_min_max.test.py

Code

import cp_library.__header__
from cp_library.misc.typing import _T
from typing import MutableSequence, SupportsIndex
import cp_library.ds.__header__
from cp_library.ds.list.list_find_fn import list_find
import cp_library.ds.que.__header__

class Deque(MutableSequence[_T]):
    def __init__(que, A = tuple(), *, maxlen=-1):
        super().__init__()
        que.cap = 1 << (maxlen-1).bit_length()
        data = [0]*que.cap
        que._sz = que._t = len(A)
        for i,a in enumerate(A): data[i] = a
        que._mask, que._h, que.maxlen, que.data = que.cap-1, 0, maxlen, data

    def __len__(que):
        return que._sz 
    
    def __contains__(que, x):
        if que._h >= que._t:
            return (list_find(que.data, x, 0, que._t) != -1
                or list_find(que.data, x, que._h, que.cap) != -1)
        else:
            return list_find(que.data, x, que._h, que._t) != -1
        
    def __getitem__(que, i: SupportsIndex) -> _T:
        if not (-que._sz <= i < que._sz): raise IndexError
        if i >= 0: return que.data[(que._h+i)&que._mask]
        else: return que.data[(que._t+i)&que._mask]
        
    def __setitem__(que, i: SupportsIndex, x):
        if not (-que._sz <= i < que._sz): raise IndexError
        if i >= 0: que.data[(que._h+i)&que._mask] = x
        else: que.data[(que._t+i)&que._mask] = x
    
    def head(que) -> _T: return que.data[que._h]

    def tail(que) -> _T: return que.data[(que._t-1)&que._mask]

    def __delitem__(que, i: SupportsIndex):
        raise NotImplemented
    
    def insert(que, i: SupportsIndex, x):
        raise NotImplemented
    
    def append(que, x):
        que.data[que._t] = x
        que._t = (que._t+1)&que._mask
        if que._sz == que.maxlen: que._h = (que._h+1)&que._mask
        else: que._sz += 1

    def appendleft(que, x):
        que._h = (que._h-1)&que._mask
        que.data[que._h] = x
        if que._sz == que.maxlen: que._t = que._h
        else: que._sz += 1

    def pop(que) -> _T:
        assert que._sz, "Deque is empty"
        que._t = (que._t-1)&que._mask
        que._sz -= 1
        return que.data[que._t]
    
    def popleft(que) -> _T:
        assert que._sz, "Deque is empty"
        x = que.data[que._h]
        que._h = (que._h+1)&que._mask
        que._sz -= 1
        return x
    
    def __hash__(que):
        """Make Deque hashable for efficient benchmarking"""
        if que._h <= que._t:
            return hash(tuple(que.data[que._h:que._t]))
        else:
            return hash(tuple(que.data[que._h:] + que.data[:que._t]))

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from typing import TypeVar

_S = TypeVar('S'); _T = TypeVar('T'); _U = TypeVar('U'); _T1 = TypeVar('T1'); _T2 = TypeVar('T2'); _T3 = TypeVar('T3'); _T4 = TypeVar('T4'); _T5 = TypeVar('T5'); _T6 = TypeVar('T6')
from typing import MutableSequence, SupportsIndex

import sys


def list_find(lst: list, value, start = 0, stop = sys.maxsize):
    try:
        return lst.index(value, start, stop)
    except:
        return -1


class Deque(MutableSequence[_T]):
    def __init__(que, A = tuple(), *, maxlen=-1):
        super().__init__()
        que.cap = 1 << (maxlen-1).bit_length()
        data = [0]*que.cap
        que._sz = que._t = len(A)
        for i,a in enumerate(A): data[i] = a
        que._mask, que._h, que.maxlen, que.data = que.cap-1, 0, maxlen, data

    def __len__(que):
        return que._sz 
    
    def __contains__(que, x):
        if que._h >= que._t:
            return (list_find(que.data, x, 0, que._t) != -1
                or list_find(que.data, x, que._h, que.cap) != -1)
        else:
            return list_find(que.data, x, que._h, que._t) != -1
        
    def __getitem__(que, i: SupportsIndex) -> _T:
        if not (-que._sz <= i < que._sz): raise IndexError
        if i >= 0: return que.data[(que._h+i)&que._mask]
        else: return que.data[(que._t+i)&que._mask]
        
    def __setitem__(que, i: SupportsIndex, x):
        if not (-que._sz <= i < que._sz): raise IndexError
        if i >= 0: que.data[(que._h+i)&que._mask] = x
        else: que.data[(que._t+i)&que._mask] = x
    
    def head(que) -> _T: return que.data[que._h]

    def tail(que) -> _T: return que.data[(que._t-1)&que._mask]

    def __delitem__(que, i: SupportsIndex):
        raise NotImplemented
    
    def insert(que, i: SupportsIndex, x):
        raise NotImplemented
    
    def append(que, x):
        que.data[que._t] = x
        que._t = (que._t+1)&que._mask
        if que._sz == que.maxlen: que._h = (que._h+1)&que._mask
        else: que._sz += 1

    def appendleft(que, x):
        que._h = (que._h-1)&que._mask
        que.data[que._h] = x
        if que._sz == que.maxlen: que._t = que._h
        else: que._sz += 1

    def pop(que) -> _T:
        assert que._sz, "Deque is empty"
        que._t = (que._t-1)&que._mask
        que._sz -= 1
        return que.data[que._t]
    
    def popleft(que) -> _T:
        assert que._sz, "Deque is empty"
        x = que.data[que._h]
        que._h = (que._h+1)&que._mask
        que._sz -= 1
        return x
    
    def __hash__(que):
        """Make Deque hashable for efficient benchmarking"""
        if que._h <= que._t:
            return hash(tuple(que.data[que._h:que._t]))
        else:
            return hash(tuple(que.data[que._h:] + que.data[:que._t]))

Back to top page