<commit_before>//
//  kp_2dtree.h
//  kingpin
//
//  Created by <NAME> on 13/08/14.
//
//

#import "KPGeometry.h"

#define KP_LIKELY(x) __builtin_expect(!!(x), 1)

typedef struct {
    __unsafe_unretained id <MKAnnotation> annotation;

    MKMapPoint *mapPoint;
} kp_internal_annotation_t;

typedef enum {
    KPAnnotationTreeAxisX = 0,
    KPAnnotationTreeAxisY = 1,
} KPAnnotationTreeAxis;

typedef struct kp_treenode_t {
    __unsafe_unretained id <MKAnnotation> annotation;
    struct kp_treenode_t *left;
    struct kp_treenode_t *right;
    MKMapPoint mk_map_point;
    NSUInteger level;
} kp_treenode_t;

typedef struct {
    kp_internal_annotation_t *annotationsSortedByCurrentAxis;
    kp_internal_annotation_t *annotationsSortedByComplementaryAxis;
    kp_internal_annotation_t *temporaryAnnotationStorage;
    uint32_t count;
    uint32_t level;
    kp_treenode_t *node;
} kp_build_stack_info_t;

typedef struct {
    uint32_t level;
    KPAnnotationTreeAxis axis;
    kp_treenode_t *node;
} kp_search_stack_info_t;

typedef struct {
    void **storage;
    void **top;
} kp_stack_t;

static inline kp_stack_t kp_stack_create(size_t capacity) {
    kp_stack_t stack;

    stack.storage = malloc(capacity * sizeof(void *));
    stack.top = stack.storage;

    return stack;
}

static inline void kp_stack_push(kp_stack_t *stack, void *el) {
    *(stack->top++) = el;
}

static inline void *kp_stack_pop(kp_stack_t *stack) {
    return *(--stack->top);
}

static inline void kp_stack_reset(kp_stack_t *stack) {
    stack->top = stack->storage;
}

typedef struct {
    kp_treenode_t *root;
    kp_treenode_t *nodes;
    kp_stack_t stack;
    NSUInteger size;
    kp_search_stack_info_t *search_stack_info;
} kp_2dtree_t;

static inline kp_2dtree_t kp_2dtree_create(NSArray *annotations);
static inline void kp_2dtree_free(kp_2dtree_t *tree);
static inline void kp_2dtree_search(kp_2dtree_t *tree, NSMutableArray *result, MKMapPoint *minPoint, MKMapPoint *maxPoint);

#pragma mark -

static inline void kp_2dtree_free(kp_2dtree_t *tree) {
    if (tree->size == 0) return;

    free(tree->nodes);
    free(tree->stack.storage);
    free(tree->search_stack_info);
}

