<commit_before># encoding: utf-8
# cython: cdivision=True
# cython: boundscheck=False
# cython: wraparound=False
#
# Author: <NAME>, <NAME>, <NAME>
#
# License: BSD Style.

# TODO: pickle https://groups.google.com/forum/?fromgroups#!topic/cython-users/vzG58m0Yr2Y
# TODO: expose attributes http://docs.cython.org/src/tutorial/cdef_classes.html


# ==============================================================================
# Imports
# ==============================================================================

cimport cython

import numpy as np
cimport numpy as np

cdef extern from "stdlib.h":
    void* malloc(size_t size)
    void* calloc(size_t nmemb, size_t size)
    void* realloc(void* ptr, size_t size)
    void free(void* ptr)

cdef extern from "math.h":
    cdef extern double log(double x)
    cdef extern double pow(double base, double exponent)

cdef extern from "float.h":
    cdef extern double DBL_MAX


# ==============================================================================
# Types and constants
# ==============================================================================

# Dtype
DTYPE = np.float32
ctypedef np.float32_t DTYPE_t
ctypedef np.int8_t BOOL_t

# Constants
cdef double INFINITY = np.inf

TREE_LEAF = -1
cdef int _TREE_LEAF = TREE_LEAF

TREE_SPLIT_BEST = 1
TREE_SPLIT_RANDOM = 2
cdef int _TREE_SPLIT_BEST = TREE_SPLIT_BEST
cdef int _TREE_SPLIT_RANDOM = TREE_SPLIT_RANDOM


# ==============================================================================
# Tree
# ==============================================================================

