cp_library/ds/list/deque_cls.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+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

Verified with

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

Code

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

class Deque(MutableSequence[_T]):
    def __init__(que, A = tuple(), *, maxlen=-1):
        super().__init__()
        data = [0]*maxlen
        que._sz = que._t = len(A)
        for i,a in enumerate(A): data[i] = a
        que._h, que.maxlen, que.data = 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.maxlen) != -1)
        else:
            return list_find(que.data, x, que._h, que._t) != -1
        
    def __getitem__(que, i: SupportsIndex) -> _T:
        assert -que._sz <= i < que._sz
        if i >= 0: return que.data[(que._h+i)%que.maxlen]
        else: return que.data[(que._t+i)%que.maxlen]
        
    def __setitem__(que, i: SupportsIndex, x):
        assert -que._sz <= i < que._sz
        if i >= 0: que.data[(que._h+i)%que.maxlen] = x
        else: que.data[(que._t+i)%que.maxlen] = x
    
    def head(que) -> _T: return que.data[que._h]

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

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

    def appendleft(que, x):
        que._h = (que._h-1)%que.maxlen
        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.maxlen
        que._sz -= 1
        return que.data[que._t]
    
    def popleft(que) -> _T:
        assert que._sz, "Deque is empty"
        x = que.data[h := que._h]
        que._h = (h+1)%que.maxlen
        que._sz -= 1
        return x

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

import sys

def list_find(lst: list, value, start = 0, stop = sys.maxsize):
    try:
        return lst.index(value, start, stop)
    except:
        return -1
from typing import TypeVar
_T = TypeVar('T')
from typing import MutableSequence, SupportsIndex

class Deque(MutableSequence[_T]):
    def __init__(que, A = tuple(), *, maxlen=-1):
        super().__init__()
        data = [0]*maxlen
        que._sz = que._t = len(A)
        for i,a in enumerate(A): data[i] = a
        que._h, que.maxlen, que.data = 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.maxlen) != -1)
        else:
            return list_find(que.data, x, que._h, que._t) != -1
        
    def __getitem__(que, i: SupportsIndex) -> _T:
        assert -que._sz <= i < que._sz
        if i >= 0: return que.data[(que._h+i)%que.maxlen]
        else: return que.data[(que._t+i)%que.maxlen]
        
    def __setitem__(que, i: SupportsIndex, x):
        assert -que._sz <= i < que._sz
        if i >= 0: que.data[(que._h+i)%que.maxlen] = x
        else: que.data[(que._t+i)%que.maxlen] = x
    
    def head(que) -> _T: return que.data[que._h]

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

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

    def appendleft(que, x):
        que._h = (que._h-1)%que.maxlen
        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.maxlen
        que._sz -= 1
        return que.data[que._t]
    
    def popleft(que) -> _T:
        assert que._sz, "Deque is empty"
        x = que.data[h := que._h]
        que._h = (h+1)%que.maxlen
        que._sz -= 1
        return x

Back to top page