Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <crater/kd_tree.h>
       4             : 
       5        5000 : inline static bool cr8r_kd_check_layer(const cr8r_vec *self, const cr8r_kd_ft *ft, uint64_t a, uint64_t b){
       6        5000 :     uint64_t mid_idx = (a + b)/2;
       7        5000 :     const void *mid = self->buf + mid_idx*ft->super.base.size;
       8       25245 :     for(uint64_t i = a; i < mid_idx; ++i){
       9       20245 :         const void *ent = self->buf + i*ft->super.base.size;
      10       20245 :         if(ft->super.cmp(&ft->super.base, ent, mid) > 0){
      11             :             return false;
      12             :         }
      13             :     }
      14       24690 :     for(uint64_t i = mid_idx + 1; i < b; ++i){
      15       19690 :         const void *ent = self->buf + i*ft->super.base.size;
      16       19690 :         if(ft->super.cmp(&ft->super.base, ent, mid) < 0){
      17             :             return false;
      18             :         }
      19             :     }
      20             :     return true;
      21             : }
      22             : 
      23             : inline static bool cr8r_kd_check_tree(const cr8r_vec *self, const cr8r_kd_ft *_ft, uint64_t a, uint64_t b){
      24             :     cr8r_kd_ft ft = *_ft;
      25             :     while(b > a){
      26             :         if(!cr8r_kd_check_layer(self, &ft, a, b)){
      27             :             return false;
      28             :         }
      29             :         uint64_t mid_idx = (a + b)/2;
      30             :         // increment depth
      31             :         ++*(uint64_t*)&ft.super.base.data;
      32             :         if(!cr8r_kd_check_tree(self, &ft, mid_idx + 1, b)){
      33             :             return false;
      34             :         }
      35             :         b = mid_idx;
      36             :     }
      37             :     return true;
      38             : }
      39             : 
      40             : bool cr8r_kd_k_closest_naive(cr8r_vec*, cr8r_kd_ft *ft, const void *bounds, const void *pt, uint64_t k, cr8r_vec *out);
      41             : 
      42             :