deque with rotatable slices

deque.py

from itertools import islice


class block:
    __slots__ = 'prev', 'next', 'val'

    def __init__(self, val, prev=None, next=None):
        self.prev = self if prev is None else prev
        self.next = self if next is None else next
        self.val = val

    def __repr__(self):
        return f'block({self.prev.val}, {self.val}, {self.next.val})'

    def __iter__(self):
        yield self.prev
        yield self
        yield self.next

    def __next__(self):
        return self.next


class deque:
    def __init__(self, iterable=None):
        self._first_block = None
        self._last_block = None
        self._len = 0
        if iterable is not None:
            for item in iterable:
                self.append(item)

    def __repr__(self):
        return f'deque([{", ".join(str(val) for val in self)}])'

    def _add(self, item, last):
        if self._first_block is None:
            self._first_block = self._last_block = block(item)
        else:
            self._last_block.next = self._first_block.prev = b = block(item, self._last_block, self._first_block)
            setattr(self, '_last_block' if last else '_first_block', b)
        self._len += 1

    def append(self, item):
        self._add(item, last=True)

    def appendleft(self, item):
        self._add(item, last=False)

    def pop(self):
        if self._first_block is None:
            raise IndexError('deque is empty')
        self._len -= 1
        val = self._last_block.val
        if self._len == 0:
            self._last_block = self._first_block = None
        else:
            self._last_block = self._first_block.prev = self._last_block.prev
            self._last_block.next = self._first_block
        return val

    def popleft(self):
        if self._first_block is None:
            raise IndexError('deque is empty')
        self._len -= 1
        val = self._first_block.val
        if self._len == 0:
            self._last_block = self._first_block = None
        else:
            self._first_block = self._last_block.next = self._first_block.next
            self._first_block.prev = self._last_block
        return val

    def rotate(self, n=1):
        if n > 0:
            for _ in range(n):
                self._last_block, self._first_block, _ = self._last_block
        else:
            for _ in range(-n):
                _, self._last_block, self._first_block = self._first_block

    def _block_iter(self, reverse=False):
        current_block = self._last_block if reverse else self._first_block
        for _ in range(self._len):
            yield current_block
            current_block = current_block.prev if reverse else current_block.next

    def _get_block(self, key):
        if key >= 0:
            return next(islice(self._block_iter(), key, None))
        return next(islice(self._block_iter(reverse=True), -key - 1, None))

    def __getitem__(self, key):
        if isinstance(key, slice):
            if key.step is not None and key.step != 1:  # TODO: allow -1 step??
                raise ValueError('step must be 1')

            start = 0 if key.start is None else key.start
            stop = self._len if key.stop is None else min(key.stop, self._len)

            return DequeSliceDescriptor(self, start, stop - 1)

        if not isinstance(key, int):
            raise TypeError('indices must be integers or slices')

        if key >= 0:
            return next(islice(self, key, None))
        return next(islice(reversed(self), -key - 1, None))

    def __len__(self):
        return self._len

    def __iter__(self):
        current_block = self._first_block
        for _ in range(self._len):
            yield current_block.val
            current_block = current_block.next

    def __reversed__(self):
        current_block = self._last_block
        for _ in range(self._len):
            yield current_block.val
            current_block = current_block.prev


class DequeSliceDescriptor:
    __slots__ = 'deq', 'start', 'stop', 'len'

    def __init__(self, deq, start, stop):
        self.deq = deq
        self.start = start
        self.stop = stop
        self.len = stop - start + 1

    def __repr__(self):
        block = self.deq._get_block(self.start).prev
        return f'DequeSliceDescriptor([{", ".join(str((block := next(block)).val) for _ in range(self.len))}])'

    def rotate(self, n=1):
        d = self.deq
        start = self.start
        stop = self.stop
        if n > 0:
            for _ in range(n):
                pre, first_block, _ = d._get_block(start)
                before_last, last_block, post = d._get_block(stop)

                first_block.prev = pre.next = last_block
                last_block.prev = pre
                last_block.next = first_block

                post.prev = before_last
                before_last.next = post

                if start == 0:
                    d._first_block = last_block
                if stop == len(d) - 1:
                    d._last_block = before_last
        else:
            for _ in range(-n):
                pre, first_block, after_first = d._get_block(start)
                _, last_block, post = d._get_block(stop)

                last_block.next = post.prev = first_block
                first_block.next = post
                first_block.prev = last_block

                pre.next = after_first
                after_first.prev = pre

                if start == 0:
                    d._first_block = after_first
                if stop == len(d) - 1:
                    d._last_block = first_block

    def __getitem__(self, key):
        if isinstance(key, slice):
            if key.step is not None and key.step != 1:
                raise ValueError('step must be 1')

            start = 0 if key.start is None else key.start
            stop = self.len - 1 if key.stop is None else min(key.stop - 1, self.len - 1)

            return DequeSliceDescriptor(self.deq, self.start + start, self.start + stop)

        if not isinstance(key, int):
            raise TypeError('indices must be integers or slices')

        if key > self.len:
            raise IndexError(str(key))

        return self.deq[self.start + key]