<commit_before>######################################################################
# Cython version of scipy.ndimage.measurements.label().
# Requires Cython version 0.17 or greater due to type templating.
######################################################################

cimport cython
from cython cimport sizeof
import numpy as np
cimport numpy as np

np.import_array()

cdef extern from *:
   ctypedef int Py_intptr_t

cdef enum:
    BACKGROUND = 0
    FOREGROUND = 1

cdef extern from "numpy/arrayobject.h" nogil:
    ctypedef struct PyArrayIterObject:
        np.npy_intp *coordinates

    void PyArray_ITER_NEXT(PyArrayIterObject *it)
    int PyArray_ITER_NOTDONE(PyArrayIterObject *it)
    void PyArray_ITER_RESET(PyArrayIterObject *it)
    void *PyArray_ITER_DATA(PyArrayIterObject *it)

    void *PyDataMem_NEW(size_t)
    void PyDataMem_FREE(void *)
    void *PyDataMem_RENEW(void *, size_t)

class NeedMoreBits(Exception):
    pass

######################################################################
# Use Cython's type templates for type specialization
######################################################################
ctypedef fused data_t:
    np.int8_t
    np.int16_t
    np.int32_t
    np.int64_t
    np.uint8_t
    np.uint16_t
    np.uint32_t
    np.uint64_t
    np.float32_t
    np.float64_t


######################################################################
# Load a line from a fused data array, setting the line to FOREGROUND wherever
# the fused data is nonzero, BACKGROUND elsewhere
######################################################################
cdef void fused_nonzero_line(data_t *p, np.intp_t stride,
                             np.uintp_t *line, np.intp_t L) nogil:
    cdef np.uintp_t i
    for i in range(L):
        line[i] = FOREGROUND if \
            (<data_t *> ((<char *> p) + i * stride))[0] \
            else BACKGROUND


######################################################################
# Load a line from a fused data array to a np.uintp_t array
######################################################################
cdef void fused_read_line(data_t *p, np.intp_t stride,
                          np.uintp_t *line, np.intp_t L) nogil:
    cdef np.uintp_t i
    for i in range(L):
        line[i] = <np.uintp_t> (<data_t *> ((<char *> p) + i * stride))[0]


######################################################################
# Store a line from a np.uintp_t array to a fused data array if possible,
# returning True if overflowed
######################################################################
cdef bint fused_write_line(data_t *p, np.intp_t stride,
                           np.uintp_t *line, np.intp_t L) nogil:
    cdef np.uintp_t i
    for i in range(L):
        # Check before overwrite, as this prevents us accidentally writing a 0
        # in the foreground, which allows us to retry even when operating
        # in-place.
        if line[i] != <np.uintp_t> <data_t> line[i]:
            return True
        (<data_t *> ((<char *> p) + i * stride))[0] = <data_t> line[i]
    return False


######################################################################
# Function specializers
######################################################################
def get_nonzero_line(np.ndarray[data_t] a):
    return <Py_intptr_t> fused_nonzero_line[data_t]

def get_read_line(np.ndarray[data_t] a):
    return <Py_intptr_t> fused_read_line[data_t]

def get_write_line(np.ndarray[data_t] a):
    return <Py_intptr_t> fused_write_line[data_t]


######################################################################
# Typedefs for referring to specialized instances of fused functions
######################################################################
ctypedef void (*nonzero_line_func_t)(void *p, np.intp_t stride,
                                     np.uintp_t *line, np.intp_t L) nogil
ctypedef void (*read_line_func_t)(void *p, np.intp_t stride,
                                  np.uintp_t *line, np.intp_t L) nogil
ctypedef bint (*write_line_func_t)(void *p, np.intp_t stride,
                                   np.uintp_t *line, np.intp_t L) nogil


######################################################################
# Mark two labels to be merged
######################################################################
cdef inline np.uintp_t mark_for_merge(np.uintp_t a,
                                      np.uintp_t b,
                                      np.uintp_t *mergetable) nogil:
    # we keep the mergetable such that merged labels always point to the
    # smallest value in the merge.
    if mergetable[a] < mergetable[b]:
        mergetable[b] = mergetable[a]
    elif mergetable[a] > mergetable[b]:
        mergetable[a] = mergetable[b]
    return mergetable[a]


######################################################################
# Take the label of a neighbor, or mark them for merging
######################################################################
cdef inline np.uintp_t take_label_or_merge(np.uintp_t cur_label,
                                           np.uintp_t neighbor_label,
                                           np.uintp_t *mergetable) nogil:
    if neighbor_label == BACKGROUND:
        return cur_label
    if cur_label == FOREGROUND:
        return neighbor_label  # neighbor is not BACKGROUND<commit_msg>BUG: make ndimage.label properly merge adjacent objects (fixes #3025)<commit_after>######################################################################
# Cython version of scipy.ndimage.measurements.label().
# Requires Cython version 0.17 or greater due to type templating.
######################################################################

cimport cython
from cython cimport sizeof
import numpy as np
cimport numpy as np

np.import_array()