static inline kp_2dtree_t kp_2dtree_create(NSArray *annotations) {
    kp_2dtree_t tree;
    memset(&tree, 0, sizeof(kp_2dtree_t));

    NSUInteger count = annotations.count;

    if (count == 0) return tree;

    tree.size = count;
    tree.search_stack_info = malloc(tree.size * sizeof(kp_search_stack_info_t));
    tree.nodes = malloc(tree.size * sizeof(kp_treenode_t));
    tree.root = tree.nodes;

    /*
     Kingpin currently implements the algorithm similar to the what is described as "A novel tree-building algorithm" on Wikipedia page:
     (follow these lines on http://en.wikipedia.org/wiki/K-d_tree).

     1. Sorting of original array by x and y is now done only once before building a tree.

     2. MKMapPointForCoordinate is now calculated only once for each annotation right before building of a tree.

     C level struct kp_internal_annotation is introduced to make 1 and 2 possible:
     - These structs serve as containers for both id <MKAnnotation> annotations and their once-precalculated MKMapPoints.
     - These structs and arrays of them allow to eliminate NSObject-based allocations (NSArray and NSIndexSet)
     - These structs allow to skip allocations of corresponding containers on every level of depth.
     */

    __block
    kp_internal_annotation_t *annotationsX = malloc(count * sizeof(kp_internal_annotation_t));
    kp_internal_annotation_t *annotationsY = malloc(count * sizeof(kp_internal_annotation_t));

    MKMapPoint *KPTemporaryPointStorage = malloc(count * sizeof(MKMapPoint));
    kp_internal_annotation_t *KPTemporaryAnnotationStorage = malloc((count / 2) * sizeof(kp_internal_annotation_t));

    dispatch_apply(count, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t idx) {
        id <MKAnnotation> annotation = annotations[idx];

        MKMapPoint mapPoint = MKMapPointForCoordinate(annotation.coordinate);

        KPTemporaryPointStorage[idx] = mapPoint;

        kp_internal_annotation_t _annotation;

        _annotation.annotation = annotation;
        _annotation.mapPoint = KPTemporaryPointStorage + idx;

        annotationsX[idx] = _annotation;
    });

    qsort_b(annotationsX, count, sizeof(kp_internal_annotation_t), ^int(const void *a1, const void *a2) {
        kp_internal_annotation_t *annotation1 = (kp_internal_annotation_t *)a1;
        kp_internal_annotation_t *annotation2 = (kp_internal_annotation_t *)a2;

        if (annotation1->mapPoint->x > annotation2->mapPoint->x) {
            return NSOrderedDescending;
        }

        if (annotation1->mapPoint->x < annotation2->mapPoint->x) {
            return NSOrderedAscending;
        }

        return NSOrderedSame;
    });

    memcpy(annotationsY, annotationsX, count * sizeof(kp_internal_annotation_t));

    qsort_b(annotationsY, count, sizeof(kp_internal_annotation_t), ^int(const void *a1, const void *a2) {
        kp_internal_annotation_t *annotation1 = (kp_internal_annotation_t *)a1;
        kp_internal_annotation_t *annotation2 = (kp_internal_annotation_t *)a2;

        if (annotation1->mapPoint->y > annotation2->mapPoint->y) {
            return NSOrderedDescending;
        }

        if (annotation1->mapPoint->y < annotation2->mapPoint->y) {
            return NSOrderedAscending;
        }

        return NSOrderedSame;
    });

    kp_treenode_t *free_node_iterator = tree.nodes;

    kp_build_stack_info_t *build_stack_info = malloc(count * sizeof(kp_build_stack_info_t));
    kp_build_stack_info_t *top_snapshot;

    kp_stack_t stack = kp_stack_create(count);
    tree.stack = stack;
    kp_stack_push(&stack, NULL);

    kp_build_stack_info_t *top = build_stack_info;
    top->level = 0;
    top->count = (uint32_t)count;
    top->node  = free_node_iterator++;
    top->annotationsSortedByCurrentAxis       = annotationsX;
    top->annotationsSortedByComplementaryAxis = annotationsY;
    top->temporaryAnnotationStorage           = KPTemporaryAnnotationStorage;

    while (top != NULL) {
        // We prefer machine way of doing odd/even check over the mathematical one: "% 2"
        KPAnnotationTreeAxis axis = (top->level & 1) == 0 ? KPAnnotationTreeAxisX : KPAnnotationTreeAxisY;

        NSUInteger medianIdx = top->count >> 1;

        kp_internal_annotation_t medianAnnotation = top->annotationsSortedByCurrentAxis[medianIdx];

        double splittingCoordinate = MKMapPointGetCoordinateForAxis(medianAnnotation.mapPoint, axis);

        /*
         http://en.wikipedia.org/wiki/K-d_tree#Construction

         Arrays should be split into subarrays that represent "less than" and "greater than or equal to" partitioning.
         This convention requires that, after choosing the median element of array 0, the element of array 0 that lies immediately below the median element be<commit_msg>Fix stack for very small trees (1,2,3 elements) #61<commit_after>//
//  kp_2dtree.h
//  kingpin
//
//  Created by <NAME> on 13/08/14.
//
//

#import "KPGeometry.h"

#define KP_LIKELY(x) __builtin_expect(!!(x), 1)

typedef struct {
    __unsafe_unretained id <MKAnnotation> annotation;

    MKMapPoint *mapPoint;
} kp_internal_annotation_t;

typedef enum {
    KPAnnotationTreeAxisX = 0,
    KPAnnotationTreeAxisY = 1,
} KPAnnotationTreeAxis;

typedef struct kp_treenode_t {
    __unsafe_unretained id <MKAnnotation> annotation;
    struct kp_treenode_t *left;
    struct kp_treenode_t *right;
    MKMapPoint mk_map_point;
    NSUInteger level;
} kp_treenode_t;

typedef struct {
    kp_internal_annotation_t *annotationsSortedByCurrentAxis;
    kp_internal_annotation_t *annotationsSortedByComplementaryAxis;
    kp_internal_annotation_t *temporaryAnnotationStorage;
    uint32_t count;
    uint32_t level;
    kp_treenode_t *node;
} kp_build_stack_info_t;

typedef struct {
    uint32_t level;
    KPAnnotationTreeAxis axis;
    kp_treenode_t *node;
} kp_search_stack_info_t;

typedef struct {
    void **storage;
    void **top;
} kp_stack_t;

static inline kp_stack_t kp_stack_create(size_t capacity) {
    kp_stack_t stack;

    stack.storage = malloc(capacity * sizeof(void *));
    stack.top = stack.storage;

    return stack;
}

static inline void kp_stack_push(kp_stack_t *stack, void *el) {
    *(stack->top++) = el;
}

static inline void *kp_stack_pop(kp_stack_t *stack) {
    return *(--stack->top);
}

static inline void kp_stack_reset(kp_stack_t *stack) {
    stack->top = stack->storage;
}

typedef struct {
    kp_treenode_t *root;
    kp_treenode_t *nodes;
    kp_stack_t stack;
    NSUInteger size;
    kp_search_stack_info_t *search_stack_info;
} kp_2dtree_t;

static inline kp_2dtree_t kp_2dtree_create(NSArray *annotations);
static inline void kp_2dtree_free(kp_2dtree_t *tree);
static inline void kp_2dtree_search(kp_2dtree_t *tree, NSMutableArray *result, MKMapPoint *minPoint, MKMapPoint *maxPoint);

#pragma mark -

static inline void kp_2dtree_free(kp_2dtree_t *tree) {
    if (tree->size == 0) return;

    free(tree->nodes);
    free(tree->stack.storage);
    free(tree->search_stack_info);
}

static inline kp_2dtree_t kp_2dtree_create(NSArray *annotations) {
    kp_2dtree_t tree;
    memset(&tree, 0, sizeof(kp_2dtree_t));

    NSUInteger count = annotations.count;

    if (count == 0) return tree;

    tree.size = count;
    tree.search_stack_info = malloc((tree.size + 2) * sizeof(kp_search_stack_info_t));
    tree.nodes = malloc(tree.size * sizeof(kp_treenode_t));
    tree.root = tree.nodes;

    /*
     Kingpin currently implements the algorithm similar to the what is described as "A novel tree-building algorithm" on Wikipedia page:
     (follow these lines on http://en.wikipedia.org/wiki/K-d_tree).

     1. Sorting of original array by x and y is now done only once before building a tree.

     2. MKMapPointForCoordinate is now calculated only once for each annotation right before building of a tree.

     C level struct kp_internal_annotation is introduced to make 1 and 2 possible:
     - These structs serve as containers for both id <MKAnnotation> annotations and their once-precalculated MKMapPoints.
     - These structs and arrays of them allow to eliminate NSObject-based allocations (NSArray and NSIndexSet)
     - These structs allow to skip allocations of corresponding containers on every level of depth.
     */

    __block
    kp_internal_annotation_t *annotationsX = malloc(count * sizeof(kp_internal_annotation_t));
    kp_internal_annotation_t *annotationsY = malloc(count * sizeof(kp_internal_annotation_t));

    MKMapPoint *KPTemporaryPointStorage = malloc(count * sizeof(MKMapPoint));
    kp_internal_annotation_t *KPTemporaryAnnotationStorage = malloc((count / 2) * sizeof(kp_internal_annotation_t));

    dispatch_apply(count, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t idx) {
        id <MKAnnotation> annotation = annotations[idx];

        MKMapPoint mapPoint = MKMapPointForCoordinate(annotation.coordinate);

        KPTemporaryPointStorage[idx] = mapPoint;

        kp_internal_annotation_t _annotation;

        _annotation.annotation = annotation;
        _annotation.mapPoint = KPTemporaryPointStorage + idx;

        annotationsX[idx] = _annotation;
    });

    qsort_b(annotationsX, count, sizeof(kp_internal_annotation_t), ^int(const void *a1, const void *a2) {
        kp_internal_annotation_t *annotation1 = (kp_internal_annotation_t *)a1;
        kp_internal_annotation_t *annotation2 = (kp_internal_annotation_t *)a2;

        if (annotation1->mapPoint->x > annotation2->mapPoint->x) {
            return NSOrderedDescending;
        }

        if (annotation1->mapPoint->x < annotation2->mapPoint->x) {
            return NSOrderedAscending;
        }

        return NSOrderedSame;
    });

    memcpy(annotationsY, annotationsX, count * sizeof(kp_internal_annotation_t));

    qsort_b(annotationsY, count, sizeof(kp_internal_annotation_t), ^int(const void *a1, const void *a2) {
        kp_internal_annotation_t *annotation1 = (kp_internal_annotation_t *)a1;
        kp_internal_annotation_t *annotation2 = (kp_internal_annotation_t *)a2;

        if (annotation1->mapPoint->y > annotation2->mapPoint->y) {
            return NSOrderedDescending;
        }

        if (annotation1->mapPoint->y < annotation2->mapPoint->y) {
            return NSOrderedAscending;
        }

        return NSOrderedSame;
    });

    kp_treenode_t *free_node_iterator = tree.nodes;

    kp_build_stack_info_t *build_stack_info = malloc(count * sizeof(kp_build_stack_info_t));
    kp_build_stack_info_t *top_snapshot;

    kp_stack_t stack = kp_stack_create(count + 3);
    tree.stack = stack;
    kp_stack_push(&stack, NULL);

    kp_build_stack_info_t *top = build_stack_info;
    top->level = 0;
    top->count = (uint32_t)count;
    top->node  = free_node_iterator++;
    top->annotationsSortedByCurrentAxis       = annotationsX;
    top->annotationsSortedByComplementaryAxis = annotationsY;
    top->temporaryAnnotationStorage           = KPTemporaryAnnotationStorage;

    while (top != NULL) {
        // We prefer machine way of doing odd/even check over the mathematical one: "% 2"
        KPAnnotationTreeAxis axis = (top->level & 1) == 0 ? KPAnnotationTreeAxisX : KPAnnotationTreeAxisY;

        NSUInteger medianIdx = top->count >> 1;

        kp_internal_annotation_t medianAnnotation = top->annotationsSortedByCurrentAxis[medianIdx];

        double splittingCoordinate = MKMapPointGetCoordinateForAxis(medianAnnotation.mapPoint, axis);

        /*
         http://en.wikipedia.org/wiki/K-d_tree#Construction

         Arrays should be split into subarrays that represent "less than" and "greater than or equal to" partitioning.
         This convention requires that, after choosing the median element of array 0, the element of array 0 that lies immediately below the median element be
{'fraction_non_alphanumeric': 0.08743912918934403, 'fraction_numerical': 0.010097393297049556, 'mean_word_length': 3.8405545927209706, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 87, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6151578', 'n_tokens_mistral': 4734, 'n_tokens_neox': 4358, 'n_words': 1039}