cp_library/ds/slidingmin_cls.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/ds/list/deque_cls.py
• cp_library/ds/list/list_find_fn.py

Code

import cp_library.ds.__header__
from cp_library.misc.typing import _T
from cp_library.ds.list.deque_cls import Deque
from typing import Iterable

class SlidingMin(Deque[_T]):
    def __init__(self, *, maxlen):
        super().__init__(maxlen=maxlen)
        self.minq = Deque(maxlen=maxlen)

    def append(self, x: _T) -> None:
        while self.minq and x < self.minq.tail(): self.minq.pop()
        self.minq.append(x)
        super().append(x)
    
    def appendleft(self, x: _T) -> None: raise NotImplemented
    
    def extend(self, iterable: Iterable) -> None:
        for x in iterable: self.append(x)

    def extendleft(self, iterable: Iterable) -> None: raise NotImplemented

    def popleft(self) -> _T:
        x = super().popleft()
        if x == self.minq.head(): self.minq.popleft()
        return x
    
    def pop(self) -> _T: raise NotImplemented

    @property
    def min(self) -> _T: return self.minq.head()

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from typing import TypeVar
_T = TypeVar('T')

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 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
from typing import Iterable

class SlidingMin(Deque[_T]):
    def __init__(self, *, maxlen):
        super().__init__(maxlen=maxlen)
        self.minq = Deque(maxlen=maxlen)

    def append(self, x: _T) -> None:
        while self.minq and x < self.minq.tail(): self.minq.pop()
        self.minq.append(x)
        super().append(x)
    
    def appendleft(self, x: _T) -> None: raise NotImplemented
    
    def extend(self, iterable: Iterable) -> None:
        for x in iterable: self.append(x)

    def extendleft(self, iterable: Iterable) -> None: raise NotImplemented

    def popleft(self) -> _T:
        x = super().popleft()
        if x == self.minq.head(): self.minq.popleft()
        return x
    
    def pop(self) -> _T: raise NotImplemented

    @property
    def min(self) -> _T: return self.minq.head()

Back to top page