cdef extern from *:
   ctypedef int Py_intptr_t

cdef enum:
    BACKGROUND = 0
    FOREGROUND = 1

cdef extern from "numpy/arrayobject.h" nogil:
    ctypedef struct PyArrayIterObject:
        np.npy_intp *coordinates

    void PyArray_ITER_NEXT(PyArrayIterObject *it)
    int PyArray_ITER_NOTDONE(PyArrayIterObject *it)
    void PyArray_ITER_RESET(PyArrayIterObject *it)
    void *PyArray_ITER_DATA(PyArrayIterObject *it)

    void *PyDataMem_NEW(size_t)
    void PyDataMem_FREE(void *)
    void *PyDataMem_RENEW(void *, size_t)

class NeedMoreBits(Exception):
    pass

######################################################################
# Use Cython's type templates for type specialization
######################################################################
ctypedef fused data_t:
    np.int8_t
    np.int16_t
    np.int32_t
    np.int64_t
    np.uint8_t
    np.uint16_t
    np.uint32_t
    np.uint64_t
    np.float32_t
    np.float64_t


######################################################################
# Load a line from a fused data array, setting the line to FOREGROUND wherever
# the fused data is nonzero, BACKGROUND elsewhere
######################################################################
cdef void fused_nonzero_line(data_t *p, np.intp_t stride,
                             np.uintp_t *line, np.intp_t L) nogil:
    cdef np.uintp_t i
    for i in range(L):
        line[i] = FOREGROUND if \
            (<data_t *> ((<char *> p) + i * stride))[0] \
            else BACKGROUND


######################################################################
# Load a line from a fused data array to a np.uintp_t array
######################################################################
cdef void fused_read_line(data_t *p, np.intp_t stride,
                          np.uintp_t *line, np.intp_t L) nogil:
    cdef np.uintp_t i
    for i in range(L):
        line[i] = <np.uintp_t> (<data_t *> ((<char *> p) + i * stride))[0]


######################################################################
# Store a line from a np.uintp_t array to a fused data array if possible,
# returning True if overflowed
######################################################################
cdef bint fused_write_line(data_t *p, np.intp_t stride,
                           np.uintp_t *line, np.intp_t L) nogil:
    cdef np.uintp_t i
    for i in range(L):
        # Check before overwrite, as this prevents us accidentally writing a 0
        # in the foreground, which allows us to retry even when operating
        # in-place.
        if line[i] != <np.uintp_t> <data_t> line[i]:
            return True
        (<data_t *> ((<char *> p) + i * stride))[0] = <data_t> line[i]
    return False


######################################################################
# Function specializers
######################################################################
def get_nonzero_line(np.ndarray[data_t] a):
    return <Py_intptr_t> fused_nonzero_line[data_t]

def get_read_line(np.ndarray[data_t] a):
    return <Py_intptr_t> fused_read_line[data_t]

def get_write_line(np.ndarray[data_t] a):
    return <Py_intptr_t> fused_write_line[data_t]


######################################################################
# Typedefs for referring to specialized instances of fused functions
######################################################################
ctypedef void (*nonzero_line_func_t)(void *p, np.intp_t stride,
                                     np.uintp_t *line, np.intp_t L) nogil
ctypedef void (*read_line_func_t)(void *p, np.intp_t stride,
                                  np.uintp_t *line, np.intp_t L) nogil
ctypedef bint (*write_line_func_t)(void *p, np.intp_t stride,
                                   np.uintp_t *line, np.intp_t L) nogil


######################################################################
# Mark two labels to be merged
######################################################################
cdef inline np.uintp_t mark_for_merge(np.uintp_t a,
                                      np.uintp_t b,
                                      np.uintp_t *mergetable) nogil:

    cdef:
        np.uintp_t orig_a, orig_b, minlabel

    orig_a = a
    orig_b = b
    # find smallest root for each of a and b
    while a != mergetable[a]:
        a = mergetable[a]
    while b != mergetable[b]:
        b = mergetable[b]
    minlabel = a if (a < b) else b

    # merge roots
    mergetable[a] = mergetable[b] = minlabel

    # merge every step to minlabel
    a = orig_a
    b = orig_b
    while a != minlabel:
        a, mergetable[a] = mergetable[a], minlabel
    while b != minlabel:
        b, mergetable[b] = mergetable[b], minlabel

    return minlabel


######################################################################
# Take the label of a neighbor, or mark them for merging
######################################################################
cdef inline np.uintp_t take_label_or_merge(np.uintp_t cur_label,
                                           np.uintp_t neighbor_label,
                                           np.uintp_t *mergetable) nogil:
    if neighbor_label == BACKGROUND:
        return cur_label
    if cur_label == FOREGROUND:
        return neighbor_label  # neighbor is not BACKGROUND
{'fraction_non_alphanumeric': 0.29127528901734107, 'fraction_numerical': 0.0052384393063583815, 'mean_word_length': 3.436298076923077, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3287220', 'n_tokens_mistral': 3332, 'n_tokens_neox': 3072, 'n_words': 837}