pyrangesort.py

"""
Este código é a integração da biblioteca rangesort que foi escrita em C:
https://gist.github.com/d3cryptofc/0629f82f18f58ae6db7caf267a38c607
"""

from __future__ import annotations

import ctypes
from typing import Sequence


class ItemStruct(ctypes.Structure):
    _fields_ = [
        ('value', ctypes.c_size_t),
        ('quantity', ctypes.c_size_t)
    ]

    def __repr__(self):
        return '{}<value={!r}, quantity={!r}>'.format(
            type(self).__name__,
            self.value,
            self.quantity
        )

    def __str__(self):
        return repr(self)


ItemPointer = ctypes.POINTER(ItemStruct)

rangesort = ctypes.CDLL("./rangesort.so")
rangesort.sort_range.restype = ItemPointer


class ItemArray:
    def __init__(self, start: ItemPointer, length: int):
        self.__start = start
        if not isinstance(start, ItemPointer):
            msg = 'parameter `start` type must be an integer.'
            raise TypeError(msg)

        self.__length = length
        if not isinstance(length, int):
            msg = 'parameter `length` type must be an ItemPointer.'
            raise TypeError(msg)

        self.__freed = False

    def __check_freed(self):
        if self.__freed:
            msg = 'the pointer no longer exists, It has been freed.'
            raise RuntimeError(msg)

    def __repr__(self):
        return '{}<length={!r}>'.format(
            type(self).__name__,
            self.__length
        )

    def __iter__(self):
        """
        ATENÇÃO: Se planeja usar um for não é encessário usar list(),
        além de que tornará o processo mais lento.
        """
        self.__check_freed()
        for index in range(self.__length):
            yield self.__start[index]

    def __getitem__(self, index: int):
        """
        Este é um método seguro, mas validar toda vez pode prejudicar
        a performance. Se busca performance e sabe o que está fazendo,
        use `._pointer[indice]`.
        """
        if not isinstance(index, int):
            msg = 'parameter `index` type must be an integer.'
            raise TypeError(msg)
        self.__check_freed()
        if index > self.__length - 1:
            msg = 'list index out of range'
            raise IndexError(msg)
        return self.__start[index]

    @property
    def _pointer(self):
        return self.__start

    @property
    def length(self):
        return self.__length

    @property
    def freed(self):
        return self.__freed

    def free(self):
        self.__check_freed()
        rangesort.free_p(self.__start)
        self.__freed = True

    def __del__(self):
        try:
            self.free()
        except RuntimeError:
            ...


def range_sort(sequence: Sequence,
               *,
               rmholes: bool = False,
               length: int = None,
               start_range: int = None):
    arr_length = ctypes.c_size_t(length or len(sequence))
    error_code = ctypes.c_uint8(0)

    item = rangesort.sort_range(
        # size_t* array
        (ctypes.c_size_t * len(sequence))(*sequence),

        # size_t start_range
        ctypes.c_size_t(min(sequence) if start_range is None else start_range),

        # size_t* arr_length
        ctypes.pointer(arr_length),

        # bool rmholes
        ctypes.c_bool(rmholes),

        # OrderedListError* error_code
        ctypes.pointer(error_code)
    )
    if not item:
        msg = f'rangesort error code: {error_code.value}'
        raise RuntimeError(msg)
    return ItemArray(start=item, length=arr_length.value)


def main():
    import time

    sample = list(range(1, 21))[::-1]
    length = len(sample)
    start_range = min(sample)

    print(f'Entrada: [{length}] ', end='')
    for item in sample:
        print(f'{item} ', end='')
    print()

    started_time = time.time()
    result = range_sort(sample, length=length, start_range=start_range)
    elapsed_time = time.time()

    print(f'Saída: [{result.length}] ', end='')
    for item in result:
        print(f'{item.value}({item.quantity}) ', end='')
    print()

    result.free()

    print(f'Tempo de ordenação: {elapsed_time - started_time:.10f}s')


if __name__ == '__main__':
    main()