n_trees.h

Go to the documentation of this file.

 
#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;
 
// create a TREE
TREE* new_tree();
// create a TREE node
TREE_NODE* tree_create_node(NODE_DATA value, void (*destroy_func)(void* ptr));
// insert a node in the parent node
int tree_insert_child(TREE_NODE* parent, TREE_NODE* child);
// delete a TREE node
int tree_delete_node(TREE* tree, TREE_NODE* node);
// delete a TREE
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;
 
// Function to create a new quad tree
QUADTREE* create_quadtree(int coord_type);
// Function to create a new quad tree node
QUADTREE_NODE* create_node(COORD_VALUE x, COORD_VALUE y, void* data_ptr);
// Function to search for a point in the quad tree
QUADTREE_NODE* search(QUADTREE* qt, QUADTREE_NODE* root, COORD_VALUE x, COORD_VALUE y);
// Function to insert a point into the quad tree
void insert(QUADTREE* qt, QUADTREE_NODE** root, COORD_VALUE x, COORD_VALUE y, void* data_ptr);
// Function to free the quad tree
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;
 
// Function prototypes
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