cdef class Tree:
    """Struct-of-arrays representation of a binary decision tree.

    The binary tree is represented as a number of parallel arrays.
    The i-th element of each array holds information about the
    node `i`. You can find a detailed description of all arrays
    below. NOTE: Some of the arrays only apply to either leaves or
    split nodes, resp. In this case the values of nodes of the other
    type are arbitrary!

    Attributes
    ----------
    node_count : int
        Number of nodes (internal nodes + leaves) in the tree.

    children : np.ndarray, shape=(node_count, 2), dtype=int32
        `children[i, 0]` holds the node id of the left child of node `i`.
        `children[i, 1]` holds the node id of the right child of node `i`.
        For leaves `children[i, 0] == children[i, 1] == self.LEAF == -1`.

    feature : np.ndarray of int32
        The feature to split on (only for internal nodes).

    threshold : np.ndarray of float64
        The threshold of each node (only for internal nodes).

    value : np.ndarray of float64, shape=(capacity, n_outputs, n_classes)
        Contains the constant prediction value of each node.

    best_error : np.ndarray of float64
        The error of the (best) split.
        For leaves `init_error == `best_error`.

    init_error : np.ndarray of float64
        The initial error of the node (before splitting).
        For leaves `init_error == `best_error`.

    n_samples : np.ndarray of np.int32
        The number of samples at each node.
    """

    # Input/Output layout
    cdef int* n_classes
    cdef int max_n_classes
    cdef int n_features
    cdef int n_outputs

    # Parameters
    cdef Criterion criterion
    cdef double max_depth
    cdef int min_samples_split
    cdef int min_samples_leaf
    cdef double min_density
    cdef int max_features
    cdef int find_split_algorithm
    cdef object random_state

    # Inner structures
    cdef int node_count
    cdef int capacity
    cdef int* children_left
    cdef int* children_right
    cdef int* feature
    cdef double* threshold
    cdef double* value
    cdef double* best_error
    cdef double* init_error
    cdef int* n_samples

    def __init__(self, object n_classes, int n_features, int n_outputs,
                 Criterion criterion, double max_depth, int min_samples_split,
                 int min_samples_leaf, double min_density, int max_features,
                 int find_split_algorithm, object random_state, int capacity=3):
        # Input/Output layout
        cdef int k

        self.n_features = n_features
        self.n_outputs = n_outputs
        self.n_classes = <int*> calloc(n_outputs, sizeof(int))
        self.max_n_classes = np.max(n_classes)

        for k from 0 <= k < n_outputs:
            self.n_classes[k] = n_classes[k]

        # Parameters
        self.criterion = criterion
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.min_density = min_density
        self.max_features = max_features
        self.find_split_algorithm = find_split_algorithm
        self.random_state = random_state

        # Inner structures
        self.node_count = 0
        self.capacity = capacity

        self.children_left = <int*> malloc(capacity * sizeof(int))
        self.children_right = <int*> malloc(capacity * sizeof(int))
        self.feature = <int*> malloc(capacity * sizeof(int))
        self.threshold = <double*> malloc(capacity * sizeof(double))
        self.value = <double*> malloc(capacity * self.n_outputs * self.max_n_classes * sizeof(double));
        self.best_error = <double*> malloc(capacity * sizeof(double));
        self.init_error = <double*> malloc(capacity * sizeof(double));
        self.n_samples = <int*> malloc(capacity * sizeof(int));

    def __del__(self):
        # Free all inner structures
        free(self.n_classes)
        free(self.children_left)
        free(self.children_right)
        free(self.feature)
        free(self.threshold)
        free(self.value)
        free(self.best_error)
        free(self.init_error)
        free(self.n_samples)

    cdef void resize(self, int capacity=-1):
        """Resize tree arrays to `capacity`, if < 0 then double capacity. """
        if capacity == self.capacity:
            return

        if capacity < 0:
            capacity = 2 * self.capacity

        self.capacity = capacity

        self.children_left = <int*> realloc(self.children_left, capacity * sizeof(int))
        self.children_right = <int*> realloc(self.children_right, capacity * sizeof(int))
        self.feature = <int*> realloc(self.feature, capacity * sizeof(int))
        self.threshold = <double*> realloc(self.threshold, capacity * sizeof(double))
        self.value = <double*> realloc(self.value, capacity * self.n_outputs * self.max_n_classes * sizeof(double))
        self.best_error = <double*> realloc(self.best_error, capacity * sizeof(double))
        self.init_error = <double*> realloc(self.init_error, capacity * sizeof(double))
        self.n_samples = <int*> realloc(self.n_samples, capacity * sizeof(int))

        # if capacity smaller than node_count, adjust the counter
        if capacity < self.node_count:
            self.node_count = capacity

    cdef int add_split_node(self, int parent, int is_left_child, int feature,
                                  double threshold, double* value,
                                  double best_error, double init_error,
                                  int n_samples):
        """Add a splitting node to the tree. The new node registers itself as
           the child of its parent. """
        cdef int node_id = self.node_count

        if node_id >= self.capacity:
            self.resize()

        self.feature[node_id] = feature
        self.threshold[node_id] = threshold

        cdef int i
        cdef int offset_node = node_id * self.n_outputs * self.max_n_classes

        for i from 0 <= i < self.n_outputs * self.max_n_classes:
            self.value[offset_node + i] = value[i]

        self.init_error[node_id] = init_error
        self.best_error[node_id] = best_error
        self.n_samples[node_id] = n_samples

        # set as left or right child of parent
        if parent > _TREE_LEAF:
            if is_left_child:
                self.children_left[parent] = node_id
            else:
                self.children_right[parent] = node_id

        self.node_count += 1

        return node_id

    cdef int add_leaf(self, int parent, int is_left_child, double* value, double error, int n_samples):
        """Add a leaf to the tree. The new node registers itself as the
           child of its parent. """
        cdef int node_id = self.node_count

        if node_id >= self.capacity:
            self.resize()

        cdef int i
        cdef int offset_node = node_id * self.n_outputs * self.max_n_classes

        for i from 0 <= i < self.n_outputs * self.max_n_classes:
            self.value[offset_node + i] = value[i]

        self.init_error[node_id] = error
        self.best_error[node_id] = error
        self.n_samples[node_id] = n_samples

        if is_left_child:
            self.children_left[parent] = node_id
        else:
            self.children_right[parent] = node_id

        self.children_left[node_id] = _TREE_LEAF
        self.children_right[node_id] = _TREE_LEAF

        self.node_count += 1

        return node_id

    cpdef build(self, np.ndarray X, np.ndarray y, np.ndarray sample_mask=None, np.ndarray X_argsorted=None):
        # Check input before recursive partitioning
        if X.dtype != DTYPE or not np.isfortran(X):
            X = np.asarray(X, dtype=DTYPE, order="F")

        if y.dtype != DTYPE or not y.flags.contiguous:
            y = np.asarray(y, dtype=DTYPE, order="C")

        if sample_mask is None:
            sample_mask = np.ones((X.shape[0],), dtype=np.bool)

        if X_argsorted is None:
            X_argsorted = np.asfortranarray(
                np.argsort(X.T, axis=1).astype(np.int32).T)

        # Pre-allocate some space
        cdef int init_capacity

        if self.max_depth <= 10:
            init_capacity = (2 ** (int(self.max_depth) + 1)) - 1
        else:
            init_capacity = 2047

        self.resize(init_capacity)
        cdef double* buffer_value = <double*> malloc(self.n_outputs * self.max_n_classes * sizeof(double))

        # Build the tree by recursive partitioning
        self.recursive_partition(X, X_argsorted, y, sample_mask, np.sum(sample_mask), 0, -1, False, buffer_value)

        # Compactify
        self.resize(self.node_count)
        free(buffer_value)

    cdef void recursive_partition(self,
                                  np.ndarray[DTYPE_t, ndim=2, mode="fortran"] X,
                                  np.ndarray[np.int32_t, ndim=2, mode="fortran"] X_argsorted,
                                  np.ndarray[DTYPE_t, ndim=2, mode="c"] y,
                                  np.ndarray sample_mask,
                                  int n_node_samples,
                                  int depth,
                                  int parent,
                                  int is_left_child,
                                  double* buffer_value):
        # Variables
        cdef Criterion criterion = self.criterion

        cdef DTYPE_t* X_ptr = <DTYPE_t*> X.data
        cdef int* X_argsorted_ptr = <int*> X_argsorted.data
        cdef DTYPE_t* y_ptr = <DTYPE_t*> y.data
        cdef BOOL_t* sample_mask_ptr = <BOOL_t*> sample_mask.data

        cdef int X_stride = <int> X.strides[1] / <int> X.strides[0]
        cdef int X_argsorted_stride = <int> X_argsorted.strides[1] / <int> X_argsorted.strides[0]
        cdef int y_stride = <int> y.strides[0] / <int> y.strides[1]

        cdef int n_total_samples = y.shape[0]
        cdef int feature
        cdef double threshold
        cdef double best_error
        cdef double init_error

        cdef int i
        cdef np.ndarray sample_mask_left
        cdef np.ndarray sample_mask_right
        cdef int n_node_samples_left
        cdef int n_node_samples_right

        # Count samples
        if n_node_samples == 0:
            raise ValueError("Attempting to find a split "
                             "with an empty sample_mask")

        # Split samples
        if depth < self.max_depth and \
           n_node_samples >= self.min_samples_split and \
           n_node_samples >= 2 * self.min_samples_leaf:
            self.find_split(X_ptr, X_stride,
                            X_argsorted_ptr, X_argsorted_stride,
                            y_ptr, y_stride,
                            sample_mask_ptr,
                            n_node_samples,
                            n_total_samples,
                            &feature, &threshold, &best_error, &init_error)

        else:
            feature = -1
            criterion.init(y_ptr, y_stride, sample_mask_ptr, n_node_samples, n_total_samples)
            init_error = criterion.eval()

        criterion.init_value(buffer_value)

        # Current node is leaf
        if feature == -1:
            self.add_leaf(parent, is_left_child, buffer_value, init_error, n_node_samples)

        # Current node is internal node (= split node)
        else:
            # Sample mask is too sparse?
            if 1. * n_node_samples / n_total_samples <= self.min_density:
                X = X[sample_mask]
                X_argsorted = np.asfortranarray(np.argsort(X.T, axis=1).astype(np.int32).T)
                y = y[sample_mask]
                sample_mask = np.ones((n_node_samples,), dtype=np.bool)

                n_total_samples = n_node_samples

                X_ptr = <DTYPE_t*> X.data
                X_argsorted_ptr = <int*> X_argsorted.data
                y_ptr = <DTYPE_t*> y.data
                sample_mask_ptr = <BOOL_t*> sample_mask.data

                X_stride = <int> X.strides[1] / <int> X.strides[0]
                X_argsorted_stride = <int> X_argsorted.strides[1] / <int> X_argsorted.strides[0]
                y_stride = <int> y.strides[0] / <int> y.strides[1]

            # Split and and recurse
            X_ptr = X_ptr + feature * X_stride
            sample_mask_left = np.zeros((n_total_samples, ), dtype=np.bool)
            sample_mask_right = np.zeros((n_total_samples, ), dtype=np.bool)
            n_node_samples_left = 0
            n_node_samples_right = 0

            for i from 0 <= i < n_total_samples:
                if sample_mask[i]:
                    if X_ptr[i] <= threshold:
                        sample_mask_left[i] = 1
                        n_node_samples_left += 1
                    else:
                        sample_mask_right[i] = 1
                        n_node_samples_right += 1

            node_id = self.add_split_node(parent, is_left_child, feature,
                                           threshold, buffer_value, best_error,
                                           init_error, n_node_samples)

            # left child recursion
            self.recursive_partition(X, X_argsorted, y,
                                sample_mask_left, n_node_samples_left,
                                depth + 1, node_id, True, buffer_value)

            # right child recursion
            self.recursive_partition(X, X_argsorted, y,
                                sample_mask_right, n_node_samples_right,
                                depth + 1, node_id, False, buffer_value)

    cdef void find_split(self, DTYPE_t* X_ptr, int X_stride,
                         int* X_argsorted_ptr, int X_argsorted_stride,
                         DTYPE_t* y_ptr, int y_stride, BOOL_t* sample_mask_ptr,
                         int n_node_samples, int n_total_samples, int* _best_i,
                         double* _best_t, double* _best_error,
                         double* _initial_error):
        """Find the best dimension and threshold that minimises the error."""
        if self.find_split_algorithm == _TREE_SPLIT_BEST:
            self.find_best_split(X_ptr, X_stride, X_argsorted_ptr,
                                 X_argsorted_stride, y_ptr, y_stride,<commit_msg>Tree refactoring (8)<commit_after># encoding: utf-8
# cython: cdivision=True
# cython: boundscheck=False
# cython: wraparound=False
#
# Author: <NAME>, <NAME>, <NAME>
#
# License: BSD Style.

# TODO: pickle https://groups.google.com/forum/?fromgroups#!topic/cython-users/vzG58m0Yr2Y
# TODO: expose attributes http://docs.cython.org/src/tutorial/cdef_classes.html


# ==============================================================================
# Imports
# ==============================================================================

cimport cython

import numpy as np
cimport numpy as np

cdef extern from "stdlib.h":
    void* malloc(size_t size)
    void* calloc(size_t nmemb, size_t size)
    void* realloc(void* ptr, size_t size)
    void free(void* ptr)

cdef extern from "math.h":
    cdef extern double log(double x)
    cdef extern double pow(double base, double exponent)

cdef extern from "float.h":
    cdef extern double DBL_MAX


# ==============================================================================
# Types and constants
# ==============================================================================

# Dtype
DTYPE = np.float32
ctypedef np.float32_t DTYPE_t
ctypedef np.int8_t BOOL_t

# Constants
cdef double INFINITY = np.inf

TREE_LEAF = -1
cdef int _TREE_LEAF = TREE_LEAF

TREE_SPLIT_BEST = 1
TREE_SPLIT_RANDOM = 2
cdef int _TREE_SPLIT_BEST = TREE_SPLIT_BEST
cdef int _TREE_SPLIT_RANDOM = TREE_SPLIT_RANDOM


# ==============================================================================
# Tree
# ==============================================================================

cdef class Tree:
    """Struct-of-arrays representation of a binary decision tree.

    The binary tree is represented as a number of parallel arrays.
    The i-th element of each array holds information about the
    node `i`. You can find a detailed description of all arrays
    below. NOTE: Some of the arrays only apply to either leaves or
    split nodes, resp. In this case the values of nodes of the other
    type are arbitrary!

    Attributes
    ----------
    node_count : int
        Number of nodes (internal nodes + leaves) in the tree.

    children : np.ndarray, shape=(node_count, 2), dtype=int32
        `children[i, 0]` holds the node id of the left child of node `i`.
        `children[i, 1]` holds the node id of the right child of node `i`.
        For leaves `children[i, 0] == children[i, 1] == self.LEAF == -1`.

    feature : np.ndarray of int32
        The feature to split on (only for internal nodes).

    threshold : np.ndarray of float64
        The threshold of each node (only for internal nodes).

    value : np.ndarray of float64, shape=(capacity, n_outputs, n_classes)
        Contains the constant prediction value of each node.

    best_error : np.ndarray of float64
        The error of the (best) split.
        For leaves `init_error == `best_error`.

    init_error : np.ndarray of float64
        The initial error of the node (before splitting).
        For leaves `init_error == `best_error`.

    n_samples : np.ndarray of np.int32
        The number of samples at each node.
    """

    # Input/Output layout
    cdef int* n_classes
    cdef int max_n_classes
    cdef int n_features
    cdef int n_outputs

    # Parameters
    cdef Criterion criterion
    cdef double max_depth
    cdef int min_samples_split
    cdef int min_samples_leaf
    cdef double min_density
    cdef int max_features
    cdef int find_split_algorithm
    cdef object random_state

    # Inner structures
    cdef int node_count
    cdef int capacity
    cdef int* children_left
    cdef int* children_right
    cdef int* feature
    cdef double* threshold
    cdef double* value
    cdef double* best_error
    cdef double* init_error
    cdef int* n_samples

    def __init__(self, object n_classes, int n_features, int n_outputs,
                 Criterion criterion, double max_depth, int min_samples_split,
                 int min_samples_leaf, double min_density, int max_features,
                 int find_split_algorithm, object random_state, int capacity=3):
        # Input/Output layout
        cdef int k

        self.n_features = n_features
        self.n_outputs = n_outputs
        self.n_classes = <int*> calloc(n_outputs, sizeof(int))
        self.max_n_classes = np.max(n_classes)

        for k from 0 <= k < n_outputs:
            self.n_classes[k] = n_classes[k]

        # Parameters
        self.criterion = criterion
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.min_density = min_density
        self.max_features = max_features
        self.find_split_algorithm = find_split_algorithm
        self.random_state = random_state

        # Inner structures
        self.node_count = 0
        self.capacity = capacity

        self.children_left = <int*> malloc(capacity * sizeof(int))
        self.children_right = <int*> malloc(capacity * sizeof(int))
        self.feature = <int*> malloc(capacity * sizeof(int))
        self.threshold = <double*> malloc(capacity * sizeof(double))
        self.value = <double*> malloc(capacity * self.n_outputs * self.max_n_classes * sizeof(double));
        self.best_error = <double*> malloc(capacity * sizeof(double));
        self.init_error = <double*> malloc(capacity * sizeof(double));
        self.n_samples = <int*> malloc(capacity * sizeof(int));

    def __del__(self):
        # Free all inner structures
        free(self.n_classes)
        free(self.children_left)
        free(self.children_right)
        free(self.feature)
        free(self.threshold)
        free(self.value)
        free(self.best_error)
        free(self.init_error)
        free(self.n_samples)

    cdef void resize(self, int capacity=-1):
        """Resize tree arrays to `capacity`, if < 0 then double capacity. """
        if capacity == self.capacity:
            return

        if capacity < 0:
            capacity = 2 * self.capacity

        self.capacity = capacity

        self.children_left = <int*> realloc(self.children_left, capacity * sizeof(int))
        self.children_right = <int*> realloc(self.children_right, capacity * sizeof(int))
        self.feature = <int*> realloc(self.feature, capacity * sizeof(int))
        self.threshold = <double*> realloc(self.threshold, capacity * sizeof(double))
        self.value = <double*> realloc(self.value, capacity * self.n_outputs * self.max_n_classes * sizeof(double))
        self.best_error = <double*> realloc(self.best_error, capacity * sizeof(double))
        self.init_error = <double*> realloc(self.init_error, capacity * sizeof(double))
        self.n_samples = <int*> realloc(self.n_samples, capacity * sizeof(int))

        # if capacity smaller than node_count, adjust the counter
        if capacity < self.node_count:
            self.node_count = capacity

    cdef int add_split_node(self, int parent, int is_left_child, int feature,
                                  double threshold, double* value,
                                  double best_error, double init_error,
                                  int n_samples):
        """Add a splitting node to the tree. The new node registers itself as
           the child of its parent. """
        cdef int node_id = self.node_count

        if node_id >= self.capacity:
            self.resize()

        self.feature[node_id] = feature
        self.threshold[node_id] = threshold

        cdef int i
        cdef int offset_node = node_id * self.n_outputs * self.max_n_classes

        for i from 0 <= i < self.n_outputs * self.max_n_classes:
            self.value[offset_node + i] = value[i]

        self.init_error[node_id] = init_error
        self.best_error[node_id] = best_error
        self.n_samples[node_id] = n_samples

        # set as left or right child of parent
        if parent > _TREE_LEAF:
            if is_left_child:
                self.children_left[parent] = node_id
            else:
                self.children_right[parent] = node_id

        self.node_count += 1

        return node_id

    cdef int add_leaf(self, int parent, int is_left_child, double* value, double error, int n_samples):
        """Add a leaf to the tree. The new node registers itself as the
           child of its parent. """
        cdef int node_id = self.node_count

        if node_id >= self.capacity:
            self.resize()

        cdef int i
        cdef int offset_node = node_id * self.n_outputs * self.max_n_classes

        for i from 0 <= i < self.n_outputs * self.max_n_classes:
            self.value[offset_node + i] = value[i]

        self.init_error[node_id] = error
        self.best_error[node_id] = error
        self.n_samples[node_id] = n_samples

        if is_left_child:
            self.children_left[parent] = node_id
        else:
            self.children_right[parent] = node_id

        self.children_left[node_id] = _TREE_LEAF
        self.children_right[node_id] = _TREE_LEAF

        self.node_count += 1

        return node_id

    cpdef build(self, np.ndarray X, np.ndarray y, np.ndarray sample_mask=None, np.ndarray X_argsorted=None):
        # Check input before recursive partitioning
        if X.dtype != DTYPE or not np.isfortran(X):
            X = np.asarray(X, dtype=DTYPE, order="F")

        if y.dtype != DTYPE or not y.flags.contiguous:
            y = np.asarray(y, dtype=DTYPE, order="C")

        if sample_mask is None:
            sample_mask = np.ones((X.shape[0],), dtype=np.bool)

        if X_argsorted is None:
            X_argsorted = np.asfortranarray(
                np.argsort(X.T, axis=1).astype(np.int32).T)

        # Pre-allocate some space
        cdef int init_capacity

        if self.max_depth <= 10:
            init_capacity = (2 ** (int(self.max_depth) + 1)) - 1
        else:
            init_capacity = 2047

        self.resize(init_capacity)
        cdef double* buffer_value = <double*> malloc(self.n_outputs * self.max_n_classes * sizeof(double))

        # Build the tree by recursive partitioning
        self.recursive_partition(X, X_argsorted, y, sample_mask, np.sum(sample_mask), 0, -1, False, buffer_value)

        # Compactify
        self.resize(self.node_count)
        free(buffer_value)

    cdef void recursive_partition(self,
                                  np.ndarray[DTYPE_t, ndim=2, mode="fortran"] X,
                                  np.ndarray[np.int32_t, ndim=2, mode="fortran"] X_argsorted,
                                  np.ndarray[DTYPE_t, ndim=2, mode="c"] y,
                                  np.ndarray sample_mask,
                                  int n_node_samples,
                                  int depth,
                                  int parent,
                                  int is_left_child,
                                  double* buffer_value):
        # Variables
        cdef Criterion criterion = self.criterion

        cdef DTYPE_t* X_ptr = <DTYPE_t*> X.data
        cdef int* X_argsorted_ptr = <int*> X_argsorted.data
        cdef DTYPE_t* y_ptr = <DTYPE_t*> y.data
        cdef BOOL_t* sample_mask_ptr = <BOOL_t*> sample_mask.data

        cdef int X_stride = <int> X.strides[1] / <int> X.strides[0]
        cdef int X_argsorted_stride = <int> X_argsorted.strides[1] / <int> X_argsorted.strides[0]
        cdef int y_stride = <int> y.strides[0] / <int> y.strides[1]

        cdef int n_total_samples = y.shape[0]
        cdef int feature
        cdef double threshold
        cdef double best_error
        cdef double init_error

        cdef int i
        cdef np.ndarray sample_mask_left
        cdef np.ndarray sample_mask_right
        cdef int n_node_samples_left
        cdef int n_node_samples_right

        # Count samples
        if n_node_samples == 0:
            raise ValueError("Attempting to find a split "
                             "with an empty sample_mask")

        # Split samples
        if depth < self.max_depth and \
           n_node_samples >= self.min_samples_split and \
           n_node_samples >= 2 * self.min_samples_leaf:
            self.find_split(X_ptr, X_stride,
                            X_argsorted_ptr, X_argsorted_stride,
                            y_ptr, y_stride,
                            sample_mask_ptr,
                            n_node_samples,
                            n_total_samples,
                            &feature, &threshold, &best_error, &init_error)

        else:
            feature = -1
            criterion.init(y_ptr, y_stride, sample_mask_ptr, n_node_samples, n_total_samples)
            init_error = criterion.eval()

        criterion.init_value(buffer_value)

        # Current node is leaf
        if feature == -1:
            self.add_leaf(parent, is_left_child, buffer_value, init_error, n_node_samples)

        # Current node is internal node (= split node)
        else:
            # Sample mask is too sparse?
            if 1. * n_node_samples / n_total_samples <= self.min_density:
                X = X[sample_mask]
                X_argsorted = np.asfortranarray(np.argsort(X.T, axis=1).astype(np.int32).T)
                y = y[sample_mask]
                sample_mask = np.ones((n_node_samples,), dtype=np.bool)

                n_total_samples = n_node_samples

                X_ptr = <DTYPE_t*> X.data
                X_argsorted_ptr = <int*> X_argsorted.data
                y_ptr = <DTYPE_t*> y.data
                sample_mask_ptr = <BOOL_t*> sample_mask.data

                X_stride = <int> X.strides[1] / <int> X.strides[0]
                X_argsorted_stride = <int> X_argsorted.strides[1] / <int> X_argsorted.strides[0]
                y_stride = <int> y.strides[0] / <int> y.strides[1]

            # Split
            X_ptr = X_ptr + feature * X_stride
            sample_mask_left = np.zeros((n_total_samples, ), dtype=np.bool)
            sample_mask_right = np.zeros((n_total_samples, ), dtype=np.bool)
            n_node_samples_left = 0
            n_node_samples_right = 0

            for i from 0 <= i < n_total_samples:
                if sample_mask[i]:
                    if X_ptr[i] <= threshold:
                        sample_mask_left[i] = 1
                        n_node_samples_left += 1
                    else:
                        sample_mask_right[i] = 1
                        n_node_samples_right += 1

            node_id = self.add_split_node(parent, is_left_child, feature,
                                          threshold, buffer_value, best_error,
                                          init_error, n_node_samples)

            # Left child recursion
            self.recursive_partition(X, X_argsorted, y, sample_mask_left,
                                     n_node_samples_left, depth + 1, node_id,
                                     True, buffer_value)

            # Right child recursion
            self.recursive_partition(X, X_argsorted, y, sample_mask_right,
                                     n_node_samples_right, depth + 1, node_id,
                                     False, buffer_value)

    cdef void find_split(self, DTYPE_t* X_ptr, int X_stride,
                         int* X_argsorted_ptr, int X_argsorted_stride,
                         DTYPE_t* y_ptr, int y_stride, BOOL_t* sample_mask_ptr,
                         int n_node_samples, int n_total_samples, int* _best_i,
                         double* _best_t, double* _best_error,
                         double* _initial_error):
        """Find the best dimension and threshold that minimises the error."""
        if self.find_split_algorithm == _TREE_SPLIT_BEST:
            self.find_best_split(X_ptr, X_stride, X_argsorted_ptr,
                                 X_argsorted_stride, y_ptr, y_stride,
{'fraction_non_alphanumeric': 0.11055308127230803, 'fraction_numerical': 0.0059698663887046335, 'mean_word_length': 2.1051392703020793, 'pattern_counts': {'":': 6, '<': 115, '<?xml version=': 0, '>': 95, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 38, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6307279', 'n_tokens_mistral': 9605, 'n_tokens_neox': 9139, 'n_words': 2404}