n_trees.h

Go to the documentation of this file.

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#ifndef __NILOREA_TREES__
#define __NILOREA_TREES__
 
#ifdef __cplusplus
extern "C" {
#endif
 
#include "nilorea/n_common.h"
#include "nilorea/n_str.h"
#include "nilorea/n_log.h"
#include "nilorea/n_list.h"
#include "nilorea/n_hash.h"
#include "nilorea/n_3d.h"
 
union NODE_DATA_TYPES {
    int ival;
    double fval;
    void* ptr;
    char* string;
    N_STR* nstr;
};
 
typedef struct NODE_DATA {
    union NODE_DATA_TYPES value;
    int32_t type;
} NODE_DATA;
 
typedef struct TREE_NODE {
    NODE_DATA data;
    void (*destroy_func)(void* ptr);
    struct TREE_NODE* parent;
    LIST_NODE* parent_list_node;
    LIST* children;
} TREE_NODE;
 
typedef struct TREE {
    TREE_NODE* root;
    pthread_rwlock_t rwlock;
    size_t nb_nodes;
    size_t height;
} TREE;
 
TREE* new_tree();
TREE_NODE* tree_create_node(NODE_DATA value, void (*destroy_func)(void* ptr));
int tree_insert_child(TREE_NODE* parent, TREE_NODE* child);
int tree_delete_node(TREE* tree, TREE_NODE* node);
void tree_destroy(TREE** tree);
 
enum COORD_TYPE {
    COORD_INT,
    COORD_FLOAT,
    COORD_DOUBLE
};
 
typedef union {
    int i;
    float f;
    double d;
} COORD_VALUE;
 
typedef struct POINT2D {
    COORD_VALUE
    x,
        y;
} POINT2D;
 
typedef struct POINT3D {
    COORD_VALUE
    x,
        y,
        z;
} POINT3D;
 
typedef int (*compare_func)(COORD_VALUE a, COORD_VALUE b);
typedef void (*print_func)(COORD_VALUE val);
 
typedef struct QUADTREE_NODE {
    COORD_VALUE x;
    COORD_VALUE y;
    POINT2D point;
    void* data_ptr;
    struct QUADTREE_NODE* nw;
    struct QUADTREE_NODE* ne;
    struct QUADTREE_NODE* sw;
    struct QUADTREE_NODE* se;
} QUADTREE_NODE;
 
typedef struct QUADTREE {
    int coord_type;
    compare_func compare;
    print_func print;
    QUADTREE_NODE* root;
} QUADTREE;
 
QUADTREE* create_quadtree(int coord_type);
QUADTREE_NODE* create_node(COORD_VALUE x, COORD_VALUE y, void* data_ptr);
QUADTREE_NODE* search(QUADTREE* qt, QUADTREE_NODE* root, COORD_VALUE x, COORD_VALUE y);
void insert(QUADTREE* qt, QUADTREE_NODE** root, COORD_VALUE x, COORD_VALUE y, void* data_ptr);
void free_quadtree(QUADTREE_NODE* root);
 
typedef struct OCTREE_NODE {
    POINT3D point;
    void* data_ptr;
    struct OCTREE_NODE* children[8];
} OCTREE_NODE;
 
typedef struct {
    OCTREE_NODE* root;
    int coord_type;
} OCTREE;
 
OCTREE* create_octree(int type);
OCTREE_NODE* create_octree_node(POINT3D point, void* data_ptr);
void insert_octree(OCTREE* OCTREE, POINT3D point, void* data_ptr);
void free_octree_node(OCTREE_NODE* node);
void free_octree(OCTREE* OCTREE);
 
#ifdef __cplusplus
}
#endif
 
#endif  // header guard